aoc/year2024/
day19.rs

1//! # Linen Layout
2//!
3//! Solves both parts simultaneously. Part one is the number of designs with non-zero possible
4//! combinations.
5//!
6//! An elegant approach to check if the design starts with any towel is to first build a
7//! [trie](https://en.wikipedia.org/wiki/Trie). Each node in the trie stores a `bool` indicating
8//! if it's a valid towel and links to the next node for each possible color.
9//!
10//! There are only 5 colors. A custom [perfect hash](https://en.wikipedia.org/wiki/Perfect_hash_function)
11//! function maps indices between 0 and 7 so that they fit into a fixed-size array. This is faster
12//! than using a `HashSet`.
13//!
14//! Additionally, we store the trie in a flat `vec`. This is simpler and faster than creating
15//! objects on the heap using [`Box`].
16type Input = (usize, usize);
17
18/// Simple Node object that uses indices to link to other nodes.
19#[derive(Default)]
20struct Node {
21    next: [usize; 6],
22}
23
24impl Node {
25    // Index 3 is not used by the hash, so we cheekily repurpose for the number of towels.
26    fn set_towel(&mut self) {
27        self.next[3] = 1;
28    }
29
30    fn towels(&self) -> usize {
31        self.next[3]
32    }
33}
34
35pub fn parse(input: &str) -> Input {
36    let (prefix, suffix) = input.split_once("\n\n").unwrap();
37
38    // Build Trie from all towels.
39    let mut trie = Vec::with_capacity(1_000);
40    trie.push(Node::default());
41
42    for towel in prefix.split(", ") {
43        let mut i = 0;
44
45        for j in towel.bytes().map(perfect_hash) {
46            // This is a new prefix, so point the link at a freshly pushed node.
47            if trie[i].next[j] == 0 {
48                trie[i].next[j] = trie.len();
49                trie.push(Node::default());
50            }
51
52            // Follow the link.
53            i = trie[i].next[j];
54        }
55
56        trie[i].set_towel();
57    }
58
59    let mut ways = Vec::with_capacity(100);
60
61    suffix.lines().map(str::as_bytes).fold((0, 0), |(part_one, part_two), design| {
62        let size = design.len();
63
64        // Reset state.
65        ways.clear();
66        ways.resize(size + 1, 0);
67
68        // There's 1 way to create any possible first prefix.
69        ways[0] = 1;
70
71        for start in 0..size {
72            // Only consider suffixes that have a valid prefix.
73            if ways[start] > 0 {
74                // Walk trie from root to leaf.
75                let mut i = 0;
76
77                for end in start..size {
78                    // Get next link.
79                    i = trie[i].next[perfect_hash(design[end])];
80
81                    // This is not a valid prefix, stop the search.
82                    if i == 0 {
83                        break;
84                    }
85
86                    // Add the number of possible ways this prefix can be reached.
87                    ways[end + 1] += trie[i].towels() * ways[start];
88                }
89            }
90        }
91
92        // Last element is the total possible combinations.
93        let total = ways[size];
94        (part_one + (total > 0) as usize, part_two + total)
95    })
96}
97
98pub fn part1(input: &Input) -> usize {
99    input.0
100}
101
102pub fn part2(input: &Input) -> usize {
103    input.1
104}
105
106/// Hashes the five possible color values white (w), blue (u), black (b), red (r), or green (g)
107/// to 0, 2, 4, 5 and 1 respectively. This compresses the range to fit into an array of 6 elements.
108fn perfect_hash(b: u8) -> usize {
109    let n = b as usize;
110    (n ^ (n >> 4)) % 8
111}
aoc/year2024/day19.rs

aoc/year2024/
day19.rs
