2022/Day 12.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Over the hills and far away\n",
    "\n",
    "- https://adventofcode.com/2022/day/12\n",
    "\n",
    "It would not be an Advent of Code calendar without a path finding challenge. Time to bust out the [A\\* search algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm) again!\n",
    "\n",
    "For past challenges that were solvable using path finding, see:\n",
    "\n",
    "- 2016:\n",
    "  - [Day 13](../2016/puzzle13.py)\n",
    "  - [Day 17](../2016/puzzle17.py)\n",
    "  - [Day 22](../2016/puzzle22.py)\n",
    "  - [Day 24](../2016/puzzle24.py)\n",
    "- 2017:\n",
    "  - [Day 12](../2017/Day%2012.ipynb)\n",
    "- 2018:\n",
    "  - [Day 15](../2018/Day%2015.ipynb)\n",
    "  - [Day 20](../2018/Day%2020.ipynb)\n",
    "  - [Day 22](../2018/Day%2022.ipynb)\n",
    "- 2019\n",
    "  - [Day 15](../2019/Day%2015.ipynb)\n",
    "  - [Day 17](../2019/Day%2017.ipynb) (part 2)\n",
    "  - [Day 18](../2019/Day%2018.ipynb)\n",
    "  - [Day 20](../2019/Day%2020.ipynb)\n",
    "- 2020\n",
    "  - [Day 20](../2020/Day%2020.ipynb)\n",
    "- 2021\n",
    "  - [Day 12](../2021/Day%2012.ipynb)\n",
    "  - [Day 15](../2021/Day%2015.ipynb)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dataclasses import dataclass\n",
    "from heapq import heappop, heappush\n",
    "from itertools import count\n",
    "from typing import Final, Iterator, Self, TypeAlias\n",
    "\n",
    "Pos: TypeAlias = tuple[int, int]\n",
    "\n",
    "\n",
    "@dataclass(frozen=True)\n",
    "class HikingNode:\n",
    "    \"\"\"Node on the A* search graph\"\"\"\n",
    "\n",
    "    x: int\n",
    "    y: int\n",
    "    steps: 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 number of steps taken (g) plus estimated\n",
    "        cost to get to end goal (h).\n",
    "\n",
    "        Here we use the manhattan distance to the target as the estimated cost.\n",
    "\n",
    "        \"\"\"\n",
    "        return self.steps + abs(target[0] - self.x) + abs(target[1] - self.y)\n",
    "\n",
    "    def transitions(self, heightmap: \"HeightMap\") -> Iterator[Self]:\n",
    "        height = heightmap[self.x, self.y]\n",
    "        accessible = chr(ord(height) + 1) if height < \"z\" else \"z\"\n",
    "        steps = self.steps + 1\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",
    "            __class__(x, y, steps)\n",
    "            for x, y in positions\n",
    "            if (x, y) in heightmap and heightmap[x, y] <= accessible\n",
    "        )\n",
    "\n",
    "\n",
    "# once we have read the heightmap, replace the start and end markers with heights\n",
    "_transmap: Final[dict[int, int]] = str.maketrans(\"SE\", \"az\")\n",
    "\n",
    "\n",
    "class HeightMap:\n",
    "    def __init__(self, map: list[str]) -> None:\n",
    "        self._height = len(map)\n",
    "        self._width = len(map[0])\n",
    "        self._start = next(\n",
    "            (x, y) for y, row in enumerate(map) if (x := row.find(\"S\")) >= 0\n",
    "        )\n",
    "        self._target = next(\n",
    "            (x, y) for y, row in enumerate(map) if (x := row.find(\"E\")) >= 0\n",
    "        )\n",
    "        self._map = [row.translate(_transmap) for row in map]\n",
    "\n",
    "    def __getitem__(self, pos: Pos) -> int:\n",
    "        x, y = pos\n",
    "        return self._map[y][x]\n",
    "\n",
    "    def __contains__(self, pos: Pos) -> bool:\n",
    "        x, y = pos\n",
    "        return 0 <= x < self._width and 0 <= y < self._height\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        return \"\\n\".join([\"\".join([str(r) for r in row]) for row in self._matrix])\n",
    "\n",
    "    def fewest_steps_needed(self) -> int:\n",
    "        start = HikingNode(*self._start)\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",
    "        seen = {\n",
    "            start.pos: start.steps\n",
    "        }  # pos -> step count. Ignore nodes that took more steps\n",
    "        while open:\n",
    "            node = heappop(pqueue)[-1]\n",
    "\n",
    "            if node.pos == self._target:\n",
    "                return node.steps\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 seen.get(new.pos, float(\"inf\")) < new.steps:\n",
    "                    continue\n",
    "                seen[new.pos] = new.steps\n",
    "                open.add(new)\n",
    "                heappush(pqueue, (new.cost(self._target), next(unique), new))\n",
    "\n",
    "\n",
    "example = \"\"\"\\\n",
    "Sabqponm\n",
    "abcryxxl\n",
    "accszExk\n",
    "acctuvwj\n",
    "abdefghi\n",
    "\"\"\".splitlines()\n",
    "test_heightmap = HeightMap(example)\n",
    "assert test_heightmap.fewest_steps_needed() == 31"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 352\n"
     ]
    }
   ],
   "source": [
    "import aocd\n",
    "\n",
    "heightmap = HeightMap(aocd.get_data(day=12, year=2022).splitlines())\n",
    "print(\"Part 1:\", heightmap.fewest_steps_needed())"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2, breath first search\n",
    "\n",
    "Where part one was best solved with A\\* path finding, the second part can best be solved using [Breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search); start at the target, and work your way back to find the shortest path to a widening set of locations, until you find an `a` stop you can reach. You are guaranteed to find the nearest `a` spot this way.\n",
    "\n",
    "Just remember to reverse the criteria for what is an acceptable next position to try; the preceding letter in the alphabet or higher are acceptable (so go from `m` down to `l`, stay on `m`, or move to `n`, `o`, `p`, etc.).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "\n",
    "class InverseHikingNode(HikingNode):\n",
    "    def transitions(self, heightmap: \"HeightMap\") -> Iterator[Self]:\n",
    "        height = heightmap[self.x, self.y]\n",
    "        accessible = chr(ord(height) - 1) if height > \"a\" else \"a\"\n",
    "        steps = self.steps + 1\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",
    "            __class__(x, y, steps)\n",
    "            for x, y in positions\n",
    "            if (x, y) in heightmap and heightmap[x, y] >= accessible\n",
    "        )\n",
    "\n",
    "\n",
    "def shortest_hiking_path(heightmap: HeightMap) -> int:\n",
    "    \"\"\"Find the shortest path from a starting point at elevation 'a'.\"\"\"\n",
    "    start = InverseHikingNode(*heightmap._target)\n",
    "    queue = deque([start])\n",
    "    seen = {start}\n",
    "    while queue:\n",
    "        node = queue.popleft()\n",
    "\n",
    "        if heightmap[node.pos] == \"a\":\n",
    "            return node.steps\n",
    "\n",
    "        for new in node.transitions(heightmap):\n",
    "            if new not in seen:\n",
    "                seen.add(new)\n",
    "                queue.append(new)\n",
    "\n",
    "\n",
    "assert shortest_hiking_path(test_heightmap) == 29"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 345\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", shortest_hiking_path(heightmap))"
   ]
  }
 ],
 "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
}