Robert Mion

Posted on Jul 31, 2022

Packet Scanners

#adventofcode #algorithms #computerscience #programming

Advent of Code 2017 Day 13

Part 1

Intimidated at first
Then, intrigued
Finding a pattern
Using the pattern
Writing my algorithm
Testing my algorithm

Intimidated at first

When skimming the instructions, my eye caught this diagram:

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

I was reminded of 2021 Day 23: Amphipod's diagrams:

#############
#...B.......#
###B#C#.#D###
  #A#D#C#A#
  #########

The similarities?

The icicle-like structure
Letters occupying spaces at any point vertically within an icicle

Then, intrigued

After reading the instructions, I realized this puzzle isn't nearly as complicated, thankfully
In fact, I think finding the answer will just take some pattern identification using arithmetic and the modulo operator

Finding a pattern

Using the example input:

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

And the example diagram:

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

I want to calculate the cycles at which, for any given range, the scanner occupies the top-most cell:

Range  Occupied         Cycle
2      0,2,4,6,8    2
3      0,4,8,12,16  4
4      0,6,12,18    6
5      0,8,16,24    8
6      0,10,20,30,40    10
7      0,12,24      12

Interesting:

How might I calculate the right number from the left?

(left - 1) * 2 = right

(2 - 1) * 2 = 2
(3 - 1) * 2 = 4
(4 - 1) * 2 = 6
(5 - 1) * 2 = 8
(6 - 1) * 2 = 10
(7 - 1) * 2 = 12

Cool!

Now, how can I determine whether the scanner will occupy a top-most cell at the same time as my packet?

Using the pattern

If the remainder after dividing the depth by double one less than the range is 0
  Caught!
Else
  Unseen!

The arithmetic and algorithm play out like this:

I really hope this expands to work on my puzzle input.

Writing my algorithm

Split the input at each newline character into an array of strings

For each string
  Accumulate a sum, starting at 0
    Extract the depth and range from each string
      Use the pattern to identify when the packet is caught
      If caught, increment the sum by the product of the depth and range

Return the accumulated sum

I'm impressed I solved this in under five lines of code.

I used split(), reduce(), map(), a ternary operator and array destructuring assignment:

input.split('\n').reduce((acc,curr) => {
    let [depth, range] = curr.split(': ').map(Number)
    acc += depth % ((range - 1) * 2) == 0 ? (depth * range) : 0
    return acc
  }, 0)

Testing my algorithm

It worked on the example input!
It worked on my puzzle input!

Part 2

I was close!
My pattern helps here, too!
Almost quitting before I generate the correct answer

I was close!

I thought Part 2 would ask:

How few picoseconds would be necessary for the packet to move safely across the firewall

I assumed the packet could start and stop...kind of like in Frogger.

But Part 2 poses an even more interesting challenge:

How many picoseconds is the smallest amount of time that must pass before the packet can move without stopping safely across the firewall?

My pattern helps here, too!

After some careful analysis, I noticed that the answer for the example input, 10, is the smallest number that satisfies this condition:

When is the first time all scanners won't be in the top-most position by the time the packet reaches their patrolled layer?

The formula is:

when (depth + ?) % ((range - 1) * 2) is not 0

Where ? is the magic number

Starting at 0 and working upward, my algorithm works like this:

The example is intentionally deceitful, though.

Almost quitting before I generate the correct answer

My algorithm uses a for loop with an arbitrary maximum
Since the example answer was 10, I started mine at 100 figuring it wouldn't be less than that

For i from 1 up to and including 100
  Perform the pattern on each depth and range using i to increment the depth
  If every scanner is not in the top-most position
    Print i

Increasing the maximum number:

100 - nothing prints
1000 - nothing prints
10000 - nothing prints
100000 - nothing prints

Was my pattern a lucky coincidence when used on the example?

The fewest number of picoseconds can't be this high...can it?!

Increasing the maximum number:

1000000 - nothing prints
10000000 - A few numbers print!

The first number to print was a few hundred thousand below 4M.

It was the correct answer!

I did it!!

I solved both parts!
I identified an equation that helped me solve Part 1 without building a simulator...
...and enabled me to solve Part 2, because with the simulator I planned to build, I never would have attempted each millions of numbers manually!

Why no simulator?

Before solving Part 1, I intended to build a simulator.
After solving Part 2, I decided not to.
Although it may be fun to build and interact with, I'm more proud that I didn't need one to solve this puzzle.
So, no simulator...because I didn't need one!

DEV Community