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

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

The puzzle text can be found here.

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

The puzzle text can be found here.

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!

⭐ Day 23, Part 1

⭐ Day 23, Part 2

Further Reading