Advent of Code 2020 - Day 15, in Kotlin - Rambunctious Recitation • Todd Ginsberg

Since today’s puzzle involves a game that never ends, it that seems like a great use case for a sequence.

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

Problem Input

We will take our input in as a single comma-separate String and parse it into a List<Int>, to be used in our solution.

class Day15(input: String) {

    private val startingNumbers = input.split(",").map { it.toInt() }

}

⭐ Day 15, Part 1

The puzzle text can be found here.

When I read this problem, it sounded to me like we could create a Sequence<Int>, and generate successive rounds of the memory game with it. When creating a sequence in Kotlin, we provide a lambda that generates the next value each time we call it. Let’s write some code, and then I’ll explain what it does.

// In Day15

private fun memoryGame(): Sequence<Int> = sequence {
    yieldAll(startingNumbers)
    val memory = startingNumbers.mapIndexed { index, i -> i to index }.toMap().toMutableMap()
    var turns = startingNumbers.size
    var sayNext = 0
    while(true) {
        yield(sayNext)
        val lastTimeSpoken = memory[sayNext] ?: turns
        memory[sayNext] = turns
        sayNext = turns - lastTimeSpoken
        turns++
    }
}

The first thing we need to do is call yieldAll with our startingNumbers. This will emit the entire list as-is because we are told the game starts by reciting the input. If we don’t do this our sequence will not start at the right point.

Next, we set up some variable. Our memory is a MutableMap<Int,Int> where the key is the spoken number, and the value is the zero-based turn on which the key was most previously spoken. We will set up a turns counter, setting it to the size of the startingNumbers list, and finally a sayNext variable, for what the sequence will emit the next time through the loop.

To do the real work of the sequence, we setup an infinite loop (since this game technically never ends). Each time through the loop we will speak the most recently calculated value. The way a sequence emits a value is through yield. When we call yield, execution is handed back to the code that is pulling values from our sequence. When it is done, our execution returns.

Since we’ve just said something, we need to calculate what to say next time. We do this by cleaning up what we just said. We figure out when what we just said (sayNext) was spoken last (lastTimeSpoken). If we’ve never said that number, we set that to the value of the turns counter. Our last bit of clean-up is to set the memory of what we just said to the turn we said it on. Finally, we calculate what we should sayNext, and increment the turns counter, before we loop back around and yield again.

We can write a function to solve the puzzle given a number of turns:

// In Day15

fun solve(turns: Int): Int =
    memoryGame().drop(turns-1).first()

Remember, since we want the last element of the sequence, we have to drop everything but the last element.

Calling this solves Part 1:

Day15(inputAsString).solve(2020)

Star earned! Onward!

⭐ Day 15, Part 2

The puzzle text can be found here.

There are no changes between Part 1 and Part 2.

Day15(inputAsString).solve(30_000_000)

On my machine, our sequence solution takes ~5.5s to run. I bet we could get this down if we pre-allocate a large array instead of a MutableMap. Let me know if you try that, but I’m satisfied with the runtime, given that this a puzzle answer.

See you tomorrow!

⭐ Day 15, Part 1

⭐ Day 15, Part 2

Further Reading