year2020/
day07.rs

1use utils::array::ArrayVec;
2use utils::hash::FastMap;
3use utils::prelude::*;
4
5/// Counting nested bags.
6#[derive(Clone, Debug)]
7pub struct Day07 {
8    rules: Vec<Contents>,
9    target: usize,
10}
11
12const MAX_INSIDE: usize = 4;
13type Contents = ArrayVec<(u16, u8), MAX_INSIDE>;
14
15#[derive(Clone, Copy, Debug)]
16enum State<T> {
17    Unvisited,
18    CurrentlyVisiting,
19    Visited(T),
20}
21
22impl Day07 {
23    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
24        let word = parser::take_while1(u8::is_ascii_lowercase);
25        let color = word
26            .with_suffix(b' ')
27            .then(word)
28            .with_consumed()
29            .map(|(_, consumed)| consumed);
30        let rule = color
31            .with_suffix(" bags contain ")
32            .then(
33                parser::parse_tree!(
34                    ("1 ".commit(), c @ color, " bag") => (1, c),
35                    (count @ parser::nonzero_u8(), b' ', c @ color, " bags") => (count.get(), c),
36                )
37                .repeat_arrayvec::<MAX_INSIDE, _>(", ", 1)
38                .or("no other bags".map(|_| ArrayVec::new())),
39            )
40            .with_suffix(b'.')
41            .with_eol();
42
43        let mut bag_ids = FastMap::with_capacity(1024);
44        let mut rules = Vec::with_capacity(1024);
45        let mut intern = |name, rules: &mut Vec<Option<Contents>>| {
46            *bag_ids.entry(name).or_insert_with(|| {
47                let id = rules.len() as u16;
48                rules.push(None);
49                id
50            })
51        };
52        for item in rule.parse_iterator(input) {
53            let (outer, contains) = item?;
54            let outer_id = intern(outer, &mut rules);
55            if rules[usize::from(outer_id)].is_some() {
56                return Err(InputError::new(input, outer, "duplicate bag rule"));
57            }
58
59            let mut children = Contents::new();
60            for &(count, inner) in &contains {
61                let inner_id = intern(inner, &mut rules);
62                if inner_id == outer_id {
63                    return Err(InputError::new(input, inner, "bag cannot contain itself"));
64                }
65                if children.iter().any(|&(id, _)| id == inner_id) {
66                    return Err(InputError::new(input, inner, "duplicate bag"));
67                }
68                children.push((inner_id, count)).unwrap();
69            }
70
71            rules[usize::from(outer_id)] = Some(children);
72        }
73
74        let Some(rules) = rules.into_iter().collect() else {
75            return Err(InputError::new(input, 0, "missing bag rule"));
76        };
77        let Some(&target) = bag_ids.get(b"shiny gold".as_slice()) else {
78            return Err(InputError::new(input, 0, "no shiny gold bag"));
79        };
80
81        Ok(Self {
82            rules,
83            target: usize::from(target),
84        })
85    }
86
87    #[must_use]
88    pub fn part1(&self) -> usize {
89        fn contains_target(
90            target: usize,
91            rules: &[Contents],
92            bag: usize,
93            states: &mut [State<bool>],
94        ) -> bool {
95            match states[bag] {
96                State::CurrentlyVisiting => panic!("no solution found: rules contain a cycle"),
97                State::Visited(b) => return b,
98                State::Unvisited => states[bag] = State::CurrentlyVisiting,
99            }
100
101            let mut result = false;
102            for &(child, _) in &rules[bag] {
103                let child = usize::from(child);
104                result |= child == target || contains_target(target, rules, child, states);
105            }
106
107            states[bag] = State::Visited(result);
108            result
109        }
110
111        let mut states = vec![State::Unvisited; self.rules.len()];
112        (0..self.rules.len())
113            .filter(|&bag| contains_target(self.target, &self.rules, bag, &mut states))
114            .count()
115    }
116
117    #[must_use]
118    pub fn part2(&self) -> u64 {
119        fn total_bags(rules: &[Contents], bag: usize, states: &mut [State<u64>]) -> u64 {
120            match states[bag] {
121                State::CurrentlyVisiting => panic!("no solution found: rules contain a cycle"),
122                State::Visited(b) => return b,
123                State::Unvisited => states[bag] = State::CurrentlyVisiting,
124            }
125
126            let mut result = 0u64;
127            for &(child, count) in &rules[bag] {
128                result += count as u64 * (1 + total_bags(rules, usize::from(child), states));
129            }
130
131            states[bag] = State::Visited(result);
132            result
133        }
134
135        let mut states = vec![State::Unvisited; self.rules.len()];
136        total_bags(&self.rules, self.target, &mut states)
137    }
138}
139
140examples!(Day07 -> (usize, u64) [
141    {file: "day07_example0.txt", part1: 4, part2: 32},
142    {file: "day07_example1.txt", part2: 126},
143]);
year2020/day07.rs

year2020/
day07.rs
