2021/Notebooks/day15.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from queue import PriorityQueue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.genfromtxt('../inputs/input-day15',delimiter=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pad data with infinite values so boundary conditions are easier:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.pad(data, 1, constant_values = np.inf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dijkstra Algorithm using a priority queue (python builtin):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dijkstra(graph):\n",
    "    Q = PriorityQueue()\n",
    "    dist = np.zeros(graph.shape)\n",
    "    dist[:] = np.inf\n",
    "    dist[1,1] = 0\n",
    "    prev = {}\n",
    "    \n",
    "    for i in range(1, graph.shape[0]):\n",
    "        for j in range(1, graph.shape[1]):\n",
    "            Q.put((dist[i,j], (i,j)))\n",
    "\n",
    "    while not Q.empty() > 0:\n",
    "\n",
    "        u = Q.get()[1]\n",
    "        if u == (len(graph) - 2, len(graph) - 2):\n",
    "            break\n",
    "        \n",
    "        for del_x in [-1,0,1]:\n",
    "            for del_y in [-1,0,1]:\n",
    "                if abs(del_x + del_y) != 1:\n",
    "                    continue\n",
    "                v = (u[0]+del_x, u[1]+del_y) \n",
    "                alt = dist[u] + graph[v]\n",
    "                if alt < dist[v]:\n",
    "                    dist[v] = alt\n",
    "                    prev[v] = u\n",
    "                    Q.put((alt, v))\n",
    "                    \n",
    "    return dist, prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def best_path(data):\n",
    "    dist, prev = dijkstra(data)\n",
    "\n",
    "    S = []\n",
    "    u = (len(data) - 2, len(data) - 2)\n",
    "\n",
    "    while u is not None:\n",
    "        S.append(u)\n",
    "        u = prev.get(u)\n",
    "\n",
    "    S = S[::-1]\n",
    "    return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "path = best_path(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "698"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int(sum([data[i,j] for (i,j) in path[1:]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "--------\n",
    "## Task 2\n",
    "Augment the initial input:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dup(arr):\n",
    "    extra = [arr]\n",
    "    tmp = arr\n",
    "    for _ in range(4):\n",
    "        tmp = tmp + 1\n",
    "        tmp[tmp == 10] = 1\n",
    "        extra.append(tmp)\n",
    "    return extra"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.genfromtxt('../inputs/input-day15',delimiter=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_line = np.hstack(dup(data))\n",
    "data = np.vstack(dup(data_line))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.pad(data, 1, constant_values = np.inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "path = best_path(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3022"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int(sum([data[i,j] for (i,j) in path[1:]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.9.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}