Notebooks/day-12.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4a4a3f7a-270c-4359-a17c-d0ad8c17563c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "386fe448-1ca7-4f1c-afa2-352747924f51",
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.genfromtxt(\"../inputs/day-12\", dtype=str, delimiter=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "8b77c013-b063-49b0-b74e-7ef73ecbb868",
   "metadata": {},
   "outputs": [],
   "source": [
    "H,W = data.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a49fc5bb-7809-410b-8e83-65bb02e80f5b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(array([20]), array([0]))\n",
      "(array([20]), array([46]))\n"
     ]
    }
   ],
   "source": [
    "print(np.where(data == 'S'))\n",
    "print(np.where(data == 'E'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "09501273-3652-40fa-b5c0-19ff1050c634",
   "metadata": {},
   "outputs": [],
   "source": [
    "start = (20,0)\n",
    "end = (20,46)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d846e666-16b8-455e-8259-498a82224754",
   "metadata": {},
   "outputs": [],
   "source": [
    "data[start] = 'a'\n",
    "data[end] = 'z'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1450a7b-7e4f-43e8-8da2-ede1ab4e2da8",
   "metadata": {},
   "source": [
    "# Dijkstra"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "0a907a82-7937-4ce4-beaa-42317bfa78c1",
   "metadata": {},
   "outputs": [],
   "source": [
    "from queue import PriorityQueue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "231a7161-bfae-4fbf-a836-8a3893724a32",
   "metadata": {},
   "outputs": [],
   "source": [
    "dist = np.ones(data.shape) * np.inf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "f8a3bd2f-83c1-44b0-b6a3-32e34fc4140d",
   "metadata": {},
   "outputs": [],
   "source": [
    "dist[end] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "000617ad-c2dc-49dd-ab01-ee3faaa042d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "q = PriorityQueue()\n",
    "prev = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "afc4de02-81df-4941-b7b7-269afe449ed3",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(H):\n",
    "    for j in range(W):\n",
    "        q.put((dist[i,j], (i,j)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "92123dab-4e6e-4da0-a6ca-9f9b259fdcf0",
   "metadata": {},
   "outputs": [],
   "source": [
    "while q.qsize() > 0:\n",
    "    u_dist, (ux, uy) = q.get()\n",
    "    \n",
    "    for dx in [-1,0,1]:\n",
    "        for dy in [-1,0,1]:\n",
    "            if abs(dx + dy) != 1:\n",
    "                    continue\n",
    "            if (0 <= ux + dx < H) and (0 <= uy + dy < W):\n",
    "                v = (ux + dx, uy + dy)\n",
    "\n",
    "                if ord(data[ux,uy]) - ord(data[v]) >= 2:\n",
    "                    continue\n",
    "\n",
    "                alt = u_dist + 1\n",
    "                if alt < dist[v]:\n",
    "                    dist[v] = alt\n",
    "                    prev[v] = (ux, uy)\n",
    "                    q.put((alt, v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "2d98c4cb-7ead-4bd9-b344-9fa8f1ab7986",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "352.0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dist[start]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7a2c59c-9c6d-48e9-a6a1-5dcf06e9c7cb",
   "metadata": {},
   "source": [
    "-------\n",
    "## Finding Best Path\n",
    "Focusing on points of height 'a' we find the minimum distance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "003840c6-defa-4f00-a80c-ec21b976eed4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "345.0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dist[data == 'a'].min()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a48f946f-a7de-4026-bbe1-bc060e32e943",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}