I was wondering if there'd be another cellular automata puzzle this year; it's been a regular staple of AoC (see 2018 day 12 & day 18, 2019 day 11 & day 24, 2020 day 11, day 17 & day 24, and 2021 day 11, day 20 & day 25).
Like most of those past puzzles, it's easiest to implement using scipy.signal.convolve2d()
; by using a kernel with increasing powers of 2 we can then use bit masking to select cells that have no neighbours in specific cells, while a 0 means there were no neighbouring elves at all (signalling an elf that won't move):
For example, if there are any elves in the NW, N or NE corners, then output for the central cell will have at least one of the 3 least significant bits set and so value & 7
will be non-zero. There is a technical note here; you need to invert the kernel as it is actually applied in the reverse order from the visual representation (the values are added directly to each cell based on the value of the underlying matrix at the central kernel cell). This is very similar to how I used convolve2d()
on day 20 in 2021.
I note that the puzzle omits one detail: Elves might not be able to choose a direction to move to, when all 4 directions have at least 1 elf in them. From the example, however, it is clear that in that case the elves behave exactly like those elves with 0 neigbours.
from collections import deque
from dataclasses import dataclass
from enum import Enum
from itertools import islice
from typing import Final, Iterator, Literal, Self, TypeAlias, TypeVar
import numpy as np
from numpy.typing import NDArray
from scipy.signal import convolve2d
Kernel: TypeAlias = NDArray[np.int_]
S = TypeVar("S", bound=np.generic, covariant=True)
SURROUNDING: Final[Kernel] = np.array(
[[2**7, 2**6, 2**5], [2**4, 0, 2**3], [2**2, 2**1, 2**0]]
)
def crop(m: NDArray[S]) -> NDArray[S]:
"""Remove outer rows and columns of zeros from a matrix."""
xy = np.argwhere(m)
return m[*(slice(f, t + 1) for f, t in zip(xy.min(axis=0), xy.max(axis=0)))]
class Direction(Enum):
# bitmask, shift, axis
north = SURROUNDING[-1].sum(), -1, 0
south = SURROUNDING[0].sum(), 1, 0
west = SURROUNDING[:, -1].sum(), -1, 1
east = SURROUNDING[:, 0].sum(), 1, 1
shift: Literal[-1, 1]
axis: Literal[0, 1]
def __new__(cls, bitmask: int, shift: Literal[-1, 1], axis: Literal[0, 1]) -> Self:
obj = object.__new__(cls)
obj._value_ = bitmask
obj.shift = shift
obj.axis = axis
return obj
def move(self, matrix: NDArray[S]) -> NDArray[S]:
return np.roll(matrix, self.shift, axis=self.axis)
def __invert__(self) -> Self:
match self:
case Direction.north:
return Direction.south
case Direction.south:
return Direction.north
case Direction.west:
return Direction.east
case Direction.east:
return Direction.west
@dataclass
class GroveElves:
matrix: NDArray[np.bool_]
@classmethod
def from_scanner(cls, image: str) -> Self:
return cls(
np.array(
[[c == "#" for c in line] for line in image.splitlines()], dtype=bool
),
)
def process(self) -> Iterator[NDArray[np.bool_]]:
"""Process the grove elves movements and yield the current positions."""
grove = self.matrix
directions = deque(Direction)
while True:
# make room for cells to move outward
m = np.pad(grove, 1)
# create bitsets of where the elves neighbours are.
choices: NDArray[np.int_] = convolve2d(m, SURROUNDING, mode="same")
# active cells that can move
active = choices > 0
# active elves pick their moves, as an index into directions + 1
# elves that can't propose moves are marked with -1
proposals: NDArray[np.int16] = np.select(
[~(active & m), *((choices & d.value == 0) for d in directions)],
[
np.zeros(m.shape, np.int16),
*(np.full(m.shape, i + 1, np.int16) for i in range(4)),
],
default=-1,
)
# use XOR to check if moves don't collide.
can_move: NDArray[np.bool_] = np.logical_xor.reduce(
[d.move(proposals == i) for i, d in enumerate(directions, 1)]
)
# construct output matrix, from the inactive elves, elves that could
# not propose a direction, those that moved, and those that can't
# move due to collisions.
moved = np.logical_or.reduce(
[
~active & m,
proposals == -1,
can_move,
*(
(proposals == i) & (~d).move(~can_move)
for (i, d) in enumerate(directions, 1)
),
]
)
# shrink the matrix to shed non-zero rows and columns
grove = crop(moved)
yield grove
directions.rotate(-1)
def empty_ground_after(self, rounds: int) -> int:
last = next(islice(self.process(), rounds - 1, None))
return last.size - last.sum()
example = GroveElves.from_scanner(
"""\
....#..
..###.#
#...#.#
.#...##
#.###..
##.#.##
.#..#..
"""
)
assert example.empty_ground_after(10) == 110
import aocd
grove = GroveElves.from_scanner(aocd.get_data(day=23, year=2022))
print("Part 1:", grove.empty_ground_after(10))
Part 1: 4247
All we have to do is run until the next state is equal to the previous.
def stops_after(grove: GroveElves) -> int:
process = grove.process()
state = next(process)
for i, new in enumerate(process, 2):
if np.array_equal(new, state):
return i
state = new
assert stops_after(example) == 20
print("Part 2:", stops_after(grove))
Part 2: 1049