Advent of Code 2021 Day 25

Solution visualization

How did I make this? Find out at the end!

Solve for X where X equals...

• The first step on which no sea cucumbers move

Meaning X must be...

• An integer greater than 0

That's our output. What's our input?

• A multi-line string
• Where each line consists of a combination of these three characters: . > v

What does our input represent?

• A rectangular area of locations
• Filled with east- > and south-moving v critters
• . represent empty locations

What happens each step?

• East- and south-moving critters move according to their constraints

What are their constraints?

• To move, the next space in their respective direction must be empty .
• When at an edge, the next space is the location at the opposite edge
• East moves first. Then south moves.

Initial thoughts on a correct algorithm

• A while loop that runs forever, until something inside triggers a break...since we're hunting for an unknown time designating the end of movement
• Two iterations through each location: once to progress east-moving critters, then again to progress south-moving critters
• A variable to track the whether any critters moved each loop
• We've arrived at our answer when an iteration through the while loop ends with the number of moves equaling 0

What was the most eloquent solution I found on Github and Youtube?

• JavaScript solver NullDev's solution seems concise, readable, and efficient
• Also, a near identical solution from another JavaScript solver Totto16

Compelling elements from their code solutions

• Saving the moves as [[">", 0, 1], ["v", 1, 0]] to avoid redundant code when looping
• Using a do-while loop with a falsifiable condition representing whether any moves occurred - instead of using while(True) and a break somewhere in the loop
• A do block with the following structure:

Increment a steps counter by 1
Reset a moves tracker to false
Loop twice, once for each direction (east and south)
  Save a copy of the input's current state
  For each row in the grid
    For each cell in this row
      Check the following, referencing the saved legend of moves, and short-circuit if any are false:
        Does the cell value in the copied grid match the current direction?
        Is the value in the next right-most or south-most cell in the copied grid empty?
        Update moves tracker to true
        Update the original grid's next right-most or south-most cell to the current cell's value
        Update the current cell's value to empty

Coding tricks that I'll remember

• Using the remainder operator % with the current position and an array's length to compare the values of the first index and the last index. In other words, how to eloquently wrap back around an array
• Also, using short-circuiting && to succinctly perform compounded operations...where each one would have otherwise been in a nested 'if' block

Here's my code

• Feel free to fork it and use it to help you learn

Close, but fell short, of a more efficient algorithm

• Why waste looping through each cell in the grid twice...
• ...when all that matters are the cells occupied by critters?
• As long as we know where each critter starts, and how and in what order they move...
• ...we should only need to loop through a set of coordinates referencing the location of each critter...
• ...update that location when a critter moves, or leave the same when it is blocked...
• ...and stop whenever no coordinates are updated

Save an ordered combination of each set of locations, encoding the character, row and column
Loop through the set, tracking the number of iterations until nothing moves
  Decode the current item
  Determine the coordinate of the next location
  Check a copy of the set, which only encoded each location
    If the next location isn't occupied
      Do an in-place update of current item to reflect its new coordinate
      Flag that there was a move
Return the iteration tracker's value

Sadly, after much confusion and struggle, I only got my implementation of this algorithm to work on the sample input, returning a value of 58.

• Can you find success where I couldn't?

How'd I make the visualization?

• Opened Google Chrome
• Opened new page using the built-in URL, about:blank
• Updated <body></body> to <body><pre id="code"></pre></body>
• Added a CSS rule for <pre> of transform: rotate(90deg)
• Copy-pasted the contents of input.txt into the Developer Tools JavaScript Console, storing the multi-line string to a variable called input
• Adjusted my prettyPrintGrid function to - instead of log the updated grid to the console - update the innerHTML of the pre tag with the updated grid string
• Used setInterval, passing in my stepper function and an interval of 33.333333 - the number of milliseconds to process 30 frames per second
• Copy-pasted my adapted code into the console, not yet pressing enter
• Opened Quicktime
• Started a New Screen Recording
• Resized my recording area
• Pressed 'Record'
• Pressed 'Enter' in the console
• Let the program run until movement stopped
• Trimmed the recording so it started and ended at the right spots
• Saved the recording
• Uploaded the recording to CloudCovert
• Configured it to convert at 30 FPS
• Downloaded the file and uploaded it here to Dev.to