commit 157250a44ceef3a76e553691042ec05e1a593606
parent fa6cebf49b96da9abe265cd82edad874eb56c846
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 16 Apr 2023 12:32:25 -0400
Add day 21 solution
Diffstat:
6 files changed, 260 insertions(+), 0 deletions(-)
diff --git a/src/21/Cargo.toml b/src/21/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "day21"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../common/aoc" }
diff --git a/src/21/input b/src/21/input
@@ -0,0 +1,3 @@
+Player 1 starting position: 7
+Player 2 starting position: 3
+
diff --git a/src/21/part1 b/src/21/part1
@@ -0,0 +1,70 @@
+--- Day 21: Dirac Dice ---
+
+There's not much to do as you slowly descend to the bottom of the ocean. The submarine computer
+challenges you to a nice game of [1m[97mDirac Dice[0m.
+
+This game consists of a single die, two pawns, and a game board with a circular track containing ten
+spaces marked 1 through 10 clockwise. Each player's [1m[97mstarting space[0m is chosen randomly (your puzzle
+input). Player 1 goes first.
+
+Players take turns moving. On each player's turn, the player rolls the die [1m[97mthree times[0m and adds up
+the results. Then, the player moves their pawn that many times [1m[97mforward[0m around the track (that is,
+moving clockwise on spaces in order of increasing value, wrapping back around to 1 after 10). So, if
+a player is on space 7 and they roll 2, 2, and 1, they would move forward 5 times, to spaces 8, 9,
+10, 1, and finally stopping on 2.
+
+After each player moves, they increase their [1m[97mscore[0m by the value of the space their pawn stopped on.
+Players' scores start at 0. So, if the first player starts on space 7 and rolls a total of 5, they
+would stop on space 2 and add 2 to their score (for a total score of 2). The game immediately ends
+as a win for any player whose score reaches [1m[97mat least 1000[0m.
+
+Since the first game is a practice game, the submarine opens a compartment labeled
+[1m[97mdeterministic dice[0m and a 100-sided die falls out. This die always rolls 1 first, then 2, then 3, and
+so on up to 100, after which it starts over at 1 again. Play using this die.
+
+For example, given these starting positions:
+
+Player 1 starting position: 4
+Player 2 starting position: 8
+
+This is how the game would go:
+
+
+ - Player 1 rolls 1+2+3 and moves to space 10 for a total score of 10.
+
+ - Player 2 rolls 4+5+6 and moves to space 3 for a total score of 3.
+
+ - Player 1 rolls 7+8+9 and moves to space 4 for a total score of 14.
+
+ - Player 2 rolls 10+11+12 and moves to space 6 for a total score of 9.
+
+ - Player 1 rolls 13+14+15 and moves to space 6 for a total score of 20.
+
+ - Player 2 rolls 16+17+18 and moves to space 7 for a total score of 16.
+
+ - Player 1 rolls 19+20+21 and moves to space 6 for a total score of 26.
+
+ - Player 2 rolls 22+23+24 and moves to space 6 for a total score of 22.
+
+
+...after many turns...
+
+
+ - Player 2 rolls 82+83+84 and moves to space 6 for a total score of 742.
+
+ - Player 1 rolls 85+86+87 and moves to space 4 for a total score of 990.
+
+ - Player 2 rolls 88+89+90 and moves to space 3 for a total score of 745.
+
+ - Player 1 rolls 91+92+93 and moves to space 10 for a final score, 1000.
+
+
+Since player 1 has at least 1000 points, player 1 wins and the game ends. At this point, the losing
+player had 745 points and the die had been rolled a total of 993 times; 745 * 993 =
+[1m[97m739785[0m.
+
+Play a practice game using the deterministic 100-sided die. The moment either player wins,
+[1m[97mwhat do you get if you multiply the score of the losing player by the number of times the die was
+rolled during the game?[0m
+
+
diff --git a/src/21/part2 b/src/21/part2
@@ -0,0 +1,22 @@
+--- Part Two ---
+
+Now that you're warmed up, it's time to play the real game.
+
+A second compartment opens, this time labeled [1m[97mDirac dice[0m. Out of it falls a single three-sided die.
+
+As you experiment with the die, you feel a little strange. An informational brochure in the
+compartment explains that this is a [1m[97mquantum die[0m: when you roll it, the universe [1m[97msplits into multiple
+copies[0m, one copy for each possible outcome of the die. In this case, rolling the die always splits
+the universe into [1m[97mthree copies[0m: one where the outcome of the roll was 1, one where it was 2, and one
+where it was 3.
+
+The game is played the same as before, although to prevent things from getting too far out of hand,
+the game now ends when either player's score reaches at least [1m[97m21[0m.
+
+Using the same starting positions as in the example above, player 1 wins in
+[1m[97m444356092776315[0m universes, while player 2 merely wins in 341960390180808 universes.
+
+Using your given starting positions, determine every possible outcome. [1m[97mFind the player that wins in
+more universes; in how many universes does that player win?[0m
+
+
diff --git a/src/21/src/main.rs b/src/21/src/main.rs
@@ -0,0 +1,156 @@
+use std::{collections::HashMap, hash::Hash};
+
+#[derive(PartialEq,Eq,Hash,Copy,Clone)]
+enum Turn {
+ P1,
+ P2
+}
+
+#[derive(PartialEq,Eq,Hash,Clone)]
+struct State {
+ p1: usize,
+ p2: usize,
+ s1: usize,
+ s2: usize,
+ turn: Turn
+}
+
+fn parse_input(input: &str) -> (usize, usize) {
+ let mut lines = input.lines();
+ let p1: usize = lines.next().unwrap().split_once(": ").unwrap().1.parse().unwrap();
+ let p2: usize = lines.next().unwrap().split_once(": ").unwrap().1.parse().unwrap();
+ return (p1, p2);
+}
+
+fn roll_det(pos: &mut usize, score: &mut usize, die: &mut usize, rolls: &mut usize) {
+ for _ in 0..3 {
+ *pos = (*pos + *die - 1) % 10 + 1;
+ *die += 1;
+ *rolls += 1;
+ }
+ *score += *pos;
+}
+
+fn roll_dirac(states_in: HashMap<State,usize>) -> (bool,HashMap<State, usize>) {
+ /* advance every possible state until only states exist where
+ * one of the two players has one (score >= 21 is reached)
+ *
+ * could optimize d1 d2 d3 loop by precomputing sum frequency */
+
+ let mut done = true;
+ let mut states = states_in;
+ let mut new_states: HashMap<State, usize> = HashMap::new();
+
+ for (s,c) in &states {
+ if usize::max(s.s1, s.s2) >= 21 {
+ new_states.insert(s.clone(), *c);
+ }
+ }
+
+ for p1 in 1..11 {
+ for p2 in 1..11 {
+ for s1 in 0..21 {
+ for s2 in 0..21 {
+ for turn in vec![Turn::P1,Turn::P2] {
+ let state = State { p1, p2, s1, s2, turn };
+ let res = states.get_mut(&state);
+ if res.is_none() { continue; }
+ let cnt = *res.unwrap();
+ if cnt == 0 { continue; }
+ aoc::debugln!("FOUND {} {} {} {}", p1, p2, s1, s2);
+ done = false;
+ for d1 in 1..4 {
+ for d2 in 1..4 {
+ for d3 in 1..4 {
+ let d = d1 + d2 + d3;
+ let new_state;
+ if turn == Turn::P1 {
+ let np1 = (p1 + d - 1) % 10 + 1;
+ new_state = State {
+ p1: np1, p2,
+ s1: s1 + np1, s2,
+ turn: Turn::P2
+ };
+ } else {
+ let np2 = (p2 + d - 1) % 10 + 1;
+ new_state = State {
+ p1, p2: np2,
+ s1, s2: s2 + np2,
+ turn: Turn::P1
+ };
+ }
+ let res = new_states.get_mut(&new_state);
+ if res.is_some() {
+ *res.unwrap() += cnt;
+ } else {
+ new_states.insert(new_state, cnt);
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
+ aoc::debugln!("ROLL RESULT");
+ for (s,c) in &new_states {
+ aoc::debugln!("{} {} {} {} {} -> {}",
+ s.p1, s.p2, s.s1, s.s2, s.turn == Turn::P1, c);
+ }
+ aoc::debugln!("");
+
+ return (done, new_states);
+}
+
+fn part1(aoc: &mut aoc::Info) {
+ let (mut p1, mut p2) = parse_input(&aoc.input);
+ let (mut s1, mut s2) = (0, 0);
+ let mut die: usize = 1;
+ let mut rolls = 0;
+
+ while s1 < 1000 && s2 < 1000 {
+ roll_det(&mut p1, &mut s1, &mut die, &mut rolls);
+ if s1 >= 1000 { break; }
+ roll_det(&mut p2, &mut s2, &mut die, &mut rolls);
+ }
+
+ let answer = rolls * usize::min(s1, s2);
+ aoc.answer = Some(format!("{}", answer));
+ aoc.solution = Some("551901");
+}
+
+fn part2(aoc: &mut aoc::Info) {
+ let (p1, p2) = parse_input(&aoc.input);
+
+ let mut states: HashMap<State,usize> = HashMap::new();
+ states.insert(State { p1, p2, s1: 0, s2: 0, turn: Turn::P1 }, 1);
+ loop {
+ let (done, new_states) = roll_dirac(states);
+ states = new_states;
+ if done { break; }
+ }
+
+ let mut w1: usize = 0;
+ let mut w2: usize = 0;
+ for (state,cnt) in states {
+ assert!(usize::max(state.s1, state.s2) >= 21);
+ if state.s1 > state.s2 {
+ w1 += cnt;
+ } else {
+ w2 += cnt;
+ }
+ }
+
+ aoc::debugln!("{} vs {}", w1, w2);
+
+ let answer = usize::max(w1, w2);
+ aoc.answer = Some(format!("{}", answer));
+ aoc.solution = Some("272847859601291");
+}
+
+fn main() {
+ aoc::run(part1, part2);
+}
+
diff --git a/src/21/test1 b/src/21/test1
@@ -0,0 +1,2 @@
+Player 1 starting position: 4
+Player 2 starting position: 8
