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:
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 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!
Top comments (0)