Advent of Code 2020 day21

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은 변응원의 가능성을 넣지 않은 것이 나타나는 횟수를 먼저 계산한다.
이 사례의 경우 1행과 2행 모두 포함dairy돼 있어 공동 포함이 후보로 거론된다.이 경우mxmxvkd와 상응하여(하나밖에 없기 때문에 확정되었지만 실제로는 많을 수 있다).마찬가지로 1행과 4행에 포함fish돼 공통mxmxvkd과sqjhc가 후보로 거론된다.soy에 관해서는 세 번째 줄sqjhc과 fvjkl 두 개만 후보에 올랐다.
이렇게 열거된 각 변응원이 포함된 리스트에 공통으로 포함된 재료가'적합 여부 후보'인 만큼 그 외 모든 재료는 추구해야 할'가능성 없는 것들'이기 때문이다.
즉, 모든 알레르기 원소에 포함된 모든 리스트에 공통적으로 나타난 재료를 추출한다.

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(",")
    }