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
- In order, each of M = 8 cup labels - of 9 cups - after N = 100 times
- 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
- Understanding the order of operations to rearrange cups
- Writing the beginning of my algorithm
- Getting it less wrong time and again
- Getting it right, finally!
- Building the simulator
- Being inspired to get it better
- Getting it right, but better!
Understanding the order of operations to rearrange cups
- Identify and separate the 3
picked up
cups - Identify the
destination
cup - Re-insert the picked up cups after the destination cup
- 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 ofn % (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
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!
- There is no need for a function that calculates a remainder
- There is no need to ever create an array from the input string or any of its substrings
- Instead of checking whether the picked up cups contain the next potential destination cup, it's easier to check the remaining cups
- 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
- 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
Top comments (0)