aoc/year2020/
day07.rs

1//! # Handy Haversacks
2//!
3//! A hashtable would be a natural data structure for this problem but is a little slow.
4//! To make things faster we implement the hashtable 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 in 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 (index, chunk) in tokens.enumerate() {
78            let [amount, first, second, _] = chunk;
79            let amount = amount.unsigned();
80            let next = perfect_minimal_hash(first, second);
81            bags[outer][index] = Some(Rule { amount, next });
82        }
83    }
84
85    let shiny_gold = perfect_minimal_hash("shiny", "gold");
86    Haversack { shiny_gold, bags }
87}
88
89pub fn part1(input: &Haversack) -> usize {
90    fn helper(key: usize, haversack: &Haversack, cache: &mut [Option<bool>]) -> bool {
91        if let Some(value) = cache[key] {
92            value
93        } else {
94            let mut value = false;
95            let mut iter = haversack.bags[key].iter();
96
97            while let Some(Some(Rule { next, .. })) = iter.next() {
98                if helper(*next, haversack, cache) {
99                    value = true;
100                    break;
101                }
102            }
103
104            cache[key] = Some(value);
105            value
106        }
107    }
108
109    let mut cache = vec![None; input.bags.len()];
110    cache[input.shiny_gold] = Some(true);
111    (0..input.bags.len()).filter(|&key| helper(key, input, &mut cache)).count() - 1
112}
113
114pub fn part2(input: &Haversack) -> u32 {
115    fn helper(key: usize, haversack: &Haversack, cache: &mut [Option<u32>]) -> u32 {
116        if let Some(value) = cache[key] {
117            value
118        } else {
119            let mut value = 1;
120            let mut iter = haversack.bags[key].iter();
121
122            while let Some(Some(Rule { amount, next })) = iter.next() {
123                value += amount * helper(*next, haversack, cache);
124            }
125
126            cache[key] = Some(value);
127            value
128        }
129    }
130
131    let mut cache = vec![None; input.bags.len()];
132    helper(input.shiny_gold, input, &mut cache) - 1
133}
aoc/year2020/day07.rs

aoc/year2020/
day07.rs
