# 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) |
---|---|

3 | 1 |

4 | 3 |

5 | 6 |

6 | 7 |

7 | 6 |

8 | 3 |

9 | 1 |

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))
}
```