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

The puzzle text can be found here.

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

The puzzle text can be found here.

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.