14 Dec 21

Dumbo Octopus - Advent of Code 2021 Day 11

 

Wynwood Walls

In today's problem we are given a set of rules that determine how a group of bioluminescent octopuses flash and are asked to count the flashes over a period of steps. We also need to determine the instance when all the octopuses flash in the same step

A full description of the problem can be found here -

Based on the rules described in the problem, in each step -
  • Each octopus's energy increases by 1
  • If the energy surpasses 9 it flashes and resets to 0
  • Neighboring octopuses gain 1 energy if an octopus flashes
    • Neighboring octopuses have to potential to flash
  • Octopuses that have flashed cannot gain any more energy in the current step

Solving it

Firstly we need a way to track when an Octopus has flashed in the current step versus the prior step. This will avoid incorrectly increasing the energy of an octopus that has just flashed in the current step.

In order to do this I decided that during the first phase of the step, an octopus that has flashed be set to 10 rather than zero. This is cleaned up at the end of each step and reset to zero. This avoids the need of a separate data structure for keeping track of flashes. This does however require a cleanup step which can be avoided if we need to optimize

Recursion

If an octopus flashes, we increase the energy of neighboring octopuses. Since this increase can trigger more flashes, a recursive function makes sense here.

In the following code all the neighbors are visited and have their energy incremented. If a flash occurs, the same function is called again

def triggerNeighborIncrease(row,col,twoDArray):

    counter = 0

    for cellDir in cellDirs:
          
        r,c = row + cellDir[0] , col + cellDir[1]

        # skip if out of bounds or flashed
        if r < 0 or c < 0 or c > (len(twoDArray[0])-1) or r > len(twoDArray)-1\
            or twoDArray[r][c] == 10:
            continue

        twoDArray[r][c] += 1 # increment the neighboring octopuses energy
        
        if twoDArray[r][c] == 10: # cell just flashed as a result of an increase
            counter += 1 + triggerNeighborIncrease(r,c,twoDArray)
        
    return counter

Finding when all the octopuses have flashed

Finally, we need to determine the most optimal time for the submarine to travel ie. when all the octopuses have flashed and provide light.

This is quite easy to do at the end of each step, and involves iterating over each element and counting the flashes after they have been reset to zero. Once we have this information we can compare it to the size of the array and figure out when all the elements have been set to zero.

def setFlashedCellsToZeroAndReturnCount(twoDArray):
    countZeroes = 0
    for i in range(0,len(twoDArray)):
       for j in range(0,len(twoDArray[i])):
            if twoDArray[i][j] == 10: # for flashed - set the cells to zero 
               twoDArray[i][j] = 0
               countZeroes += 1

    return countZeroes


The full source code can be found here -

https://github.com/jasoncoelho/adventOfCode2021/blob/main/11/run.py

show some love