day 21

3 files changed, 207 insertions, 0 deletions

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<i64> {
+        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<Game> {
+    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<i64> {
+    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<i64> {
+    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<i64> {
@@ -82,6 +84,8 @@ pub fn run(day: u8, puzzle: u8) -> anyhow::Result<i64> {
         (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)),
     }