year2015/
day19.rs

1use std::collections::HashSet;
2use utils::prelude::*;
3
4/// Molecule string replacements.
5///
6/// Part 2 assumes there is only one possible number of steps, and that the replacements are always
7/// the same length or longer.
8#[derive(Clone, Debug)]
9pub struct Day19<'a> {
10    replacements: Vec<(&'a [u8], &'a [u8])>,
11    molecule: &'a [u8],
12}
13
14impl<'a> Day19<'a> {
15    pub fn new(input: &'a str, _: InputType) -> Result<Self, InputError> {
16        let Some((replacements, molecule)) = input.rsplit_once("\n\n") else {
17            return Err(InputError::new(
18                input,
19                0,
20                "expected replacements then a blank line then the molecule",
21            ));
22        };
23
24        Ok(Self {
25            replacements: parser::take_while1(u8::is_ascii_alphabetic)
26                .then(parser::take_while1(u8::is_ascii_alphabetic).with_prefix(" => "))
27                .parse_lines(replacements)?,
28            molecule: molecule.trim_ascii_end().as_bytes(),
29        })
30    }
31
32    #[must_use]
33    pub fn part1(&self) -> usize {
34        let mut set = HashSet::new();
35        for &(from, to) in &self.replacements {
36            let new_length = self.molecule.len() - from.len() + to.len();
37            for i in 0..self.molecule.len() {
38                if self.molecule[i..].starts_with(from) {
39                    let mut molecule = Vec::with_capacity(new_length);
40                    molecule.extend_from_slice(&self.molecule[..i]);
41                    molecule.extend_from_slice(to);
42                    molecule.extend_from_slice(&self.molecule[i + from.len()..]);
43                    set.insert(molecule);
44                }
45            }
46        }
47        set.len()
48    }
49
50    #[must_use]
51    pub fn part2(&self) -> u64 {
52        let mut molecule = self.molecule.to_vec();
53        let mut steps = 0;
54        while molecule.iter().any(|&x| x != b'e') {
55            for &(from, to) in &self.replacements {
56                let mut i = 0;
57                while i < molecule.len() {
58                    if molecule[i..].starts_with(to) {
59                        // Replace to with from, presuming from.len() <= to.len()
60                        molecule[i..i + from.len()].copy_from_slice(from);
61                        molecule.drain(i + from.len()..i + to.len());
62
63                        steps += 1;
64                    } else {
65                        i += 1;
66                    }
67                }
68            }
69        }
70        steps
71    }
72}
73
74examples!(Day19<'_> -> (usize, u64) [
75    {input: "H => HO\nH => OH\nO => HH\n\nHOH", part1: 4},
76    {input: "e => H\ne => O\nH => HO\nH => OH\nO => HH\n\nHOH", part2: 3},
77    {input: "e => H\ne => O\nH => HO\nH => OH\nO => HH\n\nHOHOHO", part2: 6},
78]);
year2015/day19.rs

year2015/
day19.rs
