From a8ebbcb0158ec63efd6e55a0f6335c8ed3362be4 Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Tue, 21 Dec 2021 03:24:08 -0500 Subject: day 21 --- data/2021/21.txt | 2 + src/2021/21/mod.rs | 201 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/2021/mod.rs | 4 ++ 3 files changed, 207 insertions(+) create mode 100644 data/2021/21.txt create mode 100644 src/2021/21/mod.rs diff --git a/data/2021/21.txt b/data/2021/21.txt new file mode 100644 index 0000000..23eac83 --- /dev/null +++ b/data/2021/21.txt @@ -0,0 +1,2 @@ +Player 1 starting position: 9 +Player 2 starting position: 6 diff --git a/src/2021/21/mod.rs b/src/2021/21/mod.rs new file mode 100644 index 0000000..b8c6be9 --- /dev/null +++ b/src/2021/21/mod.rs @@ -0,0 +1,201 @@ +#[derive(Clone)] +pub struct Game { + p1_pos: i64, + p2_pos: i64, + p1_score: i64, + p2_score: i64, + rolls: i64, + die_state: i64, +} + +impl Game { + fn new(p1: i64, p2: i64) -> Self { + Self { + p1_pos: p1, + p2_pos: p2, + p1_score: 0, + p2_score: 0, + rolls: 0, + die_state: 0, + } + } + + fn roll_deterministic(&mut self) -> i64 { + self.die_state += 3; + self.rolls += 3; + self.die_state * 3 - 3 + } + + fn score(&mut self, score: i64, p1: bool) { + if p1 { + self.p1_pos += score; + while self.p1_pos > 10 { + self.p1_pos -= 10; + } + self.p1_score += self.p1_pos; + } else { + self.p2_pos += score; + while self.p2_pos > 10 { + self.p2_pos -= 10; + } + self.p2_score += self.p2_pos; + } + } + + fn value(&self, threshold: i64) -> Option { + if self.p1_score >= threshold { + Some(self.p2_score * self.rolls) + } else if self.p2_score >= threshold { + Some(self.p1_score * self.rolls) + } else { + None + } + } + + fn run_dirac(&self, p1: bool) -> (i64, i64) { + let mut p1_wins = 0; + let mut p2_wins = 0; + { + let mut clone = self.clone(); + clone.score(3, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 1; + } else { + p2_wins += 1; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0; + p2_wins += wins.1; + } + } + { + let mut clone = self.clone(); + clone.score(4, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 3; + } else { + p2_wins += 3; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0 * 3; + p2_wins += wins.1 * 3; + } + } + { + let mut clone = self.clone(); + clone.score(5, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 6; + } else { + p2_wins += 6; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0 * 6; + p2_wins += wins.1 * 6; + } + } + { + let mut clone = self.clone(); + clone.score(6, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 7; + } else { + p2_wins += 7; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0 * 7; + p2_wins += wins.1 * 7; + } + } + { + let mut clone = self.clone(); + clone.score(7, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 6; + } else { + p2_wins += 6; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0 * 6; + p2_wins += wins.1 * 6; + } + } + { + let mut clone = self.clone(); + clone.score(8, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 3; + } else { + p2_wins += 3; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0 * 3; + p2_wins += wins.1 * 3; + } + } + { + let mut clone = self.clone(); + clone.score(9, p1); + if clone.value(21).is_some() { + if p1 { + p1_wins += 1; + } else { + p2_wins += 1; + } + } else { + let wins = clone.run_dirac(!p1); + p1_wins += wins.0; + p2_wins += wins.1; + } + } + (p1_wins, p2_wins) + } +} + +pub fn parse(fh: std::fs::File) -> anyhow::Result { + let mut lines = crate::util::parse::lines(fh); + let p1 = lines + .next() + .unwrap() + .strip_prefix("Player 1 starting position: ") + .unwrap() + .parse() + .unwrap(); + let p2 = lines + .next() + .unwrap() + .strip_prefix("Player 2 starting position: ") + .unwrap() + .parse() + .unwrap(); + Ok(Game::new(p1, p2)) +} + +pub fn part1(mut game: Game) -> anyhow::Result { + let mut p1 = true; + loop { + if let Some(value) = game.value(1000) { + return Ok(value); + } + let score = game.roll_deterministic(); + game.score(score, p1); + p1 = !p1; + } +} + +pub fn part2(game: Game) -> anyhow::Result { + let (p1, p2) = game.run_dirac(true); + Ok(p1.max(p2)) +} diff --git a/src/2021/mod.rs b/src/2021/mod.rs index aee18bd..4c5e1d6 100644 --- a/src/2021/mod.rs +++ b/src/2021/mod.rs @@ -38,6 +38,8 @@ mod day18; mod day19; #[path = "20/mod.rs"] mod day20; +#[path = "21/mod.rs"] +mod day21; // NEXT MOD pub fn run(day: u8, puzzle: u8) -> anyhow::Result { @@ -82,6 +84,8 @@ pub fn run(day: u8, puzzle: u8) -> anyhow::Result { (19, 2) => day19::part2(day19::parse(crate::util::data(2021, 19)?)?), (20, 1) => day20::part1(day20::parse(crate::util::data(2021, 20)?)?), (20, 2) => day20::part2(day20::parse(crate::util::data(2021, 20)?)?), + (21, 1) => day21::part1(day21::parse(crate::util::data(2021, 21)?)?), + (21, 2) => day21::part2(day21::parse(crate::util::data(2021, 21)?)?), // NEXT PART _ => Err(anyhow::anyhow!("unknown puzzle {}-{}", day, puzzle)), } -- cgit v1.2.3-54-g00ecf