Advent of Code 2021 - Day 21, in Kotlin - Dirac Dice • Todd Ginsberg

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 PlayerStates 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!

⭐ Day 21, Part 1

⭐ Day 21, Part 2

Further Reading