day10/day10.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8af42f49-644e-40be-95ab-9e067e44d6ce",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "# [Day 10](https://adventofcode.com/2023/day/10)\n",
    "## Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "from dataclasses import dataclass\n",
    "from typing import Iterable, TypedDict, NewType\n",
    "\n",
    "\n",
    "Node = NewType('Node', tuple[int, int])\n",
    "Tube = NewType('Tube', tuple[Node, str])\n",
    "\n",
    "@dataclass(frozen=True)\n",
    "class Edge:\n",
    "    tube: Tube\n",
    "    node: Node\n",
    "\n",
    "\n",
    "def readInput(filename) -> (set[Edge], dict[Node, set[Edge]], dict[Tube, str]):\n",
    "    \"\"\"\n",
    "    Reads the input file and returns the start nodes, the edges and the map of tubes\n",
    "    \"\"\"\n",
    "\n",
    "    tubesMap: dict[Node, str] = dict()\n",
    "    edges: dict[Node, set[Edge]] = defaultdict(set[Edge])\n",
    "    start: Tube = None\n",
    "\n",
    "    with open(filename, 'r') as f:\n",
    "        y = 0\n",
    "        for line in f:\n",
    "            line = line.strip()\n",
    "\n",
    "            x = 0\n",
    "            for c in line:\n",
    "                tube: Tube = None\n",
    "                if c != '.':\n",
    "                    tube = ((y, x), c)\n",
    "                    tubesMap[(y, x)] = c\n",
    "                match c:\n",
    "                    case 'S':\n",
    "                        start = ((y, x), c)\n",
    "                    case '|':\n",
    "                        edges[(y+1, x)].add(Edge(tube, (y-1, x)))\n",
    "                        edges[(y-1, x)].add(Edge(tube, (y+1, x)))\n",
    "                    case '-':\n",
    "                        edges[(y, x+1)].add(Edge(tube, (y, x-1)))\n",
    "                        edges[(y, x-1)].add(Edge(tube, (y, x+1)))\n",
    "                    case 'L':\n",
    "                        edges[(y-1, x)].add(Edge(tube, (y, x+1)))\n",
    "                        edges[(y, x+1)].add(Edge(tube, (y-1, x)))\n",
    "                    case 'J':\n",
    "                        edges[(y-1, x)].add(Edge(tube, (y, x-1)))\n",
    "                        edges[(y, x-1)].add(Edge(tube, (y-1, x)))\n",
    "                    case '7':\n",
    "                        edges[(y+1, x)].add(Edge(tube, (y, x-1)))\n",
    "                        edges[(y, x-1)].add(Edge(tube, (y+1, x)))\n",
    "                    case 'F':\n",
    "                        edges[(y+1, x)].add(Edge(tube, (y, x+1)))\n",
    "                        edges[(y, x+1)].add(Edge(tube, (y+1, x)))\n",
    "                x += 2\n",
    "            y += 2\n",
    "    starts: set[Edge] = set()\n",
    "    for i in [-1, +1]:\n",
    "        if edges[(start[0][0]+i, start[0][1])]:\n",
    "            starts.add(Edge(start, (start[0][0]+i, start[0][1])))\n",
    "        if edges[(start[0][0], start[0][1]+i)]:\n",
    "            starts.add(Edge(start, (start[0][0], start[0][1]+i)))\n",
    "    return starts, edges, tubesMap\n",
    "\n",
    "def printField(starts: set[Edge], tubesMap: dict[Node, str], nodes: Iterable[Node] = list(), nodeChar: str = 'o'):\n",
    "    \"\"\"\n",
    "    Prints the field\n",
    "    \"\"\"\n",
    "\n",
    "    tubeChar = {'|': '║', '-': '═', 'L': '╚', 'J': '╝', '7': '╗', 'F': '╔', 'S': '╬'}\n",
    "\n",
    "    startNodes = [s.node for s in starts]\n",
    "    allKeys = set(nodes).union(tubesMap.keys()).union(startNodes)\n",
    "    minX = min([x for _, x in allKeys])\n",
    "    minY = min([y for y, _ in allKeys])\n",
    "    maxX = max([x for _, x in allKeys])\n",
    "    maxY = max([y for y, _ in allKeys])\n",
    "    for y in range(minY, maxY+1):\n",
    "        for x in range(minX, maxX+1):\n",
    "            if (y, x) in tubesMap:\n",
    "                c = tubesMap[(y, x)]\n",
    "                print(tubeChar[c] if c in tubeChar else c, end='')\n",
    "            elif (y, x) in startNodes:\n",
    "                print('S', end='')\n",
    "            elif (y, x) in nodes:\n",
    "                print(nodeChar, end='')\n",
    "            else:\n",
    "                print('.', end='')\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "96477d8f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Field (tubes and nodes):\n",
      ".........o...............................\n",
      ".╔o╔o╗.╔S╬o╔o╗.╔o╗.╔o╗.╔o╗.╔o╗.╔o═o═o═o╗.\n",
      ".o.o.o.o.S.o.o.o.o.o.o.o.o.o.o.o.......o.\n",
      ".╚o║.╚o╝.║.║.║.║.║.║.║.║.║.║.║.║.╔o═o═o╝.\n",
      "...o.....o.o.o.o.o.o.o.o.o.o.o.o.o.......\n",
      ".╔o╚o═o╗.╚o╝.╚o╝.║.║.║.║.║.║.╚o╝.╚o═o╗o╗.\n",
      ".o.....o.........o.o.o.o.o.o.........o.o.\n",
      ".╔o═o═o╝.╔o═o═o╗.║.║.╚o╝.╚o╝o╗.╔o╗.╔o╝o═o\n",
      ".o.......o.....o.o.o...o.o...o.o.o.o.o...\n",
      ".╚o═o═o═o╝.╔o═o╝.╚o╝...║.║o═o╔o╝.╚o╝o╝o╗.\n",
      ".o...o.....o...........o.o...o...o.o...o.\n",
      ".║.╔o║.╔o═o╝.╔o═o═o═o╗.╔o╗o═o╚o╗.╚o║o╗.║.\n",
      ".o.o.o.o.....o.......o.o.o.o.o.o...o.o.o.\n",
      ".║.╔o╔o╝.╔o╗.╚o╗.╔o═o╝.╔o╗.║o╝.╚o═o═o═o╗.\n",
      ".o.o.o...o.o...o.o.....o.o.o...........o.\n",
      "o╗o═o╚o═o╝.╚o╗.║.║.╔o╗.║.╚o╗.╔o═o╗.╔o╗.║.\n",
      ".o...o...o...o.o.o.o.o.o...o.o...o.o.o.o.\n",
      ".╚o..╚o╗.╚o╔o╝.║.║.║.║.║.╔o╝.╚o╗.║.║.╚o╝.\n",
      ".o...o.o.o.o...o.o.o.o.o.o.....o.o.o...o.\n",
      ".╚o╗o╝.╚o╝.╚o═o╝.╚o╝.╚o╝.╚o═o═o╝.╚o╝...╚o\n",
      "...o.....................................\n",
      "\n",
      "Cycle (tubes only):\n",
      ".╔╗╔╬╔╗╔╗╔╗╔╗╔╗╔═══╗\n",
      ".║╚╝║║║║║║║║║║║║╔══╝\n",
      ".╚═╗╚╝╚╝║║║║║║╚╝╚═╗.\n",
      "╔══╝╔══╗║║╚╝╚╝.╔╗╔╝.\n",
      "╚═══╝╔═╝╚╝....╔╝╚╝..\n",
      "...╔═╝╔═══╗...╚╗....\n",
      "..╔╝╔╗╚╗╔═╝╔╗..╚═══╗\n",
      "..╚═╝╚╗║║╔╗║╚╗╔═╗╔╗║\n",
      ".....╔╝║║║║║╔╝╚╗║║╚╝\n",
      ".....╚═╝╚╝╚╝╚══╝╚╝..\n",
      "80\n"
     ]
    }
   ],
   "source": [
    "starts, edges, tubesMap = readInput('test3.txt')\n",
    "\n",
    "print('Field (tubes and nodes):')\n",
    "printField(starts, tubesMap, edges)\n",
    "\n",
    "\n",
    "def next(current: Node, edges: dict[Node, set[Edge]], visited: set[Node]) -> Edge:\n",
    "    for e in edges[current]:\n",
    "        if e.node not in visited:\n",
    "            return e\n",
    "    return None\n",
    "\n",
    "def cycle(starts, edges) -> list[Edge]:\n",
    "    for start in starts:\n",
    "        current: Edge = start\n",
    "        visited: set[Node] = set()\n",
    "        visitedEdges: list[Edge] = list()\n",
    "        while current is not None:\n",
    "            visitedEdges.append(current)\n",
    "            visited.add(current.node)\n",
    "            current = next(current.node, edges, visited)\n",
    "        \n",
    "        if sum([1 if s.node in visited else 0 for s in starts]) == 2:\n",
    "            return visitedEdges\n",
    "path = cycle(starts, edges)\n",
    "\n",
    "print(\"\\nCycle (tubes only):\")\n",
    "printField(set(), {(p.tube[0][0]//2, p.tube[0][1]//2):p.tube[1] for p in path})\n",
    "\n",
    "print(len(path)//2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "12488988",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Outside:\n",
      "░░╔o╗░╔o╬░╔o╗░╔o╗░╔o╗░╔o╗░╔o╗░╔o═o═o═o╗\n",
      "░░o.o░o.o░o.o░o.o░o.o░o.o░o.o░o.......o\n",
      "░░║.╚o╝.║░║.║░║.║░║.║░║.║░║.║░║.╔o═o═o╝\n",
      "░░o.....o░o.o░o.o░o.o░o.o░o.o░o.o░░░░░░\n",
      "░░╚o═o╗.╚o╝.╚o╝.║░║.║░║.║░║.╚o╝.╚o═o╗░░\n",
      "░░░░░░o.........o░o.o░o.o░o.........o░░\n",
      "╔o═o═o╝.╔o═o═o╗.║░║.╚o╝.╚o╝...╔o╗.╔o╝░░\n",
      "o.......o░░░░░o.o░o...........o░o.o░░░░\n",
      "╚o═o═o═o╝░╔o═o╝.╚o╝.........╔o╝░╚o╝░░░░\n",
      "░░░░░░░░░░o.................o░░░░░░░░░░\n",
      "░░░░░░╔o═o╝.╔o═o═o═o╗.......╚o╗░░░░░░░░\n",
      "░░░░░░o.....o░░░░░░░o.........o░░░░░░░░\n",
      "░░░░╔o╝.╔o╗.╚o╗░╔o═o╝.╔o╗.....╚o═o═o═o╗\n",
      "░░░░o...o░o...o░o.....o░o.............o\n",
      "░░░░╚o═o╝░╚o╗.║░║.╔o╗.║░╚o╗.╔o═o╗.╔o╗.║\n",
      "░░░░░░░░░░░░o.o░o.o░o.o░░░o.o░░░o.o░o.o\n",
      "░░░░░░░░░░╔o╝.║░║.║░║.║░╔o╝.╚o╗░║.║░╚o╝\n",
      "░░░░░░░░░░o...o░o.o░o.o░o.....o░o.o░░░░\n",
      "░░░░░░░░░░╚o═o╝░╚o╝░╚o╝░╚o═o═o╝░╚o╝░░░░\n",
      "\n",
      "Outside (tubes only):\n",
      "░╔╗╔╬╔╗╔╗╔╗╔╗╔╗╔═══╗\n",
      "░║╚╝║║║║║║║║║║║║╔══╝\n",
      "░╚═╗╚╝╚╝║║║║║║╚╝╚═╗░\n",
      "╔══╝╔══╗║║╚╝╚╝.╔╗╔╝░\n",
      "╚═══╝╔═╝╚╝....╔╝╚╝░░\n",
      "░░░╔═╝╔═══╗...╚╗░░░░\n",
      "░░╔╝╔╗╚╗╔═╝╔╗..╚═══╗\n",
      "░░╚═╝╚╗║║╔╗║╚╗╔═╗╔╗║\n",
      "░░░░░╔╝║║║║║╔╝╚╗║║╚╝\n",
      "░░░░░╚═╝╚╝╚╝╚══╝╚╝░░\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "starts, edges, tubesMap = readInput('test3.txt')\n",
    "\n",
    "path = cycle(starts, edges)\n",
    "\n",
    "allNodes = set([p.node for p in path]).union([p.tube[0] for p in path])\n",
    "\n",
    "def floodOutside(path):\n",
    "    visited: set[Node] = set()\n",
    "    toVisit: set[Node] = set()\n",
    "\n",
    "    allNodes = set([p.node for p in path]).union([p.tube[0] for p in path])\n",
    "\n",
    "\n",
    "    maxL = max([n[0] for n in allNodes])\n",
    "    maxC = max([n[1] for n in allNodes])\n",
    "\n",
    "    for l in (0, maxL):\n",
    "        for c in range(maxC+1):\n",
    "            if (l, c) not in allNodes:\n",
    "                toVisit.add((l, c))\n",
    "\n",
    "    for c in (0, maxC):\n",
    "        for l in range(maxL+1):\n",
    "            if (l, c) not in allNodes:\n",
    "                toVisit.add((l, c))\n",
    "    \n",
    "    outside = set()\n",
    "    while toVisit:\n",
    "        current = toVisit.pop()\n",
    "        visited.add(current)\n",
    "        if current not in allNodes:\n",
    "            outside.add(current)\n",
    "            for i in (-1, +1):\n",
    "                n = (current[0]+i, current[1])\n",
    "                if 0 <= n[0] <= maxL and n not in visited:\n",
    "                    toVisit.add(n)\n",
    "                n = (current[0], current[1]+i)\n",
    "                if  0 <= n[1] <= maxC and n not in visited:\n",
    "                    toVisit.add(n)\n",
    "\n",
    "    return outside\n",
    "\n",
    "print(\"Outside:\")\n",
    "outside = floodOutside(path)\n",
    "cycleMap = {(p.tube[0][0], p.tube[0][1]):p.tube[1] for p in path}\n",
    "cycleMap.update({(p.node[0], p.node[1]):'o' for p in path})\n",
    "printField(set(), cycleMap, outside, '░')\n",
    "\n",
    "\n",
    "tubeMap = {(p.tube[0][0]//2, p.tube[0][1]//2):p.tube[1] for p in path}\n",
    "outside2 = set([(o[0]//2, o[1]//2) for o in outside])\n",
    "\n",
    "print(\"\\nOutside (tubes only):\")\n",
    "printField(set(), tubeMap, outside2, '░')\n",
    "\n",
    "maxL = max(max([n[0] for n in tubeMap]), max([n[0] for n in outside2]))\n",
    "maxC = max(max([n[1] for n in tubeMap]), max([n[1] for n in outside2]))\n",
    "\n",
    "notInside = outside2.union(tubeMap.keys())\n",
    "\n",
    "print((maxL+1)*(maxC+1) - len(notInside))\n",
    "        \n",
    "    "
   ]
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}