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

aoc/year2024/
day19.rs
