15.md

Day 15

Part 1

Each turn, if the previously spoken number was spoken for the first time, say 0; otherwise say how many turns apart the number is from when it was previously spoken. What's the 2020th number spoken?

const input = '0,3,6'
const startingNumbers = input.split(',').map((str) => +str)
const turns = 2020 - startingNumbers.length

const spokenNumbers = Array.from({ length: turns }).reduce(
  (spokenNumbers) => {
    const previousNumber = spokenNumbers[spokenNumbers.length - 1]

    const lastIndex = getLastTurn(spokenNumbers, previousNumber)
    const secondLastIndex = getLastTurn(
      spokenNumbers,
      previousNumber,
      lastIndex - 1
    )

    const nextNumber = secondLastIndex === -1 ? 0 : lastIndex - secondLastIndex
    spokenNumbers.push(nextNumber)
    return spokenNumbers
  },
  [...startingNumbers]
)

console.log(spokenNumbers[spokenNumbers.length - 1])

function getLastTurn(numbers, number, fromIndex = numbers.length - 1) {
  for (let i = fromIndex; i >= 0; i--) {
    if (numbers[i] === number) return i
  }
  return -1
}

Try it out on flems.io

Just some looping. Takes only about 5 milliseconds on my machine with the real puzzle input.

I didn't bother with map(), findIndex() et cetera because they would loop over the arrays unnecessarily much. Actually, I did try one such solution, but running it took about 50 milliseconds on my machine and the readability wasn't that great.

Part 2

Same as Part 1, but what's the 30,000,000th number spoken?

Using console.time() and console.timeEnd(), here's how long it takes on my machine to determine the nth number using the solution from Part 1:

• 10th number: 1ms
• 100th number: 2ms
• 1,000th number: 3ms
• 10,000th number: 30ms
• 100,000th number: 1,800ms

Okay, it's clear that determining the 30,000,000th number would take an eternity.

Instead of looping through the array over and over again, let's keep track of the previous indexes in an object:

const input = '0,3,6'
const startingNumbers = input.split(',').map((str) => +str)
const turns = 30_000_000

const lastTurns = startingNumbers.reduce(
  (turns, number, i) => addLastTurn(turns, number, i + 1),
  {}
)
const previousNumber = startingNumbers[startingNumbers.length - 1]

const spokenNumbers = Array.from({ length: turns }, (_, i) => i + 1)
  .slice(startingNumbers.length)
  .reduce(
    ({ lastTurns, previousNumber }, turn) => {
      const [lastIndex, secondLastIndex] = lastTurns[previousNumber]
      const nextNumber =
        secondLastIndex == null ? 0 : lastIndex - secondLastIndex

      return {
        lastTurns: addLastTurn(lastTurns, nextNumber, turn),
        previousNumber: nextNumber,
      }
    },
    { lastTurns, previousNumber }
  )

console.log(spokenNumbers.previousNumber)

function addLastTurn(turns, number, turn) {
  if (!turns[number]) turns[number] = []
  turns[number].unshift(turn)
  turns[number].length = 2
  return turns
}

flems (turns is set to 30_000 so that opening the page won't freeze your browser.)

Now the performance is better:

• 10th number: 1ms
• 100th number: 2ms
• 1,000th number: 3ms
• 10,000th number: 10ms
• 100,000th number: 35ms
• 1,000,000th number: 300ms
• 10,000,000th number: 4,500ms
• 30,000,000th number: 14,500ms

Not great, but good enough for this puzzle! If I had to improve the performance further, I would probably move the calculations to a Web Worker. It probably wouldn't increase the performance much, but at least the browser/page wouldn't freeze.

What did I learn?

Nothing. 🐧