1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

//! # Handy Haversacks
//!
//! A hashtable would be a natural data structure for this problem but is a little slow.
//! To make things faster we implement the hashtable using an array and a combination of three
//! [perfect hash functions](https://en.wikipedia.org/wiki/Perfect_hash_function) that map from
//! each combination of bag descriptions to a unique index.
//!
//! There are 18 different adjectives, for example shiny, bright, dark. Taking only the first two
//! letters in enough to discriminate. For example the hash value for "shiny" is:
//!
//! ```none
//!     "sh" =>
//!     26 * 's' + 'h' =>
//!     26 * (115 - 97) + (104 - 97) =>
//!     26 * 115 + 104 - 2619 =>
//!     475
//! ```
//!
//! There are 33 different colors, for example white, gold, blue. The first two letters
//! result in some duplicates, however incrementing the second letter if the length is odd
//! is enough to discriminate.
//!
//! These first two hash values are then used to lookup consecutive indices from
//! 0 to 17 and 0 to 32 respectively, which are then combined into a *third* hash value from
//! 0 to 593 to form a perfect minimal hash function.
//!
//! Part one and part two are very similar. A recursive solution with memoization of previously
//! seen values computes the result efficiently.
use crate::util::iter::*;
use crate::util::parse::*;

const FIRST_HASH: [usize; 18] =
    [43, 63, 78, 86, 92, 95, 98, 130, 294, 320, 332, 390, 401, 404, 475, 487, 554, 572];
const SECOND_HASH: [usize; 33] = [
    16, 31, 37, 38, 43, 44, 59, 67, 70, 76, 151, 170, 173, 174, 221, 286, 294, 312, 313, 376, 381,
    401, 410, 447, 468, 476, 495, 498, 508, 515, 554, 580, 628,
];

#[derive(Clone, Copy)]
pub struct Rule {
    amount: u32,
    next: usize,
}

type Bag = [Option<Rule>; 4];

pub struct Haversack {
    shiny_gold: usize,
    bags: [Bag; 594],
}

pub fn parse(input: &str) -> Haversack {
    let mut first_indices = [0; 676];
    let mut second_indices = [0; 676];
    let mut bags = [[None; 4]; 594];

    FIRST_HASH.iter().enumerate().for_each(|(i, &h)| first_indices[h] = i);
    SECOND_HASH.iter().enumerate().for_each(|(i, &h)| second_indices[h] = i);

    let perfect_minimal_hash = |first: &str, second: &str| {
        let first = first.as_bytes();
        let a = first[0] as usize;
        let b = first[1] as usize;

        let second = second.as_bytes();
        let c = second[0] as usize;
        let d = (second[1] as usize) + (second.len() % 2);

        first_indices[26 * a + b - 2619] + 18 * second_indices[26 * c + d - 2619]
    };

    for line in input.lines() {
        let mut tokens = line.split_ascii_whitespace().chunk::<4>();
        let [first, second, _, _] = tokens.next().unwrap();
        let outer = perfect_minimal_hash(first, second);

        for (index, chunk) in tokens.enumerate() {
            let [amount, first, second, _] = chunk;
            let amount = amount.unsigned();
            let next = perfect_minimal_hash(first, second);
            bags[outer][index] = Some(Rule { amount, next });
        }
    }

    let shiny_gold = perfect_minimal_hash("shiny", "gold");
    Haversack { shiny_gold, bags }
}

pub fn part1(input: &Haversack) -> usize {
    fn helper(key: usize, haversack: &Haversack, cache: &mut [Option<bool>]) -> bool {
        if let Some(value) = cache[key] {
            value
        } else {
            let mut value = false;
            let mut iter = haversack.bags[key].iter();

            while let Some(Some(Rule { next, .. })) = iter.next() {
                if helper(*next, haversack, cache) {
                    value = true;
                    break;
                }
            }

            cache[key] = Some(value);
            value
        }
    }

    let mut cache = vec![None; input.bags.len()];
    cache[input.shiny_gold] = Some(true);
    (0..input.bags.len()).filter(|&key| helper(key, input, &mut cache)).count() - 1
}

pub fn part2(input: &Haversack) -> u32 {
    fn helper(key: usize, haversack: &Haversack, cache: &mut [Option<u32>]) -> u32 {
        if let Some(value) = cache[key] {
            value
        } else {
            let mut value = 1;
            let mut iter = haversack.bags[key].iter();

            while let Some(Some(Rule { amount, next })) = iter.next() {
                value += amount * helper(*next, haversack, cache);
            }

            cache[key] = Some(value);
            value
        }
    }

    let mut cache = vec![None; input.bags.len()];
    helper(input.shiny_gold, input, &mut cache) - 1
}