Skip to Content

Advent of Code 2019 - Day 9, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2019, Day 9: 'Sensor Boost'

Posted on

Despite our best efforts, our trusty old IntCodeComputer is not up to today’s challenge. Rather than adding functionality and shoehorning it’s API into Days 2, 5, and 7, we’ll start a new project: IntCode Computer - Mark 2! It will take everything we’ve learned about what to do and what not to do, and will have a turbo button like all great computers.

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

Problem Input

Because one of our modifications is to support a larger memory area than we’re given as the program input, we’ll change the data type of our program input to a Map<Long, Long>. The key is the index in memory and the value is the instruction. This allows us to have a sparsely filled memory without taking a guess as to how many elements to add to an IntArray or a List<Long>.

class Day09(input: String) {

    private val program: MutableMap<Long, Long> = input
        .split(",")
        .withIndex()
        .associateTo(mutableMapOf()) { it.index.toLong() to it.value.toLong() }

}

In this example, we are still splitting our input as we have in days past, but this time we call withIndex on it, which gives us an Iterable<IndexedValue<String>>. I wasn’t aware of this one off the top of my head, and I found it by looking through the suggestions that IntelliJ offered me after I hit .. That’s a great way to explore parts of the Kotlin Standard Library.

Once we have that, we want to turn it into a MutableMap<Long, Long>. We can do that by calling associateTo() on our Iterable, giving it an empty MutableList to fill. Providing a lambda that returns a Pair<Long, Long> gives us our target data structure.

⭐ Day 9, Part 1

The puzzle text can be found here.

As I mentioned in the opening, we’ll be writing a new IntCodeComputer today. I probably should have anticipated the need for Long (or BigInteger) and not used Int to begin with, but here we are anyway. I feel that it’s probably too much work for a daily puzzle to keep going with support for the Int version.

Our new, amazing, IntCode Computer - Mark 2 will have the following features:

  • Long for all operations (was: Int)
    • I might regret not using BigInteger, but let’s find out!
  • A simpler internal structure.
    • We didn’t really end up needing the complexity that the sealed classes brought.
  • Uses coroutine Channels for input and output, no more List support.
    • View this as buying a computer from a major manufacturer and having to replace all your connectors just because.
    • Not that that happens, right?
  • A turbo button
    • All great computers have a turbo button.

Introducing IntCodeComputerMk2

Marketing really worked overtime coming up with that name, huh? At any rate, let’s define some basics for our new computer:

class IntCodeComputerMk2(
    private val program: MutableMap<Long, Long>,
    val input: Channel<Long> = Channel(Channel.UNLIMITED),
    val output: Channel<Long> = Channel(Channel.CONFLATED)
) {

    private var halted = false
    private var instructionPointer = 0L
    private var relativeBase = 0L

}

This should look somewhat close to the older IntCodeComputer we wrote in the past. The main differences are we have a flag to detect if we’ve hit a halt state, rather than identifying the operation by object type. We also have the new relativeBase value. And we also use Long everywhere we can. The output channel is CONFLATED because we generally only care about the latest value produced. If a caller wants all values, they can specify a different channel.

One change I want to make is how we find and execute instructions. I liked having the sealed classes before, but I feel that we didn’t end up needing the flexibility it could have brought. For starters, we had to pass a lot of state to each instruction. Second, they never got very complicated. I had fun writing it, and fun explaining it, and I hope you learned something from it, but we’ll move on now.

Our new instructions are going to run directly:

private suspend fun step() =
    when (val opId = (program.getValue(instructionPointer) % 100L).toInt()) {
        1 -> { // Add
            program[writeParam(3)] = readParam(1) + readParam(2)
            instructionPointer += 4
        }
        2 -> { // Multiply
            program[writeParam(3)] = readParam(1) * readParam(2)
            instructionPointer += 4
        }
        3 -> { // Input
            program[writeParam(1)] = input.receive()
            instructionPointer += 2
        }
        4 -> { // Output
            output.send(readParam(1))
            instructionPointer += 2
        }
        5 -> { // JumpIfTrue
            if (readParam(1) != 0L) {
                instructionPointer = readParam(2)
            } else {
                instructionPointer += 3
            }
        }
        6 -> { // JumpIfFalse
            if (readParam(1) == 0L) {
                instructionPointer = readParam(2)
            } else {
                instructionPointer += 3
            }
        }
        7 -> { // LessThan
            program[writeParam(3)] = if (readParam(1) < readParam(2)) 1L else 0L
            instructionPointer += 4
        }
        8 -> { // Equals
            program[writeParam(3)] = if (readParam(1) == readParam(2)) 1L else 0L
            instructionPointer += 4
        }
        9 -> { //AdjustBase
            relativeBase += readParam(1)
            instructionPointer += 2
        }
        99 -> { // Halt
            halted = true
        }
        else -> throw IllegalArgumentException("Unknown operation: $opId")
    }

I know that’s a lot of code, so let’s go over key points.

First, the step function exists to run one single instruction, whatever the instructionPointer is pointing to. An important point to notice here is that each instruction (except Halt) advances the instructionPointer manually. Before, we returned an offset and the calling function did this work. I think this makes JumpIfTrue and JumpIfFalse easier to understand now.

Next, because the logic with parameter modes is quite complicated and depends on whether we are reading or writing, I’ve provided some helpers. The readParam() and writeParam() figure out the value we need given an offset from the instructionPointer. They are different because the writing and reading logic is different. In the old version, I just looked up the write values directly. I think this makes it a lot clearer when reading the computer’s instructions.

You’ll also notice that OpCode 9, AdjustBase is implemented now. This reads the first parameter and adjusts the relativeBase by that value.

About those helpers for getting read and write parameters:


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

private fun readParam(paramNo: Int): Long =
    program.getReadRef(
        program.getOrDefault(instructionPointer, 0L).toParameterMode(paramNo), 
        instructionPointer + paramNo
    )

private fun writeParam(paramNo: Int): Long =
    program.getWriteRef(
        program.getOrDefault(instructionPointer, 0L).toParameterMode(paramNo), 
        instructionPointer + paramNo
    )

private fun MutableMap<Long, Long>.getReadRef(mode: Int, at: Long): Long =
    when (mode) {
        0 -> getOrDefault(getOrDefault(at, 0L), 0L)
        1 -> getOrDefault(at, 0L)
        2 -> getOrDefault(getOrDefault(at, 0) + relativeBase, 0)
        else -> throw IllegalArgumentException("Unknown read mode: $mode")
    }


private fun MutableMap<Long, Long>.getWriteRef(mode: Int, at: Long): Long =
    when (mode) {
        0 -> getOrDefault(at, 0L)
        2 -> getOrDefault(at, 0L) + relativeBase
        else -> throw IllegalArgumentException("Unknown write mode: $mode")
    }

These are refactorings of the versions that existed in the old IntCodeComputer. The main difference is that we now have separate functions and logic for reading and writing. These might look a bit verbose, but I wanted to make sure that our addresses were always found, so we use Map.getOrDefault here a lot. The logic in Long.toParameterMode() is identical to the version in the old computer.

Once we have a way to actually run a program, our new IntCodeComputerMk2 will be complete:

suspend fun runProgram() {
    while (!halted) {
        step()
    }
    output.close()
}

This seems a lot simpler than the old version, doesn’t it?

Now, let’s solve Part 1 by setting up our computer and executing the program:

// In Day09

private fun runComputer(startState: Long): Long = runBlocking {
    IntCodeComputerMk2(program).run {
        input.send(startState)
        runProgram()
        output.receive()
    }

This sets up our blocking coroutine context and creates a computer. We use the run extension to avoid temporary variables (because why not?). In there, we send in our initial inputs, run the program, and get the value the output channel has waiting for us (hopefully).

And to run it…

fun solvePart1(): Long =
    runComputer(1)

Star earned, onward!

⭐ Day 9, Part 2

The puzzle text can be found here.

Let me highlight the most important part of the puzzle:

You now have a complete Intcode computer.

That is fantastic news! I don’t know about you, but I’m kind of happy to not have to write IntCode Computer - Mark 3. :)

Thankfully the IntCode Computer - Mark 2 has everything we need already and we can solve Part 2 much like Part 1:

fun solvePart2(): Long =
    runComputer(2)

Star earned!

The Turbo Button!

I forgot the turbo button! Just a simple change to runProgram

suspend fun runProgram(turbo: Boolean = true) {
    while (!halted) {
        step()
        if(!turbo) delay(10)
    }
    output.close()
}

Seriously, don’t do that. Solving Part 2 without remembering to press the Turbo Button brings the runtime to well over an hour.

Further Reading

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