2020/Day 17.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 17 - 3D Cellular Automaton in an infinite grid\n",
    "\n",
    "- https://adventofcode.com/2020/day/17\n",
    "\n",
    "More cellular automatons, now in 3 dimensions and with an infinite grid. We can use [`scipy.signal.convolve()`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.convolve.html) rather than `convolve2d()` we used before (see [day 18, 2018](../2018/Day%2018.ipynb), [day 24, 2019](../2019/Day%2024.ipynb) & [day 11 this year](./Day%2011.ipynb), but we have to extend our matrix each iteration.\n",
    "\n",
    "To add 'edges' to the matrix, we can use [`numpy.pad()`](https://numpy.org/doc/stable/reference/generated/numpy.pad.html); we want to add zeros all round, so it's enough to use `numpy.pad(matrix, 1, \n",
    "=0)`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from enum import Enum\n",
    "from itertools import product\n",
    "\n",
    "import numpy as np\n",
    "from scipy.signal import convolve\n",
    "\n",
    "\n",
    "class Cube(Enum):\n",
    "    inactive = 0, \".\"\n",
    "    active = 1, \"#\"\n",
    "\n",
    "    def __new__(cls, int_: int, value: str):\n",
    "        instance = object.__new__(cls)\n",
    "        instance._value_ = value\n",
    "        instance.int = int_\n",
    "        return instance\n",
    "\n",
    "\n",
    "class ConwayCubes:\n",
    "    def __init__(self, initial_state: str, dimensions: int = 3) -> None:\n",
    "        self._dimensions = dimensions\n",
    "        extent = (1,) * (dimensions - 2)\n",
    "        self._matrix = np.array(\n",
    "            [Cube(c).int for line in initial_state.splitlines() for c in line]\n",
    "        ).reshape((-1, initial_state.index(\"\\n\"), *extent))\n",
    "\n",
    "        # generate N-dimensional kernel; all 1s except the middle.\n",
    "        self._kernel = np.full((3,) * dimensions, 1)\n",
    "        self._kernel[(1,) * dimensions] = 0\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        letters = \"zw\"\n",
    "        m = self._matrix\n",
    "        mapping = {s.int: s.value for s in Cube}\n",
    "        layers, dims = [], m.shape[2:]\n",
    "        for lidx in product(*map(range, dims)):\n",
    "            layers.append(\n",
    "                \"\\n\".join(\n",
    "                    [\n",
    "                        \" \".join(\n",
    "                            [\n",
    "                                f\"{c}={v - (d // 2)}\"\n",
    "                                for c, v, d in zip(letters, lidx, dims)\n",
    "                            ]\n",
    "                        ),\n",
    "                        *[\n",
    "                            \"\".join(map(mapping.__getitem__, row))\n",
    "                            for row in m[(Ellipsis, *lidx)]\n",
    "                        ],\n",
    "                    ]\n",
    "                )\n",
    "            )\n",
    "        return \"\\n\\n\".join(layers)\n",
    "\n",
    "    def run(self, cycles: int = 6) -> int:\n",
    "        \"\"\"Run until stability is reached, the return the number of occupied seats\"\"\"\n",
    "        f = self._matrix\n",
    "        full = {c: np.full(self._matrix.shape, c.int) for c in Cube}\n",
    "        for _ in range(cycles):\n",
    "            # grow both the matrix, and the full matrices to use in np.select()\n",
    "            f = np.pad(f, 1, constant_values=0)\n",
    "            full = {c: np.pad(m, 1, constant_values=c.int) for c, m in full.items()}\n",
    "            counts = {\n",
    "                cube: convolve(f == cube.int, self._kernel, mode=\"same\")\n",
    "                for cube in Cube\n",
    "            }\n",
    "            rules = {\n",
    "                # If a cube is **active** and **exactly 2 or 3** of its neighbors are also **active**,\n",
    "                # the cube remains **active**. Otherwise, the cube becomes **inactive**.\n",
    "                Cube.inactive: (\n",
    "                    (f == Cube.active.int)\n",
    "                    & ((counts[Cube.active] < 2) | (counts[Cube.active] > 3))\n",
    "                ),\n",
    "                # If a cube is **inactive** but **exactly 3** of its neighbors are active, the cube\n",
    "                # becomes **active**. Otherwise, the cube remains **inactive**.\n",
    "                Cube.active: (f == Cube.inactive.int) & (counts[Cube.active] == 3),\n",
    "            }\n",
    "            f = np.select(list(rules.values()), [full[c] for c in rules], default=f)\n",
    "            self._matrix = f\n",
    "        return np.sum(f == Cube.active.int)\n",
    "\n",
    "\n",
    "teststate = \".#.\\n..#\\n###\\n\"\n",
    "assert ConwayCubes(teststate).run() == 112"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import aocd\n",
    "\n",
    "initial_state = aocd.get_data(day=17, year=2020)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 298\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 1:\", ConwayCubes(initial_state).run())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2, more dimensions\n",
    "\n",
    "I just refactored the code a little bit to generate matrices (and a kernel) with more dimensions.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert ConwayCubes(teststate, 4).run() == 848"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 1792\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 1:\", ConwayCubes(initial_state, 4).run())"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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": 2
 },
 "nbformat": 4,
 "nbformat_minor": 2
}