{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 20 - regex parsing and more path finding\n",
"\n",
"- [Day 20](https://adventofcode.com/2018/day/20)\n",
"\n",
"This is essentially a path-finding problem; the regex is a tree of legal steps to reach a location, and from that tree you can construct all possible legal moves across the map. We can then find the longest possible path from this.\n",
"\n",
"Note that the _shortest route_ is required; no meandering around to get to the furstest room. The input probably includes ways to open doors between rooms that open up shortcuts to the furthest rooms. So we can build a graph of the rooms and connections first (taking care to _reuse_ a room when it already exists at that location), then use a path finding algorithm to determine which path is longest.\n",
"\n",
"The regex encodes many bracnhing paths, but the string can be treated as a stack and we only have to track the branch tips. We start with the tip of a single root branch (our starting point), and each time we reach a `(`, we push our current set of brannches on the stack, create a new set to track the new branches and continue on with parsing; each `|` creates a new set of branch tips based on the top of the stack, and with `)` we can pop from the stack and continue on as before with the accumulated branches.\n",
"\n",
"Finding the longest path is a simple exhaustive traversal of the graph, where we avaid visiting rooms we have seen before unless our new path is shorter. Because we already track per-room distances, part 2 was trivial.\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import re\n",
"from collections import deque\n",
"from dataclasses import dataclass, field\n",
"from functools import reduce\n",
"from typing import Iterable, Iterator, Mapping, Optional, Tuple\n",
"\n",
"Pos = Tuple[int, int]\n",
"_delta = {\"N\": (0, -1), \"W\": (-1, 0), \"E\": (1, 0), \"S\": (0, 1)}\n",
"_doors = dict(zip(\"NWES\", \"-||-\"))\n",
"_inverse = dict(zip(\"NWES\", \"SEWN\"))\n",
"_tokenize = re.compile(r\"(\\(|\\||\\)|[NWSE]+)\").finditer\n",
"\n",
"\n",
"# not really frozen, we allow manipulation through __getitem__ and __setitem__\n",
"# but the N, S, W, E directions are not part of the hash.\n",
"@dataclass(frozen=True)\n",
"class Room:\n",
" x: int = 0\n",
" y: int = 0\n",
" N: \"Room\" = field(default=None, compare=False, repr=False)\n",
" W: \"Room\" = field(default=None, compare=False, repr=False)\n",
" S: \"Room\" = field(default=None, compare=False, repr=False)\n",
" E: \"Room\" = field(default=None, compare=False, repr=False)\n",
"\n",
" @property\n",
" def pos(self) -> Pos:\n",
" return (self.x, self.y)\n",
"\n",
" def open_door(self, dir: str) -> \"Room\":\n",
" room = self[dir]\n",
" if room is None:\n",
" dx, dy = _delta[dir]\n",
" room = self[dir] = Room(self.x + dx, self.y + dy)\n",
" room[_inverse[dir]] = self\n",
" return room\n",
"\n",
" @property\n",
" def available(self) -> Iterator[str]:\n",
" return (d for d in \"NSWE\" if self[d] is not None)\n",
"\n",
" def __getitem__(self, dir: str) -> \"Room\":\n",
" if dir not in \"NSWE\":\n",
" raise AttributeError(dir)\n",
" return self.__dict__[dir]\n",
"\n",
" def __setitem__(self, dir: str, room: \"Room\") -> None:\n",
" if dir not in \"NSWE\":\n",
" raise AttributeError(dir)\n",
" self.__dict__[dir] = room\n",
"\n",
" def __repr__(self) -> str:\n",
" doors = \"\".join(d if self[d] is not None else d.lower() for d in \"NSWE\")\n",
" return f\"{type(self).__name__}(x={self.x}, y={self.y} {doors})\"\n",
"\n",
"\n",
"class RegularMap:\n",
" start: Optional[Room]\n",
"\n",
" def __init__(self, start: Room):\n",
" self.start = start\n",
"\n",
" @classmethod\n",
" def from_regex(cls, regex: Iterable[str]) -> \"RegularMap\":\n",
" stack = deque()\n",
" start = Room()\n",
" here = {start}\n",
" new_branch_tips = None\n",
" for token in (m.group() for m in _tokenize(regex)):\n",
" if token == \"(\":\n",
" stack.append(set(here))\n",
" new_branch_tips = set()\n",
" elif token == \"|\":\n",
" new_branch_tips.update(here)\n",
" here = set(stack[-1])\n",
" elif token == \")\":\n",
" new_branch_tips.update(here)\n",
" stack.pop()\n",
" here = new_branch_tips\n",
" else:\n",
" here = {reduce(Room.open_door, token, r) for r in here}\n",
" return RegularMap(start)\n",
"\n",
" def furthest_room(self) -> int:\n",
" queue = deque([(self.start, 0)])\n",
" distances = {self.start.pos: 0}\n",
" while queue:\n",
" room, distance = queue.popleft()\n",
" distance += 1\n",
" for dir in room.available:\n",
" next_ = room[dir]\n",
" if next_.pos in distances and distances[next_.pos] <= distance:\n",
" continue\n",
" distances[next_.pos] = distance\n",
" queue.append((next_, distance))\n",
" return max(distances.values()), sum(1 for d in distances.values() if d >= 1000)\n",
"\n",
" def _by_coords(self) -> Mapping[Pos, Room]:\n",
" # collect coords\n",
" queue = deque([self.start])\n",
" rooms = {self.start.pos: self.start}\n",
" while queue:\n",
" room = queue.popleft()\n",
" for dir in room.available:\n",
" next_ = room[dir]\n",
" if next_.pos in rooms:\n",
" continue\n",
" rooms[next_.pos] = next_\n",
" queue.append(next_)\n",
" return rooms\n",
"\n",
" def __str__(self):\n",
" rooms = self._by_coords()\n",
" minx, miny = (min(vs) for vs in zip(*rooms))\n",
" maxx, maxy = (max(vs) for vs in zip(*rooms))\n",
" width, height = abs(maxx + 1 - minx), abs(maxy + 1 - miny)\n",
" lines = [[\"#\"] * (width * 2 + 1) for _ in range(height * 2 + 1)]\n",
" for (x, y), room in rooms.items():\n",
" lines[(y - miny) * 2 + 1][(x - minx) * 2 + 1] = (\n",
" \"X\" if room.pos == (0, 0) else \".\"\n",
" )\n",
" for dir in room.available:\n",
" dx, dy = _delta[dir]\n",
" lines[(y - miny) * 2 + 1 + dy][(x - minx) * 2 + 1 + dx] = _doors[dir]\n",
"\n",
" return \"\\n\".join([\"\".join(line) for line in lines])"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"scrolled": true
},
"outputs": [],
"source": [
"tests = {\n",
" \"^E(N|S)E$\": (\"#######\\n###.|.#\\n###-###\\n#X|.###\\n###-###\\n###.|.#\\n#######\", 3),\n",
" \"^ENWWW(NEEE|SSE(EE|N))$\": (\n",
" \"#########\\n#.|.|.|.#\\n#-#######\\n#.|.|.|.#\\n#-#####-#\\n#.#.#X|.#\\n#-#-#####\\n#.|.|.|.#\\n#########\",\n",
" None,\n",
" ),\n",
" \"^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$\": (\n",
" \"###########\\n#.|.#.|.#.#\\n#-###-#-#-#\\n#.|.|.#.#.#\\n#-#####-#-#\\n#.#.#X|.#.#\\n#-#-#####-#\\n#.#.|.|.|.#\\n#-###-###-#\\n#.|.|.#.|.#\\n###########\",\n",
" None,\n",
" ),\n",
" \"^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))$\": (\n",
" \"#############\\n#.|.|.|.|.|.#\\n#-#####-###-#\\n#.#.|.#.#.#.#\\n#-#-###-#-#-#\\n#.#.#.|.#.|.#\\n#-#-#-#####-#\\n#.#.#.#X|.#.#\\n#-#-#-###-#-#\\n#.|.#.|.#.#.#\\n###-#-###-#-#\\n#.|.#.|.|.#.#\\n#############\",\n",
" 23,\n",
" ),\n",
" \"^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$\": (\n",
" \"###############\\n#.|.|.|.#.|.|.#\\n#-###-###-#-#-#\\n#.|.#.|.|.#.#.#\\n#-#########-#-#\\n#.#.|.|.|.|.#.#\\n#-#-#########-#\\n#.#.#.|X#.|.#.#\\n###-#-###-#-#-#\\n#.|.#.#.|.#.|.#\\n#-###-#####-###\\n#.|.#.|.|.#.#.#\\n#-#-#####-#-#-#\\n#.#.|.|.|.#.|.#\\n###############\",\n",
" 31,\n",
" ),\n",
"}\n",
"\n",
"for regex, (expected_str, expected_distance) in tests.items():\n",
" test_rmap = RegularMap.from_regex(regex)\n",
" assert str(test_rmap) == expected_str\n",
" if expected_distance:\n",
" assert test_rmap.furthest_room()[0] == expected_distance"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"import aocd\n",
"\n",
"data = aocd.get_data(day=20, year=2018)\n",
"regular_map = RegularMap.from_regex(data)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Part 1: 3991\n",
"Part 2: 8394\n"
]
}
],
"source": [
"furthest_room, far_rooms = regular_map.furthest_room()\n",
"print(\"Part 1:\", furthest_room)\n",
"print(\"Part 2:\", far_rooms)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The animation produced below can be viewed online [via the Jupyter notebook viewer](https://nbviewer.jupyter.org/github/mjpieters/adventofcode/blob/master/2018/Day%2020.ipynb); the GitHub renderer filters them out.\n"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%matplotlib inline\n",
"import matplotlib.pyplot as plt\n",
"import numpy as np\n",
"from matplotlib import animation, rc\n",
"\n",
"rc(\"animation\", html=\"html5\")\n",
"\n",
"\n",
"def animate_parse(regex):\n",
" rooms = RegularMap.from_regex(regex)._by_coords()\n",
" minx, miny = (min(vs) for vs in zip(*rooms))\n",
" maxx, maxy = (max(vs) for vs in zip(*rooms))\n",
" width, height = abs(maxx + 1 - minx), abs(maxy + 1 - miny)\n",
" del rooms\n",
"\n",
" stack = deque()\n",
" start = Room()\n",
" here = {start}\n",
" branches = None\n",
" frames = [[start.pos]]\n",
"\n",
" for token in (m.group() for m in _tokenize(regex)):\n",
" if token == \"(\":\n",
" stack.append(here)\n",
" branches = here = set(here)\n",
" elif token == \"|\":\n",
" branches.update(here)\n",
" here = set(stack[-1])\n",
" elif token == \")\":\n",
" branches.update(here)\n",
" stack.pop()\n",
" here = branches\n",
" else:\n",
" for dir in token:\n",
" coords = []\n",
" frames.append(coords)\n",
" new_here = set()\n",
" for room in here:\n",
" room = room.open_door(dir)\n",
" coords.append(room.pos)\n",
" new_here.add(room)\n",
" here = new_here\n",
"\n",
" frames += (None for _ in range(512)) # full fade for remainder\n",
"\n",
" fig, ax = plt.subplots(figsize=(8, 8))\n",
" fig.subplots_adjust(left=0, bottom=0, right=1, top=1, wspace=0, hspace=0)\n",
" ax.set_axis_off()\n",
"\n",
" grid = np.zeros((width, height), dtype=np.uint8)\n",
" image = ax.imshow(grid, vmin=0, vmax=255, cmap=\"magma\")\n",
"\n",
" def render(coords):\n",
" a = image.get_array()\n",
" a[(a > 0) & (a < 255)] += 1\n",
" if coords:\n",
" coords = tuple(zip(*((y - miny, x - minx) for x, y in coords)))\n",
" a[coords] = 1\n",
" return (image,)\n",
"\n",
" anim = animation.FuncAnimation(\n",
" fig, render, frames, interval=10, blit=True, repeat_delay=1000\n",
" )\n",
" plt.close(fig)\n",
" return anim\n",
"\n",
"\n",
"animate_parse(data)"
]
}
],
"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"
}
},
"nbformat": 4,
"nbformat_minor": 2
}