Rambunctious Recitation

Advent of Code 2020 Day 15

Task: Solve for X where...

X = the Nth number in a growing sequence of spoken numbers

1. N = 2020
2. N = 30000000

Example input

0,3,6

It represents:

• Three turns where each turn that number is spoken

Part 1

1. Writing the rules as pseudocode
2. Visualizing the example input after 10 turns
3. Writing a working algorithm

Writing the rules as pseudocode

For each number
  Perform a turn where that number is spoken

For each turn thereafter
  If the previous turn's number was never spoken before
    Say 0 and end turn
  Else - the previous turn's number has been spoken at least once before
    Calculate the difference between the turn number of when it was most recently spoken - the previous turn's number - and the most recent time it was spoken prior to that
    Say that number and end turn

Visualizing the example input after 10 turns

Input:
0,3,6

Turn 1:
0,

Turn 2:
0,3

Turn 3:
0,3,6

Turn 4:
0,3,6,?
    6<-
-,-
0,3,6,0

Turn 5:
0,3,6,0,?
      0<-
0,-,-
1     4
4-1 = 3
0,3,6,0,3

Turn 6:
0,3,6,0,3,?
        3<-
-,3,-,-
  2     5
5-2 = 3
0,3,6,0,3,3

Turn 7:
0,3,6,0,3,3,?
          3<-
-,-,-,-,3
        5 6
6-5 = 1
0,3,6,0,3,3,1

Turn 8:
0,3,6,0,3,3,1,?
            1<-
-,-,-,-,-,-
0,3,6,0,3,3,1,0

Turn 9:
0,3,6,0,3,3,1,0,?
              0<-
-,-,-,0,-,-,-
      4       8
8-4 = 4
0,3,6,0,3,3,1,0,4

Turn 10:
0,3,6,0,3,3,1,0,4,?
                4<-
-,-,-,-,-,-,-,-
0,3,6,0,3,3,1,0,4,0

10th number is 0

Writing a working algorithm

Split the input into an array of strings
  Coerce each string into a number

For i from the length of the array up to but not including 2020
  Generate one of two numbers:
    1. A positive integer if the most recent number is found elsewhere in the array
    2. -1 if the most recent number is not found elsewhere in the array
  If that number is positive
    Add at the end of the array of numbers the difference between the last location of the most recent number and the second-to-last location of the most recent number
  Else - the number is -1
    Add at the end of the array the number 0

Return the last number in the array

This puzzle helped me learn a new way to leverage JavaScript's multi-purpose method, lastIndexOf().

• Passing a second, optional, argument limits the scope of the search to a subset of the original string or array

So, my algorithm uses this to find the second-to-last index of the most recent number:

let secondToLastIndex = list.lastIndexOf(
  list[list.length - 1], 
  list.length - 2 
)

Part 1: Writing a more performant algorithm

• The algorithm above is fast enough for the first couple thousand numbers spoken
• But with each new number spoken, it must maintain and create near-identical lists of n and n-1 numbers spoken length with each iteration
• That's a lot of unnecessary data to manage

The smarter approach: use memoization

• When determining the next number, we only care about two values for each number previously spoken: last occurrence, and the occurrence prior, if any
• Any and all occurrences before those two are unimportant

Here's a scenario using this new algorithm

Given starting numbers:
1,3,2

Our memo starts as:
1: [1,1]
3: [2,2]
2: [3,3]

We will also keep track of the last number spoken:
2

On the next turn:

Turn 4:
Last number spoken: 2
Look-up 2 in memo: [3,3]
Subtract element 2 from element 1: 3-3 = 0

Is 0 a key in memo? Y/[N]
Add it as a key with value: [turn number, turn number]
                            [4,           4]
Update last number spoken to: 0

Our memo is now:
1: [1,1]
3: [2,2]
2: [3,3]
0: [4,4]

On the next turn:

Turn 5:
Last number spoken: 0
Look-up 0 in memo: [4,4]
Subtract element 2 from element 1: 4-4 = 0

Is 0 a key in memo? [Y]/N
Update it's value to: [turn number, element in location 1]
                      [5,           4]
Update last number spoken to: 0

Our memo is now:
1: [1,1]
3: [2,2]
2: [3,3]
0: [5,4]

On the next turn:

Turn 6:
Last number spoken: 0
Look-up 0 in memo: [5,4]
Subtract element 2 from element 1: 5-4 = 1

Is 1 a key in memo? [Y]/N
Update it's value to: [turn number, element in location 1]
                      [6,           1]
Update last number spoken to: 0

Our memo is now:
1: [6,1]
3: [2,2]
2: [3,3]
0: [5,4]

As this plays out:

• The memo grows occasionally, only when the result of a subtraction creates a number that doesn't exist as a key
• More often, a two-element array is updated with two new values
• Gone is the constantly-growing list of numbers to track, and it's one-element-fewer duplicate

Comparing algorithms:

To determine the 100,000th number spoken

• Algorithm 1 takes a few seconds
• Algorithm 2 takes a few milliseconds

Part 2

• As anticipated, this part is a stress test
• I'm glad I refactored my algorithm to drastically improve performance
• Sadly, even my new algorithm would take ages to generate the correct answer

Unaware of a better-performing algorithm, I looked up how my go-to JavaScript solver, NullDev, solved this puzzle.

How another solver's algorithm works

• There appears to be a clever use of array index as the number spoken and its value as the last (or second-to-last?) time it was spoken
• This creates one large array once, and each iteration performs two look-ups and two assignments
• The example answers are generated within a second!

Create an array of length N where N is the target number spoken
Process the input string into an array of numbers
Initialize a current number to 0
For i from 0 to N - 1
  If i is within the bounds of the input array of numbers
    Set the current number equal to the number at location i in the input array of numbers
    Set the value at the location equivalent to current number in the target number array to: i + 1
  Else - if i is beyond the bounds of the input array of numbers
    Store one of two numbers in a variable, prev:
      Either the number at the location in the target number array that is equivalent to the current number
      Or -1 if that location does not exist
    Update the number at the location in the target number array that is equivalent to the current number to: i
    Update the current number to one of two numbers:
      1. 0, if prev is -1
      2. i - prev, if prev is not -1
Return the current number

Visualizing it helped me better understand how it worked. Especially the setting of either a number or -1 depending on whether the item at the current number index was 0 or any other number.

Since I was able to re-product NullDev's algorithm and better understand after visualizing it, I ran my copy-cat algorithm to generate a correct answer for Part 2.

I'll consider that my reward for writing three algorithms: two of my own, and a third without referencing the source at any point while re-creating it.