Advent of Code 2019 - Day 5, in Kotlin • Todd Ginsberg

Today’s puzzle was a lot of fun! Granted, not as much fun as attending KotlinConf in Copenhagen (which is going on right now), but still fun. We’ll completely rewrite our IntCode computer from Day 2 in order to add more instructions, read input, and produce output!

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

Problem Input

We receive a single file with a comma separated list of integers. In order to turn that into something more useful, we will pass that to today’s class as a String and parse it into an IntArray as a private variable.

class Day05(input: String) {

    private val program: IntArray = input.split(",").map { it.toInt() }.toIntArray()

}

This is identical to Day 2.

⭐ Day 5, Part 1

The puzzle text can be found here.

Yikes!

When I encounter big problems like this I like to break them down and think about them piece by piece. It’s easy to get overwhelmed with details, and there are so many ways to solve this problem.

My plan:

Create a class to represent our new computer (we’ll call it IntCodeComputer)
Create a sealed class representing an instruction
Figure out how to elegantly parse the parameter mode (position vs. immediate)
Implement each instruction within our sealed class

Run the program

Let’s get started.

The IntCodeComputer class

One of the interesting parts of this problem is that we’re supposed to provide the computer inputs in addition to the puzzle input. In this case, a 1. We’re going to have to model that input, and I’ve decided to make it a MutableList<Int>. Despite the fact that we really only need to model a single input and could just use an Int, I feel there’s no real reason why input should be limited, and there’s a fair chance that we’ll need this in the future.

class IntCodeComputer(private val program: IntArray,
                      private val input: MutableList<Int> = mutableListOf()
) {
    // Single input constructor
    constructor(program: IntArray, singleInput: Int) : this(program, mutableListOf(singleInput))


}

We also need the computer to take in the program (our puzzle input txt file), which we will have parsed in our Day05 class already. I’m using two constructors here because I want people to be able to instantiate the computer with either a single input (an Int), many inputs (a MutableList<Int>), or no input at all (which defaults to an empty list).

IntCodeInstruction Sealed Class

Before we get too far into our implementation for each instruction, and before we figure out how to solve the whole position vs. immediate mode thing, let’s set up some support code.

We will define a sealed class so as to constrain the number of subclases, each of which will end up representing one of the IntCode operations (Add, Multiply, etc).

sealed class IntCodeInstruction(internal val nextInstructionOffset: Int) {
    abstract fun execute(pointer: Int, 
                         program: IntArray, 
                         input: MutableList<Int>, 
                         output: MutableList<Int>): Int
}

Let’s go over this, because there are a lot of new concepts.

First, you might have noticed that we have a nextInstructionOffset which is marked as internal. This value represents how wide our instruction is (In the case of Add, it is 4 instructions wide, for example). This will end up being useful later when we try to run our instructions one after another. We mark this as internal because we don’t want any code outside our sealed class to access it, but want the sealed subclasses (which we will define inside IntCodeInstruction later) to access it.

Next, is our abstract execute function. This function is given everything it could possibly need to parse its operands and execute itself:

A pointer which represents how far along the program we are. As we execute instructions this pointer will move to the next instruction to be executed. This is effectively an index into the program.
The program, which is an IntArray. This is the puzzle input.
Some input, which we’ve already described. It contains all of the inputs we’ve manually fed to the computer, if any.
An output list. Anything our program writes will end up here.

Why do we need all this though? I don’t want to have to vary the signature of the execute function based on what I know it’s going to do. I want to pass all of this to the instruction and it can use whatever it needs. In most cases, for example, input and output will be ignored. That’s fine. I’m more interested in consistency than strictly passing only what each instruction needs.

We could conglomerate all of these into one object and pass that, and that would be a nice optimization to make should you get the urge.

Figuring Out Parameter Modes

Confession - this is the part that took me the longest to sort out. I went around and around on it, and this is where I landed.

We’re going to define a few extension functions that will help us pick values out of our program, based on the opcode. Because we have to do some funky math, this is going to make our instructions look a lot cleaner.

Let’s look at the code and then go over it:

// Defined within IntCodeIntruction

private fun Int.toParameterMode(pos: Int): Int =
    this / (10.0.pow(pos + 1).toInt()) % 10

internal fun IntArray.param(paramNo: Int, offset: Int): Int =
    this.getRef(this[offset].toParameterMode(paramNo), offset + paramNo)

private fun IntArray.getRef(mode: Int, at: Int): Int =
    when (mode) {
        0 -> this[this[at]]
        1 -> this[at]
        else -> throw IllegalArgumentException("Unknown mode: $mode")
    }

First up is Int.toParameterMode. This executes on an Int (the receiver), is given a position, and returns another Int. It’s reason for being is to turn an opcode (the receiver) into a 0 (position mode) or a 1 (immediate mode). I’ll leave it to you to go back and read the instructions on what this means. The reason for the math here is to take the operand number (how many spaces over from the opcode in the program), and parse the opcode. In order to pick out a specific digit from an integer, we need to divide that integer by a power of 10 and then take the modulo 10 of that.

For example, if our opcode is 1032, “32” represents the instruction (which I’m just using for example, it doesn’t exist yet), the “0” represents that the first parameter is in position mode, and the “1” represents that the second parameter is in “immediate” mode.

Next up is IntArray.param. This function exists so we can ask the program to figure out how to get an argument relative to the start of an instruction. For example, we would call program.param(1, pointer) to get the 1st argument after the pointer for our program.

This function uses getRef, which uses our parameter mode (0 or 1) to figure out if we’re reading a pointer to a location (0) or should read directly from the location itself (1).

Defining Instructions

Now the fun part, we get to implement our four instructions:

// Defined within IntCodeInstruction

object Add : IntCodeInstruction(4) {
    override fun execute(pointer: Int, program: IntArray, input: MutableList<Int>, output: MutableList<Int>): Int {
        val writeTo = program[pointer + 3]
        program[writeTo] = program.param(1, pointer) + program.param(2, pointer)
        return nextInstructionOffset
    }
}

object Multiply : IntCodeInstruction(4) {
    override fun execute(pointer: Int, program: IntArray, input: MutableList<Int>, output: MutableList<Int>): Int {
        val writeTo = program[pointer + 3]
        program[writeTo] = program.param(1, pointer) * program.param(2, pointer)
        return nextInstructionOffset
    }
}

object Input : IntCodeInstruction(2) {
    override fun execute(pointer: Int, program: IntArray, input: MutableList<Int>, output: MutableList<Int>): Int {
        val writeTo = program[pointer + 1]
        program[writeTo] = input.removeAt(0)
        return nextInstructionOffset
    }
}

object Output : IntCodeInstruction(2) {
    override fun execute(pointer: Int, program: IntArray, input: MutableList<Int>, output: MutableList<Int>): Int {
        output.add(program.param(1, pointer))
        return nextInstructionOffset
    }
}

object Halt : IntCodeInstruction(1) {
    override fun execute(pointer: Int, program: IntArray, input: MutableList<Int>, output: MutableList<Int>): Int = 0
}

The first thing to notice is that each of our sealed “classes” are really objects. Why? Because they don’t have state, so why bother creating instances? We could turn these into classes if we want.

I’ll leave it up to you to go through this in detail, but there are a few things I’d like to direct your attention to:

Whenever we write to a spot in the program, the instructions tell is that it is always done in immediate mode. Therefore, rather than do the logic to figure out which mode we’re in, we’ll just get the value from the program directly (look at writeTo in Add).
We always return nextInstructionOffset. This will be more interesting in Part 2.
Since Halt doesn’t end up doing anything, we just return 0.

Looking Up Instructions

I’m going to show you my favorite trick with sealed classes: making it look like you are creating the containing class but getting a subclass. We do this by implementing the invoke operator in the companion object. I love this trick.

// Defined within IntCodeInstruction

companion object {
    operator fun invoke(pointer: Int, program: IntArray): IntCodeInstruction {
        return when (val operation = program[pointer] % 100) {
            1 -> Add
            2 -> Multiply
            3 -> Input
            4 -> Output
            99 -> Halt
            else -> throw IllegalArgumentException("Unknown operation: $operation")
        }
    }
}

This allows us to call IntCodeInstruction(pointer, program) and get a sealed subclass! I like this because it looks like we’re constructing IntCodeInstruction and are totally hiding the fact that we even have a sealed class from the caller. I love this trick.

In terms of mechanics, we use a when expression to dole out instruction objects based on their id. We get this id by looking at the integer in the program indicated by the pointer and taking a modulo 100 of it. This will lop off the mode part that we don’t care about right here.

One of the benefits of defining each sealed subclasses as and object rather than a class is that we can refer to it without parenthesis (Add vs. Add()). It’s subjective, but that’s nice if your object truly has no state.

Running The Code

All that’s left to do is actually run our computer program.

// Defined within IntCodeComputer

fun run(): List<Int> {
    var instructionPointer = 0
    val output = mutableListOf<Int>()

    do {
        val nextOp = IntCodeInstruction(instructionPointer, program)
        instructionPointer += nextOp.execute(instructionPointer, program, input, output)
    } while (nextOp !is Halt)

    return output
}

Our run function sets up an instructionPointer to the first instruction in the program. It also sets up a MutableList<Int> for our output. Once we have that, we can enter the loop which will only end when we hit a Halt instruction. Each time through the loop we figure out what the next operation (nextOp) will be and execute it. Remember, the instruction returns the number of spaces we should jump in order to read the next instruction, so that value is added to our pointer.

This function returns the entirety of the output.

Let’s Solve The Puzzle!

My friends, who have chosen to join me here at the summit of Programming Mount Everest - we finally have enough code to solve Part 1.

// In Day05

fun solvePart1(): Int =
    solve(1)

private fun solve(instruction: Int): Int =
    IntCodeComputer(program, instruction).run().last()

Our solve function sets up the computer with the parsed input (see way, way above) and the manual instruction. Then it runs it and takes the final output produced.

Calling that (solve(1)) gives us a very well earned star!

⭐ Day 5, Part 2

The puzzle text can be found here.

I know, this looks like we’ll be here all day right? WRONG! :)

We’ve done a good job of setting ourselves up for success in Part 2 by doing the hard work in Part 1.

Plan for Part 2:

Define new instructions
Add instructions to the lookup
Run the program

New Instructions

Let’s open up our IntCodeInstructoin sealed class and define our new operations:

// Defined in IntCodeInstruction

object JumpIfTrue : IntCodeInstruction(3) {
   override fun execute(pointer: Int, program: IntArray, input: MutableList<Int>, output: MutableList<Int>): Int {
       val a = program.param(1, pointer)
       val b = program.param(2, pointer)
       return if (a != 0) b - pointer else nextInstructionOffset
   }
}

object JumpIfFalse : IntCodeInstruction(3) {
   override fun execute(pointer: Int, program: IntArray, input: MutableList<Int>, output: MutableList<Int>): Int {
       val a = program.param(1, pointer)
       val b = program.param(2, pointer)
       return if (a == 0) b - pointer else nextInstructionOffset
   }
}

object LessThan : IntCodeInstruction(4) {
   override fun execute(pointer: Int, program: IntArray, input: MutableList<Int>, output: MutableList<Int>): Int {
       val writeTo = program[pointer + 3]
       program[writeTo] = if (program.param(1, pointer) < program.param(2, pointer)) 1 else 0
       return nextInstructionOffset
   }
}

object Equals : IntCodeInstruction(4) {
   override fun execute(pointer: Int, program: IntArray, input: MutableList<Int>, output: MutableList<Int>): Int {
       val writeTo = program[pointer + 3]
       program[writeTo] = if (program.param(1, pointer) == program.param(2, pointer)) 1 else 0
       return nextInstructionOffset
   }
}

The interesting part here is how JumpIfTrue and JumpIfFalse return a value. Remember, the return value represents how far to jump, not the position to jump to. Because the instruction itself knows the absolute position we want the instruction pointer to move to, we need to turn that into a relative position. Unless the condition doesn’t hold, and then we just want to move on to the next instruction like all of the other operations.

Look All This Up

We need to add these to the invoke function, by their id. That should look like this now:

// Defined in IntCodeInstruction

companion object {
    operator fun invoke(pointer: Int, program: IntArray): IntCodeInstruction {
        return when ( val operation = program[pointer] % 100) {
            1 -> Add
            2 -> Multiply
            3 -> Input
            4 -> Output
            5 -> JumpIfTrue
            6 -> JumpIfFalse
            7 -> LessThan
            8 -> Equals
            99 -> Halt
            else -> throw IllegalArgumentException("Unknown operation: $operation")
        }
    }
}

Yes, this could be a Map<Int, IntCodeInstruction> if you want.

Solve The Puzzle

See? I told you we didn’t have much to do this time:

fun solvePart2(): Int =
    solve(5)

Problem solved and star earned!

I really, really (REALLY) hope we end up seeing more IntCode in the 20 days remaining. I don’t usually like to refactor before I have to (YAGNI ), but I felt the risk was worth it. And it was actually fun in the end (for me). We’ll see if my gamble pays off!

Day 2: IntCodeComputer Inside!

It occurred to me that I could rewrite part of Day 2’s solution using our IntCodeComputer class. If you’d like to see that, check it out over on GitHub !

⭐ Day 5, Part 1

⭐ Day 5, Part 2

Day 2: IntCodeComputer Inside!

Further Reading