aoclib/
day_21.rs

1use hashbrown::HashMap;
2use std::fs;
3
4fn _starting_positions(input: &str) -> [u64; 2] {
5    let re = regex::Regex::new(r"^Player (1|2) starting position: (\d+)$").unwrap();
6    let mut result = [0; 2];
7    let positions: Vec<u64> = input
8        .lines()
9        .map(|line| re.captures(line).unwrap()[2].parse::<u64>().unwrap() - 1)
10        .collect();
11    result[0] = positions[0];
12    result[1] = positions[1];
13    result
14}
15
16fn _quantum_die() -> HashMap<u64, u64> {
17    let mut result = HashMap::with_capacity(27);
18    for i in 1..=3 {
19        for j in 1..=3 {
20            for k in 1..=3 {
21                *(result.entry(i + j + k).or_insert(0)) += 1;
22            }
23        }
24    }
25    result
26}
27
28fn _quantum(
29    cache: &mut HashMap<(u64, u64, u64, u64), [u64; 2]>,
30    die: &HashMap<u64, u64>,
31    lpos: u64,
32    rpos: u64,
33    lscore: u64,
34    rscore: u64,
35) -> [u64; 2] {
36    if 21 <= rscore {
37        assert!(lscore < 21);
38        return [0, 1];
39    }
40    let mut result = [0; 2];
41    for (num_step, multiplier) in die.iter() {
42        let pos = (lpos + num_step) % 10;
43        let score = lscore + pos + 1;
44        let key = (rpos, pos, rscore, score);
45        let sub = {
46            if !cache.contains_key(&key) {
47                let value = _quantum(cache, die, rpos, pos, rscore, score);
48                cache.insert(key, value);
49                value
50            } else {
51                *cache.get(&key).unwrap()
52            }
53        };
54        result[0] += sub[1] * multiplier;
55        result[1] += sub[0] * multiplier;
56    }
57    result
58}
59
60pub fn part_1(input: &str) -> u64 {
61    let mut positions = _starting_positions(input);
62    let mut scores = vec![0; 2];
63    let mut i = 0;
64    loop {
65        for player in 0..=1 {
66            let mut num_step = 0;
67            for _ in 0..3 {
68                num_step += (i % 100) + 1;
69                i += 1;
70            }
71            positions[player] = (positions[player] + num_step) % 10;
72            scores[player] += positions[player] + 1;
73            if 1000 <= scores[player] {
74                return i * scores[(player + 1) % 2];
75            }
76        }
77    }
78}
79
80pub fn part_2(input: &str) -> u64 {
81    let positions = _starting_positions(input);
82    let mut cache = HashMap::new();
83    *_quantum(
84        &mut cache,
85        &_quantum_die(),
86        positions[0],
87        positions[1],
88        0,
89        0,
90    )
91    .iter()
92    .max()
93    .unwrap()
94}
95
96fn _from_file<F, T>(func: F, stem: &str) -> T
97where
98    F: Fn(&str) -> T,
99{
100    func(&fs::read_to_string(format!("inputs/21/{}.txt", stem)).unwrap())
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    #[test]
108    fn part_1_works_on_example() {
109        assert_eq!(_from_file(part_1, "example"), 739785);
110    }
111
112    #[test]
113    fn part_1_works_on_input() {
114        assert_eq!(_from_file(part_1, "input"), 916083);
115    }
116
117    #[test]
118    fn part_2_works_on_example() {
119        assert_eq!(_from_file(part_2, "example"), 444356092776315);
120    }
121
122    #[test]
123    fn part_2_works_on_input() {
124        assert_eq!(_from_file(part_2, "input"), 49982165861983);
125    }
126}
aoclib/day_21.rs

aoclib/
day_21.rs
