aoc/year2020/
day21.rs

1//! # Allergen Assessment
2//!
3//! The rules can be expressed as:
4//!
5//! * If an ingredient is on a line, then it *may* contain the listed allergens.
6//! * If an ingredient is *not* on a line, then it definitely *does not* contain the listed
7//!   allergens, as some other food on the line must instead contain the allergen.
8//!
9//! ## Part One
10//! To find the safe foods we build two sets, then subtract them to find out the remaining possible
11//! allergens. It's important to only subtract the sets at the very end in order to prevent
12//! re-adding a previously excluded allergen. Using `kfcds` from the example:
13//!
14//! | Line | Possible    | Impossible       |
15//! | ---  | ----------- | ---------------- |
16//! | 1    | Dairy, Fish | Ø                |
17//! | 2    | Dairy, Fish | Dairy            |
18//! | 3    | Dairy, Fish | Dairy, Soy       |
19//! | 4    | Dairy, Fish | Dairy, Soy, Fish |
20//!
21//! Final result: Ø (the empty set)
22//!
23//! # Part Two
24//! This is a [constraint satisfaction problem](https://en.wikipedia.org/wiki/Constraint_satisfaction_problem),
25//! similar to [`day 16`]. Using `fvjkl` from the example:
26//!
27//! | Line | Possible   | Impossible  |
28//! | ---  | ---------- | ----------- |
29//! | 1    | Ø          | Dairy, Fish |
30//! | 2    | Dairy      | Dairy, Fish |
31//! | 3    | Dairy, Soy | Dairy, Fish |
32//! | 4    | Dairy, Soy | Dairy, Fish |
33//!
34//! Final result: Soy
35//!
36//! To solve there must be at least one ingredient with only one allergen remaining.
37//! As this allergen can only belong to this ingredient, we eliminate it from other ingredients.
38//! This causes a chain reaction where a second ingredient will reduce to only one allergen,
39//! continuing until all allergens have been resolved.
40//!
41//! As there are less than 64 lines and allergens we can speed things up by using bitwise logic
42//! on a `usize` to compute set addition and subtraction. To add to a set use OR `|`,
43//! to remove use AND `&` and to calculate the size use [`count_ones`].
44//!
45//! [`Day 16`]: crate::year2020::day16
46//! [`count_ones`]: u32::count_ones
47use crate::util::hash::*;
48use std::collections::BTreeMap;
49
50pub struct Input<'a> {
51    ingredients: FastMap<&'a str, Ingredient>,
52    allergens: FastMap<&'a str, usize>,
53}
54
55#[derive(Clone, Copy, Default)]
56pub struct Ingredient {
57    food: usize,
58    candidates: usize,
59}
60
61pub fn parse(input: &str) -> Input<'_> {
62    let mut ingredients: FastMap<&str, Ingredient> = FastMap::new();
63    let mut allergens = FastMap::new();
64    let mut allergens_per_food = Vec::new();
65
66    for (i, line) in input.lines().enumerate() {
67        let (prefix, suffix) = line.rsplit_once(" (contains ").unwrap();
68
69        for ingredient in prefix.split_ascii_whitespace() {
70            let entry = ingredients.entry(ingredient).or_default();
71            entry.food |= 1 << i;
72        }
73
74        let mut mask = 0;
75        for allergen in suffix.split([' ', ',', ')']).filter(|a| !a.is_empty()) {
76            let size = allergens.len();
77            let entry = allergens.entry(allergen).or_insert(size);
78            mask |= 1 << *entry;
79        }
80        allergens_per_food.push(mask);
81    }
82
83    for ingredient in ingredients.values_mut() {
84        let mut possible = 0;
85        let mut impossible = 0;
86
87        for (i, allergens) in allergens_per_food.iter().enumerate() {
88            if ingredient.food & (1 << i) == 0 {
89                impossible |= allergens;
90            } else {
91                possible |= allergens;
92            }
93        }
94
95        ingredient.candidates = possible & !impossible;
96    }
97
98    Input { ingredients, allergens }
99}
100
101pub fn part1(input: &Input<'_>) -> u32 {
102    input.ingredients.values().filter(|i| i.candidates == 0).map(|i| i.food.count_ones()).sum()
103}
104
105pub fn part2(input: &Input<'_>) -> String {
106    let inverse_allergens: FastMap<_, _> =
107        input.allergens.iter().map(|(k, v)| (1 << v, k)).collect();
108    let mut todo: Vec<_> = input
109        .ingredients
110        .iter()
111        .filter_map(|(&k, &v)| (v.candidates != 0).then_some((k, v.candidates)))
112        .collect();
113    let mut done = BTreeMap::new();
114
115    // Eliminate known allergens from other ingredients.
116    while done.len() < todo.len() {
117        let mut mask = 0;
118
119        // There must be at least one ingredient with only one allergen.
120        for (name, candidates) in &todo {
121            if candidates.count_ones() == 1 {
122                let allergen = inverse_allergens[candidates];
123                done.insert(*allergen, *name);
124
125                mask |= candidates;
126            }
127        }
128
129        todo.iter_mut().for_each(|(_, candidates)| *candidates &= !mask);
130    }
131
132    // Sort by alphabetical order of the allergens.
133    done.into_values().collect::<Vec<_>>().join(",")
134}
aoc/year2020/day21.rs

aoc/year2020/
day21.rs
