year2015/
day19.rs

1use std::collections::HashSet;
2use utils::array::ArrayVec;
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        let mut set = HashSet::new();
78        for (from, to) in &self.rules {
79            let Some(from) = *from else { continue };
80            let new_length = self.molecule.len() + to.len() - 1;
81            for i in 0..self.molecule.len() {
82                if self.molecule[i] == from {
83                    let mut molecule = Vec::with_capacity(new_length);
84                    molecule.extend_from_slice(&self.molecule[..i]);
85                    molecule.extend_from_slice(to);
86                    molecule.extend_from_slice(&self.molecule[i + 1..]);
87
88                    // `.into_iter().map(|x| x as u8).collect::<Vec<_>>()` makes this function 2-3x
89                    // faster as the std::hash::Hash implementation for u8 implements hash_slice
90                    // efficiently using a single call to write, and the into_iter-map-collect chain
91                    // is a no-op. It isn't possible to implement Hash::hash_slice for Atom so
92                    // efficiently without unsafe code / transmute.
93                    set.insert(molecule.into_iter().map(|x| x as u8).collect::<Vec<_>>());
94                }
95            }
96        }
97        set.len()
98    }
99
100    #[must_use]
101    pub fn part2(&self) -> u32 {
102        #[derive(Copy, Clone, Debug)]
103        struct State {
104            rule: usize,
105            dot: usize,
106            origin: usize,
107        }
108
109        // Store the chart as a list of state lists at each position, plus a bitset for the current
110        // and next positions. This works well as only the current and next position sets are ever
111        // updated, and the bitset makes duplicate checking fast. Previous sets are only ever
112        // iterated over. The current list is also reused as a queue of states to process.
113        let mut chart = vec![Vec::new(); self.molecule.len() + 1];
114
115        // Indexed by bitset[origin][dot] & (1 << rule):
116        // - 9 possible dot values (0-8 inclusive, enforced by ArrayVec N),
117        // - 64 possible rules (checked in new).
118        let mut current_bitset = vec![[0u64; 9]; self.molecule.len() + 1];
119        let mut next_bitset = vec![[0u64; 9]; self.molecule.len() + 1];
120
121        // Preprocess the rules into separate lists by the LHS, populating e rules into the initial
122        // set.
123        let mut rules_by_lhs = vec![Vec::new(); 16];
124        for (i, (lhs, _)) in self.rules.iter().enumerate() {
125            if let Some(lhs) = *lhs {
126                rules_by_lhs[lhs as usize].push(i);
127            } else {
128                let state = State {
129                    rule: i,
130                    dot: 0,
131                    origin: 0,
132                };
133                current_bitset[state.origin][state.dot] |= 1 << state.rule;
134                chart[0].push((state, 1));
135            }
136        }
137
138        // Optimization: Only do predictions once per atom per position.
139        let mut predictions_done = 0u16;
140        // Optimization: Only do completions once per (origin, atom) per position.
141        let mut completions_done = vec![0u16; self.molecule.len() + 1];
142
143        for pos in 0..chart.len() {
144            let mut set_idx = 0;
145            while let Some(&(state, steps)) = chart[pos].get(set_idx) {
146                let (lhs, rhs) = &self.rules[state.rule];
147
148                if state.dot < rhs.len() {
149                    // Prediction
150                    if predictions_done & (1 << rhs[state.dot] as usize) == 0 {
151                        predictions_done |= 1 << rhs[state.dot] as usize;
152
153                        for &i in &rules_by_lhs[rhs[state.dot] as usize] {
154                            let new = State {
155                                rule: i,
156                                dot: 0,
157                                origin: pos,
158                            };
159                            if current_bitset[new.origin][new.dot] & (1 << new.rule) == 0 {
160                                current_bitset[new.origin][new.dot] |= 1 << new.rule;
161                                chart[pos].push((new, 1));
162                            }
163                        }
164                    }
165
166                    // Scanning
167                    if self.molecule.get(pos) == Some(&rhs[state.dot]) {
168                        let new = State {
169                            rule: state.rule,
170                            dot: state.dot + 1,
171                            origin: state.origin,
172                        };
173                        if next_bitset[new.origin][new.dot] & (1 << new.rule) == 0 {
174                            next_bitset[new.origin][new.dot] |= 1 << new.rule;
175                            chart[pos + 1].push((new, steps));
176                        }
177                    }
178                } else if let Some(lhs) = *lhs {
179                    // Completion
180                    if completions_done[state.origin] & (1 << lhs as usize) == 0 {
181                        completions_done[state.origin] |= 1 << lhs as usize;
182
183                        let [current_chart, origin_chart] = chart
184                            .get_disjoint_mut([pos, state.origin])
185                            .expect("origin must be less than pos");
186
187                        for (prev_state, prev_steps) in origin_chart.iter() {
188                            let (_, prev_rhs) = &self.rules[prev_state.rule];
189                            if prev_state.dot < prev_rhs.len() && prev_rhs[prev_state.dot] == lhs {
190                                let new = State {
191                                    rule: prev_state.rule,
192                                    dot: prev_state.dot + 1,
193                                    origin: prev_state.origin,
194                                };
195                                if current_bitset[new.origin][new.dot] & (1 << new.rule) == 0 {
196                                    current_bitset[new.origin][new.dot] |= 1 << new.rule;
197                                    current_chart.push((new, steps + prev_steps));
198                                }
199                            }
200                        }
201                    }
202                } else if pos == self.molecule.len() {
203                    // Completion of a start rule consuming the entire molecule
204                    return steps;
205                }
206
207                set_idx += 1;
208            }
209
210            (current_bitset, next_bitset) = (next_bitset, current_bitset);
211            next_bitset[..=pos].fill([0; 9]);
212
213            // Reset optimization caches for the next position
214            predictions_done = 0u16;
215            completions_done[..pos].fill(0);
216        }
217
218        panic!("no solution found");
219    }
220}
221
222examples!(Day19 -> (usize, u32) [
223    {input: "H => HO\nH => OH\nO => HH\n\nHOH", part1: 4},
224    {input: "e => H\ne => O\nH => HO\nH => OH\nO => HH\n\nHOH", part2: 3},
225    {input: "e => H\ne => O\nH => HO\nH => OH\nO => HH\n\nHOHOHO", part2: 6},
226]);
year2015/day19.rs

year2015/
day19.rs
