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

On Day 13 we’ll learn when to sit down and do the math, and when to let the computer do it for you. 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 13, Part 1

The puzzle text can be found here.

This problem reminds me a lot of Advent of Code 2016, Day 15 - Timing is Everything . Let’s get parsing the input out of the way and then we’ll talk about how to think about the problem. I made a Layer data class rather than use a Pair<Int,Int> (because we’ll add some functionality to the layer later).

data class Layer(val depth: Int, val range: Int)

private val layers: List<Layer> = parseInput(input)

private fun parseInput(input: List<String>): List<Layer> =
    input
        .map { it.split(": ") }
        .map { Layer(it[0].toInt(), it[1].toInt()) }

After reading the instructions over carefully, it occurred to me that the fact that the scanners go up and down would be confusing. I didn’t want to have to keep track of where each scanner was, or if it were coming or going. Especially since I only care if it’s in the very top slot. In order to make things simpler, let’s pretend that ranges are 2x longer and just cycle back around to zero. This makes the math work out better because we can use a modulus calculation to figure out where a scanner is given a time.

To figure out the calculation, let’s take a simple example where our range is 3.

At time 0, the scanner is at slot 0.
At time 1, the scanner is at slot 1.
At time 2, the scanner is at slot 2.
At time 3, the scanner is at slot 1 (again).
At time 4, the scanner is at slot 0 (again).

Now, if we stretch that 3 to a 6, we’ll be off by one because we would effectively stay in slot 2 (point 3 above) twice. So we have to subtract one and then double our range length. So, (3-1)*2 = 4 in our case. And then, we can picture it like this:

At time 0, the scanner is at slot 0.
At time 1, the scanner is at slot 1.
At time 2, the scanner is at slot 2.
At time 3, the scanner is at slot 3.
At time 4, the scanner loops back to slot 0.

Same number of ticks of the clock, but the math just works out easier. If we’re in slot 0 at any time, we’re caught, otherwise we’re not. Given this information, we can write a nice quick function to determine if we’re caught. We’ll modify our Layer to answer this question for us, as well expose a property to tell us the severity if we do get caught:

data class Layer(private val depth: Int, private val range: Int) {
    fun caughtAt(time: Int): Boolean =
        (time + depth) % ((range - 1) * 2) == 0

    val severity: Int = 
        depth * range
}

I’m accounting for time here because I’ve read ahead and we need it for the next part. For now, we only care about time 0, so it doesn’t impact our calculation at all. I felt it was easier to just account for it now and explain this than to refactor it again (and rename it) later.

See? Modulus to the rescue again. All we need to do now is figure out what the cost is for any rows where we’re caught:

fun solvePart1(): Int =
    layers
        .filter { it.caughtAt(0) }
        .sumBy { it.severity }

Our solution sums up the severity for the layers where we’re caught if we start at time 0. Pretty easy, huh? All that hard work earns us a start which put us at the half way point for Advent of Code 2017! Take a deep breath, celebrate a bit, we’re moving on.

⭐ Day 13, Part 2

The puzzle text can be found here.

I suspect that if I took enough time I’d find some handy shortcut where I could just calculate the answer based on the length of the ranges. Given we already wrote all the code we need to solve this, let’s just run it and see what happens.

fun solvePart2(): Int =
    generateSequence(0, Int::inc)
        .filter { time ->
            layers.none { it.caughtAt(time) }
        }
        .first()

Don’t worry, I’ll explain. We’re going to generate a sequence of integers representing time, and keep trying them against our set of layers until we find one where we don’t get caught. This turns out to run in about 125ms for me, so I’m kind of glad I didn’t spend a day of my life figuring out the math.

Let’s take a detour and look at another implementation of this that’s much slower, to illustrate a point:

// Slow version!
fun solvePart2Slowly(): Int =
    generateSequence(0, Int::inc)
        .filterNot { time ->
            layers.map { it.caughtAt(time) }.contains(true)
        }
        .first()

More or less the same thing, right? Find a set of layers where we don’t get caught. It turns out that this version takes about 20x longer to execute than the code above! Why? The code above has that none call, which will stop looking at layers if we get caught early. Why go through 100 layers when we get caught on the 3rd onle? That time sure does add up, especially when we’re waiting around for nearly 4 million picoseconds!

Another tricky thing to watch out for is getting caught at layer 0. Since that would give us a severity of 0, we can’t just calculate the total severity for the set of layers and hope it adds up to 0 or we’ll get false negatives.

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

13 days and we’ve earned 26 stars with 24 left to go! Over half way!

⭐ Day 13, Part 1

⭐ Day 13, Part 2

Further Reading