Advent of Code 2021 Day 21: Dirac Dice

By Andreas Røssland

https://adventofcode.com/2021/day/21 https://github.com/roessland/advent-of-code

Today’s problem is to simulate a dice game.

Part 1: Simple simulation

The first part is pretty straight forward and serves as an introduction to the rules of the game.

package main  
  
import (  
   "fmt"  
   "github.com/roessland/gopkg/mathutil")  
  
type Die struct {  
   prevRoll int  
}  
  
func (d *Die) Roll() int {  
   d.prevRoll++  
   return d.prevRoll  
}  
  
type Game struct {  
   timesRolled int  
   positions   [2]int  
   scores      [2]int  
   numSpaces   int  
   prevPlayer  int  
   die         *Die  
}  
  
func (g *Game) DoTurn() {  
   g.prevPlayer = (g.prevPlayer + 1) % 2  
   currPlayer := g.prevPlayer  
   pos := g.positions[currPlayer]  
   g.timesRolled += 3  
   roll := g.die.Roll() + g.die.Roll() + g.die.Roll()  
   pos = ((pos-1)+roll)%g.numSpaces + 1  
   g.positions[currPlayer] = pos  
   g.scores[currPlayer] += pos  
}  
  
func main() {  
   game := Game{  
      timesRolled: 0,  
      positions:   [2]int{4, 3},  
      numSpaces:   10,  
      die:         &Die{},  
      prevPlayer:  1,  
   }  
  
   for i := 0; i < 5000; i++ {  
  
      game.DoTurn()  
  
      if game.scores[0] >= 1000 {  
         fmt.Println("player 1 won")  
         break  
      }  
      if game.scores[1] >= 1000 {  
         fmt.Println("player 2 won")  
         break  
      }  
   }  
  
   fmt.Printf("%#v\n", game)  
   fmt.Println(game.timesRolled * mathutil.MinInt(game.scores[0], game.scores[1]))  
}

Part 2: Dirac Dice

After each player’s turn the number of universes multiply by 3^3 = 27.

The possible dice rolls, and the number of universes where that roll occurs are:

$r_i$ (sum of rolls)$c_i$ (frequency)
31
43
56
67
76
83
91

The problem can be represented as a recursive function $G$ of four parameters:

  • $s_1$ the score of the player about to roll
  • $p_1$ the position of the player about to roll
  • $s_2$ the score of the other player
  • $p_2$ the position of the other player

$G$ returns a pair of two numbers $(W_1, W_2)$ where $W_1$ represents the number of universes in which the player about to roll wins, and $W_2$ is the opposite.

If either player’s score is above or equal to 21, the game is over, and that player won in 1 universe, and the other player won in 0 universes. Otherwise, we must recurse. In practice we can skip the second base case condition since it will never happen. $$ G(s_1, p_1, s_2, p_2)= \begin{cases} (1,0) &\quad \textrm{if } s_2 \ge 21\\ (0,1) &\quad \textrm{if } s_2 \ge 21\\ \sum c_i \cdot G(s_2, p_2, s_1^\prime, p_1^\prime) &\quad \textrm{otherwise}\ \end{cases} $$

Here, $s_1^\prime$ and $p_1^\prime$ is the player’s next score and position, given that they rolled $r_i$. It seemed likely that there are overlapping subproblems, so I implemented memoization to avoid unnecessary computation. This reduced the time from 600 ms to 10 ms.

To keep track of whose turn it is, I simply swap the order of the parameters – turning player 1 into player 2, and vice versa. Alternatively one could add a fifth parameter representing whose turn it is.

package main

import (
	"fmt"
	"github.com/roessland/gopkg/mathutil"
	"time"
)

var cache = map[[4]int]Pair{}

type Pair struct {
	Fst, Snd int
}

func G(s1, p1, s2, p2 int) Pair {
	if s2 >= 21 {
		return Pair{Fst: 0, Snd: 1}
	}

	cachedA, ok := cache[[4]int{s1, p1, s2, p2}]
	if ok {
		return cachedA
	}

	W1 := 0
	W2 := 0
	for _, outcome := range []Pair{
		{3, 1},
		{4, 3},
		{5, 6},
		{6, 7},
		{7, 6},
		{8, 3},
		{9, 1},
	} {
		roll, count := outcome.Fst, outcome.Snd
		p1Next := ((p1-1)+roll)%10 + 1
		s1Next := s1 + p1Next
		g := G(s2, p2, s1Next, p1Next)
		W1 += count * g.Snd
		W2 += count * g.Fst
	}

	ret := Pair{W1, W2}
	cache[[4]int{s1, p1, s2, p2}] = ret
	return ret
}


func main() {
	t0 := time.Now()
	wins := G(0, 4, 0, 3)
	fmt.Println(mathutil.MaxInt(wins.Fst, wins.Snd))
	fmt.Println(time.Since(t0))
}