year2024/
day19.rs

1use std::num::NonZeroU32;
2use utils::prelude::*;
3
4/// Counting possible combinations of patterns to form designs.
5#[derive(Clone, Debug)]
6pub struct Day19 {
7    part1: u64,
8    part2: u64,
9}
10
11#[derive(Copy, Clone, Debug, Default, Eq, PartialEq)]
12enum Stripe {
13    #[default]
14    W,
15    U,
16    B,
17    R,
18    G,
19}
20
21#[derive(Clone, Debug, Default)]
22struct TrieNode {
23    child_offsets: [Option<NonZeroU32>; 5],
24    is_terminal: bool,
25}
26
27const MAX_PATTERN_LENGTH: usize = 8;
28const MAX_DESIGN_LENGTH: usize = 64;
29
30impl Day19 {
31    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
32        let letter = parser::byte_map!(
33            b'w' => Stripe::W,
34            b'u' => Stripe::U,
35            b'b' => Stripe::B,
36            b'r' => Stripe::R,
37            b'g' => Stripe::G,
38        );
39
40        let Some((patterns, designs)) = input
41            .split_once("\n\n")
42            .or_else(|| input.split_once("\r\n\r\n"))
43        else {
44            return Err(InputError::new(input, 0, "expected patterns and designs"));
45        };
46
47        let mut trie = vec![TrieNode::default()];
48        for item in letter
49            .repeat_arrayvec::<MAX_PATTERN_LENGTH, _>(parser::noop(), 1)
50            .with_suffix(", ".or(parser::eof()))
51            .parse_iterator(patterns)
52        {
53            let mut index = 0;
54            for &s in item?.iter() {
55                match trie[index].child_offsets[s as usize] {
56                    None => {
57                        trie.push(TrieNode::default());
58                        trie[index].child_offsets[s as usize] =
59                            Some(NonZeroU32::new((trie.len() - 1 - index) as u32).unwrap());
60                        index = trie.len() - 1;
61                    }
62                    Some(offset) => index += offset.get() as usize,
63                }
64            }
65            trie[index].is_terminal = true;
66        }
67
68        let (mut part1, mut part2) = (0, 0);
69        let mut combinations = [0; MAX_DESIGN_LENGTH + 1];
70        combinations[0] = 1;
71        for item in letter
72            .repeat_arrayvec::<MAX_DESIGN_LENGTH, _>(parser::noop(), 1)
73            .with_suffix(parser::eol())
74            .parse_iterator(designs)
75        {
76            let design = item?;
77            for len in 1..=design.len() {
78                combinations[len] = 0;
79
80                let mut trie_index = 0;
81                for (i, &stripe) in design[design.len() - len..]
82                    .iter()
83                    .take(MAX_PATTERN_LENGTH)
84                    .enumerate()
85                {
86                    match trie[trie_index].child_offsets[stripe as usize] {
87                        None => break,
88                        Some(offset) => trie_index += offset.get() as usize,
89                    }
90
91                    combinations[len] +=
92                        u64::from(trie[trie_index].is_terminal) * combinations[len - 1 - i];
93                }
94            }
95
96            let ways = combinations[design.len()];
97            part1 += if ways > 0 { 1 } else { 0 };
98            part2 += ways;
99        }
100
101        Ok(Self { part1, part2 })
102    }
103
104    #[must_use]
105    pub fn part1(&self) -> u64 {
106        self.part1
107    }
108
109    #[must_use]
110    pub fn part2(&self) -> u64 {
111        self.part2
112    }
113}
114
115examples!(Day19 -> (u64, u64) [
116    {file: "day19_example0.txt", part1: 6, part2: 16},
117]);
year2024/day19.rs

year2024/
day19.rs
