Skip to Content

Advent of Code 2017 - Day 13, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 13: 'Packet Scanners'

Posted on

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

You need to cross a vast firewall. The firewall consists of several layers, each with a security scanner that moves back and forth across the layer. To succeed, you must not be detected by a scanner.

By studying the firewall briefly, you are able to record (in your puzzle input) the depth of each layer and therange of the scanning area for the scanner within it, written as depth: range. Each layer has a thickness of exactly 1. A layer at depth 0 begins immediately inside the firewall; a layer at depth 1 would start immediately after that.

For example, suppose you’ve recorded the following:

0: 3
1: 2
4: 4
6: 4

This means that there is a layer immediately inside the firewall (with range 3), a second layer immediately after that (with range 2), a third layer which begins at depth 4 (with range 4), and a fourth layer which begins at depth 6 (also with range 4). Visually, it might look like this:

 0   1   2   3   4   5   6
[ ] [ ] ... ... [ ] ... [ ]
[ ] [ ]         [ ]     [ ]
[ ]             [ ]     [ ]
                [ ]     [ ]

Within each layer, a security scanner moves back and forth within its range. Each security scanner starts at the top and moves down until it reaches the bottom, then moves up until it reaches the top, and repeats. A security scanner takes one picosecond to move one step. Drawing scanners as S, the first few picoseconds look like this:

Picosecond 0:
 0   1   2   3   4   5   6
[S] [S] ... ... [S] ... [S]
[ ] [ ]         [ ]     [ ]
[ ]             [ ]     [ ]
                [ ]     [ ]

Picosecond 1:
 0   1   2   3   4   5   6
[ ] [ ] ... ... [ ] ... [ ]
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]

Picosecond 2:
 0   1   2   3   4   5   6
[ ] [S] ... ... [ ] ... [ ]
[ ] [ ]         [ ]     [ ]
[S]             [S]     [S]
                [ ]     [ ]

Picosecond 3:
 0   1   2   3   4   5   6
[ ] [ ] ... ... [ ] ... [ ]
[S] [S]         [ ]     [ ]
[ ]             [ ]     [ ]
                [S]     [S]

Your plan is to hitch a ride on a packet about to move through the firewall. The packet will travel along the top of each layer, and it moves at one layer per picosecond. Each picosecond, the packet moves one layer forward (its first move takes it into layer 0), and then the scanners move one step. If there is a scanner at the top of the layer as your packet enters it, you are caught. (If a scanner moves into the top of its layer while you are there, you are not caught: it doesn’t have time to notice you before you leave.) If you were to do this in the configuration above, marking your current position with parentheses, your passage through the firewall would look like this:

Initial state:
 0   1   2   3   4   5   6
[S] [S] ... ... [S] ... [S]
[ ] [ ]         [ ]     [ ]
[ ]             [ ]     [ ]
                [ ]     [ ]

Picosecond 0:
 0   1   2   3   4   5   6
(S) [S] ... ... [S] ... [S]
[ ] [ ]         [ ]     [ ]
[ ]             [ ]     [ ]
                [ ]     [ ]

 0   1   2   3   4   5   6
( ) [ ] ... ... [ ] ... [ ]
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]


Picosecond 1:
 0   1   2   3   4   5   6
[ ] ( ) ... ... [ ] ... [ ]
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]

 0   1   2   3   4   5   6
[ ] (S) ... ... [ ] ... [ ]
[ ] [ ]         [ ]     [ ]
[S]             [S]     [S]
                [ ]     [ ]


Picosecond 2:
 0   1   2   3   4   5   6
[ ] [S] (.) ... [ ] ... [ ]
[ ] [ ]         [ ]     [ ]
[S]             [S]     [S]
                [ ]     [ ]

 0   1   2   3   4   5   6
[ ] [ ] (.) ... [ ] ... [ ]
[S] [S]         [ ]     [ ]
[ ]             [ ]     [ ]
                [S]     [S]


Picosecond 3:
 0   1   2   3   4   5   6
[ ] [ ] ... (.) [ ] ... [ ]
[S] [S]         [ ]     [ ]
[ ]             [ ]     [ ]
                [S]     [S]

 0   1   2   3   4   5   6
[S] [S] ... (.) [ ] ... [ ]
[ ] [ ]         [ ]     [ ]
[ ]             [S]     [S]
                [ ]     [ ]


Picosecond 4:
 0   1   2   3   4   5   6
[S] [S] ... ... ( ) ... [ ]
[ ] [ ]         [ ]     [ ]
[ ]             [S]     [S]
                [ ]     [ ]

 0   1   2   3   4   5   6
[ ] [ ] ... ... ( ) ... [ ]
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]


Picosecond 5:
 0   1   2   3   4   5   6
[ ] [ ] ... ... [ ] (.) [ ]
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]

 0   1   2   3   4   5   6
[ ] [S] ... ... [S] (.) [S]
[ ] [ ]         [ ]     [ ]
[S]             [ ]     [ ]
                [ ]     [ ]


Picosecond 6:
 0   1   2   3   4   5   6
[ ] [S] ... ... [S] ... (S)
[ ] [ ]         [ ]     [ ]
[S]             [ ]     [ ]
                [ ]     [ ]

 0   1   2   3   4   5   6
[ ] [ ] ... ... [ ] ... ( )
[S] [S]         [S]     [S]
[ ]             [ ]     [ ]
                [ ]     [ ]

In this situation, you are caught in layers 0 and 6, because your packet entered the layer when its scanner was at the top when you entered it. You are not caught in layer 1, since the scanner moved into the top of the layer once you were already there.

The severity of getting caught on a layer is equal to its depth multiplied by its range. (Ignore layers in which you do not get caught.) The severity of the whole trip is the sum of these values. In the example above, the trip severity is 0*3 + 6*4 = 24.

Given the details of the firewall you’ve recorded, if you leave immediately, what is the severity of your whole trip?

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.

  1. At time 0, the scanner is at slot 0.
  2. At time 1, the scanner is at slot 1.
  3. At time 2, the scanner is at slot 2.
  4. At time 3, the scanner is at slot 1 (again).
  5. 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:

  1. At time 0, the scanner is at slot 0.
  2. At time 1, the scanner is at slot 1.
  3. At time 2, the scanner is at slot 2.
  4. At time 3, the scanner is at slot 3.
  5. 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

This section on the Advent of Code site is massive. I’m leaving a lot out because I feel I’m already stretching a bit by including all of part one!

Now, you need to pass through the firewall without being caught - easier said than done.

You can’t control the speed of the packet, but you can delay it any number of picoseconds. For each picosecond you delay the packet before beginning your trip, all security scanners move one step. You’re not in the firewall during this time; you don’t enter layer 0 until you stop delaying the packet.

In the example above, if you delay 10 picoseconds (picoseconds 0 - 9), you won’t get caught:

<Huge Example Omitted>

Because all smaller delays would get you caught, the fewest number of picoseconds you would need to delay to get through safely is 10.

What is the fewest number of picoseconds that you need to delay the packet to pass through the firewall without being caught?

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!

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 13.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Spybreak!, by Propellerheads.