DEV Community

Cover image for Packet Scanners
Robert Mion
Robert Mion

Posted on

Packet Scanners

Advent of Code 2017 Day 13

Part 1

  1. Intimidated at first
  2. Then, intrigued
  3. Finding a pattern
  4. Using the pattern
  5. Writing my algorithm
  6. 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]
                [ ]     [ ]
Enter fullscreen mode Exit fullscreen mode

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

#############
#...B.......#
###B#C#.#D###
  #A#D#C#A#
  #########
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

And the example diagram:

 0   1   2   3   4   5   6
[S] [S] ... ... [S] ... [S]
[ ] [ ]         [ ]     [ ]
[ ]             [ ]     [ ]
                [ ]     [ ]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Interesting:

2 = 2
3 = 4
4 = 6
5 = 8
6 = 10
7 = 12
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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!
Enter fullscreen mode Exit fullscreen mode

The arithmetic and algorithm play out like this:
Part 1 arithmetic

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

Testing my algorithm

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

Part 2

  1. I was close!
  2. My pattern helps here, too!
  3. 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
Enter fullscreen mode Exit fullscreen mode
  • Where ? is the magic number

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

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
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (0)