Dueling Generators

Advent of Code 2017 Day 15

Part 1

1. 40 million?! Wait, is that a lot?
2. Animating an algorithm
3. 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 and B
• I initialize pairs to 0
• I run a loop 40M times
• Each time, I update A and B
• And increment pairs by 1 if the last 16 digits of each 0-padded binary string representation of the numbers match
• Otherwise, I increment pairs by 0, 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

1. Enter: queues
2. 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).