Skip to Content

Advent of Code 2017 - Day 18, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 18: 'Duet'

Posted on

On Day 18 we will do some multi-threading in Kotlin! If you’d rather jump straight to the code, it’s right here.

I’ve challenged myself to post each day’s solution to Github and blog about it. Like last year, I’m going to be solving these problems in Kotlin. I might go back and revise solutions, but I’ll be sure to annotate that fact in these posts.

Problem Input

We are given a set of input for this problem. I’ve loaded this into a List<String> called input, which we will do some further parsing on later.

Day 18, Part 1

You discover a tablet containing some strange assembly code labeled simply “Duet”. Rather than bother the sound card with it, you decide to run the code yourself. Unfortunately, you don’t see any documentation, so you’re left to figure out what the instructions mean on your own.

It seems like the assembly is meant to operate on a set of registers that are each named with a single letter and that can each hold a single integer. You suppose each register should start with a value of 0.

There aren’t that many instructions, so it shouldn’t be hard to figure out what they do. Here’s what you determine:

  • snd X plays a sound with a frequency equal to the value of X.
  • set X Y sets register X to the value of Y.
  • add X Y increases register X by the value of Y.
  • mul X Y sets register X to the result of multiplying the value contained in register X by the value of Y.
  • mod X Y sets register X to the remainder of dividing the value contained in register X by the value of Y (that is, it sets X to the result of X modulo Y).
  • rcv X recovers the frequency of the last sound played, but only when the value of X is not zero. (If it is zero, the command does nothing.)
  • jgz X Y jumps with an offset of the value of Y, but only if the value of X is greater than zero. (An offset of 2 skips the next instruction, an offset of -1 jumps to the previous instruction, and so on.)

Many of the instructions can take either a register (a single letter) or a number. The value of a register is the integer it contains; the value of a number is that number.

After each jump instruction, the program continues with the instruction to which the jump jumped. After any other instruction, the program continues with the next instruction. Continuing (or jumping) off either end of the program terminates it.

For example:

set a 1
add a 2
mul a a
mod a 5
snd a
set a 0
rcv a
jgz a -1
set a 1
jgz a -2

The first four instructions set a to 1, add 2 to it, square it, and then set it to itself modulo 5, resulting in a value of 4. Then, a sound with frequency 4 (the value of a) is played. After that, a is set to 0, causing the subsequent rcv and jgz instructions to both be skipped (rcv because a is 0, and jgz because a is not greater than 0). Finally, a is set to 1, causing the next jgz instruction to activate, jumping back two instructions to another jump, which jumps again to the rcv, which ultimately triggers the recover operation. At the time the recover operation is executed, the frequency of the last sound played is 4.

What is the value of the recovered frequency (the value of the most recently played sound) the first time a rcv instruction is executed with a non-zero value?

Another problem with instructions and registers! I wonder why it’s called Duet, if we only have one machine? :)

Given the fact that our instructions can refer to either a register or a number, let’s write ourselves an extension to make that bit easier. We’ll also make it return zero if we can’t convert the input to a number, assuming it is a new register that we have’t seen yet:

fun Map<String, Long>.deref(value: String): Long =
    this.getOrElse(value) {
        try {
            value.toLong()
        } catch (e: NumberFormatException) {
            0
        }
    }

I think the way we should start is to define a data class to represent our machine, with mutable state. We will have registers to store our values, a pc or program counter to tell us which instruction we’re looking at, the sound we most recently produced, and the sound we most recently recovered.

data class MachinePart1(private val registers: MutableMap<String, Long> = mutableMapOf(),
                        private var pc: Int = 0,
                        private var sound: Long = 0,
                        private var recovered: Long = 0) 

OK, great. Now for behavior. Let’s break it down into two parts: parsing end executing a single instruction, and then actually running the machine until it stops. Thanks to kotlin’s when structure, this code is nice and simple:

private fun execute(instruction: String) {
    val parts = instruction.split(" ")
    when (parts[0]) {
        "snd" -> sound = registers.deref(parts[1])
        "set" -> registers[parts[1]] = registers.deref(parts[2])
        "add" -> registers[parts[1]] = registers.deref(parts[1]) + registers.deref(parts[2])
        "mul" -> registers[parts[1]] = registers.deref(parts[1]) * registers.deref(parts[2])
        "mod" -> registers[parts[1]] = registers.deref(parts[1]) % registers.deref(parts[2])
        "rcv" -> if (registers.deref(parts[1]) != 0L) {
            recovered = sound
        }
        "jgz" -> if (registers.deref(parts[1]) > 0L) {
            pc += registers.deref(parts[2]).toInt().dec()
        }
        else -> throw IllegalArgumentException("No such instruction ${parts[0]}")
    }
    pc += 1
}

As you can see, we lean heavily on our deref extension and most of the instructions are pretty simple. The only thing I think needs calling out is the jgz implementation. We decrement the offset by one, because at the end of the when loop, we add one to the program counter and we need to account for it.

I want to point out that I did have a different approach at first - immutable state a data class for each instruction that took in the machine state, acted on it, and returned a new state (way more functional than this!). It was less time spent parsing, but way more code and totally overkill for this problem. I was anticipating needing it for part two, but I ended up not really using it so I refactored to what you see here.

Once we know how to parse and execute an instruction, we need to keep going until we stop, either because we generate a recovered value, or the program counter runs out of bounds:

fun runUntilStop(instructions: List<String>): Long {
    do {
        instructions.getOrNull(pc)?.let {
            execute(it)
        }
    } while (pc in 0 until instructions.size && recovered == 0L)
    return recovered
}

I like the use of Kotlin’s let, which lets us conditionally execute the instruction if it is found. Sure, we could do that with a variable and an if statement, but this reads clearer to me. And of course, our end condition is as describe, and we return the recovered value at the end.

This is all it takes to earn our first star of the day:

class Day18(private val input: List<String>) {

    fun solvePart1(): Long =
        MachinePart1().runUntilStop(input)

}

Day 18, Part 2

As you congratulate yourself for a job well done, you notice that the documentation has been on the back of the tablet this entire time. While you actually got most of the instructions correct, there are a few key differences. This assembly code isn’t about sound at all - it’s meant to be run twice at the same time.

Each running copy of the program has its own set of registers and follows the code independently - in fact, the programs don’t even necessarily run at the same speed. To coordinate, they use the send (snd) and receive (rcv) instructions:

  • snd X sends the value of X to the other program. These values wait in a queue until that program is ready to receive them. Each program has its own message queue, so a program can never receive a message it sent.
  • rcv X receives the next value and stores it in register X. If no values are in the queue, the program waits for a value to be sent to it. Programs do not continue to the next instruction until they have received a value. Values are received in the order they are sent. Each program also has its own program ID (one 0 and the other 1); the register p should begin with this value.

For example:

snd 1
snd 2
snd p
rcv a
rcv b
rcv c
rcv d

Both programs begin by sending three values to the other. Program 0 sends 1, 2, 0; program 1 sends 1, 2, 1. Then, each program receives a value (both 1) and stores it in a, receives another value (both 2) and stores it in b, and then each receives the program ID of the other program (program 0 receives 1; program 1 receives 0) and stores it in c. Each program now sees a different value in its own copy of register c.

Finally, both programs try to rcv a fourth time, but no data is waiting for either of them, and they reach a deadlock. When this happens, both programs terminate.

It should be noted that it would be equally valid for the programs to run at different speeds; for example, program 0 might have sent all three values and then stopped at the first rcv before program 1 executed even its first instruction.

Once both of your programs have terminated (regardless of what caused them to do so), how many times did program 1 send a value?

Oooooooh. That’s why it’s called Duet! OK, well, first things first, let’s refactor our machine so that we are given two BlockingQueue<Long> to send and receive values on.

data class MachinePart2(private val registers: MutableMap<String, Long> = mutableMapOf(),
                        private var pc: Int = 0,
                        private var sent: Long = 0,
                        private val send: BlockingQueue<Long>,
                        private val receive: BlockingQueue<Long>) 

Executing an instruction changes because snd and rcv have changed definition, so let’s redefine that as well:

private fun execute(instruction: String) {
    val parts = instruction.split(" ")
    when (parts[0]) {
        "snd" -> {
            send.put(registers.deref(parts[1]))
            sent += 1
        }
        "set" -> registers[parts[1]] = registers.deref(parts[2])
        "add" -> registers[parts[1]] = registers.deref(parts[1]) + registers.deref(parts[2])
        "mul" -> registers[parts[1]] = registers.deref(parts[1]) * registers.deref(parts[2])
        "mod" -> registers[parts[1]] = registers.deref(parts[1]) % registers.deref(parts[2])
        "rcv" ->
            try {
                registers[parts[1]] = receive.poll(1, TimeUnit.SECONDS)
            } catch (e: Exception) {
                pc = -2 // Die
            }
        "jgz" ->
            if (registers.deref(parts[1]) > 0L) {
                pc += registers.deref(parts[2]).toInt().dec()
            }
        else -> throw IllegalArgumentException("No such instruction ${parts[0]}")
    }
    pc += 1
}

That should look very similar to part 1’s execute function. As you can see, we have a timeout on the poll of our received queue. This is here because it’s an assumption on my part that one of the machines will not go off for more than about a second without sending something. This turns out to have worked fine, but I wasn’t able to think of a better way of saying “there is no value to receive, nor will there ever be”. I suppose I could have sent some kind of data class through the queue instead of a Long, which encapsulated the idea that the producer had died, but this works and I’m satisfied with it.

Because both of our machines need to operate concurrently, we will need to run our runUntilStop function in its own thread. To do that I’m going to be returning a CompletableFuture<Long>, which represents some calculation (our machine’s output) and some point in the future. The body of the function should look similar to part 1:

fun runUntilStop(instructions: List<String>): CompletableFuture<Long> =
    CompletableFuture.supplyAsync {
        do {
            instructions.getOrNull(pc)?.let {
                execute(it)
            }
        } while (pc in 0 until instructions.size)
        sent
    }

Setting up our machines becomes a bit more complicated in part two, but nothing crazy:

fun solvePart2(): Long {
    val program0Receive = LinkedBlockingDeque<Long>()
    val program1Receive = LinkedBlockingDeque<Long>()

    MachinePart2(
        registers = mutableMapOf("p" to 0L),
        send = program1Receive,
        receive = program0Receive
    ).runUntilStop(input)

    return MachinePart2(
        registers = mutableMapOf("p" to 1L),
        send = program0Receive,
        receive = program1Receive
    ).runUntilStop(input).get()
}

The first thing we do is create two LinkedBlockingDeque<Long> to act as our send/receive pairs. One machine’s send is another machine’s receive, so we create our machines that way. Once we create the machines, we immediately order them to run until they stop (either by producing a value or overrunning the program counter). Because we’re only interested in Machine 1’s value, I’m only waiting for that one to complete. If we were interested in both, we would obviously have to alter this.

And that earns us a second star! On my machine that takes just over a second to run, which isn’t so bad.

I hope you’ve learned something and as always, feedback is welcome!

18 days and we’ve earned 36 stars with 14 left to go! Only 7 days left!

Further Reading

  1. Index of All Solutions - All solutions for 2017, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 18.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Synchronicity, by The Police.