Dumbo Octopus

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.