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 5283751526The 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 11111After step 1: 34543 40004 50005 40004 34543After step 2: 45654 51115 61116 51115 45654
Read input
from utils import read_input
def transformer(line):
return [int(num) for num in list(line)]
grid = read_input(11, transformer)
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 intoalready_flashedand 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
already_flashed = set()
while True:
for x in range(len(grid)):
for y in range(len(grid[x])):
value = grid[x][y]
if (x, y) in already_flashed:
continue
elif value > 9:
flashes += 1
already_flashed.add((x, y))
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):
already_flashed = set()
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():
if octopus in already_flashed:
continue
elif octopus.flashed:
flashes += 1
already_flashed.add(octopus)
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