{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "\n",
    "# Define directions and corresponding movements\n",
    "DIRECTIONS = ['N', 'E', 'S', 'W']\n",
    "MOVEMENTS = {\n",
    "    'N': (0, -1),  # Move up\n",
    "    'E': (1, 0),   # Move right\n",
    "    'S': (0, 1),   # Move down\n",
    "    'W': (-1, 0)   # Move left\n",
    "}\n",
    "\n",
    "# Parse the ASCII map into a graph with movement and turning costs\n",
    "def parse_ascii_map_with_costs(ascii_map):\n",
    "    graph = nx.DiGraph()  # Directed graph for handling edge weights\n",
    "    rows = ascii_map.strip().split(\"\\n\")\n",
    "    height, width = len(rows), len(rows[0])\n",
    "\n",
    "    start, end = None, None\n",
    "    for y, row in enumerate(rows):\n",
    "        for x, char in enumerate(row):\n",
    "            if char != '#':  # Walkable space\n",
    "                for direction in DIRECTIONS:  # Add a node for each direction\n",
    "                    graph.add_node((x, y, direction))\n",
    "                if char == 'S':  # Starting point\n",
    "                    start = (x, y, 'E')  # Assume starting direction is North\n",
    "                elif char == 'E':  # Ending point\n",
    "                    end = (x, y)\n",
    "\n",
    "                # Add edges for moving forward\n",
    "                for direction in DIRECTIONS:\n",
    "                    dx, dy = MOVEMENTS[direction]\n",
    "                    nx_new, ny_new = x + dx, y + dy\n",
    "                    if 0 <= nx_new < width and 0 <= ny_new < height and rows[ny_new][nx_new] != '#':\n",
    "                        if rows[ny_new][nx_new] == 'E':\n",
    "                            graph.add_edge((x, y, direction), (nx_new, ny_new), weight=1)\n",
    "                        else:\n",
    "                            graph.add_edge((x, y, direction), (nx_new, ny_new, direction), weight=1)\n",
    "\n",
    "                # Add edges for turning (clockwise and counterclockwise)\n",
    "                for i, direction in enumerate(DIRECTIONS):\n",
    "                    next_dir = DIRECTIONS[(i + 1) % 4]  # Clockwise\n",
    "                    prev_dir = DIRECTIONS[(i - 1) % 4]  # Counterclockwise\n",
    "                    graph.add_edge((x, y, direction), (x, y, next_dir), weight=1000)\n",
    "                    graph.add_edge((x, y, direction), (x, y, prev_dir), weight=1000)\n",
    "\n",
    "    return graph, start, end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('input','r') as infile:\n",
    "    ascii_map = infile.read()\n",
    "\n",
    "# Parse the map and solve\n",
    "graph, start, end = parse_ascii_map_with_costs(ascii_map)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "shortestpath = nx.shortest_path(graph,start,end,weight='weight')\n",
    "shortestpath_cost = nx.shortest_path_length(graph,start,end,weight='weight')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "135512\n"
     ]
    }
   ],
   "source": [
    "print(shortestpath_cost)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "541"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "\n",
    "paths = nx.all_shortest_paths(graph,source=start,target=end,weight='weight')\n",
    "visited_nodes = set()\n",
    "\n",
    "for path in paths:\n",
    "    for grid_node in path:\n",
    "        visited_nodes.add((grid_node[0],grid_node[1]))\n",
    "\n",
    "len(visited_nodes)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "advent",
   "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.13.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}