Advent of Code, Day 23

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

• Right off the bat, let’s get the next three cups that are going to move. I’m splice()‘ing these out of my main array as we are moving them. I’m storing these in rightThree.
  • If we’re at the end of the array, we have to loop back to the start to get the full 3 items.
• Now we have to find the destination cup to place these three after. We loop through looking for the destination by removing 1 from the current cup number.
  • If we hit 0, lets start on the far right of the array and keep going
• Now we use splice() to insert the rightThree back into the array after the destination cup.
• We then grab the next cup in the array and do it again, for 100 times

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:

• initialCups is an array of the data object mapped to our Cup object. All of their next will be null since we did set them yet
• currentCup will start with the first cup in the array. This variable will be changed to the current cup for each loop we do
• lastCup grabs the last cup, since we’re going to add more cups after that, we need to know who’s last

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

• create a new cup for the number we’re on
• we set this number to this cup in the cups Map
• we set the next of the previous cup to this cup
• then we set the previous cup to this cup for the next loop

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
}

• Our loop will run 10 million times and then stop.
  • I initially kept part 1’s function moveCups and looped it, recursively. This crashed after about 7,000 runs because my call stack filled up. There was no need to do it recursively, it’s just a loop…
• We grab the next three cups. Here we grab the next cup from the currentCup, then grab that cup’s next, and grab that cup’s next.
  • I’m already liking the link list, it’s very sequential and clean, no indexes, counters or numbers to fumble through
• Next we find the destination. We grab the current cup’s value and start removing 1 from that until we find a valid number
  • If the destination is less than 1, we loop back to the start and keep searching for a valid number
  • I check the three cups we pulled out. If these match, just move to the next number. continue allows us to skip the rest of the code in our while and run the next iteration
  • Finally, if the above to pass, we have our destination number.
• Next we grab the destinationCup
• This next block inserts the cup into their location.
  • Quick picture of what’s going on. Thinking of 389547612, we want to take 895 and move it to after 2. 2’s next is 3. You can see everyone else’s next clearly. Once we’re done, it should look like 347612895, where 5’s next is 3. Got it?
  • We grab the destinationCup and nextThree (the last cup moving) next values and save them for a moment.
  • Then we set the destinationCup next to the first cup we moved, nextOne
  • We set the third cups next to the previous destintation next value we just saved
  • Finally, we update the currentCup so its next is now what was after the third cup we moved
• Finally we set the currentCup to its next and do it all over again… ten million times

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.