{ "cells": [ { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "# Day 23, elfular automatons\n", "\n", "- https://adventofcode.com/2022/day/23\n", "\n", "I was wondering if there'd be another [cellular automata](https://en.wikipedia.org/wiki/Cellular_automaton) puzzle this year; it's been a regular staple of AoC (see 2018 [day 12](../2018/Day%2012.ipynb) & [day 18](../2018/Day%2018.ipynb), 2019 [day 11](../2019/Day%2011.ipynb) & [day 24](../2019/Day%2024.ipynb), 2020 [day 11](../2020/Day%2011.ipynb), [day 17](../2020/Day%2017.ipynb) & [day 24](../2020/Day%2024.ipynb), and 2021 [day 11](../2021/Day%2011.ipynb), [day 20](../2021/Day%2020.ipynb) & [day 25](../2021/Day%2025.ipynb)).\n", "\n", "Like most of those past puzzles, it's easiest to implement using [`scipy.signal.convolve2d()`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.convolve2d.html#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):\n", "\n", "$$\\begin{bmatrix}2^0 & 2^1 & 2^2\\\\2^3 & 0 & 2^4\\\\2^5 & 2^6 & 2^7\\end{bmatrix}$$\n", "\n", "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.\n", "\n", "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.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from collections import deque\n", "from dataclasses import dataclass\n", "from enum import Enum\n", "from itertools import islice\n", "from typing import Final, Iterator, Literal, Self, TypeAlias, TypeVar\n", "\n", "import numpy as np\n", "from numpy.typing import NDArray\n", "from scipy.signal import convolve2d\n", "\n", "Kernel: TypeAlias = NDArray[np.int_]\n", "S = TypeVar(\"S\", bound=np.generic, covariant=True)\n", "\n", "SURROUNDING: Final[Kernel] = np.array(\n", " [[2**7, 2**6, 2**5], [2**4, 0, 2**3], [2**2, 2**1, 2**0]]\n", ")\n", "\n", "\n", "def crop(m: NDArray[S]) -> NDArray[S]:\n", " \"\"\"Remove outer rows and columns of zeros from a matrix.\"\"\"\n", " xy = np.argwhere(m)\n", " return m[*(slice(f, t + 1) for f, t in zip(xy.min(axis=0), xy.max(axis=0)))]\n", "\n", "\n", "class Direction(Enum):\n", " # bitmask, shift, axis\n", " north = SURROUNDING[-1].sum(), -1, 0\n", " south = SURROUNDING[0].sum(), 1, 0\n", " west = SURROUNDING[:, -1].sum(), -1, 1\n", " east = SURROUNDING[:, 0].sum(), 1, 1\n", "\n", " shift: Literal[-1, 1]\n", " axis: Literal[0, 1]\n", "\n", " def __new__(cls, bitmask: int, shift: Literal[-1, 1], axis: Literal[0, 1]) -> Self:\n", " obj = object.__new__(cls)\n", " obj._value_ = bitmask\n", " obj.shift = shift\n", " obj.axis = axis\n", " return obj\n", "\n", " def move(self, matrix: NDArray[S]) -> NDArray[S]:\n", " return np.roll(matrix, self.shift, axis=self.axis)\n", "\n", " def __invert__(self) -> Self:\n", " match self:\n", " case Direction.north:\n", " return Direction.south\n", " case Direction.south:\n", " return Direction.north\n", " case Direction.west:\n", " return Direction.east\n", " case Direction.east:\n", " return Direction.west\n", "\n", "\n", "@dataclass\n", "class GroveElves:\n", " matrix: NDArray[np.bool_]\n", "\n", " @classmethod\n", " def from_scanner(cls, image: str) -> Self:\n", " return cls(\n", " np.array(\n", " [[c == \"#\" for c in line] for line in image.splitlines()], dtype=bool\n", " ),\n", " )\n", "\n", " def process(self) -> Iterator[NDArray[np.bool_]]:\n", " \"\"\"Process the grove elves movements and yield the current positions.\"\"\"\n", " grove = self.matrix\n", " directions = deque(Direction)\n", " while True:\n", " # make room for cells to move outward\n", " m = np.pad(grove, 1)\n", " # create bitsets of where the elves neighbours are.\n", " choices: NDArray[np.int_] = convolve2d(m, SURROUNDING, mode=\"same\")\n", " # active cells that can move\n", " active = choices > 0\n", " # active elves pick their moves, as an index into directions + 1\n", " # elves that can't propose moves are marked with -1\n", " proposals: NDArray[np.int16] = np.select(\n", " [~(active & m), *((choices & d.value == 0) for d in directions)],\n", " [\n", " np.zeros(m.shape, np.int16),\n", " *(np.full(m.shape, i + 1, np.int16) for i in range(4)),\n", " ],\n", " default=-1,\n", " )\n", " # use XOR to check if moves don't collide.\n", " can_move: NDArray[np.bool_] = np.logical_xor.reduce(\n", " [d.move(proposals == i) for i, d in enumerate(directions, 1)]\n", " )\n", "\n", " # construct output matrix, from the inactive elves, elves that could\n", " # not propose a direction, those that moved, and those that can't\n", " # move due to collisions.\n", " moved = np.logical_or.reduce(\n", " [\n", " ~active & m,\n", " proposals == -1,\n", " can_move,\n", " *(\n", " (proposals == i) & (~d).move(~can_move)\n", " for (i, d) in enumerate(directions, 1)\n", " ),\n", " ]\n", " )\n", " # shrink the matrix to shed non-zero rows and columns\n", " grove = crop(moved)\n", " yield grove\n", " directions.rotate(-1)\n", "\n", " def empty_ground_after(self, rounds: int) -> int:\n", " last = next(islice(self.process(), rounds - 1, None))\n", " return last.size - last.sum()\n", "\n", "\n", "example = GroveElves.from_scanner(\n", " \"\"\"\\\n", "....#..\n", "..###.#\n", "#...#.#\n", ".#...##\n", "#.###..\n", "##.#.##\n", ".#..#..\n", "\"\"\"\n", ")\n", "\n", "assert example.empty_ground_after(10) == 110" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Part 1: 4247\n" ] } ], "source": [ "import aocd\n", "\n", "grove = GroveElves.from_scanner(aocd.get_data(day=23, year=2022))\n", "print(\"Part 1:\", grove.empty_ground_after(10))" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "## Part 2, keep on running, until you are done\n", "\n", "All we have to do is run until the next state is equal to the previous.\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "def stops_after(grove: GroveElves) -> int:\n", " process = grove.process()\n", " state = next(process)\n", " for i, new in enumerate(process, 2):\n", " if np.array_equal(new, state):\n", " return i\n", " state = new\n", "\n", "\n", "assert stops_after(example) == 20" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Part 2: 1049\n" ] } ], "source": [ "print(\"Part 2:\", stops_after(grove))" ] } ], "metadata": { "kernelspec": { "display_name": "adventofcode-mOkh6lsX", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.0" }, "orig_nbformat": 4, "vscode": { "interpreter": { "hash": "b1b6870d1e0a983b1943c858d70ac8a7c80477f9f3ca364eb8daa198319a8a87" } } }, "nbformat": 4, "nbformat_minor": 2 }