Advent of Code 2017 Day 15
Part 1
- 40 million?! Wait, is that a lot?
- Animating an algorithm
- Writing my algorithm
40 million?! Wait, is that a lot?
- Many prior Part 2's ask for some result after millions or billions of iterations
- The trick there is either to find a pattern - since performing that many iterations would take forever - or optimize an algorithm's performance so it can, indeed, perform that many iterations within milliseconds
- This puzzle presents a performance test in Part 1! Or does it?
- 40 million seems like a lot
- But let's say I just wanted to perform some simple operation 40 million times
For i from 0 to 40 million
If i is divisible by 1 million
Print i
Surprisingly, this loop finishes in a web browser in milliseconds!
That was one operation, though:
1 * 40M = 40M
I will likely have to perform several operations to generate the correct answer for Part 1
5 * 40M = 200M
10 * 40M = 400M
20 * 40M = 800M
Yikes! The performance implication of a few operations seems drastic.
Animating an algorithm
The instructions outline most of this, but it helped me to visualize it as a GIF:
Writing my algorithm
- This felt very easy to write
- It is also extremely slow: taking about two minutes to finish
- But, hey...it works!
let [A,B] = [...stream.matchAll(/\d+/g)].map(el => +el[0])
let pairs = 0
for (let i = 0; i < 40000000; i++) {
A = (A * 16807) % 2147483647
B = (B * 48271) % 2147483647
pairs += (A).toString(2).padStart(32,0).slice(-16)
== (B).toString(2).padStart(32,0).slice(-16)
? 1 : 0
}
return pairs
- I extract the two integers from the input as variables
A
andB
- I initialize
pairs
to0
- I run a loop 40M times
- Each time, I update
A
andB
- And increment
pairs
by1
if the last 16 digits of each 0-padded binary string representation of the numbers match - Otherwise, I increment
pairs
by0
, leaving it unchanged
It generates the correct answers for the example input and my puzzle input...eventually!
I do wonder how I could achieve near-instant runtime, though.
Part 2
- Enter: queues
- My working algorithm
Enter: queues
The way I understand it:
Track the number of matching pairs, starting at 0
Track the number of passing values that each generator has given to the judge
While either generator has yet to pass its 5 millionth value to the judge
Continue generating and checking values for pass/fail
If any pass, add them to the appropriate one of two queues being tracked by the judge
Exhaust the judge's queue of accrued values
Check the last 16 bits for an exact match
If a match, increment the number of matching pairs by 1
My working algorithm
- I create and pre-fill two typed arrays, specifically
UInt32Array()
, with 5 million 0s - I track the current location to fill in each one, starting at 0
- I track the number of matching pairs, starting at 0
Do as long as the last number in either array is not 0 (meaning it has been filled with a value that meets the criteria)
Generate the next number for each generator
If the array is not already full, and the number meets that generator's criteria
Set the value at the current location as that number
Increment the value to refer to the next location
For i from 0 up to but not including 5000000
Increment pairs by 1 if the converted-to-binary-and-sliced numbers at location i in each array are a match
Similar to Part 1, my algorithm takes a few minutes to run.
If you'd like, you can watch it run, too:
Regardless of its slowness, it generated the correct answer!
I did it!!
- I solved both parts!
- By writing two very slow, but working algorithms!
- I used a typed array for the...second?...time!
- I got more practice learning the subtle difference between
||
and&&
operators in JavaScript - I made a short GIF that visually depicts the equation described in the instructions
Wow. I'm going in to Day 14 with 18 stars!
This feels incredible!
I'll admit, I'm still prepared for a few puzzles that I'm unable to solve due to their theme (e.g. pathfinding, tree data structures, performance stress tests).
Top comments (0)