aoc/year2020/
day07.rs

1//! # Handy Haversacks
2//!
3//! A hash table would be a natural data structure for this problem but is a little slow.
4//! To make things faster we implement the hash table using an array and a combination of three
5//! [perfect hash functions](https://en.wikipedia.org/wiki/Perfect_hash_function) that map from
6//! each combination of bag descriptions to a unique index.
7//!
8//! There are 18 different adjectives, for example shiny, bright, dark. Taking only the first two
9//! letters is enough to discriminate. For example, the hash value for "shiny" is:
10//!
11//! ```none
12//!     "sh" =>
13//!     26 * 's' + 'h' =>
14//!     26 * (115 - 97) + (104 - 97) =>
15//!     26 * 115 + 104 - 2619 =>
16//!     475
17//! ```
18//!
19//! There are 33 different colors, for example white, gold, blue. The first two letters
20//! result in some duplicates, however incrementing the second letter if the length is odd
21//! is enough to discriminate.
22//!
23//! These first two hash values are then used to lookup consecutive indices from
24//! 0 to 17 and 0 to 32 respectively, which are then combined into a *third* hash value from
25//! 0 to 593 to form a perfect minimal hash function.
26//!
27//! Part one and part two are very similar. A recursive solution with memoization of previously
28//! seen values computes the result efficiently.
29use crate::util::iter::*;
30use crate::util::parse::*;
31
32const FIRST_HASH: [usize; 18] =
33    [43, 63, 78, 86, 92, 95, 98, 130, 294, 320, 332, 390, 401, 404, 475, 487, 554, 572];
34const SECOND_HASH: [usize; 33] = [
35    16, 31, 37, 38, 43, 44, 59, 67, 70, 76, 151, 170, 173, 174, 221, 286, 294, 312, 313, 376, 381,
36    401, 410, 447, 468, 476, 495, 498, 508, 515, 554, 580, 628,
37];
38
39#[derive(Clone, Copy)]
40pub struct Rule {
41    amount: u32,
42    next: usize,
43}
44
45type Bag = [Option<Rule>; 4];
46
47pub struct Haversack {
48    shiny_gold: usize,
49    bags: [Bag; 594],
50}
51
52pub fn parse(input: &str) -> Haversack {
53    let mut first_indices = [0; 676];
54    let mut second_indices = [0; 676];
55    let mut bags = [[None; 4]; 594];
56
57    FIRST_HASH.iter().enumerate().for_each(|(i, &h)| first_indices[h] = i);
58    SECOND_HASH.iter().enumerate().for_each(|(i, &h)| second_indices[h] = i);
59
60    let perfect_minimal_hash = |first: &str, second: &str| {
61        let first = first.as_bytes();
62        let a = first[0] as usize;
63        let b = first[1] as usize;
64
65        let second = second.as_bytes();
66        let c = second[0] as usize;
67        let d = (second[1] as usize) + (second.len() % 2);
68
69        first_indices[26 * a + b - 2619] + 18 * second_indices[26 * c + d - 2619]
70    };
71
72    for line in input.lines() {
73        let mut tokens = line.split_ascii_whitespace().chunk::<4>();
74        let [first, second, _, _] = tokens.next().unwrap();
75        let outer = perfect_minimal_hash(first, second);
76
77        for (slot, [amount, first, second, _]) in bags[outer].iter_mut().zip(tokens) {
78            let amount = amount.unsigned();
79            let next = perfect_minimal_hash(first, second);
80            *slot = Some(Rule { amount, next });
81        }
82    }
83
84    let shiny_gold = perfect_minimal_hash("shiny", "gold");
85    Haversack { shiny_gold, bags }
86}
87
88pub fn part1(input: &Haversack) -> usize {
89    fn helper(key: usize, haversack: &Haversack, cache: &mut [Option<bool>]) -> bool {
90        if let Some(value) = cache[key] {
91            return value;
92        }
93
94        let value =
95            haversack.bags[key].iter().flatten().any(|rule| helper(rule.next, haversack, cache));
96
97        cache[key] = Some(value);
98        value
99    }
100
101    let mut cache = vec![None; input.bags.len()];
102    cache[input.shiny_gold] = Some(true);
103    (0..input.bags.len()).filter(|&key| helper(key, input, &mut cache)).count() - 1
104}
105
106pub fn part2(input: &Haversack) -> u32 {
107    fn helper(key: usize, haversack: &Haversack, cache: &mut [Option<u32>]) -> u32 {
108        if let Some(value) = cache[key] {
109            return value;
110        }
111
112        let value = 1 + haversack.bags[key]
113            .iter()
114            .flatten()
115            .map(|rule| rule.amount * helper(rule.next, haversack, cache))
116            .sum::<u32>();
117
118        cache[key] = Some(value);
119        value
120    }
121
122    let mut cache = vec![None; input.bags.len()];
123    helper(input.shiny_gold, input, &mut cache) - 1
124}
aoc/year2020/day07.rs

aoc/year2020/
day07.rs
