year2015/
day19.rs

1use utils::array::ArrayVec;
2use utils::hash::FastSet;
3use utils::prelude::*;
4
5/// Molecule string replacements.
6///
7/// Part 2 assumes there is only one possible number of steps but does not assume the `Rn` `Y` `Ar`
8/// bracket structure or use the formula. Instead, it uses an optimized
9/// [Earley parser](https://en.wikipedia.org/wiki/Earley_parser), which ensures the molecule can be
10/// created from the provided rules.
11#[derive(Clone, Debug)]
12pub struct Day19 {
13    rules: Vec<(Option<Atom>, ArrayVec<Atom, 8>)>,
14    molecule: Vec<Atom>,
15}
16
17parser::parsable_enum! {
18    #[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Hash)]
19    #[repr(u8)]
20    enum Atom {
21        #[default]
22        "Al" => Al,
23        "Ar" => Ar,
24        "B" => B,
25        "Ca" => Ca,
26        "C" => C,
27        "F" => F,
28        "H" => H,
29        "Mg" => Mg,
30        "N" => N,
31        "O" => O,
32        "P" => P,
33        "Rn" => Rn,
34        "Si" => Si,
35        "Th" => Th,
36        "Ti" => Ti,
37        "Y" => Y,
38    }
39}
40
41const _: () = {
42    assert!(Atom::ALL.len() <= 16);
43};
44
45impl Day19 {
46    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
47        let Some((rules_str, molecule)) = input
48            .rsplit_once("\n\n")
49            .or_else(|| input.rsplit_once("\r\n\r\n"))
50        else {
51            return Err(InputError::new(
52                input,
53                0,
54                "expected rules then a blank line then the molecule",
55            ));
56        };
57
58        let rules = Atom::PARSER
59            .map(Some)
60            .or(b'e'.map(|_| None))
61            .with_suffix(" => ")
62            .then(Atom::PARSER.repeat_arrayvec(parser::noop(), 1))
63            .parse_lines(rules_str)?;
64
65        if rules.len() > 64 {
66            return Err(InputError::new(input, rules_str.len(), "too many rules"));
67        }
68
69        Ok(Self {
70            rules,
71            molecule: Atom::PARSER.parse_all(molecule)?,
72        })
73    }
74
75    #[must_use]
76    pub fn part1(&self) -> usize {
77        // Total molecules generated by the rules, before deduplication
78        let mut counts = [0; Atom::ALL.len()];
79        for &atom in &self.molecule {
80            counts[atom as usize] += 1;
81        }
82        let total = self
83            .rules
84            .iter()
85            .filter_map(|(from, _)| from.map(|from| counts[from as usize]))
86            .sum();
87
88        let mut set = FastSet::with_capacity(total);
89        for (from, to) in &self.rules {
90            let Some(from) = *from else { continue };
91            let new_length = self.molecule.len() + to.len() - 1;
92            for i in 0..self.molecule.len() {
93                if self.molecule[i] == from {
94                    let mut molecule = Vec::with_capacity(new_length);
95                    molecule.extend_from_slice(&self.molecule[..i]);
96                    molecule.extend_from_slice(to);
97                    molecule.extend_from_slice(&self.molecule[i + 1..]);
98
99                    // `.into_iter().map(|x| x as u8).collect::<Vec<_>>()` makes this function 2-3x
100                    // faster as the std::hash::Hash implementation for u8 implements hash_slice
101                    // efficiently using a single call to write, and the into_iter-map-collect chain
102                    // is a no-op. It isn't possible to implement Hash::hash_slice for Atom so
103                    // efficiently without unsafe code / transmute.
104                    set.insert(molecule.into_iter().map(|x| x as u8).collect::<Vec<_>>());
105                }
106            }
107        }
108        set.len()
109    }
110
111    #[must_use]
112    pub fn part2(&self) -> u32 {
113        #[derive(Copy, Clone, Debug)]
114        struct State {
115            rule: usize,
116            dot: usize,
117            origin: usize,
118        }
119
120        // Store the chart as a list of state lists at each position, plus a bitset for the current
121        // and next positions. This works well as only the current and next position sets are ever
122        // updated, and the bitset makes duplicate checking fast. Previous sets are only ever
123        // iterated over. The current list is also reused as a queue of states to process.
124        let mut chart = vec![Vec::new(); self.molecule.len() + 1];
125
126        // Indexed by bitset[origin][dot] & (1 << rule):
127        // - 9 possible dot values (0-8 inclusive, enforced by ArrayVec N),
128        // - 64 possible rules (checked in new).
129        let mut current_bitset = vec![[0u64; 9]; self.molecule.len() + 1];
130        let mut next_bitset = vec![[0u64; 9]; self.molecule.len() + 1];
131
132        // Preprocess the rules into separate lists by the LHS, populating e rules into the initial
133        // set.
134        let mut rules_by_lhs = vec![Vec::new(); 16];
135        for (i, (lhs, _)) in self.rules.iter().enumerate() {
136            if let Some(lhs) = *lhs {
137                rules_by_lhs[lhs as usize].push(i);
138            } else {
139                let state = State {
140                    rule: i,
141                    dot: 0,
142                    origin: 0,
143                };
144                current_bitset[state.origin][state.dot] |= 1 << state.rule;
145                chart[0].push((state, 1));
146            }
147        }
148
149        // Optimization: Only do predictions once per atom per position.
150        let mut predictions_done = 0u16;
151        // Optimization: Only do completions once per (origin, atom) per position.
152        let mut completions_done = vec![0u16; self.molecule.len() + 1];
153
154        for pos in 0..chart.len() {
155            let mut set_idx = 0;
156            while let Some(&(state, steps)) = chart[pos].get(set_idx) {
157                let (lhs, rhs) = &self.rules[state.rule];
158
159                if state.dot < rhs.len() {
160                    // Prediction
161                    if predictions_done & (1 << rhs[state.dot] as usize) == 0 {
162                        predictions_done |= 1 << rhs[state.dot] as usize;
163
164                        for &i in &rules_by_lhs[rhs[state.dot] as usize] {
165                            let new = State {
166                                rule: i,
167                                dot: 0,
168                                origin: pos,
169                            };
170                            if current_bitset[new.origin][new.dot] & (1 << new.rule) == 0 {
171                                current_bitset[new.origin][new.dot] |= 1 << new.rule;
172                                chart[pos].push((new, 1));
173                            }
174                        }
175                    }
176
177                    // Scanning
178                    if self.molecule.get(pos) == Some(&rhs[state.dot]) {
179                        let new = State {
180                            rule: state.rule,
181                            dot: state.dot + 1,
182                            origin: state.origin,
183                        };
184                        if next_bitset[new.origin][new.dot] & (1 << new.rule) == 0 {
185                            next_bitset[new.origin][new.dot] |= 1 << new.rule;
186                            chart[pos + 1].push((new, steps));
187                        }
188                    }
189                } else if let Some(lhs) = *lhs {
190                    // Completion
191                    if completions_done[state.origin] & (1 << lhs as usize) == 0 {
192                        completions_done[state.origin] |= 1 << lhs as usize;
193
194                        let [current_chart, origin_chart] = chart
195                            .get_disjoint_mut([pos, state.origin])
196                            .expect("origin must be less than pos");
197
198                        for (prev_state, prev_steps) in origin_chart.iter() {
199                            let (_, prev_rhs) = &self.rules[prev_state.rule];
200                            if prev_state.dot < prev_rhs.len() && prev_rhs[prev_state.dot] == lhs {
201                                let new = State {
202                                    rule: prev_state.rule,
203                                    dot: prev_state.dot + 1,
204                                    origin: prev_state.origin,
205                                };
206                                if current_bitset[new.origin][new.dot] & (1 << new.rule) == 0 {
207                                    current_bitset[new.origin][new.dot] |= 1 << new.rule;
208                                    current_chart.push((new, steps + prev_steps));
209                                }
210                            }
211                        }
212                    }
213                } else if pos == self.molecule.len() {
214                    // Completion of a start rule consuming the entire molecule
215                    return steps;
216                }
217
218                set_idx += 1;
219            }
220
221            (current_bitset, next_bitset) = (next_bitset, current_bitset);
222            next_bitset[..=pos].fill([0; 9]);
223
224            // Reset optimization caches for the next position
225            predictions_done = 0u16;
226            completions_done[..pos].fill(0);
227        }
228
229        panic!("no solution found");
230    }
231}
232
233examples!(Day19 -> (usize, u32) [
234    {input: "H => HO\nH => OH\nO => HH\n\nHOH", part1: 4},
235    {input: "e => H\ne => O\nH => HO\nH => OH\nO => HH\n\nHOH", part2: 3},
236    {input: "e => H\ne => O\nH => HO\nH => OH\nO => HH\n\nHOHOHO", part2: 6},
237]);
year2015/day19.rs

year2015/
day19.rs
