Site icon David Lozzi

Advent of Code, Day 23

David Lozzi
This post is a part of Advent of Code 2020 with JavaScript Series
Advertisements

Day 23 of Advent of Code is here! See all of my other blogged solutions here and my code on Github. If you’re interested, check out what my colleagues at Slalom are doing with their Advent of Code!

Day 23: Crab Cups

Part I

I don’t know why I’m still playing with a crab, I must be lonely. Regardless, let’s play. I need to predict where his cups will be after he follows a pattern for 100 iterations.

My data is super simple: 

389547612

Each number is one cup, so let’s make an array of cups:

const cups = [3,8,9,5,4,7,6,1,2]

After completing Part 2, I would do Part 1 differently, but that’s how we learn. As we continue to develop, keep an open mind that our way isn’t the only way, we press through our challenges, we start to rethink how we do things. We can continually look at our old code and think “yuck, I would do that totally different”. The differences between part 1 and part 2 for many of these days have been like that. It’s a great learning opportunity!

Here I have a function called moveCups which will move the cups around

const moveCups = (cupNumber) => {
  console.log(cupNumber)
  if(loopCount < 100) {
    const rightThree = cups.splice(cups.indexOf(cupNumber) + 1, 3)
    if(rightThree.length < 3) {
      rightThree.push(...cups.splice(0,3 - rightThree.length))
    }
    let destination = cupNumber - 1
    
    let foundIt = false
    while(!foundIt) {
      if(destination <= 0) {
        destination = Math.max(...cups)
        foundIt = true
      }
      const testNumber = cups.indexOf(destination)
      if(testNumber > -1) {
        foundIt = true
      } else {
        destination -= 1
      }
    }
    cups.splice(cups.indexOf(destination) + 1, 0, ...rightThree)
    console.log(cups.join(''))
    loopCount += 1

    let newCupNumber = cups[cups.indexOf(cupNumber) + 1]
    if(!newCupNumber) newCupNumber = cups[0]
    moveCups(newCupNumber)
  }
}

Nothing too fancy in here

moveCups(cups[0])

const [secondHalf, firstHalf] = cups.join('').split('1')
console.log('Final values', `${firstHalf}${secondHalf}`)

I call the moveCups function starting with the first cup. Once it finishes, we create a string starting at cup number 1, and listing all the cup numbers after that. Chances are 1 won’t be at the start of the array, so we have to get the numbers after 1, then get the numbers before 1. Think of 639714528, the answer is 45286397

Part II

Let’s juice this up. What’s the answer have 10 million loops, yea, 10,000,000, when we have 1 million numbers to work with? My current approach in Part 1 would certainly work, but might take days to run, remember Day 10? So I had to do some googling on this to find the best approach and found something called linked lists.

I won’t go too much into it here, I found this blog post very helpful. The long and short of it is: we’re going to work with objects that point to their next cup, not relying on them in order in an array. I also referred to a few other’s day 23 part 2 code to understand how best to implement link lists. I found this code most helpful, thank you lnguyenh!

Using a link list with a Map(), this gets done in about 3 seconds!

The first, the big thing for a link list is this object

class Cup {
  constructor(value) {
    this.value = value
    this.next = null
  }
}

My Cup object has the current value and then points to what is next. Eventually, when we hit the last number, that will have a next of the first cup. Once that connects, we’re basically in a HUGE circle with 1 million cups. There is no start or end.

const data = [3,8,9,5,4,7,6,1,2]

const initialCups = data.map(d => new Cup(d))
let currentCup = initialCups[0]
const lastCup = initialCups[initialCups.length - 1]

Next up we instantiate a few vars:

const cups = new Map()
initialCups.forEach((c, i) => {
  c.next = initialCups[i+1]
  cups.set(c.value, c)
})

One of the cons of using a link list is there is no fast easy method to find data in it. It’s great for iterating, not great for searching. To resolve that we’re going to use a Map() (which we learned in Day 10 is super fast) to store at each cup value that cup. That will let us quickly get a cup by its value, and find its next cup.

We are also setting the next cup for each cup here. So cup 3 will have cup 8 as next, cup 8 will have cup 9, and so on.

let addCup = lastCup
for(let i = initialCups.length + 1; i <= 1000000; i += 1) {
  const aCup = new Cup(i)
  cups.set(i, aCup)
  addCup.next = aCup
  addCup = aCup
}
addCup.next = currentCup

Here we add the rest of the cups, heading up to 1 million. In this loop, we

Finally, we set the last cup set next value to the currentCup, thus completing our 1 million cup circle.

Let’s get looping

for(let i = 0; i < 10000000; i+= 1) {
  i % 1000000 === 0 ? console.log(i) : null
  const nextOne = currentCup.next
  const nextTwo = nextOne.next
  const nextThree = nextTwo.next

  let destinationNumber = currentCup.value
  let foundDestination = false
  while(!foundDestination) {
    destinationNumber -= 1
    if(destinationNumber < 1) destinationNumber = cups.size
    if(
      nextOne.value === destinationNumber || 
      nextTwo.value === destinationNumber || 
      nextThree.value === destinationNumber) continue
    foundDestination = true
  }
  const destinationCup = cups.get(destinationNumber)

  const prevDestinatioNext = destinationCup.next
  const prevThirdCupNext = nextThree.next
  destinationCup.next = nextOne
  nextThree.next = prevDestinatioNext
  currentCup.next = prevThirdCupNext

  currentCup = currentCup.next
}

Once all that looping is done, we can print out the answer

const cupOne = cups.get(1)
const firstCup = cupOne.next
const secondCup = firstCup.next
console.log('Final values', firstCup.value, secondCup.value, '=', firstCup.value * secondCup.value)

Starting with cup 1, we grab the next two cups and multiply their values together for the answer

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.

Series Navigation<< Advent of Code, Day 24 – Black Lives MatterAdvent of Code, Day 22 >>
Exit mobile version