Advent of Code 2017 - Day 18, in Kotlin • Todd Ginsberg

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

The puzzle text can be found here.

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

The puzzle text can be found here.

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!

⭐ Day 18, Part 1

⭐ Day 18, Part 2

Further Reading