Dirac Dice

Advent of Code 2021 Day 21

In Part 1, solve for X where X equals...

• A product of two numbers: the score of the losing player, and the number of times the die was rolled during the game

Meaning X must be:

• A positive integer

That's our output. What's our input?

• A multi-line string. Two lines, to be exact.
• Each line follows this pattern: Player X starting position: N

What does our input represent?

• The starting position for each of two players

Players, you say? How the game is played?

• Each player rolls a die three times
• The rolls are predictable: three continuous numbers, starting from 1, not exceeding 100
• Based on the sum of all three rolls, the player move their pawn that many times repeating around a circular game board with 10 locations
• The player's score at the end of each turn equals the sum of their previous score and the location their pawn lands on
• The first player to reach or surpass a score of 1000 wins

My working algorithm to solve Part 1

Use String mutation methods to extract each player's starting position
Initialize both player's scores to 0
Create an array of three values to keep a running tracker of the next three die rolls
Create a tracker for the number of rolls
Declare a win condition at 1000

While both players' scores are less than 1000
  If the rolls tracker is odd
    Then update player 1's position
      Calculate the sum of: the current position and the sum of each value in tracker of upcoming die rolls...
      Calculate the remainder of that sum when divided by 10
      Update player 1's score to the sum of the current score and the new position
  Else do the same but for player 2
  Increment the number of rolls by 3
  Increment each value in the die roll tracker by 3

Return the product of the lesser of both scores and the rolls tracker value minus 1 (it was initialized to 1 only to make the odd-even condition work correctly above)

This generated a correct answer.
But it is far from eloquent or efficient by any means.

Here is an eloquent solution - to both parts, in fact - that taught me some great programming techniques by Python solver Topaz

Part 1 of their solution is described below. It amounts to 10 lines of surprisingly understandable and efficient code.

Setup four variables:
1. Array: Forego parsing the input, just store both positions - minus 1 each to account for zero-based positioning - as two values in an array
2. Array: Store both players' initial scores as two values in an array
3. Integer: Track the number of rolls, starting from 1
4. Integer: Track the currently moving player as a number that will toggle between 0 and 1. It should start at 1 so that the first moving player is player 1, represented as 0.

While the score of the player who moved last is less than 1000
  Switch players by updating the current player tracker to equal the difference of 1 and its current value, effectively toggling between 0 and 1
  Update the current player's position by calculating the sum of their current position, and the outcome of this equation: multiply the rolls tracker's current value by 3, and add 3; lastly, calculate the remainder after dividing the sum by 10
  Update the current player's score by adding to it their new position, plus 1 (accounting for minus 1 done to account for zero-indexed positioning)
  Increment the rolls tracker by 3

Return the product of the lesser of both values in the scores array and the value in the rolls tracker, minus 1 (representing the prior roll)

What I learned from Topaz's eloquent code

• The trick of n*x+x: 1 + 2 + 3 == 1 * 3 + 3 and 4 + 5 + 6 == 4 * 3 + 3
• The trick of p = 1; p = 1 - p: p is 1, 0, 1, 0...
• Storing the players' positions and scores as 2-value arrays instead of four separate variables

It was rewarding to comprehend Topaz's code, translate it into JavaScript code, and run it to reveal the same correct answer my inferior code generated.

Visualizing Part 1's solution

I created a website where you can play the game and better understand Part 1's algorithm

Visit this repl.it to try the demo and explore the website's code

Part 2 was a whole different ball game

Solve for X where X equals...

• The total universes in which the player with the most wins won

Woah. What's this about universes?

• The game has changed significantly
• Same: Each player gets three rolls per term
• Different: the winning score is 21
• Different: The die only has three values: 1, 2, 3
• Difficult: Each of the three rolls creates a universe where the face landed on 1, on 2, and on 3

The programmer's dilemma

• Fully explore each roll's branching outcomes
• Determine which player wins each game in all of the generated universes
• Tally up each win: a number likely in the degree of 1 with 14 zeros

I had no clue where to start. But I had Topaz's algorithm for Part 2.

• Luckily, it is only 8 lines of code
• Time to study closely, analyze, and simulate
• I'll save that for another day - maybe tomorrow, maybe a while from now