We are back to cellar automatons, in a finite 2D grid, just like day 18 of 2018. I'll use similar techniques, with scipy.signal.convolve2d() to turn neigr counts into the next state. Our state is simpler, a simple on or off so we can use simple boolean selections here.
from __future__ import annotations
from typing import Sequence, Set, Tuple
import numpy as np
from scipy.signal import convolve2d
def readmap(maplines: Sequence[str]) -> np.array:
return np.array([c == "#" for line in maplines for c in line]).reshape((5, -1))
def biodiversity_rating(matrix: np.array) -> int:
# booleans -> single int by multiplying with powers of 2, then summing
return (
matrix.reshape((-1))
* np.logspace(0, matrix.size - 1, num=matrix.size, base=2, dtype=np.uint)
).sum()
def find_repeat(matrix: np.array) -> int:
# the four adjacent tiles matter, not the diagonals
kernel = np.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]])
# previous states seen (matrix flattened to a tuple)
seen: Set[Tuple] = set()
while True:
counts = convolve2d(matrix, kernel, mode="same")
matrix = (
# A bug dies (becoming an empty space) unless there is exactly one bug adjacent to it.
(matrix & (counts == 1))
|
# An empty space becomes infested with a bug if exactly one or two bugs are adjacent to it.
(~matrix & ((counts == 1) | (counts == 2)))
)
key = tuple(matrix.flatten())
if key in seen:
return biodiversity_rating(matrix)
seen.add(key)
test_matrix = readmap(
"""\
....#
#..#.
#..##
..#..
#....""".splitlines()
)
assert find_repeat(test_matrix) == 2129920
import aocd
data = aocd.get_data(day=24, year=2019)
erismap = readmap(data.splitlines())
print("Part 1:", find_repeat(erismap))
Part 1: 13500447
# how fast is this?
%timeit find_repeat(erismap)
103 µs ± 3.09 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
I'm not sure if we might be able to use scipy.signal.convolve() (the N-dimensional variant of convolve2d()) to count neigurs across multiple layers in one go. It works for counting neigurs across a single layer however, and for 200 steps, the additional 8 computations are not exactly strenuous.
I'm creating all layers needed to fit all the steps. An empty layer is filled across 2 steps; first the inner ring, then the outer ring, at which point another layer is needed. So for 200 steps we need 100 layers below and a 100 layers above, ending up with 201 layers. These are added by using np.pad().
Then use convolve() to count neigurs on the same level, and a few sums for additional counts from the levels above and below.
from scipy.signal import convolve
def run_multidimensional(matrix: np.array, steps: int = 200) -> int:
# 3d kernel; only those on the same level, not above or below
kernel = np.array(
[
[[0, 0, 0], [0, 0, 0], [0, 0, 0]],
[[0, 1, 0], [1, 0, 1], [0, 1, 0]],
[[0, 0, 0], [0, 0, 0], [0, 0, 0]],
]
)
matrix = np.pad(matrix[None], [((steps + 1) // 2,), (0,), (0,)])
for _ in range(steps):
# count neigurs on the same layer, then clear the hole
counts = convolve(matrix, kernel, mode="same")
counts[:, 2, 2] = 0
# layer below, counts[:-1, ...] are updated from kernel[1:, ...].sum()s
counts[:-1, 1, 2] += matrix[1:, 0, :].sum(
axis=1
) # cell above hole += top row next level
counts[:-1, 3, 2] += matrix[1:, -1, :].sum(
axis=1
) # cell below hole += bottom row next level
counts[:-1, 2, 1] += matrix[1:, :, 0].sum(
axis=1
) # cell left of hole += left column next level
counts[:-1, 2, 3] += matrix[1:, :, -1].sum(
axis=1
) # cell right of hole += right column next level
# layer above, counts[1-:, ...] slices are updated from kernel[:-1, ...] indices (true -> 1)
counts[1:, 0, :] += matrix[
:-1, 1, 2, None
] # top row += cell above hole next level
counts[1:, -1, :] += matrix[
:-1, 3, 2, None
] # bottom row += cell below hole next level
counts[1:, :, 0] += matrix[
:-1, 2, 1, None
] # left column += cell left of hole next level
counts[1:, :, -1] += matrix[
:-1, 2, 3, None
] # right column += cell right of hole next level
# next step is the same as part 1:
matrix = (
# A bug dies (becoming an empty space) unless there is exactly one bug adjacent to it.
(matrix & (counts == 1))
|
# An empty space becomes infested with a bug if exactly one or two bugs are adjacent to it.
(~matrix & ((counts == 1) | (counts == 2)))
)
return matrix.sum()
assert run_multidimensional(test_matrix, 10) == 99
print("Part 2:", run_multidimensional(erismap))
Part 2: 2120
# how fast is this?
%timeit run_multidimensional(erismap)
92.4 ms ± 1.16 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)