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-movingv
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 abreak
...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 usingwhile(True)
and abreak
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>
oftransform: rotate(90deg)
- Copy-pasted the contents of
input.txt
into the Developer Tools JavaScript Console, storing the multi-line string to a variable calledinput
- Adjusted my
prettyPrintGrid
function to - instead of log the updated grid to the console - update theinnerHTML
of thepre
tag with the updated grid string - Used
setInterval
, passing in mystepper
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
Top comments (0)
Some comments may only be visible to logged-in visitors. Sign in to view all comments.