aoc/year2021/
day21.rs

1//! # Dirac Dice
2use crate::util::iter::*;
3use crate::util::parse::*;
4
5type Pair = (usize, usize);
6type State = (Pair, Pair);
7
8/// Rolling the Dirac dice 3 times results in 27 quantum universes. However the dice total is
9/// one of only 7 possible values. Instead of handling 27 values, we encode the possible dice
10/// totals with the number of times that they occur. For example a score of 3 (1 + 1 + 1) only
11/// happens once in the 27 rolls, but a score of 6 happens a total of 7 times.
12const DIRAC: [Pair; 7] = [(3, 1), (4, 3), (5, 6), (6, 7), (7, 6), (8, 3), (9, 1)];
13
14/// Extract the starting position for both players converting to zero based indices.
15pub fn parse(input: &str) -> State {
16    let [_, one, _, two]: [usize; 4] = input.iter_unsigned().chunk::<4>().next().unwrap();
17    ((one - 1, 0), (two - 1, 0))
18}
19
20/// The initial deterministic dice roll total is 6 (1 + 2 + 3) and increases by 9 each turn.
21/// An interesting observation is that since the player's position is always modulo 10, we can
22/// also increase the dice total modulo 10, as (a + b) % 10 = (a % 10) + (b % 10).
23pub fn part1(input: &State) -> usize {
24    let mut state = *input;
25    let mut dice = 6;
26    let mut rolls = 0;
27
28    loop {
29        // Player position is 0 based from 0 to 9, but score is 1 based from 1 to 10
30        let ((player_position, player_score), (other_position, other_score)) = state;
31        let next_position = (player_position + dice) % 10;
32        let next_score = player_score + next_position + 1;
33
34        dice = (dice + 9) % 10;
35        rolls += 3;
36
37        // Return the score of the losing player times the number of dice rolls.
38        if next_score >= 1000 {
39            break other_score * rolls;
40        }
41
42        // Swap the players so that they take alternating turns.
43        state = ((other_position, other_score), (next_position, next_score));
44    }
45}
46
47/// [Memoization](https://en.wikipedia.org/wiki/Memoization) is the key to solving part two in a
48/// reasonable time. For each possible starting universe we record the number of winning and losing
49/// recursive universes so that we can re-use the result and avoid uneccessary calculations.
50///
51/// Each player can be in position 1 to 10 and can have a score from 0 to 20 (as a score of 21
52/// ends the game). This is a total of (10 * 21) ^ 2 = 44100 possible states. For speed this
53/// can fit in an array with perfect hashing, instead of using a slower `HashMap`.
54pub fn part2(input: &State) -> usize {
55    let mut cache = vec![None; 44100];
56    let (win, lose) = dirac(*input, &mut cache);
57    win.max(lose)
58}
59
60fn dirac(state: State, cache: &mut [Option<Pair>]) -> Pair {
61    let ((player_position, player_score), (other_position, other_score)) = state;
62
63    // Calculate the perfect hash of the state and lookup the cache in case we've seen this before.
64    let index = player_position + 10 * other_position + 100 * player_score + 2100 * other_score;
65    if let Some(result) = cache[index] {
66        return result;
67    }
68
69    let helper = |(win, lose), &(dice, frequency)| {
70        let next_position = (player_position + dice) % 10;
71        let next_score = player_score + next_position + 1;
72
73        if next_score >= 21 {
74            (win + frequency, lose)
75        } else {
76            // Sneaky trick here to handle both players with the same function.
77            // We swap the order of players state each turn, so that turns alternate
78            // and record the result as (lose, win) instead of (win, lose).
79            let next_state = ((other_position, other_score), (next_position, next_score));
80            let (next_lose, next_win) = dirac(next_state, cache);
81            (win + frequency * next_win, lose + frequency * next_lose)
82        }
83    };
84
85    // Compute the number of wins and losses from this position and add to the cache.
86    let result = DIRAC.iter().fold((0, 0), helper);
87    cache[index] = Some(result);
88    result
89}
aoc/year2021/day21.rs

aoc/year2021/
day21.rs
