From 1b24db05ed43796847389ea94b973c36b6b262d2 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 21 Dec 2021 10:19:29 +0200 Subject: Day 21 part 2 --- src/bin/day_21.rs | 65 ++++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 50 insertions(+), 15 deletions(-) (limited to 'src') diff --git a/src/bin/day_21.rs b/src/bin/day_21.rs index e937bcb..245a0e6 100644 --- a/src/bin/day_21.rs +++ b/src/bin/day_21.rs @@ -1,3 +1,4 @@ +use cached::proc_macro::cached; use nom::{ bytes::complete::tag, character::complete::u32 as nom_u32, @@ -9,27 +10,61 @@ use std::fs; fn main() -> Result<(), Box> { let input = fs::read_to_string("inputs/day_21.txt")?; - let mut player_positions = parse_starting_positions(&input).unwrap().1; - 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; + 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; } - 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 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(( -- cgit v1.2.3