# Advent of Code 2020 - Day 15, in Kotlin - Rambunctious Recitation

Kotlin solutions to parts 1 and 2 of Advent of Code 2020, Day 15: 'Rambunctious Recitation'

Posted on

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!