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

Today we’ll have a lot of fun with coroutines and channels!

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

Problem Input

Our IntCode input is always parsed the same way…

@ExperimentalCoroutinesApi
class Day23(input: String) {

    private val program: MutableMap<Long, Long> = input
        .split(",")
        .withIndex()
        .associateTo(mutableMapOf()) { it.index.toLong() to it.value.toLong() }

}

We will also annotate our class with @ExperimentalCoroutinesApi because we’re using an experimental opt-in feature.

⭐ Day 23, Part 1

The puzzle text can be found here.

Most of the work to solve both parts happens in Part 1 today, so let’s go over what we’re going to build.

A function that starts a coroutine context via runBlocking which will…
Create 50 instances of our IntCodeComputerMk2, each in their own coroutine
Create a Channel that the answer will eventually be delivered to
Create another Channel called nat that will assist with routing messages between computers
Create a coroutine for each computer to listen to its output and forward anything it receives to a router
A router, which will handle routing messages to other computers, or the answer channel.

Let’s start with the router:

private fun CoroutineScope.router(
    computers: Array<IntCodeComputerMk2>, 
    nat: SendChannel<Pair<Long, Long>>
): SendChannel<Triple<Long, Long, Long>> {
    val input: Channel<Triple<Long, Long, Long>> = Channel(UNLIMITED)
    launch {
        while (true) {
            val (to, x, y) = input.receive()
            if (to == 255L) {
                nat.send(Pair(x, y))
            } else {
                computers[to.toInt()].input.send(x)
                computers[to.toInt()].input.send(y)
            }
        }
    }
    return input
}

This is an extension function on CoroutineScope, so it can be launched more easily from the function we’ll write a bit later on. This takes in an Array of all the computers, and a Channel called nat, which we will use to send anything destined for computer 255, which is a special signal. The router function itself returns a Channel that can be used to send messages to the router logic, which we kick off in a coroutine. If a message (a Pair<Long, Long>) is intended for a computer, it is sent directly. Otherwise, the nat Channel receives it.

Let’s write the function that we described above that does all the work:

private fun runComputers(
	    natMessageHandler: suspend (Array<IntCodeComputerMk2>, ReceiveChannel<Pair<Long, Long>>, SendChannel<Pair<Long, Long>>) -> Unit
): Int = runBlocking {
    val computers = Array(50) {
        IntCodeComputerMk2(program = program.copyOf(), output = Channel(UNLIMITED))
    }
    val answer = Channel<Pair<Long, Long>>(CONFLATED)
    val nat = Channel<Pair<Long, Long>>(UNLIMITED)
    val router = router(computers, nat)

    launch {
        natMessageHandler(computers, nat, answer)
    }

    computers.forEachIndexed { id, computer ->
        launch {
            computer.runProgram()
        }
        // Initialize with network id.
        computer.input.send(id.toLong())
        computer.input.send(-1)

        launch {
            while (true) {
                router.send(
                    Triple(
                        computer.output.receive(),
                        computer.output.receive(),
                        computer.output.receive()
                    )
                )
            }
        }
    }

    answer.receive().second.toInt().also {
        this.coroutineContext.cancelChildren()
    }
}

I know there’s a lot there, so let’s go over it. This function expects the caller to hand it another suspending function that is used to handle messages sent to computer 255. This is where we will differentiate the logic between Part 1 and Part 2.

First we create our computers, giving each one of them a copy of the program (our input) and setting the output channel to UNLIMITED because they produce more than one output. We also create some helper channels: answer and nat. Each of these handles Pair<Long,Long>, which will ultimately be the x and y values. We’ll make answer a CONFLATED channel, because we only want one answer.

Next, we pass the computer and the nat channel to the router function we created and get back another Channel. We also launch our natMessageHandler suspending function in its own coroutine.

Next, we need to start all our computers and create a coroutine for each to listen to output and pass it to the router. It’s important to initialize the computer with its id, and tell it that there is no other input by sending -1. I was hoping that we could just ignore that, leveraging the fact that our coroutine channel would suspend when there is no input, but I couldn’t get that to work. I suspect the -1 drives logic within the IntCode program.

Finally, we listen to our answer channel for the first message it sends. Since this is our answer we can return it after killing off all the coroutines we just started.

For part 1, we need to call this function with the logic we want applied when we get a message for computer 255:

fun solvePart1(): Int =
    runComputers { _, nat, answerChannel ->
        answerChannel.send(nat.receive())
    }

In Part 1, we call our runComputers function and hand it the implementation of our natMessageHandler as a lambda. In this case, we want to grab the first message sent on the nat channel (where 255-destined messages go), and pass it to the answer channel. This might seem a bit overkill, but we’ll use this to make Part 2 simpler.

Star earned!

⭐ Day 23, Part 2

The puzzle text can be found here.

For Part 2, we have everything we need because of the work we did in Part 1. All we need to do is write the logic to determine the answer and pass messages to computer 0 if they are all waiting around for something to do:

fun solvePart2(): Int =
    runComputers { computers, nat, answerChannel ->
        coroutineScope {
            var mostRecentNatValue: Pair<Long, Long> = nat.receive()
            launch {
                while (true) {
                    mostRecentNatValue = nat.receive()
                }
            }
            launch {
                var latestDelivery: Long? = null
                while (true) {
                    if (computers.all { it.input.isEmpty }) {
                        val toSend = mostRecentNatValue
                        computers[0].input.send(toSend.first)
                        computers[0].input.send(toSend.second)

                        if (latestDelivery == toSend.second) {
                            answerChannel.send(toSend)
                        }
                        latestDelivery = toSend.second
                    }
                    delay(10) // Give the computers a chance to work
                }
            }
        }
    }

In this part, our lambda/suspend function records the mostRecentValue received from the nat channel. Since we don’t want to do anything unless we receive something destined for computer 255, we can start off by suspending on nat.receive(). Once that happens, we can launch a coroutine to maintain this value - any time nat receives a value, overwrite the mostRecentNatValue.

Finally, we launch a coroutine to monitor the state of the input channels on all our computers. If they are all empty, we send whatever is in mostRecentNatValue to computer 0. Otherwise, we check to see if the y value we just received matches the previous one. If they do match, that’s our answer, so we sent it along the answerChannel. It’s important to note here that I needed to insert a delay, otherwise we would either calculate the wrong value or swam our computers with -1. Perhaps you know a way to improve this? Let me know!

Star earned!

⭐ Day 23, Part 1

⭐ Day 23, Part 2

Further Reading