Day15.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a39dc127-bfa3-41e5-b814-340953ed3d7b",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"Day15.txt\") as file:\n",
    "    boxes, moves = file.read().split(\"\\n\\n\")\n",
    "moves = \"\".join(moves.splitlines())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8f9778d5-3f62-4a22-8250-016ab512639e",
   "metadata": {},
   "outputs": [],
   "source": [
    "DIRECTIONS = {\"<\": (-1, 0), \">\": (+1, 0), \"^\": (0, -1), \"v\": (0, +1)}\n",
    "\n",
    "def build(boxes, double=False):\n",
    "    grid = {}\n",
    "    if double:\n",
    "        boxes = (\n",
    "            boxes\n",
    "            .replace(\"#\", \"##\")\n",
    "            .replace(\"O\", \"[]\")\n",
    "            .replace(\".\", \"..\")\n",
    "            .replace(\"@\", \"@.\"))\n",
    "    for y, line in enumerate(boxes.splitlines()):\n",
    "        for x, char in enumerate(line):\n",
    "            grid[x, y] = char\n",
    "            if char == \"@\":\n",
    "                start = x, y\n",
    "    return grid, start\n",
    "\n",
    "def backup(grid, coords, direction):\n",
    "    # Recursively replace every item in front of the robot\n",
    "    # until reaching a wall or empty space.\n",
    "    # Crates force recursivity on two columns.\n",
    "    (x, y), (dx, dy) = coords, direction\n",
    "    if (v := grid[x, y]) in \"#.\":\n",
    "        return {}\n",
    "    grid[coords] = \".\"\n",
    "    items = {(x, y): v}\n",
    "    items |= backup(grid, (x + dx, y + dy), direction)\n",
    "    if v == \"[\":\n",
    "        items |= backup(grid, (x + 1, y), direction)\n",
    "    if v == \"]\":\n",
    "        items |= backup(grid, (x - 1, y), direction)\n",
    "    return items\n",
    "\n",
    "def solve(grid, moves, start):\n",
    "    x, y = start\n",
    "    for move in moves:\n",
    "        dx, dy = DIRECTIONS[move]\n",
    "        items = backup(grid, (x, y), (dx, dy))\n",
    "        if all(grid[x + dx, y + dy] == \".\" for x, y in items):\n",
    "            items = {(x + dx, y + dy): v for (x, y), v in items.items()}\n",
    "            x, y = x + dx, y + dy\n",
    "        grid.update(items)\n",
    "    return sum(y * 100 + x for (x, y), v in grid.items() if v in \"O[\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "d97bc532-2b4b-4744-b63e-82f7b7e38274",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 23.1 ms, sys: 12 μs, total: 23.1 ms\n",
      "Wall time: 22.6 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1456590"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "grid, start = build(boxes)\n",
    "solve(grid, moves, start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6294ca3f-491d-4dea-9033-9f1a37d25b53",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 28 ms, sys: 2 μs, total: 28 ms\n",
      "Wall time: 28.2 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1489116"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "grid, start = build(boxes, double=True)\n",
    "solve(grid, moves, start)"
   ]
  }
 ],
 "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.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}