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 iciclelike 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 topmost 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:
2 = 2
3 = 4
4 = 6
5 = 8
6 = 10
7 = 12
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 topmost 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 topmost 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 topmost 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!
Top comments (0)