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)
}
```

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.