Advent of Code 2020 - Day 8, in Kotlin - Handheld Halting • Todd Ginsberg

If you’ve done Advent of Code before, you’ve probably written yourself a couple of interpreters. If not, well, here’s your first one! Today we’ll emulate a very simple instruction set (only three instructions!) and do some debugging.

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

Problem Input

We will read our input in as List<String> and convert them into an Instruction data class we’ll write.

// In Day08

data class Instruction(val name: String, val argument: Int) {
    companion object {
        fun of(input: String): Instruction =
            input.split(" ").run {
                Instruction(this.first(), this.last().toInt())
            }
    }
}

We add the of function to the companion object in order to make the syntax a bit nicer. This lets us create an Instruction from a String. This function splits the input on a space character and take the first and last elements (the only two elements) and uses them to create an Instruction.

From there, we can parse our input:

class Day08(input: List<String>) {

    private val instructions: List<Instruction> = input.map { Instruction.of(it) }

}

⭐ Day 8, Part 1

The puzzle text can be found here.

Now that our input is parsed, let’s write ourselves a computer class to handle the processing. In years past, we’ve reused the same computer a few times, or expanded on it. I’m opting not to break this out into its own class just yet. So this Computer class will be declared with our Day08 class:

// In Day08

data class Computer(val instructions: List<Instruction>) {
    enum class ExecutionState {
        HALTED,
        INFINITE_LOOP,
        RUNNING
    }

    private val executed = mutableSetOf<Int>()
    private var instructionPointer: Int = 0
    var accumulator: Int = 0
    
    // ... more below ...
}

We’ll start off with defining our state. We take in a List<Instructions> to operate over. Next, we declare a type for our possible end states. Either our application enters an INFINITE_LOOP it is HALTED (we learn this in part 2), or it is RUNNING. In order to maintain state we’ll declare a MutableSet<Int> to capture which instructions (by their index value) we have already run. If we run an instruction twice, we know we are in an infinite loop. Finally, we declare our instructionPointer which tells us which instruction we’re running and our accumulator values.

Next, we need a function to run one single instruction of the computer and take care of all the side effects:

// In Day08.Computer

private fun executeStep(): ExecutionState? {
    return when (instructionPointer) {
        in executed -> ExecutionState.INFINITE_LOOP
        !in instructions.indices -> ExecutionState.HALTED
        else -> {
            val current = instructions[instructionPointer]
            executed += instructionPointer

            when (current.name) {
                "acc" -> {
                    accumulator += current.argument
                    instructionPointer += 1
                }
                "jmp" -> instructionPointer += current.argument
                "nop" -> instructionPointer += 1
            }
            ExecutionState.RUNNING
        }
    }
}

We get our two main end conditions out of the way first. If the instruction we are about to execute is in the list of instructions we have already executed, we are in an INFINITE_LOOP. Similarly, if we have run out of instructions, we are HALTED (again, we find that out later, but we can code it in now). Otherwise, we will interpret the current instruction, as pointed to by the instructionPointer, taking care to add the current instruction to the set of instructions we’ve already executed. We will use a when statement to execute each instruction. We could have gone with a sealed class structure here or something like that, but I feel this instruction set is simple enough to just do this. Because we’re actually executing an instruction, we can return RUNNING, indicating we haven’t reached the end of the program yet.

A computer that only runs one instruction isn’t all that useful, so let’s write another function to run until the computer terminates:

// In Day08.Computer

fun runUntilTerminate(): ExecutionState =
    generateSequence { executeStep() }.first { it != ExecutionState.RUNNING }

Essentially this calls the executeStep() function until it returns something that is not RUNNING, meaning we’ve halted or are stuck in an infinite loop.

Since we’ve written our computer, now we can run it over our instructions and see what the accumulator is:

// In Day08

fun solvePart1(): Int =
    Computer(instructions).run {
        runUntilTerminate()
        accumulator
    }

Star earned! Onward!

⭐ Day 8, Part 2

The puzzle text can be found here.

The good news is that our computer does not need to change and we’re nearly done! There are probably a lot of ways to solve this part, but we’re going to brute force it. Meaning: we will look at our instructions and flip nop and jmp instructions one at a time and then run them until the computer halts successfully.

Let’s make an alteration to our Instruction command to either flip itself from a nop to jmp or a jmp to a nop. If the instruction isn’t one of those, we’ll return null, and we’ll name this according to the Kotlin style guide: flipOrNull. Meaning, we either flip this instruction or we return null. You’ll see that naming convention quite frequently in Kotlin.

// In Day08.Instruction

fun flipOrNull(): Instruction? =
    when (name) {
        "jmp" -> Instruction("nop", argument)
        "nop" -> Instruction("jmp", argument)
        else -> null
    }

Next, we have to do the same for a List<Instruction> - flip one specific element or return null. We’ll call this flipIndexOrNull:

// In Day08

private fun List<Instruction>.flipIndexOrNull(index: Int): List<Instruction>? =
    this[index].flipOrNull()?.let { flipped ->
        this.toMutableList().apply { this[index] = flipped }
    }

I realize I nested a few scoping functions there so let me explain. If the instruction at the given index has been flipped (is not null), create a new mutable copy of the instructions list (this) and set the newly flipped instruction in place. Because our function signature explicitly specifies List<Instruction>, callers will not see that this is really a MutableList<Instruction>.

Now we can solve Part 2:

// In Day08

fun solvePart2(): Int =
    instructions
        .indices
        .asSequence()
        .mapNotNull { index -> instructions.flipIndexOrNull(index) }
        .mapNotNull { inst ->
            Computer(inst).run {
                if (runUntilTerminate() == Computer.ExecutionState.HALTED) accumulator
                else null
            }
        }.first()

First we get all of the indices of our instructions list. This is an IntRange and we can work with that. We’ll turn this into a sequence so we can terminate early, but I suppose we could have just left it alone as we’re not dealing with that much data. Next, we see if the instruction at the index we are looking at would flip and generate a new instruction set if it does. Next we execute those instructions in our computer. If the computer halts successfully, we grab the accumulator value as our answer, otherwise, we return null so we can try again.

This function is nice because we lean heavily on Kotlin’s null handling. We can pass null back from flipOrNull, flipIndexOrNull and the final computer run and Kotlin will remove them from further consideration via mapNotNull!

I hope you had as much fun as I did, see you tomorrow!

⭐ Day 8, Part 1

⭐ Day 8, Part 2

Further Reading