Skip to Content

Advent of Code 2017 - Day 23, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 23: 'Coprocessor Conflagration'

Posted on

On Day 23 we will reuse some code from Day 18, and re-write some slow assembly code into easy to understand 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 23, Part 1

You decide to head directly to the CPU and fix the printer from there. As you get close, you find an experimental coprocessor doing so much work that the local programs are afraid it will halt and catch fire. This would cause serious issues for the rest of the computer, so you head in and see what you can do.

The code it’s running seems to be a variant of the kind you saw recently on that tablet. The general functionality seems very similar, but some of the instructions are different:

  • set X Y sets register X to the value of Y.
  • sub X Y decreases 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.
  • jnz X Y jumps with an offset of the value of Y, but only if the value of X is not zero. (An offset of 2 skips the next instruction, an offset of -1 jumps to the previous instruction, and so on.)

Only the instructions listed above are used. The eight registers here, named a through h, all start at 0.

The coprocessor is currently set to some kind of debug mode, which allows for testing, but prevents it from doing any meaningful work.

If you run the program (your puzzle input), how many times is the mul instruction invoked?

This is so close to what we did for Day 18 that we’re going to employ on of the best tools modern programming has: cut and paste. We will use a modified version of MachinePart1 from Day 18:

data class Machine(private val registers: MutableMap<String, Long> = mutableMapOf(),
                   private var pc: Int = 0,
                   val debug: MutableMap<String, Long> = mutableMapOf()) {

    fun runUntilStop(instructions: List<String>): Machine {
        do {
            instructions.getOrNull(pc)?.let {
                execute(it)
            }
        } while (pc in 0 until instructions.size)
        return this
    }

    private fun execute(instruction: String) {
        val parts = instruction.split(" ")
        debug[parts[0]] = debug.deref(parts[0]) + 1
        when (parts[0]) {
            "set" -> registers[parts[1]] = registers.deref(parts[2])
            "sub" -> registers[parts[1]] = registers.deref(parts[1]) - registers.deref(parts[2])
            "mul" -> registers[parts[1]] = registers.deref(parts[1]) * registers.deref(parts[2])
            "jnz" -> if (registers.deref(parts[1]) != 0L) {
                pc += registers.deref(parts[2]).toInt().dec()
            }
            else -> throw IllegalArgumentException("No such instruction ${parts[0]}")
        }
        pc += 1
    }
}

In this case, we’ve removed the instructions we don’t need, and added a debug map to store how many times each instruction was executed. Yes, the instructions only ask for mul, but there are only a handful of instruction types so why not just record them all? It still depends heavily on our deref extension function. The runUntilStop method has been modified to just check the bounds of the program counter. Execute this, extract the mul count, and we’re done.

fun solvePart1(): Long =
    Machine().runUntilStop(input).debug["mul"] ?: 0

An easy star, copied over from Day 18. Let’s move on.

Day 23, Part 2

Now, it’s time to fix the problem.

The debug mode switch is wired directly to register a. You flip the switch, which makes register a now start at 1 when the program is executed.

Immediately, the coprocessor begins to overheat. Whoever wrote this program obviously didn’t choose a very efficient implementation. You’ll need to optimize the program if it has any hope of completing before Santa needs that printer working.

The coprocessor’s ultimate goal is to determine the final value left in register h once the program completes. Technically, if it had that… it wouldn’t even need to run the program.

After setting register a to 1, if the program were to run to completion, what value would be left in register h?

Here is an annotated and indented version of what my input file looks like:

set a 1                    # IMPLIED by instructions (not in actual input file)
set b 67                   # This is the only change between input sets
set c b
jnz a 2                    # IF a is not 0 (Part 2) skip this next jump and execute the block thereafter
jnz 1 5                    # ELSE if a is 0 (Part 1), jump over this next block
    mul b 100              
    sub b -100000          # b = (b * 100) + 100,000
    set c b         
    sub c -17000           # c = b + 17000
                           # NOTE: At this point b is 17,000 less than c.
set f 1                    # START Main outer loop, Set f = 1
    set d 2                # START Middle loop, Set d = 2
        set e 2            # START Inner loop, Set e = 2
            set g d        
            mul g e        
            sub g b        # g = (d * e) - b
            jnz g 2        # IF g == 0
                set f 0    # THEN f = 0
            sub e -1       # e = e - 1
            set g e        
            sub g b        # g = e - b 
            jnz g -8       # Start inner loop over
        sub d -1           # d = d + 1
        set g d            
        sub g b            # g = d - b
    jnz g -13              # If g != 0, Start middle loop over 
    jnz f 2                # IF f == 0 
        sub h -1           # THEN Increment our h counter by 1
    set g b                
    sub g c                # g = b - c
    jnz g 2                # IF g != 0, keep going  
                           # (Meaning: If we've increased b by 17 enough 
                           #           times so that it == c...)
    jnz 1 3                # ELSE, end the program by jumping beyond instructions
    sub b -17              # b = b + 17
jnz 1 -23                  # Start outer loop over

Our input will differ from everybody else’s in terms of b. In my case, it is 67. So b and c will both be different for me than yours (unless we have the same input, obviously). Everything else about this file is the same, and as you can see there are a few “loops”. The jnz (jump not zero) command serves two functions depending on whether we are jumping forward (positive) or backward (negative). Forward jumps are like if statements (or a return statement when we jump beyond the instructions), and backward jumps are like loops starting over.

So that the heck is that all actually doing? It’s a rather inefficient way to find prime numbers. Or more accurately, count up numbers that aren’t prime.

Cutting to the chase, we can just parse b from the input and find all the numbers that aren’t prime between b = b * 100 + 100000 and b+17000, skipping by 17. More clearly: starting at b, how many of the next 1,000 numbers, skipping by 17, are NOT prime?

Rather than write and execute a direct-to-Kotlin version of our assembly, I just wrote it more directly so it would a) complete in a reasonable amount of time (~20ms) and b) be readable:

fun solvePart2(): Int {
    val a = input.first().split(" ")[2].toInt() * 100 + 100000
    return (a .. a+17000 step 17).count {
        !it.toBigInteger().isProbablePrime(5)
    }

I took advantage of the step parameter when constructing a range in Kotlin, that sure helped make this clearer. Thankfully, BigDecimal has a function to test for prime, so I just used that and this code cranked out the correct answer.

Whew! We sure earned our second star today! I wonder what tomorrow has in store for us?

I hope you had fun.

That makes 23 days and 46 stars with only 2^2 left to go! Only 2 days remaining!

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 23.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Cut to the Chase, by Rush.