Day 13: Packet Scanners

Take a look at today’s challenge text. The description is a little complicated on the first read through, but the diagrams help to clarify the challenge, and what you have to do in order to solve it.

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.) The severity of getting caught on a layer is equal to its depth multiplied by its range.

The example of each scanner, S, going up and down each layer of the firewall is repeated below:

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]

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

For the first part of the challenge we need to figure out when we get caught by the scanner and keeping a track of the cumulative severity. In order to do this we need to come up with the formula for figuring out where the scanner will be in the layer for a given time offset, or more specifically, whether the scanner will be in the first layer (‘range’) of each level in the firewall.

We can do this by figuring out how many steps it takes to take the scanner from the top, to the bottom and back to the top again.

The formula to determine the steps is (2 * n) - 2 or 2 * (n - 1). Armed with this we can fire up a Q console and get to work.

Solving Part 1

As usual, we have been given an answer for the example input, 24, so let’s work towards that before tackling our input.

In order to model the layers, we can use a list of numbers, each number representing the depth of that layer. We can represent the gaps in the layers with the null long, 0N.

If we take the example input and combine with a rotated diagram, we get the following:

0: 3   [ ][ ][ ]     layer 0 (first layer) has length of 3
1: 2   [ ][ ]        layer 1 has length of 2
-  -   ...           there is no layer 2, so null
-  -   ...           there is no layer 3, so null
4: 4   [ ][ ][ ][ ]  layer 4 has length of 4
-  -   ...           there is no layer 5, so null
6: 4   [ ][ ][ ][ ]  layer 5 has length of 4

…which translates to the following list in Q

3 2 0N 0N 4 0N 4

We can save this as f for firewall:

q)f:3 2 0N 0N 4 0N 4
q)f
3 2 0N 0N 4 0N 4

We can then apply the 2 * (n - 1) formula to this list which will give us the number of steps required for the scanner to be at the top of the firewall… Or to rephrase this, by performing a modulo operation we can determine whether or not the scanner is at the top of the firewall for a given step.

q){2 * (x - 1)} f
4 2 0N 0N 6 0N 6

Save the result as g (simply because ‘g’ comes after ‘f’ in the alphabet):

q)g:{2 * x - 1} f
q)g
4 2 0N 0N 6 0N 6

There are 7 layers to the example firewall, only 4 of them real. If we start at the left and step through each layer, the step number will increase by 1 for each step we take. This means that by the 7th layer we will be at step 6. Aligning the firewall steps against the steps we take as we go through the firewall we get the following:

4  2 0N 0N  6 0N  6 / steps required until scanner in 1st layer
0  1  2  3  4  5  6 / layers (also steps taken to reach layer)

If we perform the modulo operation with the list 0..6 with 4 2 0N 0N 6 0N 6, we get the following:

q)0  1  2  3  4  5  6 mod g
0 1 0N 0N 4 0N 0

The indices where this list is 0 are the indices where we were caught by the scanner, we can use the equality operator, = to see this more clearly

q)0=0  1  2  3  4  5  6 mod g
1000001b

Adding the where keyword will give us the indices themselves:

q)where 0=0  1  2  3  4  5  6 mod g
0 6

In order to get the severity score, we need to multiply the scanners size (‘depth’) and what level it is (‘range’). The range is equal to its position in the list, so we can save this as variable w, and then we need to multiply by the scanner sizes - which are stored in f.

q)w:where 0=0  1  2  3  4  5  6 mod g

We can pull out the scanners we are interested in by indexing into f at w:

q)f w
3 4
q)f[w] / square notation
3 4

Multiplying f[w] by w gets us:

q)f[w]*w
0 24
q)w*f w / Q developers prefer to omit brackets when possible
0 24

and performing the sum operation on this give us an answer that matches the example solution:

q)sum w*f w
24

Now we need to parse our puzzle input and get our first star.

q)read0 `:input/13.txt
"0: 3"
"1: 2"
"2: 4"
"4: 6"
"6: 5"
"8: 6"
"10: 6"
"12: 4"
..

We have two lists of numbers, the first is the scanner’s ‘range’ and the second is the scanner’s ‘depth’. We can split the lines using vs in a couple of different ways.

q)(": " vs) each read0 `:input/13.txt / brackets and each
,"0" ,"3"
,"1" ,"2"
,"2" ,"4"
,"4" ,"6"
,"6" ,"5"
,"8" ,"6"
"10" ,"6"
"12" ,"4"
..
q)": "vs/:read0 `:input/13.txt / no brackets and each-right
,"0" ,"3"
,"1" ,"2"
,"2" ,"4"
,"4" ,"6"
,"6" ,"5"
,"8" ,"6"
"10" ,"6"
"12" ,"4"
..

We can then use the big-J cast to convert these lists to longs:

q)"J"$": "vs/:read0 `:input/13.txt
0  3
1  2
2  4
4  6
6  5
8  6
10 6
12 4
..

.. and then flip to get two long lists, rather than many tuples

q)flip "J"$": "vs/:read0 `:input/13.txt
0 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 52 54 56 58 60 62 64 66 68 70 72 80 82 84 86 90 96 98
3 2 4 6 5 6 6  4  8  8  9  8  6  14 12 10 12 8  10 8  8  12 12 12 12 14 14 12 12 12 12 14 14 14 14 14 14 18 14 20 14 17 20 24

Save as i for input:

q)i:flip "J"$": "vs/:read0 `:input/13.txt

The first of these lists is the range, the last is the depth. In order to represent our firewall as a list, with nulls for gaps, we can start off with an empty list of nulls, and then assign the depths to the correct ranges. Due to the gaps in the firewall, the length of the firewall is 1 greater than the last element in the first list.

q)(1 + last first i)#0N / generate our list of nulls
0N 0N 0N 0N 0N 0N 0N 0N 0N 0N 0N 0N 0N 0N ..

We can do this as a one- or two-step operation:

// multi-step
q)f:(1 + last first i)#0N / assign it to variable f
q)f[first i]:last i       / fill in depths at ranges
q)f                       / admire our handiwork
3 2 4 0N 6 0N 5 0N 6 0N 6 0N 4 0N 8 0N 8 ..

// single-step
q)f:@[(1 + last first i)#0N;first i;:;last i] / apply assignment of last i at indices first i
q)f                                           / admire our handiwork
3 2 4 0N 6 0N 5 0N 6 0N 6 0N 4 0N 8 0N 8 ..

Now to retrace our earlier steps. Generate the modulo list and save as g:

q)g:{2*x-1}f

Rather than hard-coding the 0..n range, we can count the length of g and use the til operator to generate the range for us:

q)til count g
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..

Perform the modulo:

q)(til count g) mod g
0 1 2 0N 4 0N 6 0N 8 0N 0 0N 0 0N 0 0N 2 ..

… check for equality with 0

q)0=(til count g) mod g
100000000010101000000000000000000000000000001000000010000000000000000000000000000000000000000000000b

…extract indices where true

q)where 0=(til count g) mod g
0 10 12 14 44 52

…save the indices as w

q)w:where 0=(til count g) mod g

…multiply by depths

q)f[w]*w:where 0=(til count g) mod g
0 60 48 112 528 728

and finally sum to get today’s first star!

q)sum f[w]*w:where 0=(til count g) mod g
1476

Solving Part 2

Today is another lucky day, Topaz has been kind to us; we need to determine the lowest offset that will result in our packet making its way through the firewall - or to put it another way, we need to iterate until we find a delay that results in a severity of zero.

Let’s set g back to the example:

q)f:3 2 0N 0N 4 0N 4
q)f
3 2 0N 0N 4 0N 4
q)g:{2 * x - 1} f
q)g
4 2 0N 0N 6 0N 6

For Part 1, we were starting with a delay of 0. This had a non-zero severity.

q)sum f[w]*w:where 0=(til count g) mod g
24

We do not care what the severity is, we just care whether it is zero or not. This means we can simplify the statement:

q)0=(til count g) mod g     / where zero matches the list
1000001b
q)any 0=(til count g) mod g / are there any matches?
1b

In order to simulate a delay of 1 (picosecond), we can add 1 to the argument being mod‘d:

q)(1+til count g) mod g
1 0 0N 0N 5 0N 1
q)0=(1+til count g) mod g
0100000b
q)any 0=(1+til count g) mod g
1b

To generalise this we can wrap everything in a lambda, and pass the ‘delay’ in:

q){[delay] any 0=(delay+til count g) mod g } / explicit argument
q){ any 0=(x+til count g) mod g }            / implicit argument

We can keep incrementing until the result is false (0b):

q){ any 0=(x+til count g) mod g } 2
1b
q){ any 0=(x+til count g) mod g } 3
1b
q){ any 0=(x+til count g) mod g } 4
1b
..
q){ any 0=(x+til count g) mod g } 9
1b
q){ any 0=(x+til count g) mod g } 10 / at delay 10, no scanners are in position 0
0b

That was fairly tedious to do by hand, and judging by the size of our input, we better come up with a programmatic solution. We can use the overloaded over function to iterate until a condition is met: {function}/[{condition};initial value]

An example of listing all numbers from 1 to 10 with over used in this way:

q){ x + 1 }/[{x < 10};1]
10
q){ x + 1 }\[{x < 10};1]
1 2 3 4 5 6 7 8 9 10

In the above example, we initialise x as 1 and the left function { x + 1 } is called until the right function { x < 10 } no longer yields ‘true’.

For our challenge, we don’t want to check whether x is less than 10, we want to check whether {any 0=(x+til count g) mod g} is true, and keep going until it is false:

q){ x + 1 }/[{ any 0=(x+til count g) mod g };1]
10

The only thing left to do is to swap out g for our real input and collect our second star:

q)f:@[(1 + last first i)#0N;first i;:;last i]   / reset f
q)g:{2 * x - 1} f                               / reset g
q){ x + 1 }/[{ any 0=(x+til count g) mod g };1] / this will take a few seconds
3937334

Complete Solution To Day 13

My full solution for Day 13 is shown below. The only change over what has been written in this post is that rather than incrementing by 1, I am starting at zero incrementing by 2 - this is because my input has a scanner of size 2, which means it will always be at position 0 when the delay is an odd number - so there is no point checking them - this also makes the solution run in half the time!