# Advent of Code 2021 - Day 21, in Kotlin - Dirac Dice

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 21: 'Dirac Dice'

Posted on

I can’t say I understand much about quantum theory, but I do understand recursive functions. I almost never get to use them in my day job, but I love using them in Advent of Code when I can. For part one, we’ll write a fairly iterative solution, and in part two we’ll write a nice recursive functional solution with some caching to speed things up.

If you’d rather just view code, the GitHub Repository is here .

Problem Input

Parsing today’s input is a breeze thanks to `substringAfterLast` from the Kotlin standard library. Take the part of the `String` after the last space, turn it into an `Int`, and we’re done.

``````class Day21(input: List<String>) {

private val player1Start: Int = input.first().substringAfterLast(" ").toInt()
private val player2Start: Int = input.last().substringAfterLast(" ").toInt()

}
``````

#### ⭐ Day 21, Part 1

The puzzle text can be found here.

We’ll begin coding by creating a class to represent the `DeterministicDie`. It will contain the `value` of the die, how many `rolls` it has done, and will have a `roll` function to calculate the next three rolls (since we always want three rolls). I was tempted to not maintain mutable state within `DeterministicDie` but eventually decided that the rest of the code is cleaner this way.

``````// In Day21

private class DeterministicDie(var value: Int = 0, var rolls: Int = 0) {
fun roll(): Int {
rolls += 3
value += 3
return 3 * value - 3
}
}
``````

You might notice that `DeterministicDie` doesn’t wrap back around at 100. Why? Let’s look at where this number eventually gets used, in `PlayerState`, the data class we’ll crate next.

``````// In Day21

private data class PlayerState(val place: Int, val score: Int = 0) {
fun next(die: Int): PlayerState {
val nextPlace = (place + die - 1) % 10 + 1

return PlayerState(
place = nextPlace,
score = score + nextPlace
)
}
}
``````

The `PlayerState` class is a data class because we’ll be copying them in part two as part of our state management. The `PlayerState` class has a `place` indicating where in the 1-10 spots the player in question is located, and a `score`. The `PlayerState` class has a single function - `next` which takes in the amount of a `die` roll and returns the next `PlayerState`, as if that player moved. First we calculate the `nextPlace` the player will go given the current `place` and the `die` value, and return a new `PlayerState` object with an updated `place` and `score`.

Getting back to why the `DeterministicDie` doesn’t wrap back around to 1 when it gets to 100. Suppose we are handed the `DeterministicDie` and it has just rolled a 98. For us, we know that it will roll (99, 100, 1) if we’re wrapping around properly, or (99, 100, 101) if we aren’t. Because the `place` in `PlayerState` figures out the new location and does a mod 10 (divide by 10 and take the remainder), we can take advantage of the fact that our `DeterministicDie` “wraps around” at a multiple of 10. Getting back to our options - (99, 100, 1) or (99, 100, 101), let’s do some math. 99+100+1=200. 99+100+101=300. Both 200 and 300 mod 10 results in 0. This is why we don’t have to wrap the `value` counter in `DeterministicDie`.

The next thing we’ll need to write is another data class (again, because we’ll be copying them in part two) to represent the `GameState`. This class has `PlayerState`s for both `player1` and `player2` and a `Boolean` called `player1Turn` to indicate whether it is currently player 1’s turn or not. The main function of `GameState` is called `next` and its job is to generate the next state, given a `die` roll. We can do this by examining `player1Turn`. If it is player 1’s turn, our next `GameState` is the result of player 1’s next turn, plus player 2’s previous (existing) turn, and the opposite of the `player1Turn` flag, so play flips to the opposite player each turn.

There are some helper functions in `GameState` as well. One to determine if this state represents a win state, called `isWinner` (we default the `scoreNeeded` to 1000 here, we’ll have a different value in part two). And two, a `minScore` function to return the smallest player score, to make our calling code a bit friendlier to look at.

``````// In Day21

private data class GameState(
val player1: PlayerState,
val player2: PlayerState,
val player1Turn: Boolean = true
) {
fun next(die: Int): GameState =
GameState(
if (player1Turn) player1.next(die) else player1,
if (!player1Turn) player2.next(die) else player2,
player1Turn = !player1Turn
)

fun isWinner(scoreNeeded: Int = 1000): Boolean =
player1.score >= scoreNeeded || player2.score >= scoreNeeded

fun minScore(): Int =
minOf(player1.score, player2.score)
}
``````

Now that we have those, we can play a complete game.

``````// In Day21

private val initialGameState = GameState(PlayerState(player1Start), PlayerState(player2Start))

fun solvePart1(): Int {
var game = initialGameState
val die = DeterministicDie()
while (!game.isWinner()) {
game = game.next(die.roll())
}
return game.minScore() * die.rolls
}
``````

The first thing to note is that we now have a new field called `initialGameState`. We define that because we’ll use it in part two as well, and it just cleans things up a bit. Note that we don’t really need `player1Start` and `player2Start` as fields any longer, we could just parse those as-needed and put them into `initialGameState`, but I felt this was cleaner. Our solution creates a `DeterministicDie` and keeps rolling it and passing it to `game.next` in order to generate the next game state. We do this `while` there is not a winner. Once there is a winner, we get the `minScore` and multiply it by the number of `rolls` the `DeterministicDie` has performed.

Star earned! Onward!

#### ⭐ Day 21, Part 2

The puzzle text can be found here.

Our strategy for part two is going to be a recursive function that ultimately returns a `WinCounts` object. This object contains the number of times player 1 has won, and the number of times player 2 has won. We could use a `Pair<Long,Long>` here but I’m trying to avoid Pair this year for clarity. Let’s define `WinCounts` before discussing our algorithm further.

``````// In Day21

private class WinCounts(val player1: Long, val player2: Long) {
operator fun plus(other: WinCounts): WinCounts =
WinCounts(player1 + other.player1, player2 + other.player2)

operator fun times(other: Long): WinCounts =
WinCounts(player1 * other, player2 * other)

fun max(): Long =
maxOf(player1, player2)
}
``````

Since our algorithm will need to add `WinCount` objects together and also multiply `WinCounts` by some value, we’ll provide operator functions to make that easy to look at.

Before continuing the discussion of our algorithm, let’s think about what happens when we roll the die. It’s either a 1, 2, or 3. Keep in mind that we’re rolling that three times because that rules hasn’t changed. So for each turn, 27 (3 * 3 * 3) universes open up in front of us. Can we reduce this? Sure! Think about the three rolls. If we roll three times and each time roll a 1, we have (1, 1, 1) for a total of 3. If we roll (1, 1, 2) we have a total of 4. But wait! If we roll (1,2,1) or (2,1,1) we also have a 4, but there are now more ways to get there.

We could go off and write a function to calculate this but I ended up just storing the values in a map since Kotlin doesn’t have great support for permutations or cartesian products out of the box.

Let’s define that map:

``````// In Day21

private val quantumDieFrequency: Map<Int, Long> =
mapOf(3 to 1, 4 to 3, 5 to 6, 6 to 7, 7 to 6, 8 to 3, 9 to 1)
``````

To read that, the key of the map is the total rolled (3 to 9) and the value of the map is how many different ways there are to get that total. So for a total of 3, there is 1 way to do it. For a total of 4, there are 3 ways to do it. This will let us simulate a lot of rolls without doing all of the work. If we know (for example) how many times player 1 wins if we roll a total of 4 in a specific game state, we can multiply that number by 3 (frequency) to get the total wins for any combination of die rolls that adds up to 4.

OK! Strategy. Let’s define a recursive function to run through all of the possible games we can play. Our function will be given a `GameState` object and if it wins, we’ll return a `WinCounts` object. Otherwise, we’ll generate every possible next `GameState` and recurse, checking for winners. Eventually we’ll get a bunch of `WinCounts` objects that we can put together to get the `WinCounts` for the entire problem space.

Now we can write our recursive function:

``````// In Day21

private val stateMemory: MutableMap<GameState, WinCounts> = mutableMapOf()

private fun playQuantum(state: GameState = initialGameState): WinCounts =
when {
state.isWinner(21) ->
if (state.player1.score > state.player2.score) WinCounts(1, 0) else WinCounts(0, 1)
state in stateMemory ->
stateMemory.getValue(state)
else ->
quantumDieFrequency.map { (die, frequency) ->
playQuantum(state.next(die)) * frequency
}.reduce { a, b -> a + b }.also { stateMemory[state] = it }
}
``````

Because we end up going through the same `GameState` multiple times, we are going to cache them as we figure them out in `stateMemory` - a `MutableMap` that holds each `GameState` and the `WinCounts` object associated with that state. Our recursive function begins, like all recursive function should, with our “terminal state”. Our terminal state in this case is “there is a winner”. If so, we return a `WinCounts` object with either 1 win for player 1 or 1 win for player 2.

Next, we check the cache. Have we seen this state before? If so, we return the `WinCounts` we’ve already calculated, there’s no sense in recalculating that. Note that both `GameState` and `PlayerState` are data classes rather than classes because we put them in the map and need their `hashcode` and `equals` methods to be defined. Since data class gives us that for free, we’ll define them both that way.

Finally, we look at every possible roll total we can have from `quantumDieFrequency` (3 through 9) and for each one of those, generate the `next` `GameState` and pass it to ourselves (`playQuantum`). Since the result from that call will ultimately be a `WinCounts` object, we’ll need to multiply it by the `frequency` (remember, there are 3 ways to roll up to a 4). Once we have `WinCounts` objects for each possible roll total (3 through 9) we add them up to get the total `WinCounts` for this game at this state. We’ll cache that knowledge in `stateMemory` by tacking an `also` on to our `reduce` function. I love `also` because it lets me add a side-effect to an otherwise nice functional call chain.

All that’s left to do is play!

``````// In Day21

fun solvePart2(): Long =
playQuantum().max()
``````

Star earned!