Today's challenge is another cellular automata variant; we've had similar puzzles in years before (see 2018 day 12, 2018 day 18, 2019 day 11, 2019 day 24, 2020 day 11, 2020 day 17 and 2020 day 24).
For this puzzle, there are 4 distinct steps to follow each round:
To locate all neighbours I'm using the trusty scipy.signal.convolve2d()
function again, with a kernel that maps to all 8 surrounding cells, which gives us a matrix where each cell is a count of the number of neighbours that are flashing.
import numpy as np
from scipy.signal import convolve2d
KERNEL: np.ndarray = np.array([[1, 1, 1], [1, 0, 1], [1, 1, 1]], dtype=np.uint8)
class DumboOctopuses:
_matrix: np.ndarray
def __init__(self, grid: list[str]) -> None:
self._matrix = np.genfromtxt(grid, dtype=np.uint8, delimiter=1)
def __str__(self) -> str:
return np.array2string(self._matrix, separator="").translate(
# Remove spaces and square brackets, [ and ]
dict.fromkeys((0x20, 0x5B, 0x5D))
)
def step(self) -> int:
m = self._matrix
m += 1
flashed = np.zeros(m.shape, dtype=np.bool_)
while np.any(flashing := (~flashed & (m > 9))):
m += convolve2d(flashing, KERNEL, mode="same")
flashed |= flashing
m[m > 9] = 0
return np.sum(flashed)
def simulate(self, steps: int = 100) -> int:
return sum(self.step() for _ in range(steps))
test_energy_levels = """\
5483143223
2745854711
5264556173
6141336146
6357385478
4167524645
2176841721
6882881134
4846848554
5283751526
""".splitlines()
assert DumboOctopuses(test_energy_levels).simulate(100) == 1656
import aocd
octopus_levels = aocd.get_data(day=11, year=2021).splitlines()
print("Part 1:", DumboOctopuses(octopus_levels).simulate(100))
Part 1: 1625
For part 2, all that is needed is a loop counter, and a check if the current step flash count is equal to the number of cells, 100.
from itertools import count
def find_simultatious_flash(start_levels: list[str]) -> int:
levels = DumboOctopuses(start_levels)
for step in count(1):
if levels.step() == 100:
return step
assert find_simultatious_flash(test_energy_levels) == 195
print("Part 2:", find_simultatious_flash(octopus_levels))
Part 2: 244
This task just begs for being visualised; as before matplotlib supplies the tools to convert the matrix to a frame and to output a video of all the frames put together.
I use a ListedColormap()
to give cells with values 9 and 0 different (flash) colours from the rest of the cells.
Note: this video is best viewed on the [Jupyter notebook viewer site](https://nbviewer.org/github/mjpieters/adventofcode/blob/master/2021/Day 11.ipynb), as GitHub filters out video content.
%matplotlib inline
import matplotlib.pyplot as plt
from matplotlib import animation, colormaps
from matplotlib.colors import ListedColormap
plt.rc("animation", html="html5")
def animate(start_levels: list[str], steps=300) -> animation.ArtistAnimation:
fig, ax = plt.subplots()
fig.subplots_adjust(left=0, bottom=0, right=1, top=1, wspace=0, hspace=0)
ax.set_axis_off()
colours = colormaps["Blues"].resampled(9)(np.linspace(0, 1, 10))
colours[1:9, :] = colours[8:0:-1, :] # reverse colour progress from dark to light
colours[9, :] = np.array([1, 248 / 256, 128 / 256, 1])
colours[0, :] = np.array([1, 240 / 256, 31 / 256, 1])
cmap = ListedColormap(colours)
levels = DumboOctopuses(start_levels)
frames = []
for _ in range(steps):
frames.append([plt.imshow(levels._matrix, cmap=cmap, animated=True)])
levels.step()
anim = animation.ArtistAnimation(
fig, frames, interval=150, blit=True, repeat_delay=1000
)
plt.close(fig)
return anim
animate(test_energy_levels)
/var/folders/zr/sp474f_d38xfvml_n2y_8tfr0000gn/T/ipykernel_33658/4245431018.py:14: MatplotlibDeprecationWarning: The get_cmap function was deprecated in Matplotlib 3.7 and will be removed two minor releases later. Use ``matplotlib.colormaps[name]`` or ``matplotlib.colormaps.get_cmap(obj)`` instead. colours = cm.get_cmap("Blues", 9)(np.linspace(0, 1, 10))