day-12-hill-climbing-algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 🌟 Advent of Code 2022"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 12: Hill Climbing Algorithm](https://adventofcode.com/2022/day/12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_grid(file):\n",
    "    lines = file.read().strip().splitlines()\n",
    "    return [list(x for x in y) for y in lines]\n",
    "\n",
    "def height_value(height):\n",
    "    normalized_height = \"a\" if height == \"S\" else \"z\" if height == \"E\" else height\n",
    "    return ord(normalized_height) - ord(\"a\")\n",
    "\n",
    "# get list of valid neighbors (their height value can be lower or at most one than that of node)\n",
    "def valid_neighbors(grid, node):\n",
    "    x, y = node\n",
    "    for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "        nx, ny = x + dx, y + dy\n",
    "        if 0 <= nx < len(grid) and 0 <= ny < len(grid[nx]):\n",
    "            # check if move is allowed (at most 1 level of elevation up)\n",
    "            if (height_value(grid[nx][ny]) <= height_value(grid[x][y]) + 1):\n",
    "                yield (nx, ny)\n",
    "\n",
    "# find shortest path from start to end using BFS\n",
    "def bfs(grid, start, end):\n",
    "    # tuple of (node, distance)\n",
    "    queue = [(start, 0)]\n",
    "    visited = set()\n",
    "\n",
    "    while queue:\n",
    "        node, dist = queue.pop(0)\n",
    "        if node == end:\n",
    "            return dist\n",
    "        elif node not in visited:\n",
    "            visited.add(node)\n",
    "            for neighbor in valid_neighbors(grid, node):\n",
    "                queue.append((neighbor, dist + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "file = open(\"./inputs/day-12.txt\", \"r\")\n",
    "height_map = parse_grid(file)\n",
    "\n",
    "# coordinates: (row, column)\n",
    "S, E = None, None\n",
    "for i in range(len(height_map)):\n",
    "    for j in range(len(height_map[i])):\n",
    "        if (height_map[i][j] == \"S\"):\n",
    "            S = (i, j)\n",
    "        elif (height_map[i][j] == \"E\"):\n",
    "            E = (i, j)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Challenge 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The fewest steps required (shortest path) to move from the starting point to the location that should get the best signal is '423' steps.\n"
     ]
    }
   ],
   "source": [
    "shortest_path = bfs(height_map, S, E)\n",
    "\n",
    "print(f\"The fewest steps required (shortest path) to move from the starting point to the location that should get the best signal is '{shortest_path}' steps.\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Challenge 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The fewest steps required (shortest path) to move to any point with elevation 'a' to the location that should get the best signal is '416' steps.\n"
     ]
    }
   ],
   "source": [
    "possible_starting_points = []\n",
    "for i in range(len(height_map)):\n",
    "    for j in range(len(height_map[i])):\n",
    "        if (height_map[i][j] == \"a\"):\n",
    "            possible_starting_points.append((i, j))\n",
    "\n",
    "path_lengths = []\n",
    "for starting_point in possible_starting_points:\n",
    "    shortest_path = bfs(height_map, starting_point, E)\n",
    "    if (shortest_path): # if path exists\n",
    "        path_lengths.append(bfs(height_map, starting_point, E))\n",
    "\n",
    "print(f\"The fewest steps required (shortest path) to move to any point with elevation 'a' to the location that should get the best signal is '{min(path_lengths)}' steps.\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.8 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.9.8"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "6c822c96e91247aa88aa050c21c3cf4338cecd35fe4765b117b1af47ffe54c4d"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}