Advent of Code 2020 day21

5 min read読了の目安(約4700字

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が含まれるので、共通するmxmxvkdsqjhcが候補になる。soyについては3行目だけしか無いのでsqjhcfvjklの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

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

上の例だと前述したようにdairymxmxvkdと特定できる。となるとfishmxmxvkdsqjhcが候補だったがmxmxvkddairyと分かっているなら残る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(",")
    }