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
18pub fn parse(input: &str) -> Input {
19    let (prefix, suffix) = input.split_once("\n\n").unwrap();
20
21    // Build Trie from all towels.
22    let mut trie = Vec::with_capacity(1_000);
23    trie.push(Node::new());
24
25    for towel in prefix.split(", ") {
26        let mut i = 0;
27
28        for j in towel.bytes().map(perfect_hash) {
29            if trie[i].next[j] == 0 {
30                // This is a new prefix, so update the index to point to it then push new node.
31                trie[i].next[j] = trie.len();
32                i = trie.len();
33                trie.push(Node::new());
34            } else {
35                // Follow existing prefix.
36                i = trie[i].next[j];
37            }
38        }
39
40        trie[i].set_towel();
41    }
42
43    let mut part_one = 0;
44    let mut part_two = 0;
45    let mut ways = Vec::with_capacity(100);
46
47    for design in suffix.lines().map(str::as_bytes) {
48        let size = design.len();
49
50        // Reset state.
51        ways.clear();
52        ways.resize(size + 1, 0);
53
54        // There's 1 way to create any possible first prefix.
55        ways[0] = 1;
56
57        for start in 0..size {
58            // Only consider suffixes that have a valid prefix.
59            if ways[start] > 0 {
60                // Walk trie from root to leaf.
61                let mut i = 0;
62
63                for end in start..size {
64                    // Get next link.
65                    i = trie[i].next[perfect_hash(design[end])];
66
67                    // This is not a valid prefix, stop the search.
68                    if i == 0 {
69                        break;
70                    }
71
72                    // Add the number of possible ways this prefix can be reached.
73                    ways[end + 1] += trie[i].towels() * ways[start];
74                }
75            }
76        }
77
78        // Last element is the total possible combinations.
79        let total = ways[size];
80        part_one += (total > 0) as usize;
81        part_two += total;
82    }
83
84    (part_one, part_two)
85}
86
87pub fn part1(input: &Input) -> usize {
88    input.0
89}
90
91pub fn part2(input: &Input) -> usize {
92    input.1
93}
94
95/// Hashes the five possible color values white (w), blue (u), black (b), red (r), or green (g)
96/// to 0, 2, 4, 5 and 1 respectively. This compresses the range to fit into an array of 6 elements.
97fn perfect_hash(b: u8) -> usize {
98    let n = b as usize;
99    (n ^ (n >> 4)) % 8
100}
101
102/// Simple Node object that uses indices to link to other nodes.
103struct Node {
104    next: [usize; 6],
105}
106
107impl Node {
108    fn new() -> Self {
109        Node { next: [0; 6] }
110    }
111
112    // Index 3 is not used by the hash, so we cheekily repurpose for the number of towels.
113    fn set_towel(&mut self) {
114        self.next[3] = 1;
115    }
116
117    fn towels(&self) -> usize {
118        self.next[3]
119    }
120}
aoc/year2024/day19.rs

aoc/year2024/
day19.rs
