Advent of Code 2022 - Day 10, in Kotlin - Cathode-Ray Tube • Todd Ginsberg

Thanks to the assembly language class I was compelled to take as part of my effort to get a Computer Science degree many (many) years ago, I knew exactly how I wanted to solve this puzzle as soon as I read the instructions. In the spirit of “noop does nothing”, we’ll insert a lot of instructions that don’t do anything.

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

Puzzle Input

When we first read the instructions it might seem like a giant pain to keep track of the number of cycles each instruction takes up. Thankfully, we’re only really given two instructions - noop (does nothing) and addx (adds the value to the register). Unfortunately, addx takes up two clock cycles where noop only takes one. What if we represent our parsed input as the change in the register, rather than actual instructions?

For example, if we were given this input:

addx 2
noop 
addx 3

We would want a list that looks like this: [1, 0, 2, 0, 0, 3]. The first 1 is there because x (the register) starts at 1. The first 0 is cycle 1 where we have started executing addx 2 but have not yet finished. The 2 (cycle 2) is our addx 2 instruction finishing. The next 0 is the noop (no change in x). The next 0 is our addx 3 instruction starting in cycle 4 but not finishing yet (so no change in x), and finally 3 to represent the fact that addx 3 finished in cycle 6.

Given this structure, we can add the deltas together to determine the signal. I really like this because we don’t have to do anything other than add. We don’t have to keep track of cycle lengths except during parsing, and we don’t have to account for no-ops. The fact that we can add zero to something means we get the best of both worlds - executing an “instruction” every clock cycle without actually doing any work.

So let’s parse our input which we received as a List<String> into a List<Int> (you could go with an IntArray if you want here).

class Day10(input: List<String>) {

    private val signals: List<Int> = parseInput(input).runningReduce(Int::plus)

    private fun parseInput(input: List<String>): List<Int> =
        buildList {
            add(1)
            input.forEach { line ->
                add(0)
                if (line.startsWith("addx")) {
                    add(line.substringAfter(" ").toInt())
                }
            }
        }

}

Today’s parseInput introduces us to buildList. This is a nice function in the Kotlin Standard Library that lets us build a MutableList and when we’re done, get a List (not mutable). This is handy for situations like the one we’re in, where one single item (each row of input in our case) may lead to multiple items being added to the list. In other words, if we were doing a straight map where each symbol of input led to a single symbol of output, we probably wouldn’t need to use buildList. But since each symbol of input in our case may add more “add 0” commands, we will get a benefit here. The other alternative is to flatMap and have each iteration return a List<Int> but that doesn’t seem as nice as using buildList.

The first order of business is to add(1), seeding the eventual list with the fact that our x register starts at 1 (I forgot this and all my outputs were off by 1 for a while). Then we go through each line of input and no matter what, we’re going to add a 0 to the list. Why? Either this is a noop and there is nothing to do this clock cycle, or it is an addx and the actual addition will not take place until the next clock cycle. If the line does start with “addx”, we’ll parse out the delta and add it to the list as well.

At this point, addInstructions represents the changes in signal, indexed by clock cycle!

But hold on, whats that runningReduce call there? A reduce in Kotlin (and many other functional languages) lets us run through an Iterable (a List<Int> in our case) and do some operations on the items one at a time. We’re given the result of the previous reduction and the next element in the sequence. So if we have a List: [1, 2, 3, 4], and call reduce(Int::plus) on it, we’ll see some additions happen: [1 + 2], [3 + 3], [6 + 4]. The first element being the “carry over” from the last reduction, and the second being the next element in the sequence.

At the end of a reduce we’ve “reduced” the List<Int> down to a single Int.

By contrast, a runningReduce works the same way except it keeps all the intermediate steps! So [1, 2, 3, 4].runningReduce(Int::plus) doesn’t result in a single Int, it gives us a List<Int> with all the steps we’ve taken: [3, 6, 10]. We can use this!

After calling runningReduce and giving it the function reference Int::plus (we could have also done a lambda: { a, b -> a + b }) we convert the register deltas we parsed originally into a “running” actual signal value list.

Isn’t that cool?

⭐ Day 10, Part 1

The puzzle text can be found here.

Because we’ve done the work in the parsing section to get the signals, we’re only tasked with picking out the samples we care about.

// In Day10

private fun List<Int>.sampleSignals(): List<Int> =
     (60 .. size step 40).map { cycle ->
        cycle * this[cycle - 1]
    } + this[19] * 20

Keep in mind that the values in our list are the values at the end of that clock cycle. So element 20 is the size of the signal at the end of cycle 20. For our answer, we want the value at the start of the cycle, so we need to subtract 1 from any cycle value we end up caring about. Sure, we could have added a dummy 0 to the start of the signals list to move everything over one, but I thought that wasn’t all that clear.

To get every 40th element starting from element 60, we set up a range remembering to step by 40, and do the same work. We map the cycle multiplied by the value of that cycle (remembering that we care about the previous value). Then we tack on the value at cycle 20. It turns out that order isn’t important, otherwise we’d have to add it to the head of the list. Either way, don’t forget about cycle 20.

At the end of sampleSignals we have only the signal values we care about and can sum them up for our answer.

// In Day10

fun solvePart1(): Int =
    signals.sampleSignals().sum()

Star earned! Onward!

⭐ Day 10, Part 2

The puzzle text can be found here.

We’ve done all the work we really need to do in Part One. All that’s left to do is print the output to the screen and read the results. I’m not going to go through the effort to write code to interpret the letters - I’ll leave that to you. Reading the results from the console is fine for me. I’m not sure what a visually impaired developer is supposed to do with puzzles like this to be honest.

While we could print the signal out in one function, I want to do it in two because it is easier to explain.

First, we’ll write a function called screen which will convert the signal into which pixels are on or off and return us a List<Boolean>.

// In Day10

private fun List<Int>.screen(): List<Boolean> =
    this.mapIndexed { pixel, signal ->
        (signal-(pixel%40)).absoluteValue <= 1
    }

To determine if a pixel is on, we need to compare it with the signal. If the difference between those two is zero or one, we know the paddle covers that pixel and the pixel is on, otherwise the pixel is off. Because our signal values never go above 40, we need to account for the fact that the pixel value will tell us how far along the current row of output we are. Therefore, we need to mod 40 any pixel values we might receive so the “is this on or not” lines up (the signal values are relative to the row being drawn, not the entire screen).

Next, we’ll write a print function to print our List<Boolean> to the console.

// In Day10

private fun List<Boolean>.print() {
    this.windowed(40, 40, false).forEach { row ->
        row.forEach { pixel ->
            print(if(pixel) '#' else ' ')
        }
        println()
    }
}

We’ll use windowed like we have in the past to break up our list into lists of size 40, sliding over 40 each time, and not worrying about partial lists (there’s a lone pixel at the end in this implementation that we don’t care about). For each row we, iterate and print each pixel if it is on. I’ve chosen to print either “#” or a space, but you can pick whatever you find easier to read.

Remember that at the end of each row, we need a println, or you’ll end up with one single row of output (ask me how I know that).

Running these functions gives us the answer to Part Two!

// In Day10

fun solvePart2(): Unit =
    addInstructions.screen().print()

Star earned! See you tomorrow.

⭐ Day 10, Part 1

⭐ Day 10, Part 2

Further Reading