AoC 2021 Day 21: Dicinator

Source: Dirac Dice

Part 1: Play a simple game (describe below) with a loaded D100 (that always rolls 1, 2, 3, … 99, 100, 1, …). Return the score of the losing player times the number of times the die was rolled.

  • The board has a circle of 10 squares, numbered 1-10
  • The player pieces start on given squares
  • Each turn, roll 3 dice, advance the sum of the three many spaces (wrapping around)
  • Score points equal to the square you land on
  • The first player to score >= 1000 wins

This is not a hard problem, so I’m going to dramatically overengineer it.

Die = Generator[int, None, None]

def LoadedDie(sides: int) -> Die:
    while True:
        for i in range(sides):
            yield i + 1

class Game:
    '''Reprents a weird/simple game.'''

    die: Die
    size: int
    target: int

    current: int
    players: List[int]
    scores: List[int]

    roll_count: int

    def __init__(
            die: Die,
            size: Optional[int] = 10,
            target: Optional[int] = 1000,
            number_of_players: Optional[int] = 2,
            initial_spots: Optional[List[int]] = None,
        '''Create a game with various defaults.'''

        if number_of_players is None:
            number_of_players = 2

        self.die = die
        self.size = size or 10 = target or 1000
        self.current = 0
        self.players = initial_spots or [0 for i in range(number_of_players)]
        self.scores = [0 for i in range(number_of_players)]
        self.roll_count = 0

        if not number_of_players == len(self.players):
            raise Exception('If both number of players and initial spots are provided, they must match')

    def winner(self) -> Optional[int]:
        '''Return the current winner (or None if no winner)'''

        for i, score in enumerate(self.scores):
            if score >=
                return i + 1

        return None

    def update(self):
        '''Plays one round.'''

        if self.winner():
  'Cannot update, game is already over')

        self.roll_count += 3
        rolls = [next(self.die), next(self.die), next(self.die)]
        new_space = self.players[self.current] + sum(rolls)
        while new_space > self.size:
            new_space -= self.size

        self.players[self.current] = new_space
        self.scores[self.current] += new_space'''\
Player {self.current+1} rolls {rolls} \
and moves to space {self.players[self.current]} \
for a total score of {self.scores[self.current]}.\

        self.current = (self.current + 1) % len(self.players)

Now with any user supplied die, any size board, any number of players, and any target score! I think the most interesting thing was the LoadedDie generator. Any generator will work though.

Wrap that in the problem statement:

def part1(file: typer.FileText):

    p1 = int(file.readline().split()[-1])
    p2 = int(file.readline().split()[-1])

    game = Game(die=LoadedDie(100), initial_spots=[p1, p2])

    while not game.winner():

    winning_player = game.winner()

        winning_player, 'wins,',
        game.scores[1 if winning_player == 1 else 0] * game.roll_count

And we’re golden:

$ python3 part1 input.txt
1 wins, 752247
# time 45107958ns / 0.05s

Part 2: Instead of the loaded die, you have a 3-sided quantum Dirac Die. Every time it rolls, split into 3 universes (rolling a 1, 2, or 3). Changing the target score to only 21, calculate the number of universes in which the player who wins more matches wins.

Yeah… all of the code I wrote for the first time? Throw it out.

Instead, I’m going to maintain a current state map with the (player number, location of 1, score of 1, location of 2, score of 2) mapped to the number of games that got to this state. That way, each time we advance a turn, we can regenerate that map and multiply the number of ways we got to that state times the number of ways (out of 27) we can advance. Make sense?

def part2(file: typer.FileText):

    location1 = int(file.readline().split()[-1])
    location2 = int(file.readline().split()[-1])

    # State is a mapping of (current player, p1 location, p1 score, p2 location, p2 score): count
    state = {
        (1, location1, 0, location2, 0): 1

    # Rolls are the number (out of 27) of each possible roll we could see
    rolls: MutableMapping[int, int] = {}
    for i in range(1, 4):
        for j in range(1, 4):
            for k in range(1, 4):
                sum = i + j + k

                if sum in rolls:
                    rolls[sum] += 1
                    rolls[sum] = 1

    # Wins is the number of times each player has won
    wins = [0, 0, 0]

    # Advance the state of all possible simulations until every one is finished
    # Since we'll always advance at least 3, this will take a maximum of 7 plays for each player (14 total rounds)
    while state:'{state=}, {wins=}')
        next_state = {}

        # Unpack all of the current states
        for (player, location1, score1, location2, score2), current_count in state.items():
            # Try every possible combination of rolls of the dice
            for roll, new_count in rolls.items():
                # Make sure we're working on the correct player
                (location, score) = (location1, score1) if player == 1 else (location2, score2)

                # Update that player's location and score
                new_location = location + roll
                while new_location > 10:
                    new_location -= 10

                score += new_location

                # If the score is >= 21, don't add those possibilities back into the state space
                # Instead, increment number of wins by the ways we got here (current_count) times the ways to advance (new_count)
                if score >= 21:
                    wins[player] += current_count * new_count

                # If we didn't win, calculate the new index into the state variable
                # This basically means swapping the player and updating either location1,score1 or location2,score2
                new_index = (
                    2 if player == 1 else 1,
                    new_location if player == 1 else location1,
                    score if player == 1 else score1,
                    new_location if player == 2 else location2,
                    score if player == 2 else score2

                # Update the counts in the next state by the ways we got here (current_count) times the ways to advance (new_count)
                if new_index not in next_state:
                    next_state[new_index] = 0
                next_state[new_index] += current_count * new_count

        state = next_state'Final {state=}, {wins=}')

It’s… pretty crazy, but I think it makes sense to me at least. And it works!

$ python3 part2 input.txt
# time 181642208ns / 0.18s

They won 221 TRILLION times. Go them!