🎄

Advent of Code 2020 day21

2021/01/05に公開

Rust

adventofcode

tech

https://adventofcode.com/2020/day/21

part1

mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
trh fvjkl sbzzf mxmxvkd (contains dairy)
sqjhc fvjkl (contains soy)
sqjhc mxmxvkd sbzzf (contains fish)

のような入力が与えられる。どれかのアレルゲンがどれか1つの材料に入っているが、左側のリストにある材料に含まれてるアレルゲンがすべて右側の括弧で表示されているとは限らない、らしい。

part1はまず、アレルゲンの入っている可能性の無いものが出現する回数を数えよ、というもの。

この例の場合について考えると、1行目と2行目で双方にdairyが含まれるので、共通して含まれているものが候補になる。この場合だとmxmxvkdがそれに該当する(1つだけなので確定してしまうが、実際には複数あるかもしれない)。同様に1行目と4行目にfishが含まれるので、共通するmxmxvkdとsqjhcが候補になる。soyについては3行目だけしか無いのでsqjhcとfvjklの2つが候補になる。
こうして挙げられた各アレルゲンが含まれるリストに共通して含まれている材料が「該当するかもしない候補」になるので、それ以外すべてが、求めるべき「可能性の無いもの」になる。

つまり、各アレルゲンについて含まれているリストすべてに共通して出現している材料を抽出し、

use regex::Regex;

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        let re = Regex::new(r"^(.+?) \(contains (.*?)\)$").unwrap();
        let mut data = Vec::new();
        for line in inputs.iter() {
            if let Some(cap) = re.captures(line) {
                let ingredients: Vec<String> = cap[1].split(' ').map(|s| s.to_string()).collect();
                let allergens: Vec<String> = cap[2].split(", ").map(|s| s.to_string()).collect();
                data.push((ingredients, allergens));
            }
        }
        Self { inputs: data }
    }
    fn candidates(&self) -> HashMap<String, Vec<String>> {
        let mut counts_map = HashMap::new();
        for (ingredients, allergens) in self.inputs.iter() {
            for allergen in allergens.iter() {
                for ingredient in ingredients.iter() {
                    *counts_map
                        .entry(allergen.to_string())
                        .or_insert_with(HashMap::new)
                        .entry(ingredient.to_string())
                        .or_insert(0) += 1;
                }
            }
        }
        let mut candidates = HashMap::new();
        for (allergen, counts) in counts_map.iter() {
            if let Some(&max) = counts.values().max() {
                candidates.insert(
                    allergen.to_string(),
                    counts
                        .iter()
                        .filter_map(|(ingredient, &count)| {
                            if count == max {
                                Some(ingredient.to_string())
                            } else {
                                None
                            }
                        })
                        .collect(),
                );
            }
        }
        candidates
    }
}

それらの候補に含まれないものだけを数え上げてやれば良い。

    fn solve_1(&self) -> usize {
        let candidates = self.candidates();
        let mut candidate_ingredients = HashSet::new();
        for ingredients in candidates.values() {
            for ingredient in ingredients.iter() {
                candidate_ingredients.insert(ingredient);
            }
        }
        self.inputs
            .iter()
            .map(|(ingredients, _)| {
                ingredients
                    .iter()
                    .filter(|&ingredient| !candidate_ingredients.contains(ingredient))
                    .count()
            })
            .sum()
    }

part2

では実際にどのアレルゲンがどの材料に含まれているかを特定し、アレルゲンの名前順に該当する材料を列挙して返せ、という問題。

上の例だと前述したようにdairyはmxmxvkdと特定できる。となるとfishはmxmxvkdとsqjhcが候補だったがmxmxvkdがdairyと分かっているなら残るsqjhcの方が含むことになる。同様に考えてsoyは残っているfvjklになる。

このように、候補が複数あっても他が確定することによって候補が絞られていって確定していけるようになっている。このへんはday16と同様に考えていける。

    fn solve_2(&self) -> String {
        let mut candidates = self.candidates();
        let mut dangerous_ingredients = HashMap::with_capacity(candidates.len());
        while !candidates.is_empty() {
            let mut figure_outs = Vec::new();
            for (allergen, ingredients) in candidates
                .iter()
                .filter(|(_, ingredients)| ingredients.len() == 1)
            {
                dangerous_ingredients.insert(allergen.clone(), ingredients[0].clone());
                figure_outs.push(allergen.clone());
            }
            for allergen in figure_outs.iter() {
                if let Some(removed) = candidates.remove(allergen) {
                    candidates.values_mut().for_each(|ingredients| {
                        ingredients.retain(|ingredient| *ingredient != removed[0]);
                    });
                }
            }
        }
        let mut allergens: Vec<&String> = dangerous_ingredients.keys().collect();
        allergens.sort_unstable();
        allergens
            .into_iter()
            .filter_map(|allergen| dangerous_ingredients.get(allergen))
            .map(String::to_string)
            .collect::<Vec<String>>()
            .join(",")
    }

part1

part2

Discussion