Crab Cups

Advent of Code 2020 Day 23

Try the Simulator for Part 1

Task: Solve for X where...

X = label numbers of cups M spaces clockwise from cup labeled 1 after being manipulated N times

1. In order, each of M = 8 cup labels - of 9 cups - after N = 100 times
2. In order, each of M = 2 cup labels - of 1000000 cups - after N = 10000000 times - multiplied together

Example input

389125467

It represents

• The single-digit numerical labels on 9 cups arranged clockwise in a circle

Part 1

1. Understanding the order of operations to rearrange cups
2. Writing the beginning of my algorithm
3. Getting it less wrong time and again
4. Getting it right, finally!
5. Building the simulator
6. Being inspired to get it better
7. Getting it right, but better!

Understanding the order of operations to rearrange cups

1. Identify and separate the 3 picked up cups
2. Identify the destination cup
3. Re-insert the picked up cups after the destination cup
4. Identify the new current cup

Writing the beginning of my algorithm

Create an array from the input string
Set the current cup as the item in the first location
Create a new array containing the three picked up cups
Create an empty placeholder for the destination cup
As long as the destination placeholder remains empty
  Search the array of picked up cups for a number equivalent to the current cup number minus a revolving, decreasing value that sits within a range of numbers between 1 and 9 inclusively
    As soon as a number is not found, set it as destination
Mold together a new array from the bits and pieces above: 
  current cup, remaining cups, destination cup, picked up cups
Update current cup to reflect the number to its right
Shift the contents of this new array from beginning to end until the new current cup is at location one

After the last step:
Shift the contents of this new array from beginning to end until the new current cup is 1
Return the array with the first item removed

Getting it less wrong time and again

• I wasn't setting the decrementing value correctly when identifying the destination cup
• I mistakenly assumed I was working with numbers when instead I was working with strings
• I wasn't correctly calculating the remainder when getting the next wrapping value in the circle: I mistakenly was using n % input.length instead of n % (input.length + 1)
• I kept forgetting to find the index of the location one right of the destination cup at which to re-insert the picked up cups

Getting it right, finally!

Set a string as the input
Set current as the first number in the input string
Create a function that accepts a number as input and returns the remainder after dividing that number by the length of the input string
Do 100 times:
  Split the latest input string into an array of strings
    Coerce each string into a number
  Get the location of the new current cup
  Extract three values from the array of strings:
    1. The item at the location one to the right of current
    2. Two to the right of current
    3. Three to the right of current
  Create an empty placeholder for the destination cup
  As long as the destination placeholder remains empty
    Search the array of picked up cups for a number equivalent to the current cup number minus a revolving, decreasing value that sits within a range of numbers between 1 and 9 inclusively - leveraging the function created before the loop
    As soon as a number is not found, set it as destination
  Create a string containing - in order - cup numbers without the three picked up cups
  Split that string into an array of numbers
  Insert into that array - at the location one to the right of where destination is - each of the three picked up cups in order
  Update current cup to reflect the number to its right
  Shift the contents of this new array from beginning to end until the new current cup is at location one - likely one pass to move the first item to the end
  Update the input string to reflect a concatenation of each number in the array

After the 100th time:
Shift the contents of this new array from beginning to end until the new current cup is 1
Return the array with the first item removed

Building the simulator

• My algorithm felt overly literal
• This felt terrible from the point of view of eloquence and conciseness
• But it made building the simulator much easier since I had already built it out of log statements while debugging my algorithm
• I borrowed my own boilerplate code from a few prior simulators: HTML, CSS and JS snippets; interval slider and corresponding event listeners
• I used trial and error to repurpose my for loop into code that didn't run all at once
• Soon enough, I had a working simulator that displayed each move's status much like in the instructional diagrams

Try the Simulator for Part 1

Being inspired to get it better

• As I mentioned above, my algorithm seemed like it was doing too much
• I referenced the solution of my go-to JavaScript solver, NullDev
• Sure enough, there was a marginally simpler way of programming the same overall algorithm as mine

Getting it right, but better!

1. There is no need for a function that calculates a remainder
2. There is no need to ever create an array from the input string or any of its substrings
3. Instead of checking whether the picked up cups contain the next potential destination cup, it's easier to check the remaining cups
4. In that check, destination shouldn't start empty and eventually contain a value; rather, destination should start as 1 less than current and eventually store the value of the first correct cup
5. There will still be a complex series of string methods composed together to 'reassemble' the new input string

It was incredibly helpful having my simulator as a tool to help me debug this updated algorithm.

Set input to the starting string
Do 100 times:
  Set current to the first number in the updated input string
  Create a string with all but three of the numbers from the input string: those three numbers being in the three locations to the right of current
  Set destination to current - 1
  Do until a test returns true
    If destination is 0, set it to 9 - otherwise leave it alone
    If destination is in the string of all-but-three numbers
      Break out of the otherwise never-ending loop
    Else
      Decrement destination by 1
  Update input to be a string comprised of the following numbers:
    1. the remaining numbers in order after current up to and including destination - from the smaller created string
    2. the three numbers in order after current in the fuller input string
    3. the remaining numbers in order after destination - from the smaller created string
    4. current - from the smaller created string

Here's a visualization of this algorithm

Part 2 - nah.

• This challenge seems all about performance and scalability
• I knew my algorithm wouldn't come close to working
• I considered how the only things that change each iteration are the locations of 5 numbers (current, destination and the picked up cups) - regardless of the size of the input string: 9 or 999999 + 1
• I've heard of linked lists: how each node has a value and a pointer to the next node - both of which can change, thereby making rearrangement of entire lists in memory avoidable
• Looking at a few solutions and the reddit thread, this appears to be the data structure used to solve Part 2
• But I'm a bit burned out from Part 1
• So, maybe I'll come back another day