Advent of Code - 2021
This is a solution to Day 21 of Advent of Code 2021.
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 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: 8This 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.
Read input
Today's input is simple: two lines that look like this:
Player 2 starting position: 4
We're only really interested in the second number on each line: the starting position. Using regex to find all numbers and then taking the second one. We create a namedtuple for Player and read our inputs into a list of Players.
Then we create a game state with two players, a and b (because 1 and 2 are not valid identifiers), a counter for how many times the die has been rolled and who's turn it will be next.
from collections import namedtuple
import re
from utils import read_input
Player = namedtuple('Player', ["position", "score"])
GameState = namedtuple('GameState', ['a', 'b', 'die_rolled', 'turn'])
def transformer(line):
starting_position = re.findall(r'\d', line)[1]
return Player(position=int(starting_position), score=0)
players = read_input(21, transformer)
game = GameState(
a = players[0],
b = players[1],
die_rolled = 0,
turn = 0
)
Part 1
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?
Let's start by building our die. The practice die counts from 1 to 100 and then loops over.
A Python generator function is great for this. By combining while True loop and yield keyword, we can create an infinite generator that will gives us our next roll when called next on.
Since calling next on a die is not thematic, I also built a helper funciton roll(die) to make it clear that is what we are doing. Wrapping function calls into other function calls is sometimes a good way to create a clearer API for your application, even if it just changes the name of the function being called. Here roll makes much more sense when read through than next.
def deterministic_d100():
roll = 0
while True:
yield roll % 100 + 1
roll += 1
def roll(die):
return next(die)
Next, our gameplay loop. Each turn consists of a player rolling three times, seeing where they land an calculating a score.
To calculate the new position on a board that loops over after 10, I take the last digit of the resulting position and if it's 0, set the position to 10.
def play_a_turn(player, die):
position = player.position
for _ in range(3):
roll = next(die)
position += roll
if position > 10:
position = int(str(position)[-1])
if position == 0:
position = 10
score = player.score + position
return position, score
To play a full game, we start by creating our deterministic D100 die.
Then we play until either player scores 1000 points.
def play_game(game_state):
die = deterministic_d100()
while game_state.a.score < 1000 and game_state.b.score < 1000:
player = game_state[game_state.turn % 2]
new_pos, new_score = play_a_turn(player, die)
if game_state.turn == 0:
game_state = GameState(
a = Player(new_pos, new_score),
b = game_state.b,
die_rolled = game_state.die_rolled + 3,
turn = 1
)
else:
game_state = GameState(
a = game_state.a,
b = Player(new_pos, new_score),
die_rolled = game_state.die_rolled + 3,
turn = 0
)
return game_state
Score for the puzzle is lower of the two scores multiplied by how many times the die was rolled.
def score(game_state):
loser = min([game_state.a, game_state.b], key=lambda player: player.score)
return loser.score * game_state.die_rolled
end_state = play_game(game)
res = score(end_state)
print(f'Solution: {res}')
assert res == 998088 # For refactoring
Solution: 998088
Part 2
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 hand, 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
444356092776315universes, while player 2 merely wins in341960390180808universes.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?
It's time to build some trees again. I was mostly disappointed that I didn't get to build a new die for this one, I built the original one as a generator with hopes that building a more complex die was gonna play a role in this second part.
Instead, we got multiverse puzzle and lots and lots of die rolling.
Few helpers to get started.
Game can only finish after each 3 rolls since that's when the new score is counted. For the game played in part 2, the score to get is 21 (I originally forgot that part, turns out playing to 1000 is quite a lot).
def is_over(game):
return game.die_rolled % 3 == 0 and (game.a.score >= 21 or game.b.score >= 21)
def did_player_a_win(game):
return game.a.score > game.b.score
Main loop of the game is quite similarly implemented as in part 1 but instead of us rolling three times in a row, we only roll once because after each roll, more universes must be created.
So player moves according to their roll, counts new position and score and if it was their third roll, give the turn to the other player.
def advance(game, roll):
player = game[game.turn % 2]
new_position = player.position + roll
if new_position > 10:
new_position = int(str(new_position)[-1])
if new_position == 0:
new_position = 10
new_score = player.score
next_turn = game.turn
if (game.die_rolled + 1) % 3 == 0: # Switch turns after 3 rolls
new_score = player.score + new_position
next_turn = 1 if game.turn == 0 else 0
if game.turn == 0:
return GameState(
a=Player(new_position, new_score),
b=game.b,
die_rolled=game.die_rolled+1,
turn=next_turn
)
else:
return GameState(
a=game.a,
b=Player(new_position, new_score),
die_rolled=game.die_rolled+1,
turn=next_turn
)
Erno taught me about functools.cache today which helps with performance. It required me to rewrite my game state logic from a non-hashable dictionary into a hashable tuple (which in turn also helped make my code much cleaner).
If I run my play function without a cache, it takes a long, long time to run (I stopped waiting after a few minutes). With @cache decorator, it takes 12 seconds.
What @cache does, is that it takes a look at the input (in our case, the game state) and sees if that exact game state has already been encountered and if so, it will use the value of that previously saved called.
from functools import cache
@cache
def play(game_state):
if is_over(game_state):
if did_player_a_win(game_state):
return [1, 0]
else:
return [0, 1]
wins = [0, 0]
for roll in [1,2,3]:
next_game_state = game_state
next_game_state = advance(next_game_state, roll)
new_wins = play(next_game_state)
for idx, win in enumerate(new_wins):
wins[idx] += win
return wins
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?
We calculate all the wins and find the larger one.
wins = play(game)
result = max(wins)
print(f'Solution: {result}')
assert result == 306621346123766
Solution: 306621346123766