advent_of_code/year2020/
day21.rs

1use crate::input::Input;
2use std::collections::{HashMap, HashSet};
3
4pub fn solve(input: &Input) -> Result<String, String> {
5    let on_error = || "Invalid input";
6
7    let mut allergen_to_idx = HashMap::with_capacity(8);
8    let mut allergen_names = Vec::with_capacity(8);
9
10    let mut ingredient_to_idx = HashMap::with_capacity(200);
11    let mut ingredient_names = Vec::with_capacity(200);
12
13    let mut ingredient_occurences: Vec<u16> = Vec::with_capacity(200);
14    let mut allergen_to_possible_ingredients = Vec::with_capacity(8);
15
16    for line in input.text.lines() {
17        let mut line_parts = line.splitn(2, " (contains ");
18
19        let ingredients = line_parts.next().ok_or_else(on_error)?;
20        let mut current_ingredients = HashSet::new();
21        for ingredient_name in ingredients.split(' ') {
22            let num_ingredients = ingredient_to_idx.len();
23            let ingredient_id = *ingredient_to_idx
24                .entry(ingredient_name)
25                .or_insert(num_ingredients);
26
27            if ingredient_id == ingredient_occurences.len() {
28                ingredient_occurences.push(1);
29                ingredient_names.push(ingredient_name);
30            } else {
31                ingredient_occurences[ingredient_id] += 1;
32            }
33
34            current_ingredients.insert(ingredient_id);
35        }
36
37        if let Some(allergens) = line_parts.next().ok_or_else(on_error)?.strip_suffix(')') {
38            for allergen_name in allergens.split(", ") {
39                let num_allergens = allergen_to_idx.len();
40                let allergen_id = *allergen_to_idx
41                    .entry(allergen_name)
42                    .or_insert(num_allergens);
43                if allergen_id == allergen_names.len() {
44                    allergen_names.push(allergen_name);
45                    allergen_to_possible_ingredients.push(current_ingredients.clone());
46                } else {
47                    let existing = &allergen_to_possible_ingredients[allergen_id];
48                    allergen_to_possible_ingredients[allergen_id] = current_ingredients
49                        .intersection(existing)
50                        .copied()
51                        .collect();
52                }
53            }
54        } else {
55            return Err(on_error().to_string());
56        }
57    }
58
59    if input.is_part_one() {
60        return Ok((0..ingredient_to_idx.len())
61            .filter_map(|ingredient_id| {
62                if allergen_to_possible_ingredients
63                    .iter()
64                    .any(|possible| possible.contains(&ingredient_id))
65                {
66                    None
67                } else {
68                    Some(u64::from(ingredient_occurences[ingredient_id]))
69                }
70            })
71            .sum::<u64>()
72            .to_string());
73    }
74
75    let mut identified_products = allergen_to_possible_ingredients
76        .iter()
77        .filter_map(|possibilities| {
78            if possibilities.len() == 1 {
79                possibilities.iter().next().copied()
80            } else {
81                None
82            }
83        })
84        .collect::<Vec<usize>>();
85
86    while let Some(product_id) = identified_products.pop() {
87        for possibilities in allergen_to_possible_ingredients.iter_mut() {
88            if possibilities.len() > 1
89                && possibilities.remove(&product_id)
90                && possibilities.len() == 1
91            {
92                let p = possibilities
93                    .iter()
94                    .next()
95                    .ok_or_else(|| "Internal error".to_string())?;
96                identified_products.push(*p);
97            }
98        }
99    }
100
101    let mut ingredient_and_allergents = allergen_to_possible_ingredients
102        .iter()
103        .enumerate()
104        .map(
105            |(idx, possible_ingredients)| -> Result<(usize, usize), String> {
106                Ok((
107                    *possible_ingredients
108                        .iter()
109                        .next()
110                        .ok_or_else(|| "Internal error".to_string())?,
111                    idx,
112                ))
113            },
114        )
115        .collect::<Result<Vec<_>, _>>()?;
116
117    ingredient_and_allergents.sort_unstable_by(|a, b| {
118        let a_allergen_name = allergen_names[a.1];
119        let b_allergen_name = allergen_names[b.1];
120        a_allergen_name.cmp(b_allergen_name)
121    });
122
123    Ok(ingredient_and_allergents
124        .iter()
125        .map(|&(ingredient_id, _)| ingredient_names[ingredient_id])
126        .collect::<Vec<_>>()
127        .join(","))
128}
129
130#[test]
131pub fn tests() {
132    use crate::input::{test_part_one, test_part_two};
133
134    let example = "mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
135trh fvjkl sbzzf mxmxvkd (contains dairy)
136sqjhc fvjkl (contains soy)
137sqjhc mxmxvkd sbzzf (contains fish)";
138    test_part_one!(example => "5".to_string());
139    test_part_two!(example => "mxmxvkd,sqjhc,fvjkl".to_string());
140
141    let other_input = include_str!("day21_input_other.txt");
142    test_part_one!(other_input => "2724".to_string());
143    test_part_two!(other_input => "xlxknk,cskbmx,cjdmk,bmhn,jrmr,tzxcmr,fmgxh,fxzh".to_string());
144
145    let real_input = include_str!("day21_input.txt");
146    test_part_one!(real_input => "2317".to_string());
147    test_part_two!(real_input => "kbdgs,sqvv,slkfgq,vgnj,brdd,tpd,csfmb,lrnz".to_string());
148}
advent_of_code/year2020/day21.rs

advent_of_code/year2020/
day21.rs
