DEV Community

Cover image for Dueling Generators
Robert Mion
Robert Mion

Posted on

Dueling Generators

#adventofcode #algorithms #computerscience #programming

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

Surprisingly, this loop finishes in a web browser in milliseconds!

That was one operation, though:

1 * 40M = 40M
Enter fullscreen mode Exit fullscreen mode

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

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:
The operations in each iteration

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

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

Similar to Part 1, my algorithm takes a few minutes to run.

If you'd like, you can watch it run, too:
My algorithm processing in real-time

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)