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 is Ø (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 is Soy.
35//!
36//! To solve this, 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 fewer 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 std::collections::BTreeMap;
48
49use crate::util::hash::*;
50
51pub struct Input<'a> {
52    ingredients: FastMap<&'a str, Ingredient>,
53    allergens: FastMap<&'a str, usize>,
54}
55
56#[derive(Clone, Copy, Default)]
57pub struct Ingredient {
58    food: usize,
59    candidates: usize,
60}
61
62pub fn parse(input: &str) -> Input<'_> {
63    let mut ingredients: FastMap<&str, Ingredient> = FastMap::new();
64    let mut allergens = FastMap::new();
65    let mut allergens_per_food = Vec::new();
66
67    for (i, line) in input.lines().enumerate() {
68        let (prefix, suffix) = line.rsplit_once(" (contains ").unwrap();
69
70        for ingredient in prefix.split_ascii_whitespace() {
71            ingredients.entry(ingredient).or_default().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            mask |= 1 << *allergens.entry(allergen).or_insert(size);
78        }
79        allergens_per_food.push(mask);
80    }
81
82    for ingredient in ingredients.values_mut() {
83        let mut possible = 0;
84        let mut impossible = 0;
85
86        for (i, allergens) in allergens_per_food.iter().enumerate() {
87            if ingredient.food & (1 << i) == 0 {
88                impossible |= allergens;
89            } else {
90                possible |= allergens;
91            }
92        }
93
94        ingredient.candidates = possible & !impossible;
95    }
96
97    Input { ingredients, allergens }
98}
99
100pub fn part1(input: &Input<'_>) -> u32 {
101    input
102        .ingredients
103        .values()
104        .filter_map(|i| (i.candidates == 0).then_some(i.food.count_ones()))
105        .sum()
106}
107
108pub fn part2(input: &Input<'_>) -> String {
109    let inverse_allergens: FastMap<_, _> =
110        input.allergens.iter().map(|(&k, &v)| (1 << v, k)).collect();
111    let mut todo: Vec<_> = input
112        .ingredients
113        .iter()
114        .filter_map(|(&k, &v)| (v.candidates != 0).then_some((k, v.candidates)))
115        .collect();
116    let mut done = BTreeMap::new();
117
118    // Eliminate known allergens from other ingredients.
119    while done.len() < todo.len() {
120        let mut mask = 0;
121
122        // There must be at least one ingredient with only one allergen.
123        for (name, candidates) in &todo {
124            if candidates.count_ones() == 1 {
125                done.insert(inverse_allergens[candidates], *name);
126                mask |= candidates;
127            }
128        }
129
130        todo.iter_mut().for_each(|(_, candidates)| *candidates &= !mask);
131    }
132
133    // Sort by alphabetical order of the allergens.
134    done.into_values().collect::<Vec<_>>().join(",")
135}
aoc/year2020/day21.rs

aoc/year2020/
day21.rs
