1 files changed, 76 insertions, 0 deletions
diff --git a/2021/src/bin/day_21.rs b/2021/src/bin/day_21.rs
new file mode 100644
index 0000000..245a0e6
--- /dev/null
+++ b/2021/src/bin/day_21.rs
@@ -0,0 +1,76 @@
+use cached::proc_macro::cached;
+use nom::{
+    bytes::complete::tag,
+    character::complete::u32 as nom_u32,
+    combinator::map,
+    sequence::{preceded, tuple},
+    IResult,
+};
+use std::fs;
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_21.txt")?;
+    let player_positions = parse_starting_positions(&input).unwrap().1;
+    {
+        let mut player_positions = player_positions.clone();
+        let mut player_scores = [0, 0];
+        let mut dice = (1..=100).cycle().enumerate().peekable();
+        let mut player_turn = 0;
+        while player_scores[0] < 1000 && player_scores[1] < 1000 {
+            let dice_roll: u32 = dice.by_ref().take(3).map(|(_, roll)| roll).sum();
+            player_positions[player_turn] = (player_positions[player_turn] + dice_roll) % 10;
+            if player_positions[player_turn] == 0 {
+                player_positions[player_turn] = 10;
+            }
+            player_scores[player_turn] += player_positions[player_turn];
+            player_turn = (player_turn + 1) % 2;
+        }
+        let losing_score = player_scores.iter().min().cloned().unwrap_or(0);
+        let dice_roll_count = dice.peek().unwrap().0;
+        dbg!((losing_score, dice_roll_count));
+        dbg!(losing_score * dice_roll_count as u32);
+    }
+
+    let win_counts = player_win_counts(player_positions, [0, 0]);
+    dbg!(win_counts);
+    dbg!(win_counts.into_iter().max().unwrap_or(0));
+    Ok(())
+}
+
+#[cached]
+fn player_win_counts(player_positions: [u32; 2], player_scores: [u32; 2]) -> [u64; 2] {
+    let mut win_counts = [0; 2];
+    for dice_roll_1 in 1..=3 {
+        for dice_roll_2 in 1..=3 {
+            for dice_roll_3 in 1..=3 {
+                let dice_roll = dice_roll_1 + dice_roll_2 + dice_roll_3;
+                let mut new_position = (player_positions[0] + dice_roll) % 10;
+                if new_position == 0 {
+                    new_position = 10;
+                }
+                let new_score = player_scores[0] + new_position;
+                if new_score >= 21 {
+                    win_counts[0] += 1;
+                } else {
+                    let recursive_wins = player_win_counts(
+                        [player_positions[1], new_position],
+                        [player_scores[1], new_score],
+                    );
+                    win_counts[0] += recursive_wins[1];
+                    win_counts[1] += recursive_wins[0];
+                }
+            }
+        }
+    }
+    win_counts
+}
+
+fn parse_starting_positions(input: &str) -> IResult<&str, [u32; 2]> {
+    map(
+        tuple((
+            preceded(tag("Player 1 starting position: "), nom_u32),
+            preceded(tag("\nPlayer 2 starting position: "), nom_u32),
+        )),
+        |(a, b)| [a, b],
+    )(input)
+}