2018/Day 22.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 22 - More pathfinding, adding weights\n",
    "\n",
    "- [Day 22](https://adventofcode.com/2018/day/22)\n",
    "\n",
    "At first this appears to be a matrix problem, but the modulus over 3 prime numbers rules that out quickly. Part two reveals that this is actually a pathfinding problem, with part 1 just setting you up with a map generator.\n",
    "\n",
    "The map is essentially infinite in the positive `x` and `y` directions, so you need to generate more map as you try to find your path. You could add a row or column as you reach a new highest `x` or `y` position, but those function calls and list appends will add up to a rather high amount of time.\n",
    "\n",
    "So in my solution I double the row or column count each time a coordinate strays outside of the generated erosion level map, amortising the cost of expanding; the function only needs to be called a few times for the full rescue operation.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "from dataclasses import dataclass\n",
    "from enum import Enum\n",
    "from heapq import heappop, heappush\n",
    "from itertools import accumulate, chain, count, islice\n",
    "from typing import Iterator, List, Tuple\n",
    "\n",
    "M: int = 20183\n",
    "X0: int = 16807\n",
    "Y0: int = 48271\n",
    "\n",
    "Pos = Tuple[int, int]\n",
    "\n",
    "\n",
    "class Tool(Enum):\n",
    "    neither = 0\n",
    "    torch = 1\n",
    "    climbing_gear = 2\n",
    "\n",
    "\n",
    "class RegionType(Enum):\n",
    "    rocky = 0, \".\", Tool.climbing_gear, Tool.torch\n",
    "    wet = 1, \"=\", Tool.climbing_gear, Tool.neither\n",
    "    narrow = 2, \"|\", Tool.torch, Tool.neither\n",
    "\n",
    "    def __new__(cls, value, char, *tools):\n",
    "        instance = object.__new__(cls)\n",
    "        instance._value_ = value\n",
    "        instance.char = char\n",
    "        instance.tools = tools\n",
    "        return instance\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        return self.char\n",
    "\n",
    "\n",
    "@dataclass(frozen=True)\n",
    "class Node:\n",
    "    \"\"\"Node on the A* search graph\"\"\"\n",
    "\n",
    "    x: int = 0\n",
    "    y: int = 0\n",
    "    tool: Tool = Tool.torch\n",
    "    time: int = 0\n",
    "\n",
    "    @property\n",
    "    def pos(self) -> Pos:\n",
    "        return self.x, self.y\n",
    "\n",
    "    def cost(self, target: Pos) -> int:\n",
    "        \"\"\"Calculate the cost for this node, f(n) = g(n) + h(n)\n",
    "\n",
    "        The cost of this node is the time taken (g) plus\n",
    "        estimated cost to get to nearest goal (h).\n",
    "\n",
    "        Here we use the manhattan distance to the target as\n",
    "        the estimated cost.\n",
    "\n",
    "        \"\"\"\n",
    "        return self.time + abs(target[0] - self.x) + abs(target[1] - self.y)\n",
    "\n",
    "    def transitions(self, maze: \"ModeMaze\") -> Iterator[\"Node\"]:\n",
    "        cls = type(self)\n",
    "        other = next(t for t in maze[self.pos].tools if t is not self.tool)\n",
    "        # switching tools\n",
    "        yield cls(self.x, self.y, other, self.time + 7)\n",
    "        positions = (\n",
    "            (self.x + dx, self.y + dy) for dx, dy in ((-1, 0), (0, -1), (0, 1), (1, 0))\n",
    "        )\n",
    "        yield from (\n",
    "            cls(x, y, self.tool, self.time + 1)\n",
    "            for x, y in positions\n",
    "            if x >= 0 and y >= 0 and self.tool in maze[x, y].tools\n",
    "        )\n",
    "\n",
    "\n",
    "class ModeMaze:\n",
    "    def __init__(self, depth: int, target: Pos) -> None:\n",
    "        self.depth = depth\n",
    "        self.target = target\n",
    "        # y rows, x columns\n",
    "        self._erosion_levels: List[List[int]] = [[0]]\n",
    "        self._width, self._height = 1, 1\n",
    "\n",
    "    def _gen_levels(self, pos: Pos) -> None:\n",
    "        # make sure there is enough erosion level info up to the given position\n",
    "        # We'll grow this dynamically to the next power of 2 larger than needed each time\n",
    "        # to amortize the cost\n",
    "        cw, ch = self._width, self._height\n",
    "        width = max(2 ** math.ceil(math.log2(pos[0] + 1)), cw)\n",
    "        height = max(2 ** math.ceil(math.log2(pos[1] + 1)), ch)\n",
    "\n",
    "        depth = self.depth\n",
    "        target = self.target\n",
    "        maze = self._erosion_levels\n",
    "\n",
    "        # accumulator function\n",
    "        if cw <= target[1] < width or ch <= target[0] < height:\n",
    "            # takes a nonlocal cx as a counter\n",
    "            cx = None\n",
    "\n",
    "            def geoindex(px, py, m=M):\n",
    "                return depth if (next(cx), y) == target else (px * py + depth) % m\n",
    "\n",
    "        else:\n",
    "\n",
    "            def geoindex(px, py, m=M):\n",
    "                return (px * py + depth) % m\n",
    "\n",
    "        if width > cw:\n",
    "            # add more columns\n",
    "            rows = iter(maze)\n",
    "            next(rows).extend((x * X0 + depth) % M for x in range(cw, width))\n",
    "            # iterate over rows pairwise, so we get the preceding and current row together\n",
    "            for p, row in zip(maze, rows):\n",
    "                # accumulate values based on the preceding column value and the row above\n",
    "                cx = count(cw)  # only used if target position is in range\n",
    "                new_x = accumulate(\n",
    "                    chain(row[-1:], islice(p, len(row), width)), geoindex\n",
    "                )\n",
    "                next(new_x)  # this is the last value in the row, row[-1]\n",
    "                row += new_x\n",
    "\n",
    "        if height > ch:\n",
    "            # add more rows; pairwise iteration with the preceding row (last in the maze so far)\n",
    "            for y, p in zip(range(ch, height), islice(maze, ch - 1, None)):\n",
    "                row = [(y * Y0 + self.depth) % M]\n",
    "                cx = count(1)\n",
    "                row = list(accumulate(chain(row, islice(p, 1, width)), geoindex))\n",
    "                maze.append(row)\n",
    "\n",
    "        self._width, self._height = width, height\n",
    "\n",
    "    @property\n",
    "    def risk_level(self) -> int:\n",
    "        assert self[self.target] is RegionType.rocky\n",
    "        tx, ty = self.target\n",
    "        return sum(\n",
    "            sum(i % 3 for i in row[: tx + 1]) for row in self._erosion_levels[: ty + 1]\n",
    "        )\n",
    "\n",
    "    def __getitem__(self, pos: Pos) -> RegionType:\n",
    "        if pos[0] >= self._width or pos[1] >= self._height:\n",
    "            self._gen_levels(pos)\n",
    "        return RegionType(self._erosion_levels[pos[1]][pos[0]] % 3)\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        lines = [[str(RegionType(i % 3)) for i in row] for row in self._erosion_levels]\n",
    "        try:\n",
    "            lines[0][0] = \"M\"\n",
    "            lines[self.target[1]][self.target[0]] = \"T\"\n",
    "        except IndexError:\n",
    "            pass\n",
    "        return \"\\n\".join([\"\".join(line) for line in lines])\n",
    "\n",
    "    def rescue(self) -> int:\n",
    "        start = Node()\n",
    "        open = {start}\n",
    "        unique = count()  # tie breaker when costs are equal\n",
    "        pqueue = [(start.cost(self.target), next(unique), start)]\n",
    "        closed = set()\n",
    "        times = {\n",
    "            (start.pos, start.tool): start.time\n",
    "        }  # (pos, tool) -> time. Ignore nodes that take longer\n",
    "        while open:\n",
    "            node = heappop(pqueue)[-1]\n",
    "\n",
    "            if node.pos == self.target and node.tool is Tool.torch:\n",
    "                return node.time\n",
    "\n",
    "            open.remove(node)\n",
    "            closed.add(node)\n",
    "            for new in node.transitions(self):\n",
    "                if new in closed or new in open:\n",
    "                    continue\n",
    "                if times.get((new.pos, new.tool), float(\"inf\")) < new.time:\n",
    "                    continue\n",
    "                times[new.pos, new.tool] = new.time\n",
    "                open.add(new)\n",
    "                heappush(pqueue, (new.cost(self.target), next(unique), new))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "test = ModeMaze(510, (10, 10))\n",
    "assert test.risk_level == 114\n",
    "assert (\n",
    "    str(test)\n",
    "    == \"\"\"\\\n",
    "M=.|=.|.|=.|=|=.\n",
    ".|=|=|||..|.=...\n",
    ".==|....||=..|==\n",
    "=.|....|.==.|==.\n",
    "=|..==...=.|==..\n",
    "=||.=.=||=|=..|=\n",
    "|.=.===|||..=..|\n",
    "|..==||=.|==|===\n",
    ".=..===..=|.|||.\n",
    ".======|||=|=.|=\n",
    ".===|=|===T===||\n",
    "=|||...|==..|=.|\n",
    "=.=|=.=..=.||==|\n",
    "||=|=...|==.=|==\n",
    "|=.=||===.|||===\n",
    "||.|==.|.|.||=||\"\"\"\n",
    ")\n",
    "assert test.rescue() == 45"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "import aocd\n",
    "\n",
    "data = aocd.get_data(day=22, year=2018)\n",
    "depth, tx, ty = map(int, re.findall(r\"\\d+\", data))\n",
    "maze = ModeMaze(depth, (tx, ty))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 8090\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 1:\", maze.risk_level)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 992\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", maze.rescue())"
   ]
  }
 ],
 "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
}