Skip to Content

Advent of Code 2018 - Day 19, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 19: 'Go With The Flow'

Posted on

Today we’ll reuse a lot of code from Day 16 and reverse engineer some ElfCode!

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

Problem Input

We are given one file with two types of information: the register our instruction pointer is pinned to (line 1), and the instructions to execute (rest of the input). We’ll parse them below.

Day 19, Part 1

With the Elves well on their way constructing the North Pole base, you turn your attention back to understanding the inner workings of programming the device.

You can’t help but notice that the device’s opcodes don’t contain any flow control like jump instructions. The device’s manual goes on to explain:

“In programs where flow control is required, the instruction pointer can be bound to a register so that it can be manipulated directly. This way, setr/seti can function as absolute jumps, addr/addi can function as relative jumps, and other opcodes can cause truly fascinating effects.”

This mechanism is achieved through a declaration like #ip 1, which would modify register 1 so that accesses to it let the program indirectly access the instruction pointer itself. To compensate for this kind of binding, there are now six registers (numbered 0 through 5); the five not bound to the instruction pointer behave as normal. Otherwise, the same rules apply as the last time you worked with this device.

When the instruction pointer is bound to a register, its value is written to that register just before each instruction is executed, and the value of that register is written back to the instruction pointer immediately after each instruction finishes execution. Afterward, move to the next instruction by adding one to the instruction pointer, even if the value in the instruction pointer was just updated by an instruction. (Because of this, instructions must effectively set the instruction pointer to the instruction before the one they want executed next.)

The instruction pointer is 0 during the first instruction, 1 during the second, and so on. If the instruction pointer ever causes the device to attempt to load an instruction outside the instructions defined in the program, the program instead immediately halts. The instruction pointer starts at 0.

It turns out that this new information is already proving useful: the CPU in the device is not very powerful, and a background process is occupying most of its time. You dump the background process’ declarations and instructions to a file (your puzzle input), making sure to use the names of the opcodes rather than the numbers.

For example, suppose you have the following program:

#ip 0
seti 5 0 1
seti 6 0 2
addi 0 1 0
addr 1 2 3
setr 1 0 0
seti 8 0 4
seti 9 0 5

When executed, the following instructions are executed. Each line contains the value of the instruction pointer at the time the instruction started, the values of the six registers before executing the instructions (in square brackets), the instruction itself, and the values of the six registers after executing the instruction (also in square brackets).

ip=0 [0, 0, 0, 0, 0, 0] seti 5 0 1 [0, 5, 0, 0, 0, 0]
ip=1 [1, 5, 0, 0, 0, 0] seti 6 0 2 [1, 5, 6, 0, 0, 0]
ip=2 [2, 5, 6, 0, 0, 0] addi 0 1 0 [3, 5, 6, 0, 0, 0]
ip=4 [4, 5, 6, 0, 0, 0] setr 1 0 0 [5, 5, 6, 0, 0, 0]
ip=6 [6, 5, 6, 0, 0, 0] seti 9 0 5 [6, 5, 6, 0, 0, 9]

In detail, when running this program, the following events occur:

  • The first line (#ip 0) indicates that the instruction pointer should be bound to register 0 in this program. This is not an instruction, and so the value of the instruction pointer does not change during the processing of this line.
  • The instruction pointer contains 0, and so the first instruction is executed (seti 5 0 1). It updates register 0 to the current instruction pointer value (0), sets register 1 to 5, sets the instruction pointer to the value of register 0 (which has no effect, as the instruction did not modify register 0), and then adds one to the instruction pointer.
  • The instruction pointer contains 1, and so the second instruction, seti 6 0 2, is executed. This is very similar to the instruction before it: 6 is stored in register 2, and the instruction pointer is left with the value 2.
  • The instruction pointer is 2, which points at the instruction addi 0 1 0. This is like a relative jump: the value of the instruction pointer, 2, is loaded into register 0. Then, addi finds the result of adding the value in register 0 and the value 1, storing the result, 3, back in register 0. Register 0 is then copied back to the instruction pointer, which will cause it to end up 1 larger than it would have otherwise and skip the next instruction (addr 1 2 3) entirely. Finally, 1 is added to the instruction pointer.
  • The instruction pointer is 4, so the instruction setr 1 0 0 is run. This is like an absolute jump: it copies the value contained in register 1, 5, into register 0, which causes it to end up in the instruction pointer. The instruction pointer is then incremented, leaving it at 6.
  • The instruction pointer is 6, so the instruction seti 9 0 5 stores 9 into register 5. The instruction pointer is incremented, causing it to point outside the program, and so the program ends.

What value is left in register 0 when the background process halts?

Lucky for us, we can reuse a lot of the code we wrote for Day 16! Because I have each day in one big package, the typealiases from Day 16 still apply here.

Instructions

First, let’s create a class to represent the name of our instruction and its three arguments (a, b, and c). On Day 16, we just had an IntArray because we referred to instructions by number.

// In Day19

private data class Instruction(val name: String, val a: Int, val b: Int, val c: Int) {
    companion object {
        fun of(input: List<String>): List<Instruction> =
            input.map {
                val (op, a, b, c) = it.split(" ")
                Instruction(op, a.toInt(), b.toInt(), c.toInt())
            }
    }
}

And because we have that, we can parse our input which is in two parts, so we’ll have to be careful:

// In Day 19

class Day19(rawInput: List<String>) {

    private val instructionPointer: Int = rawInput.first().split(" ")[1].toInt()
    private val instructions: List<Instruction> = Instruction.of(rawInput.drop(1))

}

Operations

We can largely reuse code from Day 16 here. The only material changes are to refer to them by name instead of number and to refer to the components of the instruction by name (a, b, and c), rather than by position:

// In Day19

    private object Operations {

        val operations: Map<String, (Registers, Instruction) -> Registers> = mapOf(
            "addr" to ::addr,
            "addi" to ::addi,
            "mulr" to ::mulr,
            "muli" to ::muli,
            "banr" to ::banr,
            "bani" to ::bani,
            "borr" to ::borr,
            "bori" to ::bori,
            "setr" to ::setr,
            "seti" to ::seti,
            "gtir" to ::gtir,
            "gtri" to ::gtri,
            "gtrr" to ::gtrr,
            "eqir" to ::eqir,
            "eqri" to ::eqri,
            "eqrr" to ::eqrr
        )

        private fun addr(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = registers[instruction.a] + registers[instruction.b] }

        private fun addi(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = registers[instruction.a] + instruction.b }

        private fun mulr(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = registers[instruction.a] * registers[instruction.b] }

        private fun muli(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = registers[instruction.a] * instruction.b }

        private fun banr(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = registers[instruction.a] and registers[instruction.b] }

        private fun bani(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = registers[instruction.a] and instruction.b }

        private fun borr(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = registers[instruction.a] or registers[instruction.b] }

        private fun bori(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = registers[instruction.a] or instruction.b }

        private fun setr(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = registers[instruction.a] }

        private fun seti(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = instruction.a }

        private fun gtir(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = if (instruction.a > registers[instruction.b]) 1 else 0 }

        private fun gtri(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = if (registers[instruction.a] > instruction.b) 1 else 0 }

        private fun gtrr(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = if (registers[instruction.a] > registers[instruction.b]) 1 else 0 }

        private fun eqir(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = if (instruction.a == registers[instruction.b]) 1 else 0 }

        private fun eqri(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = if (registers[instruction.a] == instruction.b) 1 else 0 }

        private fun eqrr(registers: Registers, instruction: Instruction): Registers =
            registers.copyOf().apply { this[instruction.c] = if (registers[instruction.a] == registers[instruction.b]) 1 else 0 }
    }

Other than that, Operations is largely the same.

Solving!

The last piece of code we need to think about is the code to execute the instructions until it ends (by incrementing the instruction pointer beyond the instructions). We need to manage the instruction pointer according to the instructions, look up our operation, and execute it on the registers. Since our operations return new registers instead of mutating them in place, we’ll make that a var and overwrite it. If you wanted, you could modify Operations to overwrite the registers and this code might be a little bit cleaner.

// In Day19

private fun execute(instructions: List<Instruction>, ipBind: Int): Registers {
    var registers = IntArray(6)
    var ip = registers[ipBind]
    while (ip in (0 until instructions.size)) {
        registers[ipBind] = ip
        val thisInstruction = instructions[ip]
        registers = Operations.operations.getValue(thisInstruction.name).invoke(registers, thisInstruction)
        ip = registers[ipBind] + 1
    }
    return registers
}

As you can see we define the registers as an IntArray(6) (because there are 6 of them now, not 4).

All that’s left is to call this with our input and wait for the solution!

fun solvePart1(): Int =
    execute(instructions, instructionPointer).first()

Star earned! Onward!

Day 19, Part 2

A new background process immediately spins up in its place. It appears identical, but on closer inspection, you notice that this time, register 0 started with the value 1.

What value is left in register 0 when this new background process halts?

If you do what they tell you, you’ll be waiting around for a long time for the answer. This is one of those problems where you have to open up your input and figure out what’s going on. If you do this, you’ll discover that early on one of the registers gets set with a huge number. The rest of the program loops around, calculating the sum of even divisors of this huge number.

So by knowing what the huge number is, we can answer Part 2 pretty quickly and not run the program at all.

How did I find the huge number? I cheated. I ran part 2 by modifying my registers and printed them all out on each step. I then manually calculated the huge number. :)

// In Day19

private fun Int.factors(): List<Int> =
    (1..this).mapNotNull { n ->
        if(this % n == 0) n else null
    }

There are faster ways to find all the divisors, but this is what I went with to get the problem done quickly.

// In Day19

fun solvePart2(): Int =
    yourHugeNumber.factors().sum()

If I have time this weekend, I’ll come back and write a general purpose way to discover the big number. It’s not straight forward because it changes location dependent on your input.

Star “earned”! :)

Further Reading

  1. Index of All Solutions - All solutions for 2018, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 19
  4. Advent of Code - Come join in and do these challenges yourself!

I miss you, Dad.