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 Dirac Dice.
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 starting space is chosen randomly (your puzzle input). Player 1 goes first.
Players take turns moving. On each player's turn, the player rolls the die three times and adds up the results. Then, the player moves their pawn that many times forward 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 score 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 at least 1000.
Since the first game is a practice game, the submarine opens a compartment labeled deterministic dice 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 = 739785.
Play a practice game using the deterministic 100-sided die. The moment either player wins, what do you get if you multiply the score of the losing player by the number of times the die was rolled during the game?
# Python imports
from functools import lru_cache
from itertools import combinations, permutations
from pathlib import Path
from typing import Callable, Dict, Generator, Iterable, List, Optional, Set, Tuple
import numpy as np
# Paths to data
testpath = Path("day21_test.txt")
datapath = Path("day21_data.txt")
def load_input(fpath: Path) -> Tuple[Dict[int,int], np.array]:
"""Return the game start positions
:param fpath: Path to data file
"""
with fpath.open("r") as ifh:
p1_start = int(ifh.readline().strip().split()[-1])
p2_start = int(ifh.readline().strip().split()[-1])
return p1_start, p2_start
We can approach this with a prett straight-ahead function that plays the game until there's a winner:
def play(p1_start, p2_start, die_size=100, board_size=10, end_score=1000):
p1_pos, p2_pos = p1_start % board_size, p2_start % board_size
p1_score, p2_score = 0, 0
die_roll_count, die_state = 0, 0
while True:
# P1 move
# Roll die x3
die_rolls = (die_state + np.array([1, 2, 3])) % die_size
die_roll_count += 3
die_state = die_rolls[-1]
# Move
p1_pos = (p1_pos + die_rolls.sum()) % board_size
# Increment score
if p1_pos == 0: # we're doing mod10 so need this
p1_score += 10
p1_score += p1_pos
if p1_score >= end_score:
break
# P2 move
# Roll die x3
die_rolls = (die_state + np.array([1, 2, 3])) % die_size
die_roll_count += 3
die_state = die_rolls[-1]
# Move
p2_pos = (p2_pos + die_rolls.sum()) % board_size
# Increment score
if p2_pos == 0: # we're doing mod10 so need this
p2_score += 10
p2_score += p2_pos
if p2_score >= end_score:
break
return die_roll_count, min(p1_score, p2_score)
This looks to give the correct answer for our example:
p1_start, p2_start = load_input(testpath)
print(f"{np.prod(play(p1_start, p2_start))=}")
np.prod(play(p1_start, p2_start))=739785
And with our puzzle data, we have:
p1_start, p2_start = load_input(datapath)
print(f"{np.prod(play(p1_start, p2_start))=}")
np.prod(play(p1_start, p2_start))=720750
Now that you're warmed up, it's time to play the real game.
A second compartment opens, this time labeled Dirac dice. 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 quantum die: when you roll it, the universe splits into multiple copies, one copy for each possible outcome of the die. In this case, rolling the die always splits the universe into three copies: 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 h}and, the game now ends when either player's score reaches at least 21.
Using the same starting positions as in the example above, player 1 wins in 444356092776315 universes, while player 2 merely wins in 341960390180808 universes.
Using your given starting positions, determine every possible outcome. Find the player that wins in more universes; in how many universes does that player win?
This is very different from the first problem and caused me all kinds of headaches! Not least - again - understanding the way the question was phrased.
So, on each turn, a player rolls the Dirac die three times, resulting in a total roll in:
3: {(1, 1, 1)}, [1]
4: {(1, 1, 2),(1, 2, 1),(2, 1, 1)}, [3]
5: {(1, 1, 3),(1, 2, 2),(1, 3, 1),(2, 1, 2),(2, 2, 1),(3, 1, 1)}, [6]
6: {(1, 2, 3),(1, 3, 2),(2, 1, 3),(2, 2, 2),(2, 3, 1),(3, 1, 2),(3, 2, 1)}, [7]
7: {(1, 3, 3),(2, 2, 3),(2, 3, 2),(3, 1, 3),(3, 2, 2),(3, 3, 1)}, [6]
8: {(2, 3, 3), (3, 2, 3), (3, 3, 2)}, [3]
9: {(3, 3, 3)} [1]
leading to 27 universes spawned on each turn. For each universe, the other player spawns another 27 universes, and so on.
Using the frequencies (in square brackets above), we need only account for one universe per sum of rolls - but we need to keep a count of the number of such universes.
We approach this with a recursive function and, because of the extremely large number of universes/calculations implied in the text above, we want to make sure that, for a given set of input values, we've cached the appropriate outputs.
We consider one player at a time, taking care to consider the "current player" (active) and "other player" (passive). The end-state for the recursion is a "win" for the "other player" before the current player even starts, so we first determine if the other player has won and, if so, return (0, 1) as "current player wins, other player wins" (we need to maintain this form so that we pass up both win counts as the recursion proceeds). If the other player has not won, we consider every roll for the current player and recurse the function.
When recursing, we pass down the player positions and scores, taking care to swap the current/other player. So, at the first iteration, "current" is P1, "other" is P2; P2 can't win immediately, so we consider all rolls for P1 and recurse the function with "current" as P2 and "other" as P1.
# (Sum of) roll frequencies - see above
freqdict = {3:1, 4:3, 5:6, 6:7, 7:6, 8:3, 9:1}
@lru_cache(maxsize=None)
def play_dirac(cur_player_pos, other_player_pos, cur_player_score, other_player_score):
# Return a winner if either player scored >= 21
if other_player_score >= 21:
return 0, 1 # the other player wins before the current player rolls
# We don't have a winner, so current player rolls
# So far we don't know how many wins there are downstream
# of this state, so set total wins for each player here to 0
cur_player_tot_wins, other_player_tot_wins = 0, 0
# We know that the current state will result in 27 universes for
# the current player, on the next roll, but we need only consider
# the possible roll sums, and multiply the wins by their frequency
for roll, count in freqdict.items():
new_cur_player_pos = (cur_player_pos + roll) % 10
if new_cur_player_pos == 0: # we're doing mod10 so need this
new_cur_player_score = cur_player_score + 10
else:
new_cur_player_score = cur_player_score + new_cur_player_pos
# Play next round (swap players)
other_player_win, cur_player_win = play_dirac(other_player_pos,
new_cur_player_pos,
other_player_score,
new_cur_player_score)
# Update win counts
cur_player_tot_wins += cur_player_win * count
other_player_tot_wins += other_player_win * count
# Return total win count for each player
return cur_player_tot_wins, other_player_tot_wins
Trying this on the example data:
p1_start, p2_start = load_input(testpath)
print(f"Most wins: {max(play_dirac(p1_start, p2_start, 0, 0))=}")
Most wins: max(play_dirac(p1_start, p2_start, 0, 0))=444356092776315
And with the puzzle data:
p1_start, p2_start = load_input(datapath)
print(f"Most wins: {max(play_dirac(p1_start, p2_start, 0, 0))=}")
Most wins: max(play_dirac(p1_start, p2_start, 0, 0))=275067741811212