# Advent of Code 2019 - Day 7, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2019, Day 7: 'Amplification Circuit'

Posted on

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 ->
}
}
}
``````

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,
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,
output: Channel<Int>): Int {
val writeTo = program[pointer + 1]
return nextInstructionOffset
}
}

object Output : IntCodeInstruction(2) {
override suspend fun execute(pointer: Int,
program: IntArray,
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 {
}
}
}
``````

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
}

``````

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.