Computing, Fast and Slow

Part Two gets tougher.

The Problem

The goal of Part Two is to use the same list of changes from Part One and find the first frequency that repeats. It may be necessary to go through the list of changes more than once.

Using the list of Example Data from before

-19
+3
+7
-1
+21

starting from 0, applying the frequency changes one at a time, gets the following frequencies:

0 - 19 = -19
-19 + 3 = -16
-16 + 7 = -9
-9 - 1 = -10
-10 + 21 = 11
(repeat the list)
11 - 19 = -8
-8 + 3 = 5
5 + 7 = 12
12 - 1 = 11

For this list, 11 is the first frequency that occurs twice.

Naturally, the list in the Advent of Code problem is a lot bigger - over 1000 numbers, structured in a way that means the list has to be looped over many times to get a single frequency to repeat. We'll have to write code for this one.

Solution Steps

The solution to this problem has to do the following:

• loop over the list an indefinite number of times
• keep track of which frequencies occur
• detect when a frequency occurs twice

Dealing with Data Storage, Take One

If you're like me, the first thing you think of to store a bunch of data is an array. To find whether an array includes a value, you can use the .includes() method. For this problem, with the amount of data involved, that works! But it's not the best. Here's a solution, with some timing code added so we can see how long it takes.

// sequence is defined as above
console.time('arraySolution')
let currentFrequency = 0
let allFrequencies = []
let sequenceIndex = 0
// the while statement will loop until a frequency repeats
while (!allFrequencies.includes(currentFrequency)) {
  // push into the allFrequencies array to keep track
  // of which frequencies have occurred
  allFrequencies.push(currentFrequency)
  currentFrequency += sequence[sequenceIndex]
  sequenceIndex += 1
  if (sequenceIndex === sequence.length) {
    // restart the list of frequency changes
    // whe you reach the end of the changes array
    sequenceIndex = 0
  }
}
console.log(currentFrequency)
console.timeEnd('arraySolution')

The calls to console.time('arraySolution') and console.timeEnd('arraySolution') provide benchmarking data, meaning at timeEnd what gets printed to the console is the time elapsed since console.time. (The timer name argument is optional in this case; in more complicated code, multiple timers can be run all at once by giving each time / timeEnd pair its own name.)

This solution is valid, but it's slow. On my 2014 MacBook Air, it takes about 14000ms. We can do better.

Dealing with Data Storage, Take Two

Objects can be used to store data, too. Usually, objects have categorical keys and specific values, like

let computer = {
  manufacturer: 'Apple',
  operatingSystem: 'macOS Sierra',
}
let phone = {
  manufacturer: 'Motorola',
  operatingSystem: 'Android 8.1.0',
}

For this problem, there aren't any categories like "manufacturer" to associate with the frequencies we want to store. The solution is to use the frequencies themselves as the keys! Or at least the string versions of them - all keys in JavaScript objects are strings. The value associated with every key in the object can be simply true, because the only thing of interest about a key in this object is that it exists in the object.

The frequencies derived from the example data above (which were -19, -16, -9, etc) could be stored in an object like

let frequencies = { '-19': true, '-16': true, '-9': true }

Once we have an object with frequencies used for keys, looking for a frequency means accessing the key in the object:

frequencies[-16] // true; -16 is a frequency in the object
frequencies[42] // undefined; 42 is not a frequency in the object

Accessing a key in an object like that is much faster than searching through an array with .includes. Here is the object-focused solution:

console.time('objectSolution')
let currentFrequency = 0
let allFrequencies = {}
let sequenceIndex = 0
while (!allFrequencies[currentFrequency]) {
  allFrequencies[currentFrequency] = true
  currentFrequency += sequence[sequenceIndex]
  sequenceIndex += 1
  if (sequenceIndex === sequence.length) {
    sequenceIndex = 0
  }
}
console.log(currentFrequency)
console.timeEnd('objectSolution')

More than half of this code is identical to the array solution. The only changes are

• initializing allFrequencies to an empty object instead of an empty array
• looking for currentFrequency in the while condition with !allFrequencies[currentFrequency] instead of !allFrequencies.includes(currentFrequency)
• adding to the data collection with allFrequencies[currentFrequency] = true instead of allFrequencies.push(currentFrequency)

Even so, using an object instead of an array reduces the algorithm's runtime from ~14000ms to ~20ms.

Dealing with Data, Take three

A third option that didn't occur to me until months later is to use the new(-ish) Set object, which is made for just this kind of thing.

console.time('objectSolution')
let currentFrequency = 0
let allFrequencies = new Set()
let sequenceIndex = 0
while (!allFrequencies.has(currentFrequency)) {
  allFrequencies.add(currentFrequency)
  currentFrequency += sequence[sequenceIndex]
  sequenceIndex += 1
  if (sequenceIndex === sequence.length) {
    sequenceIndex = 0
  }
}
console.log(currentFrequency)
console.timeEnd('objectSolution')

Once again, only three lines need to change compared to the other solutions. They are

• initializing allFrequencies to a new Set
• looking for currentFrequency in the while condition with !allFrequencies.has(currentFrequency)
• adding to the data collection with allFrequencies.add(currentFrequency)

I was surprised to see that even though this problem seems like a perfect use case for a Set, on my machine, the set-based solution took about twice as long as the object-based solution.