advent-of-code

commit 29faa3c03c6dc773cef82d51e47ce63b14c806ce
parent ec2e4a7e3c014e1529054f5734e64d0eb2d2240d
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date:   Tue, 21 Dec 2021 19:17:06 -0600

Add 2021 day 21

Diffstat:
A
2021/day21/input.txt
 | 
2
++
A
2021/day21/main.rs
 | 
105
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 107 insertions(+), 0 deletions(-)
diff --git a/2021/day21/input.txt b/2021/day21/input.txt
@@ -0,0 +1,2 @@
+Player 1 starting position: 7
+Player 2 starting position: 1
diff --git a/2021/day21/main.rs b/2021/day21/main.rs
@@ -0,0 +1,105 @@
+use std::collections::{HashMap, VecDeque};
+
+fn main() {
+    let (p1, p2) = (7, 1);
+    // 684495
+    println!("Part 1: {}", part_1(p1, p2, 1000));
+    // 152587196649184
+    println!("Part 2: {}", part_2(p1, p2, 21));
+}
+
+struct DeterministicDice {
+    value: usize,
+    count: usize,
+}
+
+impl DeterministicDice {
+    fn next(&mut self) -> usize {
+        self.value = self.value % 100 + 1;
+        self.count += 1;
+        self.value
+    }
+}
+
+fn part_1(mut p1: usize, mut p2: usize, winning_score: usize) -> usize {
+    let mut dice = DeterministicDice { value: 0, count: 0 };
+    let mut p1_score = 0;
+    let mut p2_score = 0;
+    loop {
+        p1 = (p1 + dice.next() + dice.next() + dice.next() - 1) % 10 + 1;
+        p1_score += p1;
+        if p1_score >= winning_score {
+            return dice.count * p2_score;
+        }
+        p2 = (p2 + dice.next() + dice.next() + dice.next() - 1) % 10 + 1;
+        p2_score += p2;
+        if p2_score >= winning_score {
+            return dice.count * p1_score;
+        }
+    }
+}
+
+fn calc_winning_steps(p: usize, winning_score: usize) -> HashMap<usize, usize> {
+    // comput number of ways to win in n steps
+    let mut winning_steps = HashMap::new();
+    let mut queue = VecDeque::new();
+    queue.push_back((p, 0, 0, 1));
+    while let Some((pos, score, step_count, mult)) = queue.pop_front() {
+        let mut next_batch = HashMap::new();
+        for dice_1 in 1..=3 {
+            for dice_2 in 1..=3 {
+                for dice_3 in 1..=3 {
+                    let next_pos = (pos + dice_1 + dice_2 + dice_3 - 1) % 10 + 1;
+                    let next_score = score + next_pos;
+                    let next_step_count = step_count + 1;
+                    if next_score >= winning_score {
+                        winning_steps.insert(
+                            next_step_count,
+                            *winning_steps.get(&next_step_count).unwrap_or(&0) + mult,
+                        );
+                    } else {
+                        let entry = (next_pos, next_score, next_step_count);
+                        next_batch.insert(entry, *next_batch.get(&entry).unwrap_or(&0) + mult);
+                    }
+                }
+            }
+        }
+        for ((next_pos, next_score, next_step_count), next_mult) in next_batch.into_iter() {
+            queue.push_back((next_pos, next_score, next_step_count, next_mult));
+        }
+    }
+    winning_steps
+}
+
+fn part_2(p1: usize, p2: usize, winning_score: usize) -> usize {
+    let p1_winning_steps = calc_winning_steps(p1, winning_score);
+    let p2_winning_steps = calc_winning_steps(p2, winning_score);
+
+    let mut p1_win_count = 0;
+    for (&p1_step, &p1_step_win_count) in p1_winning_steps.iter() {
+        // p1 moves first, so p2 have only moved p1_step - 1 steps
+        let p2_step_win_count = p2_winning_steps
+            .iter()
+            .filter(|&(p2_step, _)| *p2_step <= p1_step - 1)
+            .map(|(p2_step, p2_count)| {
+                p2_count * 3usize.pow(3).pow(((p1_step - 1) - p2_step) as u32)
+            })
+            .sum::<usize>();
+        let p2_step_lose_count = 3usize.pow(3).pow((p1_step - 1) as u32) - p2_step_win_count;
+        p1_win_count += p1_step_win_count * p2_step_lose_count;
+    }
+
+    let mut p2_win_count = 0;
+    for (&p2_step, &p2_step_win_count) in p2_winning_steps.iter() {
+        // p1 moves first, so p1 have also moved p2_step steps
+        let p1_step_win_count = p1_winning_steps
+            .iter()
+            .filter(|&(p1_step, _)| *p1_step <= p2_step)
+            .map(|(p1_step, p1_count)| p1_count * 3usize.pow(3).pow((p2_step - p1_step) as u32))
+            .sum::<usize>();
+        let p1_step_lose_count = 3usize.pow(3).pow(p2_step as u32) - p1_step_win_count;
+        p2_win_count += p2_step_win_count * p1_step_lose_count;
+    }
+
+    p1_win_count.max(p2_win_count)
+}