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 LETTER_LOOKUP: [Option<Stripe>; 256] = {
28    let mut x = [None; 256];
29    x[b'w' as usize] = Some(Stripe::W);
30    x[b'u' as usize] = Some(Stripe::U);
31    x[b'b' as usize] = Some(Stripe::B);
32    x[b'r' as usize] = Some(Stripe::R);
33    x[b'g' as usize] = Some(Stripe::G);
34    x
35};
36
37const MAX_PATTERN_LENGTH: usize = 8;
38const MAX_DESIGN_LENGTH: usize = 64;
39
40impl Day19 {
41    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
42        let letter = parser::byte()
43            .map_res(|b| LETTER_LOOKUP[b as usize].ok_or("expected 'w', 'u', 'b', 'r' or 'g'"));
44
45        let Some((patterns, designs)) = input.split_once("\n\n") else {
46            return Err(InputError::new(input, 0, "expected patterns and designs"));
47        };
48
49        let mut trie = vec![TrieNode::default()];
50        for item in letter
51            .repeat_arrayvec::<MAX_PATTERN_LENGTH, _>(parser::noop(), 1)
52            .with_suffix(", ".or(parser::eof()))
53            .parse_iterator(patterns)
54        {
55            let mut index = 0;
56            for &s in item?.iter() {
57                match trie[index].child_offsets[s as usize] {
58                    None => {
59                        trie.push(TrieNode::default());
60                        trie[index].child_offsets[s as usize] =
61                            Some(NonZeroU32::new((trie.len() - 1 - index) as u32).unwrap());
62                        index = trie.len() - 1;
63                    }
64                    Some(offset) => index += offset.get() as usize,
65                }
66            }
67            trie[index].is_terminal = true;
68        }
69
70        let (mut part1, mut part2) = (0, 0);
71        let mut combinations = [0; MAX_DESIGN_LENGTH + 1];
72        combinations[0] = 1;
73        for item in letter
74            .repeat_arrayvec::<MAX_DESIGN_LENGTH, _>(parser::noop(), 1)
75            .with_suffix(parser::eol())
76            .parse_iterator(designs)
77        {
78            let design = item?;
79            for len in 1..=design.len() {
80                combinations[len] = 0;
81
82                let mut trie_index = 0;
83                for (i, &stripe) in design[design.len() - len..]
84                    .iter()
85                    .take(MAX_PATTERN_LENGTH)
86                    .enumerate()
87                {
88                    match trie[trie_index].child_offsets[stripe as usize] {
89                        None => break,
90                        Some(offset) => trie_index += offset.get() as usize,
91                    }
92
93                    combinations[len] +=
94                        u64::from(trie[trie_index].is_terminal) * combinations[len - 1 - i];
95                }
96            }
97
98            let ways = combinations[design.len()];
99            part1 += if ways > 0 { 1 } else { 0 };
100            part2 += ways;
101        }
102
103        Ok(Self { part1, part2 })
104    }
105
106    #[must_use]
107    pub fn part1(&self) -> u64 {
108        self.part1
109    }
110
111    #[must_use]
112    pub fn part2(&self) -> u64 {
113        self.part2
114    }
115}
116
117examples!(Day19 -> (u64, u64) [
118    {file: "day19_example0.txt", part1: 6, part2: 16},
119]);
year2024/day19.rs

year2024/
day19.rs
