Advent of Code 2021 Day 11
Try the simulator
Solve for X where
X = the first step after which all octopuses flash in unison
- Checkpoint in Part 1 asks for the total number of times a flash occurred up to and including step 100
Input is
- A multi-line string
It represents
- A 10x10 square of octopuses
- Each number is that octopus's energy level:
0-9
Data structures I used to solve this challenge
- Multi-dimensional - 2D - array
- Relative coordinates to compare adjacent values in an array
- List to unique coordinates to track which values, if any, flashed
Pseudocode of the algorithms I wrote to generate a correct answer
Parse the input:
Split each new line into an array of lines
Split each line into an array of characters
Coerce each character into a number
Keep track of octopuses that flashed:
Expects these parameters:
1. Incremented 10x10 grid
2. List of coordinates of octopuses that already flashed
Setup new list to track newly flashing octopuses
For each cell in the 10x10 grid
If the cell's value is 10 and the accumulated list of coordinates does not include the cell's location:
Add the coordinate to the new list
Return the new list
Update energy levels of adjacent octopuses:
Expects these parameters:
1 and 2. row, cell indexes
3. 10x10 grid
For each of this cell's eight adjacent cells:
Add one to that cell's value, as long as:
It exists (mindful of corners and edges)
It is not 10
Main algorithm:
For each cell in the 10x10 grid:
Update each cell's value by 1
Setup array to store coordinates of each octopus that flashes this round
Collect the coordinates of each octopus that just flashed
While at least one octopus just flashed:
For each octopus that just flashed:
Update the energy levels of each adjacent octopus
Add their row,cell locations to the list
Collect the row,cell locations of any adjacent octopuses that flashed
Update the list of coordinates of octopuses that flashed last round to reference the collection of adjacent flashing octopuses
Update the values of all octopuses that flashed from 10 to 0
Find the round after which all octopuses flash simultaneously:
Set a count to 0
While every cell's value in the 10x10 grid is not 0:
Increment the count by 1
Perform the main algorithm
Critiquing my code
There are so many loops
- Some cover the 100 cells of the grid
- Some cover more, since each time an octopus flashes, the loop must loop-up 8 cells
- Some cover separate lists of locations of flashing octopuses
I'm surprised I got the right answer, twice!
- The imposter in me thought my main
while
loop didn't fully cover each newly flashing octopus and each of its adjacent octopuses
Celebrating and visualizing
- I solved both parts by myself!
- After browsing other solvers' code, I was relieved to see that I more-or-less solved this the same way...albeit with extra or unneeded steps and variables
- I made a fun web page to visualize each of the flashes, including a way to pause and play
Since I'm going in reverse order, I hope some of the remaining puzzles will offer the reward of solving without having to study another incredible solver's code first.
Top comments (0)