Advent of Code 2019 - Day 7, in Kotlin • Todd Ginsberg

Today we’ll reuse our IntCodeComputer class and scratch the surface and see what Kotlin Coroutines have to offer.

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

Problem Input

We receive a single file with a comma separated list of integers. In order to turn that into something more useful, we will pass that to today’s class as a String and parse it into an IntArray as a private variable.

class Day07(input: String) {

    private val program: IntArray = input.split(",").map { it.toInt() }.toIntArray()

}

This is identical to Days 2 and 5.

⭐ Day 7, Part 1

The puzzle text can be found here.

Well, it looks like all the work we did on Day 5 to make our IntCodeComputer reusable is about to pay off. The good news is that for part 1, we can reuse our IntCodeComputer as-is!

In order to solve Part 1, we need to:

Write a function to get all of the permutations of a list
Write a function to hook five IntCodeComputer instances together and feed it our potential input
Run every combination and figure out which one yields the largest number

Let’s dig in!

Permutation Situation

Let’s start by writing an extension function on List<T> to get all of the permutations of that list, and return them all in a List. Meaning, if we call permutations() on a List<Int>, we will get back a List<List<Int>>.

Depending on how many permutations we will end up with, we might have to change our return type. If the number is small, we can return all of the possible permutations as a List as we’ve outlined above. Otherwise, if we expect so many permutations that it will cause memory pressure, we might want to return a Sequence<List<T>> because a Sequence is lazily evaluated. This reduces the number of permutations that need to be in memory all at once, and they are only generated when needed.

Because we know from the puzzle description that we have 5 inputs in our list (0-4), we can go the simple route with our permutations function and return a List<List<T>>.

// In Extensions.kt

fun <T> List<T>.permutations(): List<List<T>> =
    if (this.size <= 1) listOf(this)
    else {
        val elementToInsert = first()
        drop(1).permutations().flatMap { permutation ->
            (0..permutation.size).map { i ->
                permutation.toMutableList().apply { add(i, elementToInsert) }
            }
        }
    }

Our new function is recursive (it calls itself). The first thing we do is check for the easy cases. If the List is empty or has one element, we can calculate all of the permutations without doing any work. On the other hand, if we have a longer List, we need to start moving some elements around. In this version, we see the familiar flatMap/map structure that we’ve seen in days past. This lets us create one big List out of multiple Lists. Our main logic looks at the first element of the list and places it in each position it can. This is done recursively so we get every possible combination (permutation!).

I’m a bit disappointed that something like this doesn’t exist in the Kotlin Standard Library. I know Scala has this. I know there are plenty of Kotlin or Java implementations I could have pulled in, but I want to avoid dependencies for this project.

Building the Amplifier Array

Our next task is to create a function called runPhase which will take a set of inputs and link five IntCodeComputer instances together, providing the output from one as the input to the next, finally retrieving the final computer’s output.

We will do this with a fold:

private fun runPhase(settings: List<Int>): Int =
    (0..4).fold(0) { past, id ->
        IntCodeComputer(program.copyOf(), mutableListOf(settings[id], past)).run().first()
    }

We “fold” over a range of 0 to 4 in this case, in order to trigger our logic 5 times. When using a fold, we need to give it an initial state (in this case, just the number zero). What’s nice about fold is that for every iteration, we get back the value that was generated the last time through (past) as well as the next element from the collection we’re folding over (id). This combination of things let’s us create a computer, give it the appropriate inputs, run it, and pass the output value down the chain to the next fold. At the end the result of the fold is the output from the final computer.

Solving Part 1

Now that we have a way to link our IntCodeComputer instances together into an Amplifier Array and run it for a single set of inputs, we can solve Part 1.

fun solvePart1(): Int =
    listOf(0, 1, 2, 3, 4).permutations().map { runPhase(it) }.max()
        ?: throw IllegalStateException("No max value, something is wrong")

To solve the puzzle, we first create a list of all the possible Amplifier inputs (0 through 4), get every permutation of that list, and then for each one of those, run our logic. Once that’s done, we take the max value is our answer!

Star earned! Onward!

⭐ Day 7, Part 2

The puzzle text can be found here.

Yikes! This might look difficult, but if we come up with a plan, we can do it.

The Plan:

Make IntCodeComputer work with Kotlin Coroutines
Write a function to chain the Amplifiers in a circle
Generate permutations and solve the problem.

Let’s go!

Kotlin Coroutines and IntCodeComputer

You might be asking: “why bother with coroutines?”. At a fundamental level, coroutines allow us to write asynchronous code while making it look imperative. More directly, we want to run IntCodeComputer and instead of having an error when it tries to read inputs that aren’t there, we want to have it suspend until input becomes available. We also want all of our IntCodeComputer instances to run at the same time.

The core of our change is the Channel. Think of these like queues that we can write to and read from. Kotlin Coroutines use them to send messages to one another. One coroutine calls send() to send its message. On the other end of the Channel, another coroutine can call receive() to get the message. Depending on the settings, this Channel can hold unlimited messages, one message, or replace a message that has not been delivered. And all of the sending and receiving can happen asynchronously.

How does this help us? Well, if we replace our input and output in the existing IntCodeComputer with Channels, we can have our computer suspend operation until a message is available!

Wait? Suspend? When we read coroutines code, we often see the keyword suspend. This tells the compiler that when this function is going to be called in the context of a coroutine, it can be suspended if there is no work to be done. That means if another coroutine is ready to do work, it can be scheduled to run and when the suspended function has more work to do, it can resume.

The problem with this is that we can’t call suspending functions from non-suspending functions. This will have to be taken into account when we refactor IntCodecomputer.

The challenge here is to modify IntCodeComputer to use coroutines in a way that does not break our existing usages (Day 2 and Day 5 solutions)!

Let’s start by changing our input from a List<Int> to a Channel<Int>. We’ll also make it public. And we’ll move our output up to the class level and turn it into a Channel<Int> as well.

class IntCodeComputer(private val program: IntArray,
                      val input: Channel<Int>
) {

    val output: Channel<Int> = Channel(Channel.UNLIMITED)

    ...
}

Remember how we wanted to make our existing callers unaware of these changes? Let’s do that now. We have two constructors that will no longer work because we need to use Channel and not List. We’ll use the trick of overriding invoke in the companion to mimic constructors and move our old logic here:

// In IntCodeComputer

companion object {
    operator fun invoke(program: IntArray, singleInput: Int) = runBlocking {
        IntCodeComputer(program, mutableListOf(singleInput).toChannel())
    }

    operator fun invoke(program: IntArray, input: MutableList<Int> = mutableListOf()) = runBlocking {
        IntCodeComputer(program, input.toChannel())
    }
}

You might have noticed that we’ve introduced a runBlocking call here. That allows us to bridge our non-coroutines client with our soon-to-be-coroutines code. The runBlocking is a coroutines context. It lets us call suspending functions and will block until the entire function has completed. This means we can receive a List or an Int from our caller and turn that into a Channel without them knowing!

We also need to define an extension function to turn a List into a Channel. I wouldn’t go putting this into production, but it works for Advent of Code:

fun <T> List<T>.toChannel(capacity: Int = Channel.UNLIMITED): Channel<T> =
    Channel<T>(capacity).also { this.forEach { e -> it.offer(e) } }

The next step is to add a suspending version of our run function. We will move all of the logic from our existing run function here:

// In IntCodeComputer

suspend fun runSuspending() {
    var instructionPointer = 0

    do {
        val nextOp = IntCodeInstruction(instructionPointer, program)
        instructionPointer += nextOp.execute(instructionPointer, program, input, output)
    } while (nextOp !is Halt)

    output.close()
}

This more or less does the same thing as before, except with a bit of channel management. We loop through the operations, execute them, and halt. Before we return, we close the output channel to signal that we do not anticipate any more work.

Since the logic is here, we’ll refactor run to be runBlocking and call our runSuspended function. At the end, we’ll turn our output Channel into a List, so again, the caller doesn’t know our internal implementation has changed.

// In IntCodeComputer

// Replaces old version of run()
fun run(): List<Int> = runBlocking {
    runSuspending()
    output.toList()
}

In the real world, we might not be able to get away with this. But this is Advent of Code and has a highly specific definition and a finite number of inputs.

The final thing we need to do here is to make sure our IntCodeInstruction works with Channel instead of List. To do this, we replace List with Channel and mark it suspend.

// In IntCodeInstruction

abstract suspend fun execute(pointer: Int, 
                             program: IntArray, 
                             input: ReceiveChannel<Int>,
                             output: Channel<Int>): Int

This will cause all of the sealed subclasses to change. The only two interesting ones are Input and Output, the two that work with the Channel.

// In IntCodeInstruction

object Input : IntCodeInstruction(2) {
    override suspend fun execute(pointer: Int, 
                                 program: IntArray, 
                                 input: ReceiveChannel<Int>, 
                                 output: Channel<Int>): Int {
        val writeTo = program[pointer + 1]
        program[writeTo] = input.receive()
        return nextInstructionOffset
    }
}

object Output : IntCodeInstruction(2) {
    override suspend fun execute(pointer: Int, 
                                 program: IntArray, 
                                 input: ReceiveChannel<Int>, 
                                 output: Channel<Int>): Int {
        output.send(program.param(1, pointer))
        return nextInstructionOffset
    }
}

Other than the signature change, there are two important changes here:

When we read from the channel, we call input.receive(), which will suspend until something is on the channel to read.
When we write to the channel, we call output.send(), which will also suspend if we don’t have room on the Channel. Since I’ve defined all of our channels as unlimited in length, this won’t be an issue.

Circle of Amplifiers

One of the requirement is for the output of the amplifiers to feed back into each other. So the output of the final amplifier (E) must be the input to the first amplifier (A). Since we also need to know what the final output is, we’ll have to resort to spying!

class ChannelSpy<T>(
    private val input: Channel<T>,
    private val output: Channel<T>,
    val spy: Channel<T> = Channel(Channel.CONFLATED)) {

    suspend fun listen() = coroutineScope {
        for (received in input) {
            spy.send(received)
            output.send(received)
        }
    }
}

Our ChannelSpy is given an input Channel and an output Channel and defines its own spy Channel. This channel is a CONFLATED channel in our case. That means if there is a value in the channel, it is replaced. So the receiver only ever sees the latest write. This works for our needs today, we don’t care about any values other than the final one. When we call the listen function, it suspends while waiting for a message to be received from the input Channel. Once that happens, the message is copied to our spy Channel, and the output Channel. Pretty sneaky.

Next up, we need to create each of our 5 IntCodeComputer instances, send them off to asynchronously calculate the answer, and wait for them to halt.

// In Day07.kt

private suspend fun runAmplified(settings: List<Int>): Int = coroutineScope {

    // Part 1: Set up computers
    val a = IntCodeComputer(program.copyOf(), listOf(settings[0], 0).toChannel())
    val b = IntCodeComputer(program.copyOf(), a.output.andSend(settings[1]))
    val c = IntCodeComputer(program.copyOf(), b.output.andSend(settings[2]))
    val d = IntCodeComputer(program.copyOf(), c.output.andSend(settings[3]))
    val e = IntCodeComputer(program.copyOf(), d.output.andSend(settings[4]))
    val channelSpy = ChannelSpy(e.output, a.input)

    // Part 2: Run asynchronous tasks
    coroutineScope {
        launch { channelSpy.listen() }
        launch { a.runSuspending() }
        launch { b.runSuspending() }
        launch { c.runSuspending() }
        launch { d.runSuspending() }
        launch { e.runSuspending() }
    }

    // Part 3: Return results
    channelSpy.spy.receive()
}

In Part 1, we set up our spy, and a, b, c, d, and e. These are our IntCodeComputer instances. The interesting part is that we capture the output from a as the input for b, and so on. Because these channels need to have a value in there already, we’ll use our andSend() extension function to make this look a little more clean:

// In Day07.kt 

private suspend fun <T> Channel<T>.andSend(msg: T): Channel<T> =
    this.also { send(msg) }

In Part 2, we set up a new coroutine scope. This is so any child process (that we launch within it) will be registered with that context. This in turn ensures that the context will end until all of its children have completed. It also has the benefit that if any of its children fail, the rest will be cleaned up automatically. This is nice because we don’t have to manually check any of that. We also kick off our spy so it will start listening for messages.

Part 3 we receive the final message that the spy has waiting for us. Our answer.

Solving Part 2

Well, we’re finally here. We finally have enough to solve the problem and it looks a lot like Part 1:

fun solvePart2(): Int = runBlocking {
    listOf(5, 6, 7, 8, 9).permutations().map { runAmplified(it) }.max()
        ?: throw IllegalStateException("No max value, something is wrong")
}

The only real differences between this and the code that solves Part 1 is the fact that this is run within a runBlocking (see above) and has different starting values (5 through 9 instead of 0 through 4).

Problem solved and star earned! I think this was the most fun day so far, for me. The best part about this, to me, is that our code for Day 2 and Day 5 does not change at all, but now we have new coroutine functionality that will hopefully come in handy in future puzzles.

⭐ Day 7, Part 1

⭐ Day 7, Part 2

Further Reading