Juha-Matti Santala

# Advent of Code - 2021

This is a solution to Day 11 of Advent of Code 2021.

## Day 11 - Dumbo Octopus

You enter a large cavern full of rare bioluminescent dumbo octopuses! They seem to not like the Christmas lights on your submarine, so you turn them off for now.

There are 100 octopuses arranged neatly in a 10 by 10 grid. Each octopus slowly gains energy over time and flashes brightly for a moment when its energy is full. Although your lights are off, maybe you could navigate through the cave without disturbing the octopuses if you could predict when the flashes of light will happen.

Each octopus has an energy level - your submarine can remotely measure the energy level of each octopus (your puzzle input). For example:

``````5483143223
2745854711
5264556173
6141336146
6357385478
4167524645
2176841721
6882881134
4846848554
5283751526
``````

The energy level of each octopus is a value between 0 and 9. Here, the top-left octopus has an energy level of 5, the bottom-right one has an energy level of 6, and so on.

You can model the energy levels and flashes of light in steps. During a single step, the following occurs:

• First, the energy level of each octopus increases by 1.
• Then, any octopus with an energy level greater than 9 flashes. This increases the energy level of all adjacent octopuses by 1, including octopuses that are diagonally adjacent. If this causes an octopus to have an energy level greater than 9, it also flashes. This process continues as long as new octopuses keep having their energy level increased beyond 9. (An octopus can only flash at most once per step.)
• Finally, any octopus that flashed during this step has its energy level set to 0, as it used all of its energy to flash.

Adjacent flashes can cause an octopus to flash on a step even if it begins that step with very little energy. Consider the middle octopus with 1 energy in this situation:

``````Before any steps:
11111
19991
19191
19991
11111
``````
``````After step 1:
34543
40004
50005
40004
34543
``````
``````After step 2:
45654
51115
61116
51115
45654
``````

``````from utils import read_input

def transformer(line):
return [int(num) for num in list(line)]

### Part 1

I can already tell there's gonna be a lot of debugging steps happening to figure out where I might be wrong and the puzzle maker was kind enough to provide step-by-step grids for many of the steps up to 100 with the example input so to compare to those, I'll create a debugging printing function so it's easy to print the grid at any point.

``````def print_grid(grid):
for x in range(len(grid)):
for y in range(len(grid[x])):
print(grid[x][y], end="")
print()``````

At the beginning of each step, one thing guaranteed to happen is that every dumbo octopus's energy level will increase by one so let's have a function for that.

(There's a lot of for loops in this solution and some of it could probably be refactored out with some smart tricks.)

``````def initial_increase(grid):
for x in range(len(grid)):
for y in range(len(grid[x])):
grid[x][y] += 1
return grid``````

Neighbors? That sounds familiar. Last time (in Day 9) we only cared about adjacent neighbors and now we care about diagonal ones too. Luckily did this already once so easy to adjust (and improve!) my last solution for today.

``````def get_neighbors(position, max_height, max_width):
x, y = position
neighbors = [
(x-1, y-1),
(x-1, y),
(x-1, y+1),
(x, y-1),
(x, y+1),
(x+1, y-1),
(x+1, y),
(x+1, y+1)
]

def valid(x, y, max_height, max_width):
return x >= 0 and y >= 0 and x < max_height and y < max_width

return [(x, y) for (x, y) in neighbors if valid(x, y, max_height, max_width)]``````

Few helper functions:

`increase_neighbors` is a helper function to run through a list of coordinates and increase everyone's energy level by one.

`reset` sets the energy level of any dumbo octopus to 0 if it flashed (was over 9).

``````def increase_neighbors(grid, neighbors):
for (x, y) in neighbors:
grid[x][y] += 1
return grid

def reset(grid):
for x in range(len(grid)):
for y in range(len(grid[x])):
if grid[x][y] > 9:
grid[x][y] = 0``````

`flash_increase` is the main logic of this simulation.

We loop over the main part until there were no more flashes on a given round.
On each loop round, we check every octopus:

• if it already flashed, we ignore it
• if it's gonna flash, we record that flash into `flashes`, mark it flashed into `already_flashed` and increase the levels of all of its neighbors

If we had any flashes, we record those to our step flash counter `all_flashes`, set round flashes to 0 and repeat until there were none.

Finally, we "reset" the grid by making the energy level of any flashed octopus into 0.

``````def flash_increase(grid):
max_height, max_width = len(grid), len(grid[0])
flashes = 0
all_flashes = 0
while True:
for x in range(len(grid)):
for y in range(len(grid[x])):
value = grid[x][y]
continue
elif value > 9:
flashes += 1
neighbors = get_neighbors((x, y), max_height, max_width)
increase_neighbors(grid, neighbors)
if flashes == 0:
break
else:
all_flashes += flashes
flashes = 0
reset(grid)
return all_flashes``````

Our simulation function runs `n` steps of simulation, running both the initial increase and flashing increases on each step and counts flashes.

In a previous puzzle we created a copy of a list with `list2 = list1[:]` but since that only works on the first level (ie. it's a shallow copy) and we have a list of lists, we need to deep copy it to prevent future simulations from affecting the original input.

To do that, we use `deepcopy` method from copy library.

``````import copy

def simulate(n, grid):
grid = copy.deepcopy(grid)
score = 0
for step in range(n):
initial_increase(grid)
score += flash_increase(grid)
return score``````

Given the starting energy levels of the dumbo octopuses in your cavern, simulate 100 steps. How many total flashes are there after 100 steps?

``````result = simulate(100, grid)

assert result == 1546 # If assert failes, re-read the input
print(f'Solution: {result}')``````

Solution: 1546

### Part 2

It seems like the individual flashes aren't bright enough to navigate. However, you might have a better option: the flashes seem to be synchronizing!

If you can calculate the exact moments when the octopuses will all flash simultaneously, you should be able to navigate through the cavern. What is the first step during which all octopuses flash?

An easy way to see if an simultaneous flash happened is to check if the grid is all zeroes after a step has happened.

We can keep everything else the same and count for steps and after each step, check for a synchronous flash.

``````import copy

def check_for_sync(grid):
for x in range(len(grid)):
for y in range(len(grid[x])):
if grid[x][y] != 0:
return False
return True

def simulate_until_syncronous(grid):
grid = copy.deepcopy(grid)

step = 1
while True:
initial_increase(grid)
flash_increase(grid)
if check_for_sync(grid):
break
else:
step += 1

return step``````
``````result = simulate_until_syncronous(grid)
print(f'Solution: {result}')``````

Solution: 471

### Alternative solution: `Octopus` class

After completing my two stars and enjoying some breakfast, I wanted to see if I could make the code nicer by using some classes.

I really like how this solution turned out. First of all, no more `for x in range(len(grid)): for y in range(len(grid[x]))` which can be cumbersome to read and write. Second, the octopus can take care of itself now, making the rest of the logic cleaner.

We start with `Octopus` class.

It knows a few things about itself: it's `energy_level`, if it recently `flashed` and its `position` in the swarm.

Because it knows its place, it also knows all the possible neighbors (notice here that I don't filter the possible neighbors at all, I do that in the main logic).

And it knows if it should reset or not based on its `energy_level`.

``````class Octopus:

def __init__(self, position, energy_level):
self.energy_level = energy_level
self.position = position
self.flashed = False

def energize(self):
self.energy_level += 1
if self.energy_level > 9:
self.flashed = True

def reset(self):
if self.energy_level > 9:
self.energy_level = 0
self.flashed = False

def get_neighbors(self):
x, y = self.position
return [
(x-1, y-1),
(x-1, y),
(x-1, y+1),
(x, y-1),
(x, y+1),
(x+1, y-1),
(x+1, y),
(x+1, y+1)
]

def __repr__(self):
return f'{self.position}: {self.energy_level}'``````

We start by creating the octopus bunch from the input data.

Sync check for part 2 is simple: we check every octopus to see if their level is 0.

`step` function is the main logic here again and it's quite simple but much easier to read than the previous one.

We got rid of the nested `for` loops (for `x` and `y`) because we store each octopus in a dictionary now.

I also put the initial increase from the previous solution into this function because it became so much simpler that I didn't feel it needed a separate function anymore.

In

``````try:
octopi[neighbor].energize()
except KeyError: # If such neighbor doesn't exist, skip
continue``````

I'm using a trick that I probably wouldn't use outside a puzzle setting like this. As I mentioned earlier, I don't filter out invalid neighbor positions at an octopus level but rather here. I try to energize and octopus at given position but if that position doesn't exist, I just ignore it with `try`/`catch`.

Most of the other code is same as in the original solution.

``````def initialize():
raw_data = copy.deepcopy(grid)
octopi = {
(x,y): Octopus((x, y), value)
for x, _ in enumerate(raw_data)
for y, value in enumerate(raw_data[x])
}

return octopi

def check_for_sync(octopi):
return all(octopus.energy_level == 0 for octopus in octopi.values())

def step(octopi):
flashes = 0
all_flashes = 0
# Increase all energy levels by one
for octopus in octopi.values():
octopus.energize()

# Increase neighbors levels by one until no more flashes happen
while True:
for octopus in octopi.values():
continue
elif octopus.flashed:
flashes += 1
for neighbor in octopus.get_neighbors():
try:
octopi[neighbor].energize()
except KeyError: # If such neighbor doesn't exist, skip
continue

if flashes == 0:
break
else:
all_flashes += flashes
flashes = 0

# After the round, reset every octopus
for octopus in octopi.values():
octopus.reset()

return all_flashes

def simulate_octopi(n):
octopi = initialize()
score = 0
for _ in range(n):
score += step(octopi)
return score

def simulate_until_sync():
octopi = initialize()
step_count = 1
while True:
step(octopi)
if check_for_sync(octopi):
return step_count
step_count += 1

print(f'Solution, part 1: {simulate_octopi(100)}')
print(f'Solution, part 2: {simulate_until_sync()}')
``````

Solution, part 1: 1546

Solution, part 2: 471