AoC_2022_Day_12.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPdM1XJCHytJ8TeTnhVY9ap",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/mattmorganpdx/AdventOfCode2022/blob/main/AoC_2022_Day_12.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 44,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "i8z1eHS9VdrF",
        "outputId": "70ca10db-ce0b-4f46-d3bc-6161608de9d9"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "394\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "388"
            ]
          },
          "metadata": {},
          "execution_count": 44
        }
      ],
      "source": [
        "import string\n",
        "from functools import lru_cache\n",
        "from queue import Queue\n",
        "\n",
        "def create_heightmap(g):\n",
        "    start = None\n",
        "    end = None\n",
        "    _map = []\n",
        "    for ldx, line in enumerate(g.splitlines()):\n",
        "        row = []\n",
        "        for cdx, char in enumerate(line):\n",
        "            if char == \"S\":\n",
        "                start = (ldx, cdx)\n",
        "                char = -1\n",
        "            elif char == \"E\":\n",
        "                end = (ldx, cdx)\n",
        "                char = 26\n",
        "            else:\n",
        "                char = string.ascii_lowercase.index(char)\n",
        "            row.append(char)\n",
        "        _map.append(row)\n",
        "    return start, end, _map\n",
        "\n",
        "@lru_cache\n",
        "def get_neighbors(p):\n",
        "    v = grid[p[0]][p[1]]\n",
        "\n",
        "    # Super lazy edge \"detection\"\n",
        "    def _try(n):\n",
        "        if n[0] < 0 or n[1] < 0:\n",
        "            return n, 27\n",
        "        try:\n",
        "            return n, grid[n[0]][n[1]]\n",
        "        except:\n",
        "            return n, 27\n",
        "\n",
        "    n, s, e, w = (p[0] - 1, p[1]), (p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0], p[1] - 1)\n",
        "\n",
        "    return {n for n, e in map(_try, [n, s, e, w]) if e <= v + 1}\n",
        "\n",
        "def bfs(start_node, target_node):\n",
        "    visited = set()\n",
        "    queue = Queue()\n",
        "    \n",
        "    queue.put(start_node)\n",
        "    visited.add(start_node)\n",
        "    \n",
        "    parent = dict()\n",
        "    parent[start_node] = None\n",
        "\n",
        "    path_found = False\n",
        "    while not queue.empty():\n",
        "        current_node = queue.get()\n",
        "        if current_node == target_node:\n",
        "            path_found = True\n",
        "            break\n",
        "\n",
        "        for next_node in get_neighbors(current_node):\n",
        "            if next_node not in visited:\n",
        "                queue.put(next_node)\n",
        "                parent[next_node] = current_node\n",
        "                visited.add(next_node)\n",
        "                \n",
        "    path_len = 0\n",
        "    if path_found:\n",
        "        while parent[target_node] is not None:\n",
        "            path_len += 1\n",
        "            target_node = parent[target_node]\n",
        "        \n",
        "    return path_len\n",
        "\n",
        "start, end, grid = create_heightmap(input)\n",
        "\n",
        "# Part 1\n",
        "print(bfs(start, end))\n",
        "\n",
        "# Part 2, need to drop the -1 value so we take index 1 from the sorted\n",
        "sorted({bfs((y,x), end) for y in range(len(grid)) for x in range(len(grid)) if grid[y][x] == 0})[1]\n"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "test_input = '''Sabqponm\n",
        "abcryxxl\n",
        "accszExk\n",
        "acctuvwj\n",
        "abdefghi'''"
      ],
      "metadata": {
        "id": "iqU60MnT7R0h"
      },
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "input = '''abccccccccaaaaaaaccaaaaaaaaaaaaaaaaccccccccccccccccccccccccccccccccccccaaaaaa\n",
        "abccccccccaaaaaaaccaaaaaaaaaaaaaaaaccccccccccccccccccccccccccccccccccccaaaaaa\n",
        "abccccccccccaaaaaaccaaaaaaaaaaaaaaaaccccccccccccccccacccccccccccccccccccaaaaa\n",
        "abcccccaaaacaaaaaaccaaaaaaaaaaaaaaaaacccccccccccccccaaaccccaccccccccccccccaaa\n",
        "abccccaaaaacaaccccccaaaaaacaaacaacaaaaaaacccccccccccaaaacccaacccccccccccccaaa\n",
        "abaaccaaaaaaccccaaacaaaacacaaacaaccaaaaaacccccccccccaklaccccccccccccccccccaac\n",
        "abaaccaaaaaaccaaaaaacccccccaaacccaaaaaaaccccccccccckkkllllccccccccccccccccccc\n",
        "abaaccaaaaaaccaaaaaacccccccaaaaacaaaaaaacccccccccckkkklllllcccccccaaaccaccccc\n",
        "abacccccaacccccaaaaacccccccaaaaaccaaaaaaacccccccckkkkpppllllccccccaaaaaaccccc\n",
        "abacccccccccccaaaaacccccccccaaaacccaaaaaaccccccckkkkpppppplllccccddddaaaccccc\n",
        "abccccccccccccaaaaaccccccccccaaaccaaaccccccccccckkkppppppppllllldddddddaccccc\n",
        "abccacccccccccccccccccccccccccccccaaccccccccccckkkopppupppplllmmmmdddddaacccc\n",
        "abccaaacaaaccccccccccccccccccccaaaaaaaaccccccckkkkopuuuuupppllmmmmmmddddacccc\n",
        "abccaaaaaaaccccccccccccccccccccaaaaaaaacccccjjkkkooouuuuuuppqqqqqmmmmddddcccc\n",
        "abccaaaaaacccccccccccccccaaccccccaaaacccccjjjjjjoooouuxuuuppqqqqqqmmmmdddcccc\n",
        "abcaaaaaaaacccccccccccccaaacccccaaaaaccccjjjjoooooouuuxxuuvvvvvqqqqmmmdddcccc\n",
        "abaaaaaaaaaacccccccaaaaaaacaacccaacaaacccjjjooooouuuuxxxxvvvvvvvqqqmmmdddcccc\n",
        "abaaaaaaaaaacccaaacaaaaaaaaaacccacccaaccjjjooootttuuuxxxyyvyyvvvqqqmmmeeecccc\n",
        "abcccaaacaaacccaaaaaaacaaaaaccccccccccccjjjooottttxxxxxxyyyyyyvvqqqmmmeeccccc\n",
        "abcccaaacccccccaaaaaacaaaaaccccaaccaacccjjjnnntttxxxxxxxyyyyyvvvqqqnneeeccccc\n",
        "SbccccaacccccccaaaaaaaaacaaacccaaaaaacccjjjnnntttxxxEzzzzyyyyvvqqqnnneeeccccc\n",
        "abcccccccccccccaaaaaaaaacaaccccaaaaaccccjjjnnnttttxxxxyyyyyvvvrrrnnneeecccccc\n",
        "abcccaacccccccaaaaaaaaaccccccccaaaaaacccciiinnnttttxxxyyyyywvvrrrnnneeecccccc\n",
        "abcccaaaaaaccaaaaaaaacccccccccaaaaaaaaccciiiinnnttttxyyywyyywvrrrnnneeecccccc\n",
        "abcccaaaaaaccaaaaaaaacccccccccaaaaaaaacccciiinnnntttxwywwyyywwwrrnnneeecccccc\n",
        "abcaaaaaaaccaaaaaaaaaccccccccccccaacccccccciiinnnttwwwwwwwwwwwwrrnnneeecccccc\n",
        "abcaaaaaaaccaaaaaacccccccccccccccaaccccccaaiiiinnttwwwwwwwwwwwrrrnnnffecccccc\n",
        "abcccaaaaaaccaaaaaccccccccccccccccccccaaaaaciiinnssswwwssssrwwrrrnnnfffcccccc\n",
        "abaacaaccaaccaaaccccccccaacccccccccccccaaaaaiiinnssssssssssrrrrrronnfffcccccc\n",
        "abaccaaccaacccccccccaaacaacccccccccccccaaaaaiiimmmssssssmoosrrrrooonffaaacccc\n",
        "abaaaccccaaaaaaccccccaaaaaccccccccccccaaaaaccihmmmmsssmmmoooooooooofffaaacccc\n",
        "abaaaccccaaaaaacccccccaaaaaacccccccccccccaacchhhmmmmmmmmmoooooooooffffaaccccc\n",
        "abaacccaaaaaaaccccccaaaaaaaaccccaaccccccccccchhhhmmmmmmmgggggooofffffaaaccccc\n",
        "abaacccaaaaaaaccccccaaaaaaaccccaaaaccccccccccchhhhmmmmhggggggggfffffaaaaccccc\n",
        "abccccccaaaaaaacccccaacaaaaacccaaaaccccccccccchhhhhhhhggggggggggfffaacaaccccc\n",
        "abccaacccaaaaaaccccccccaaaaaccaaaaacccccccccccchhhhhhhggaaaaaaccccccccccccccc\n",
        "abccaaaccaaccccccccccccccaaaaaaaaaccccccccccccccchhhhaaaccaaaacccccccccccccaa\n",
        "abaaaaaaaccccccccccccccccaaaaaaaaccccccccccccccccccccaaaccccaaccccccccccccaaa\n",
        "abaaaaaaaccccccccaaaccccacaaaaaacccccccccccccccccccccaaaccccccccccccccccccaaa\n",
        "abaaaaaacccccccaaaaacaaaaaaaaaaacccccccccccccccccccccaaccccccccccccccccaaaaaa\n",
        "abaaaaaacccccccaaaaaaaaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccaaaaaa'''"
      ],
      "metadata": {
        "id": "1eXIYh8R7R3L"
      },
      "execution_count": 4,
      "outputs": []
    }
  ]
}