day_12/solution.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done!\n",
      "[(0, 20), (0, 19), (0, 18), (0, 17), (0, 16), (0, 15), (0, 14), (0, 13), (1, 13), (2, 13), (3, 13), (4, 13), (5, 13), (5, 12), (6, 12), (7, 12), (8, 12), (9, 12), (10, 12), (11, 12), (11, 11), (11, 10), (11, 9), (12, 9), (13, 9), (14, 9), (15, 9), (16, 9), (17, 9), (18, 9), (19, 9), (20, 9), (21, 9), (22, 9), (23, 9), (24, 9), (25, 9), (26, 9), (27, 9), (28, 9), (29, 9), (30, 9), (31, 9), (32, 9), (33, 9), (34, 9), (35, 9), (36, 9), (37, 9), (38, 9), (39, 9), (40, 9), (41, 9), (42, 9), (43, 9), (44, 9), (45, 9), (46, 9), (47, 9), (48, 9), (49, 9), (50, 9), (51, 9), (52, 9), (53, 9), (54, 9), (55, 9), (56, 9), (56, 10), (57, 10), (58, 10), (59, 10), (60, 10), (61, 10), (62, 10), (63, 10), (64, 10), (65, 10), (65, 11), (65, 12), (65, 13), (65, 14), (66, 14), (67, 14), (68, 14), (69, 14), (70, 14), (71, 14), (72, 14), (73, 14), (73, 15), (73, 16), (74, 16), (75, 16), (76, 16), (76, 17), (76, 18), (76, 19), (76, 20), (76, 21), (76, 22), (76, 23), (76, 24), (76, 25), (76, 26), (76, 27), (76, 28), (76, 29), (76, 30), (77, 30), (78, 30), (79, 30), (80, 30), (80, 31), (81, 31), (82, 31), (83, 31), (84, 31), (85, 31), (86, 31), (87, 31), (88, 31), (89, 31), (90, 31), (91, 31), (92, 31), (93, 31), (94, 31), (95, 31), (96, 31), (97, 31), (98, 31), (99, 31), (100, 31), (101, 31), (101, 32), (101, 33), (101, 34), (102, 34), (102, 35), (102, 36), (102, 37), (103, 37), (104, 37), (105, 37), (105, 38), (105, 39), (106, 39), (107, 39), (107, 40), (108, 40), (109, 40), (110, 40), (111, 40), (112, 40), (113, 40), (114, 40), (115, 40), (116, 40), (117, 40), (118, 40), (119, 40), (120, 40), (121, 40), (122, 40), (123, 40), (124, 40), (125, 40), (126, 40), (126, 39), (126, 38), (126, 37), (126, 36), (126, 35), (126, 34), (125, 34), (124, 34), (123, 34), (122, 34), (121, 34), (120, 34), (119, 34), (118, 34), (117, 34), (116, 34), (116, 33), (115, 33), (115, 32), (114, 32), (114, 31), (114, 30), (114, 29), (114, 28), (113, 28), (113, 27), (113, 26), (112, 26), (112, 25), (111, 25), (111, 24), (110, 24), (110, 23), (109, 23), (109, 22), (109, 21), (109, 20), (109, 19), (109, 18), (109, 17), (109, 16), (109, 15), (110, 15), (111, 15), (111, 14), (112, 14), (112, 13), (113, 13), (113, 12), (114, 12), (114, 11), (114, 10), (115, 10), (115, 9), (115, 8), (116, 8), (116, 7), (117, 7), (118, 7), (119, 7), (120, 7), (121, 7), (121, 8), (122, 8), (123, 8), (123, 9), (124, 9), (124, 10), (125, 10), (125, 11), (126, 11), (127, 11), (128, 11), (129, 11), (129, 12), (130, 12), (131, 12), (132, 12), (132, 13), (133, 13), (133, 14), (134, 14), (134, 15), (134, 16), (134, 17), (134, 18), (134, 19), (134, 20), (134, 21), (134, 22), (134, 23), (134, 24), (134, 25), (134, 26), (134, 27), (134, 28), (134, 29), (133, 29), (133, 30), (132, 30), (132, 31), (131, 31), (130, 31), (129, 31), (128, 31), (127, 31), (126, 31), (125, 31), (124, 31), (123, 31), (122, 31), (121, 31), (120, 31), (119, 31), (118, 31), (117, 31), (117, 30), (116, 30), (116, 29), (116, 28), (116, 27), (116, 26), (116, 25), (115, 25), (115, 24), (114, 24), (113, 24), (113, 23), (112, 23), (112, 22), (112, 21), (112, 20), (112, 19), (112, 18), (112, 17), (112, 16), (113, 16), (114, 16), (114, 15), (115, 15), (115, 14), (116, 14), (116, 13), (116, 12), (117, 12), (117, 11), (117, 10), (118, 10), (119, 10), (120, 10), (121, 10), (122, 10), (122, 11), (123, 11), (123, 12), (124, 12), (124, 13), (125, 13), (125, 14), (126, 14), (127, 14), (128, 14), (129, 14), (130, 14), (131, 14), (131, 15), (131, 16), (131, 17), (131, 18), (131, 19), (131, 20), (131, 21), (131, 22), (131, 23), (131, 24), (131, 25), (131, 26), (131, 27), (131, 28), (130, 28), (129, 28), (128, 28), (127, 28), (126, 28), (125, 28), (124, 28), (123, 28), (123, 29), (122, 29), (121, 29), (120, 29), (119, 29), (119, 28), (118, 28), (118, 27), (118, 26), (118, 25), (118, 24), (118, 23), (117, 23), (116, 23), (116, 22), (115, 22), (115, 21), (115, 20), (115, 19), (115, 18), (115, 17), (116, 17), (117, 17), (117, 16), (118, 16), (118, 15), (118, 14), (118, 13), (119, 13), (120, 13), (121, 13), (122, 13), (122, 14), (123, 14), (123, 15), (124, 15), (124, 16), (125, 16), (126, 16), (127, 16), (128, 16), (128, 17), (128, 18), (128, 19), (128, 20), (128, 21), (128, 22), (128, 23), (128, 24), (128, 25), (127, 25), (126, 25), (125, 25), (124, 25), (123, 25), (123, 26), (122, 26), (121, 26), (120, 26), (120, 25), (120, 24), (120, 23), (120, 22), (120, 21), (121, 21), (121, 20), (120, 20), (119, 20)]\n",
      "423\n"
     ]
    }
   ],
   "source": [
    "import string\n",
    "import collections\n",
    "\n",
    "origin = None\n",
    "dest = None\n",
    "with open('input/input.txt') as f:\n",
    "    heightmap = []\n",
    "    for i, line in enumerate(f):\n",
    "        line = line.strip()\n",
    "        if line.find('S') != -1:\n",
    "            origin = (line.index('S'), i)\n",
    "            line = line.replace('S', 'a')\n",
    "        if line.find('E') != -1:\n",
    "            dest = (line.index('E'), i)\n",
    "            line = line.replace('E', 'z')\n",
    "        heightmap.append([string.ascii_lowercase.index(x) for x in line])\n",
    "\n",
    "\n",
    "def next_steps(heightmap, pos):\n",
    "    options = []\n",
    "    for (x, y) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:\n",
    "        new_pos = (pos[0] + x, pos[1] + y)\n",
    "        if new_pos[0] < 0 or new_pos[1] < 0 or new_pos[0] >= len(heightmap[0]) or new_pos[1] >= len(heightmap):\n",
    "            continue\n",
    "        if heightmap[pos[1] + y][pos[0] + x] <= heightmap[pos[1]][pos[0]] + 1:\n",
    "            options.append(new_pos)\n",
    "    return options\n",
    "\n",
    "\n",
    "queue = collections.deque()\n",
    "queue.extend([[origin, x] for x in next_steps(heightmap, origin)])\n",
    "visited = set()\n",
    "while len(queue):\n",
    "    path = queue.popleft()\n",
    "    steps = next_steps(heightmap, path[-1])\n",
    "    for step in steps:\n",
    "        if step == dest:\n",
    "            print(\"done!\")\n",
    "            print(path + [step])\n",
    "            print(len(path))\n",
    "            break\n",
    "        if step not in visited:\n",
    "            visited.add(step)\n",
    "            queue.append(path + [step])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "new best: 423\n",
      "new best: 422\n",
      "new best: 421\n",
      "new best: 420\n",
      "new best: 419\n",
      "new best: 418\n",
      "new best: 417\n",
      "new best: 416\n",
      "416\n"
     ]
    }
   ],
   "source": [
    "import string\n",
    "import collections\n",
    "\n",
    "possible_origins = []\n",
    "dest = None\n",
    "with open('input/sample.txt') as f:\n",
    "    heightmap = []\n",
    "    for i, line in enumerate(f):\n",
    "        line = line.strip()\n",
    "        if line.find('S') != -1:\n",
    "            origin = (line.index('S'), i)\n",
    "            line = line.replace('S', 'a')\n",
    "        for j, char in enumerate(line):\n",
    "            if char == 'a':\n",
    "                possible_origins.append((j, i))\n",
    "        if line.find('E') != -1:\n",
    "            dest = (line.index('E'), i)\n",
    "            line = line.replace('E', 'z')\n",
    "        heightmap.append([string.ascii_lowercase.index(x) if x in string.ascii_lowercase else print(x) for x in line])\n",
    "\n",
    "\n",
    "def next_steps(heightmap, pos):\n",
    "    options = []\n",
    "    for (x, y) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:\n",
    "        new_pos = (pos[0] + x, pos[1] + y)\n",
    "        if new_pos[0] < 0 or new_pos[1] < 0 or new_pos[0] >= len(heightmap[0]) or new_pos[1] >= len(heightmap):\n",
    "            continue\n",
    "        if heightmap[pos[1] + y][pos[0] + x] <= heightmap[pos[1]][pos[0]] + 1:\n",
    "            options.append(new_pos)\n",
    "    return options\n",
    "\n",
    "\n",
    "def find_route(origin):\n",
    "    queue = collections.deque()\n",
    "    queue.extend([[origin, x] for x in next_steps(heightmap, origin)])\n",
    "    visited = set()\n",
    "    while len(queue):\n",
    "        path = queue.popleft()\n",
    "        steps = next_steps(heightmap, path[-1])\n",
    "        for step in steps:\n",
    "            if step == dest:\n",
    "                return len(path)\n",
    "            if step not in visited:\n",
    "                visited.add(step)\n",
    "                queue.append(path + [step])\n",
    "    return None\n",
    "\n",
    "\n",
    "shortest_route = None\n",
    "for o in possible_origins:\n",
    "    new_len = find_route(o)\n",
    "    if new_len is not None and (shortest_route is None or new_len < shortest_route):\n",
    "        print(f\"new best: {new_len}\")\n",
    "        shortest_route = new_len\n",
    "\n",
    "print(shortest_route)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.6 64-bit",
   "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.10.6 (main, Nov 14 2022, 16:10:14) [GCC 11.3.0]"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}