Advent of Code, Day 15

Day 15 of Advent of Code is here! Where are days 13 and 14? I had a hard time with Part 2 on those, and didn’t have a ton of time to work them through. I will go back to them now and get them up soon. Some of these puzzles are more mathematical challenges than coding challenges, and that’s a muscle I haven’t worked on in quite some time.

See all of my other solutions here. If you’re interested, check out what my colleagues at Slalom are doing with Advent of Code!

Do your best!

I highly encourage you to get through the day’s challenge on your own. Certainly refer to this and other’s examples to help you get through. I would love to hear how you did! Did you find a better approach than I did? Do tell!

Day 15: Rambunctious Recitation

Part I

“In this game, the players take turns saying numbers. They begin by taking turns reading from a list of starting numbers (your puzzle input). Then, each turn consists of considering the most recently spoken number… what will be the 2020th number spoken? ” ref

Before we start, let’s get pull this data in. But wait! There’s no separate data input today, it’s just these few numbers, thankfully:

5,2,8,16,18,0,1

Let’s throw those in an array and get loopin’

var nums = [5,2,8,16,18,0,1,0]
var spokenNums = [...nums]

for(let i = nums.length - 1; i <= 2020; i += 1) {
  var theNum = spokenNums[i]
  var earlierNums = spokenNums.slice(0,-1)
  if(earlierNums.some(s => s === theNum)) {
    var lastIndex = earlierNums.map(s => s === theNum).lastIndexOf(true)
    spokenNums.push(i - lastIndex)
  } else {
    spokenNums.push(0)
  }
}

console.log(spokenNums[2019])

Here’s what we’re doing: (I like part 2 more, but we’ll get to that)

• We added 0 into the array, that’s part of the requirements. If a number was not spoken before, then the next number is 0.
• We load these numbers into a new array spokenNums. This array will collect every spoken number and will be used to find out if the current number was spoken
• Now we loop until we reach 2020 numbers spoken, starting with the last number in the array, the 0
• We grab the current spoken number set it to theNum
• Check for any earlier instances of this number. I am slice()‘ing out the last number, which is the current number, so we only look at all numbers previous to this number.
• We use a some() to find any references to this number
• Then we find the lastIndexOf() this number.
• Then we push this number into the spokenNums array.
• If the number hasn’t been spoken yet, we push a 0 instead
• As we loop, we grab the last number in the array, the last number that was just spoken.
• Finally, we write out the answer in the last index of the array, 2019 (such a better year than 2020!)

Part II

“Given your starting numbers, what will be the 30000000th number spoken?“

Simple enough, go from 2020 to 30,000,000. The above code would’ve taken way too long to run. I didn’t even try, I knew from previous experiences that it was going to be a loooong time. So I had to rethink the approach, and I like this approach MUCH more. It took about 7 minutes to run, which still feels long, but better than hours and days

var nums = [5,2,8,16,18,0,1]
var numIndexes = new Map()

console.log(new Date())
nums.forEach((n, i) => numIndexes.set(n, i))

let theNum = 0
for(let i = nums.length; i <= 30000000 - 2; i += 1) {
  if(numIndexes.has(theNum)) {
    var lastIndex = numIndexes.get(theNum)
    numIndexes.set(theNum, i)
    theNum = i - lastIndex
  } else {
    numIndexes.set(theNum, i)
    theNum = 0
  }
  if(i % 1000000 === 0) console.log(new Date(), i)
}

console.log(theNum)
console.log(new Date())

Here’s what we did

• Right off the bat, we changed the array by dropping the last 0.
• I am converting my array approach to an object a Map(). (THANK YOU Eremiten Annsofi (@annsofip)) Instead of a massive array with 30 million numbers in it, this Map contains MUCH less data AND is much faster than a traditional object. numIndexes will have a parameter for each number spoken, and the value of that parameter will be the last index it was spoken in.
  • Thank you Ermiten for commenting on this post to use a Map. This changed my process from 7mins to 7 seconds. Incredibly faster. Awesome, just awesome.
• Now we loop to 30 million minus 2. I minused two because 1 is due to arrays being 0 based, so always minus 1, and I minus another 1 because I don’t want to process the last number, the last number is the answer.
• As we loop, we check the numIndexes for the number, if it exists, we minus the current index (i) from the last index to get the new theNum and we loop.
• I added a console log in there for every million so I can see it progressing and ensure it wasn’t going to take hours.

How did it go for you?

How did you find the answer on your own? How did you do it? Anything stump you? I’d love to hear how you did! Please comment below! I have also loaded up just the challenge and code from this and my other days on github, you can follow along there too: pretty Git pages or the code in the repo.