Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Splitting Time

Advent of Code 2021 - Day 21

Day 21: Dirac Dice

Useful Links

Concepts and Packages Demonstrated

lru_cacheitertools.productAbstract classABCgeneratormemoization

yieldrecursion

Problem Intro

Okay, we’re going to play a game of Dirac Dice. Part 1 was nice and easy. Part 2 nearly broke my brain.

So, we have two players (each with their own pawn), a single die, and a game board with a circular track. The track contains 10 spaces, marked 1 through 10.

Diract Board

We’re told:

Part 1

We’re given a 100 sided deterministic die. I.e. every roll of the die returns an incrementing number from 1 to 100. When it gets to 100, we go back to 1. The game is won when a player reaches a score of at least 1000.

What is the product of the score of the losing player and the number of times the die was rolled in the game?

This is quite an easy problem, and we get to play with a few new things.

Setup

Some new things here, which we’ll cover as we get to them.

from abc import ABC, abstractmethod
from functools import lru_cache
import logging
import os
import time
from typing import Iterator, NamedTuple
from copy import deepcopy
from itertools import product

SCRIPT_DIR = os.path.dirname(__file__) 
INPUT_FILE = "input/input.txt"
# INPUT_FILE = "input/sample_input.txt"

logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s", 
                    datefmt='%H:%M:%S')
logger = logging.getLogger(__name__)
logger.setLevel(logging.DEBUG)

Solution

First, a class for the players:

class Player(NamedTuple):
    """ A player has a current position on the board, and a cumulative score """
    posn: int
    score: int

This subclasses NamedTuple. It’s a lot like the more powerful Dataclass. It allows us to create a class which is actually a tuple, but where the attributes of the tuple can be referenced by name.

Now we’ll create an abstract class, called AbstractDie:

class AbstractDie(ABC):
    """ Abstract die """
    def __init__(self, faces: int) -> None:
        self._faces = faces
        self._total_rolls = 0   # How many times have we rolled this die
        self._roll_gen = self._roll()   # A generator that performs the roll.
            
    @property
    def total_rolls(self):
        return self._total_rolls
    
    def roll(self):
        """ This is how we roll the die. Calls next() on the roll generator. """
        return next(self._roll_gen)
    
    @abstractmethod
    def _roll(self) -> Iterator[int]:
        """ We need to override this method. """
        return NotImplemented

The concept of an abstract class is that it provides some functionality that we can reuse in subclasses, but the abstract class itself cannot be instantiated. This is because the abstract class has one or more abstract methods, meaning that these methods do not yet have any actual implementation. So when we extend the abstract class, we need to provide an implementation for any abstract methods. In our AbstractDie, we can see that the _roll() method lacks any implementation, and is decorated as @abstractmethod.

Note that our AbstractDie class in inherits from ABC, i.e. the abstract base class. This is what marks our class as abstract.

If we try to do something like this:

die = AbstractDie(faces=100)

Then we’ll get an error like this:

TypeError: Can't instantiate abstract class AbstractDie with abstract method _roll

Other things to note about our AbstractDie:

Now let’s implement our DeterministicDie:

class DeterministicDie(AbstractDie):
    """ Subclass of AbstractDie. Persists state between rolls.
    Always yields an incrementing int from the number of available faces, starting at 1.
    E.g. from 1-100. When we get to the number of faces, we wrap back around to 1. """
    
    def _roll(self) -> Iterator[int]:
        """ Yield the next available number. """
        while True:
            for i in range(1, self._faces+1):
                self._total_rolls += 1
                yield i

Nice and short. This is a subclass of AbstractDie, so we only need to override the abstract method, i.e. the _roll() method. This method yields incrementing values of i (i.e. from 1 to 100), and then wraps back around to 1, by virtue of being in an infinite while True loop. Note the use of the yield keyword here. It works like a return statement, but allows the method execution to continue on the very next method line, when we next call the method. E.g. if i has a value of 50 and we’ve just yielded that value, then when we next call roll(), which in turn calls next() on our _roll() method, then the method will continue within the for loop, setting i to 51.

Now let’s define a class for the Game itself:

class Game():
    """ We're on a circular track, with grid numbers 1 to 10. The player moves around the circle with each go.
    If the player lands on number x, the player gains x points.
    The player starts on an arbitrary grid number, and with a score of 0. """
    SPACES = 10
    ROLLS_PER_TURN = 3    
    
    def __init__(self, players: list[Player], die: AbstractDie, target: int) -> None:
        self._players = players  # Our two players.
        self._die = die          # Our die may be deterministic, so we need to store die state
        self._target = target    # The score a player needs to reach, to win the game    
    
    @property
    def players(self):
        return self._players
    
    @property
    def die(self):
        return self._die
    
    def play(self) -> int:
        """ Play a game. Each player takes a turn, until the target score is reached by a player. """
        while True:
            for player_num in range(len(self.players)):
                score = self._take_turn(player_num)
                if score >= self._target:   # This player has won!
                    return player_num
        
        assert False, "Game should end!"
        
    def _take_turn(self, player_num: int) -> int:
        """ Takes a turn for this player.  Roll the die n (e.g. 3) times, to give score x.
        Then move around the circle x places.  Whatever we land on, that's the score returned.
        Add this to existing score. Update the player.  Returns the cumulative score of the player """

        old_posn, old_total = self.players[player_num] # unpack the player
        
        die_score = sum(self._die.roll() for i in range(Game.ROLLS_PER_TURN)) # Roll n times
        new_posn = (((old_posn + die_score)-1) % Game.SPACES) + 1 # Move forward n spaces
        new_total = old_total + new_posn  # Add new board position to existing player score
        self.players[player_num] = Player(new_posn, new_total)  # Update the player
        
        return new_total

When we create a new Game, we pass in a list of players (there will be two), a die instance (which will be a subclass of AbstractDie), and the score we need to reach, for the game to end.

After initialisation, the game is played by calling play() on our Game instance.

The _take_turn() method:

Finally, we run it:

    input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
    with open(input_file, mode="rt") as f:
        data = f.read().splitlines()

    init_players: list[Player] = []
    for line in data:
        tokens = line.split() # Into 5 tokens, e.g. "Player" "1" "starting" "position:" "4"
        init_players.append(Player(posn=int(tokens[-1]), score=0))
    
    # Part 1
    players = deepcopy(init_players)
    die = DeterministicDie(faces=100)
    game = Game(players, die, target=1000)
    won = game.play()
    
    total_rolls = game.die.total_rolls
    logger.info("Die has been rolled %d times", total_rolls)
    logger.info("Player %d won with score of: %d", won+1, players[won].score)
    logger.info("Part 1 result = %d\n", total_rolls * min(player.score for player in game.players))

This is what we’re doing here:

So, Part 1 was pretty easy!

Part 2

Well, this escalated quickly!

We now only have a 3-sided die. It’s just as well. It’s a quantum die. Every roll of the die splits the universe into three different universes: one for each of the possible roll outcomes!

To win, we only need to reach a score of 21.

Our objective:

Find the player that wins in more universes; in how many universes does that player win?

OMG.

Let’s consider Player 1’s first turn. On the first roll, we generate 3 universes, with roll values of 1, 2 and 3. On roll 2, each of those universes splits into 3 more universes. And on roll 3, each of those universes splits into 3 more universes!! Thus, 3 rolls gives us 33 = 27 different universes per turn:

Roll 1                1                 2                 3
Roll 2          1     2     3     1     2     3     1     2     3
Roll 3        1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3

Sum           3 4 5 4 5 6 5 6 7 4 5 6 5 6 7 6 7 8 5 6 7 6 7 8 7 8 9

To determine the 27 different different sums that are achievable from our 3 rolls programmatically, we can use a cartesian product:

TRIPLE_ROLL_SUMS = [sum(score) for score in product(range(1, 4), repeat=3)] 

Here, we’re using another handy utility from the itertools package. This is asking for the cartesian product of (1, 2, 3)(1, 2, 3)(1, 2, 3). It’s a shorthand for doing a nested for loop 3 times.

The result is:

[3, 4, 5, 4, 5, 6, 5, 6, 7, 4, 5, 6, 5, 6, 7, 6, 7, 8, 5, 6, 7, 6, 7, 8, 7, 8, 9]

Great. Those are the different 3-roll die sums for the 27 different universes of the first move of the game. If player 2 now takes their turn, they have 27 different universes that follow each of the universes created by player 1. Thus, with two turns, we have 27*27 = 729 universes. After three turns, there are nearly 20000 universes. After four turns, half a million universes. After 5 turns, 14 million universes. You can see that this is going to get rapidly out of hand.

In theory, if both players were only ever rolling a score of 1 with their die, you could envisage a game that takes 14 turns to finish (i.e. 7 turns each, with each turn having a cumulative roll score of 3). That would result in 109418989131512359209 universes. Way too many to process!

So, what’s our game plan?

Clearly we can’t simulate every possible universe. The solution space is just too large. But it turns out there aren’t that many different game states. And from any given game state, we just need to work out how many ways there are to win from that state. But what is a game state?

A game state is represented by:

Thus, we have 10*10*21*21 = 44100 game states. That means only 44100 unique universes from which a player can win. Clearly, there are a lot more possible universes than that. But it doesn’t matter, since we can cache game states we’ve seen before, and whenever we see a previous game state, we know exactly how many ways there are to win from that game state.

So now we can solve using recursion. Recall from Day 14 that to implement recursion, we need:

We’ll create a function that determines how many ways each player can win from the current game state. This is called count_wins().

So what’s our base case? This is the case where we’ve reached our goal, and the function should exit. We’ve reached our goal when either player has won. Either player has won when their score is >= 21. So if Player A has >= 21, then there is 1 way that Player A can win, and 0 ways that Player B can win. (Since Player A has won.) And if Player B has >= 21, there is 1 way that Player B can win, and 0 ways that Plaer A can win.

In all other cases, we want to determine our 27 different triple roll outcomes possible for this player, move the player the appropriate number of spaces, and update the player’s score; thus creating a new game state. Then we recurse into our function with this new game state. But crucially, when we recurse, we swap the player A and player B positions as parameters to the function call, since if Player A took the last turn, then Player B needs to take this turn.

@lru_cache(maxsize=None)    
def count_wins(posn_a: int, posn_b: int, score_a: int, score_b: int) -> tuple[int, int]:
    """ Return number of universes in which each player can win from this state.
    With a given game state, player a starts at posn_a with score_a and player b at posn_b with score_b.
    Player a's turn.

    Returns:
        tuple[int, int]: (Ways to win for player a, ways to win for player b)
    """
    if score_a >= 21:
        return (1, 0)   # Player A has won; player B has lost. No other options are possible.
    
    if score_b >= 21:
        return (0, 1)   # Player B has won; player A has lost. No other options are possible.
    
    wins_a = wins_b = 0  # Initialise; no wins yet
    
    # Perform the triple roll to get a new game state, and then handover to other player to take their turn
    for score in TRIPLE_ROLL_SUMS:  # 27 differnet recursions for this turn
        new_posn_a = (posn_a + score - 1) % Game.SPACES + 1     # move player
        new_score_a = score_a + new_posn_a                      # update player score
        
        # Now recurse. Next move is from player b. So, next call will return (ways b, ways a).
        wins_b_from_here, wins_a_from_here = count_wins(posn_b, new_posn_a, score_b, new_score_a)
        wins_a += wins_a_from_here
        wins_b += wins_b_from_here
        
    return wins_a, wins_b

The last point to note is the addition of the decorator @lru_cache(). This implements a least recently used cache, such that when the function is given a set of parameters that have been used before (i.e. a previously seen game state), then the function returns the same result as it did before, without actually doing any work. Thus, the function is caching previously seen states, including all the recursions that a given state would have needed to process. We pass maxsize=None to the @lru_cache() decorator, such that there’s no limit on the number of parameter permutations that are cached.

This combination of recursion, combined with caching the results of a call we’ve seen before, is called memoization.

We call the code, as follows:

   # Part 2
    # With a given game state, player_1 starts at posn_1 with score_1and player_2 at posn_2 with score_2.
    # How many ways can they win from this state?
    players = deepcopy(init_players)
    wins = count_wins(players[0].posn, players[1].posn, players[0].score, players[1].score)
    for i, win in enumerate(wins):
        logger.info("Player %d wins: %d", i+1, win)
        
    logger.info("Part 2: universes in which the player wins the most = %d", max(wins))

And the output looks like this:

21:57:08.588:INFO:__main__:     Die has been rolled 861 times
21:57:08.590:INFO:__main__:     Player 1 won with score of: 1008
21:57:08.590:INFO:__main__:     Part 1 result = 684495

21:57:08.799:INFO:__main__:     Player 1 wins: 138289532619163
21:57:08.799:INFO:__main__:     Player 2 wins: 152587196649184
21:57:08.799:INFO:__main__:     Part 2: universes in which the player wins the most = 152587196649184    
21:57:08.799:INFO:__main__:     Execution time: 0.2135 seconds

Wow, that’s a lot of universes!