Skip to Content

Advent of Code 2017 - Day 8, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 8: 'I Heard You Like Registers'

Posted on

Day 8 has us implementing a small set of CPU instructions, with some conditional logic. 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 parsed this into an List<String> that we will further parse into instructions.

Day 8, Part 1

You receive a signal directly from the CPU. Because of your recent assistance with jump instructions, it would like you to compute the result of a series of unusual register instructions.

Each instruction consists of several parts: the register to modify, whether to increase or decrease that register’s value, the amount by which to increase or decrease it, and a condition. If the condition fails, skip the instruction without modifying the register. The registers all start at 0. The instructions look like this:

b inc 5 if a > 1
a inc 1 if b < 5
c dec -10 if a >= 1
c inc -20 if c == 10

These instructions would be processed as follows:

Because a starts at 0, it is not greater than 1, and so b is not modified.

  • a is increased by 1 (to 1) because b is less than 5 (it is 0).
  • c is decreased by -10 (to 10) because a is now greater than or equal to 1 (it is 1).
  • c is increased by -20 (to -10) because c is equal to 10.

After this process, the largest value in any register is 1.

You might also encounter <= (less than or equal to) or != (not equal to). However, the CPU doesn’t have the bandwidth to tell you what all the registers are named, and leaves that to you to determine.

What is the largest value in any register after completing the instructions in your puzzle input?

I think there are several approaches we could take here. We could parse each line of input and execute the instruction right then and there, or we could create an object to represent each instruction, and then execute them. I chose the latter, because that just seems clearer to me. Plus, we haven’t seen part two yet and I suspect we’ll want a more robust solution.

Let’s first define some things that we’ll need:

private val instructionRegex = """(\S+)""".toRegex()
private val registers: MutableMap<String, Int> = mutableMapOf()
private val instructions: List<Instruction> = parseInput(input) 

We’re going to parse our input with another regular expression, just like yesterday. This one is fairly simple, it just says “find anything that’s not whitespace and group them together”. Our input has seven total fields, and we can refer to them by number later. We’ll also define a mutable map to hold our registers. The instructions state that every register starts off at zero, so we’ll have to be careful to account for that whenever we read from the map. And finally, we’ll have a list of instructions we can go through later.

I want to look at our input and make a few decisions about how we’ll represent it. I’ve spaced it out to make it easier to read.

c inc -20    if    c == 10   

I’m going to call the part after the if, a condition, and like the parser we have a decision to make on how to represent it. We could implement all of the logic as a set of sealed classes, or we could just create and return a function that takes an Int and returns a Boolean, indicating if the condition is met or not. In our case above, it would return true if the c register is 10 exactly. I’m going to go with the function approach, but if this gets more complicated in part two, maybe we’ll have to rethink this.

So let’s write some code to create a condition:

private fun createCondition(symbol: String, amount: Int): (Int) -> Boolean =
    when (symbol) {
        "==" -> { n -> n == amount }
        "!=" -> { n -> n != amount }
        "<" -> { n -> n < amount }
        ">" -> { n -> n > amount }
        "<=" -> { n -> n <= amount }
        ">=" -> { n -> n >= amount }
        else -> throw IllegalArgumentException("Unknown symbol: $symbol")
  }

Thanks to the when expression, this is nice and clean and easy to see what we’re trying to do. Each time this is called a new function will be returned that compares the input to the amount.

Looking at our input some more, the left hand side of the if statement has some conditional logic as well (increment or decrement), and we will take a similar approach: create a function that takes an Int and returns an Int representing the new register value. We’ll call this the changer (I realize that name is kind of lame, feel free to call yours just about anything else for clarity).

And by now, we have all of our concepts ready, so we can define our Instruction class:

class Instruction(private val condition: (Int) -> Boolean,
                  private val conditionRegister: String,
                  private val instructionRegister: String,
                  private val changer: (Int) -> Int) {

    fun execute(registers: MutableMap<String, Int>) {
        if (condition(registers.getOrDefault(conditionRegister, 0))) {
            registers[instructionRegister] = changer(registers.getOrDefault(instructionRegister, 0))
        }
    }
}

The Instruction takes four parameters:

  1. Our condition, which must be true to actually execute the instruction.
  2. A conditionRegister, the 5th field of input, the register the condition applies to.
  3. An instructionRegister, the 1st field of input, the register the instruction applies to.
  4. A changer function, which does the changing of the instruction register.

Going through the code, it’s fairly straight forward. Somebody will call execute and pass in the map of register values. If our condition is true after being evaluated with the condition register, we will call the changer with the value of the instruction register, and save the value. Also, we define registers as we need them because assume they are zero unless we add or subtract them ourselves.

And therefore, parsing looks like this:

private fun parseInput(input: List<String>): List<Instruction> =

    input
        .map {
            val groups = instructionRegex.findAll(it).toList().map { it.value }
            val condition = createCondition(groups[5], groups[6].toInt())
            if (groups[1] == "inc")
                Instruction(condition, groups[4], groups[0]) { it + groups[2].toInt() }
            else
                Instruction(condition, groups[4], groups[0]) { it - groups[2].toInt() }
        }

This might look a bit terse, so let’s walk through it. For each raw row of input we parse it with our regular expression and end up with a List<String> (groups). We create a condition, and an instruction. If we’re incrementing, our changer function is defined to add, otherwise to subtract. This way, we don’t have to have two nearly identical implementations of Instruction for increment and decrement.

Solving part one is a simple matter of executing the instructions and finding the register with the largest value:

fun solvePart1(): Int {
    instructions.forEach { it.execute(registers) }
    return registers.values.max() ?: 0
}

This runs very fast, and earns us a star!

Day 8, Part 2

To be safe, the CPU also needs to know the highest value held in any register during this process so that it can decide how much memory to allocate to these operations. For example, in the above instructions, the highest value ever held was 10 (in register c after the third instruction was evaluated).

That doesn’t seem all that hard, does it? It looks like we can solve this with one minor change to our existing code. Every time an Instruction executes, it has the possibility of altering a register value. What if we returned the register being changed, even if our condition isn’t met?

Now, our Instruction class looks like this:

class Instruction(private val condition: (Int) -> Boolean,
                  private val conditionRegister: String,
                  private val instructionRegister: String,
                  private val changer: (Int) -> Int) {

    fun execute(registers: MutableMap<String, Int>): Int {
        if (condition(registers.getOrDefault(conditionRegister, 0))) {
            registers[instructionRegister] = changer(registers.getOrDefault(instructionRegister, 0))
        }
        return registers.getOrDefault(instructionRegister, 0)
    

Our execute function returns an Int, the value of its register.

And to solve, we just find the maximum value returned from each Instruction after execution:

  fun solvePart2(): Int =
      instructions.map { it.execute(registers) }.max() ?: 0

We’re done! It works just as quickly as part one and earns us a star.

I hope you’ve learned something, and as always, feedback is welcome!

2^3 days and we’ve earned 2^4 stars with 34 left to go!

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 8.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - 10538 Overture, by Electric Light Orchestra.