src/day_18.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "51081afa",
   "metadata": {},
   "source": [
    "> # Day 18: Lavaduct Lagoon\n",
    ">\n",
    "> Thanks to your efforts, the machine parts factory is one of the first factories up and running since the lavafall came back. However, to catch up with the large backlog of parts requests, the factory will also need a large supply of lava for a while; the Elves have already started creating a large lagoon nearby for this purpose.\n",
    ">\n",
    "> However, they aren't sure the lagoon will be big enough; they've asked you to take a look at the dig plan (your puzzle input). For example:\n",
    ">\n",
    "> ```\n",
    "> R 6 (#70c710)\n",
    "> D 5 (#0dc571)\n",
    "> L 2 (#5713f0)\n",
    "> D 2 (#d2c081)\n",
    "> R 2 (#59c680)\n",
    "> D 2 (#411b91)\n",
    "> L 5 (#8ceee2)\n",
    "> U 2 (#caa173)\n",
    "> L 1 (#1b58a2)\n",
    "> U 2 (#caa171)\n",
    "> R 2 (#7807d2)\n",
    "> U 3 (#a77fa3)\n",
    "> L 2 (#015232)\n",
    "> U 2 (#7a21e3)\n",
    "> ```\n",
    ">\n",
    "> The digger starts in a 1 meter cube hole in the ground. They then dig the specified number of meters up (U), down (D), left (L), or right (R), clearing full 1 meter cubes as they go. The directions are given as seen from above, so if \"up\" were north, then \"right\" would be east, and so on. Each trench is also listed with the color that the edge of the trench should be painted as an RGB hexadecimal color code.\n",
    ">\n",
    "> When viewed from above, the above example dig plan would result in the following loop of trench (#) having been dug out from otherwise ground-level terrain (.):\n",
    ">\n",
    "> ```\n",
    "> #######\n",
    "> #.....#\n",
    "> ###...#\n",
    "> ..#...#\n",
    "> ..#...#\n",
    "> ###.###\n",
    "> #...#..\n",
    "> ##..###\n",
    "> .#....#\n",
    "> .######\n",
    "> ```\n",
    ">\n",
    "> At this point, the trench could contain 38 cubic meters of lava. However, this is just the edge of the lagoon; the next step is to dig out the interior so that it is one meter deep as well:\n",
    ">\n",
    "> ```\n",
    "> #######\n",
    "> #######\n",
    "> #######\n",
    "> ..#####\n",
    "> ..#####\n",
    "> #######\n",
    "> #####..\n",
    "> #######\n",
    "> .######\n",
    "> .######\n",
    "> ```\n",
    ">\n",
    "> Now, the lagoon can contain a much more respectable 62 cubic meters of lava. While the interior is dug out, the edges are also painted according to the color codes in the dig plan.\n",
    ">\n",
    "> The Elves are concerned the lagoon won't be large enough; if they follow their dig plan, how many cubic meters of lava could it hold?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "656d9a71",
   "metadata": {},
   "source": [
    "All right, we're dealing with loops and areas contained within them again, a throwback to day 10. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fbd9c02",
   "metadata": {},
   "source": [
    "## Read input\n",
    "\n",
    "Each line has three parts: first, either a L, R, U or D followed by a space, followed by a number and finally followed by a hex number in parentheses. That means regular expression makes a good solution here. For each line, I match that pattern and return its findings with distance casted to integer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "0ac7468d",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import read_input\n",
    "import re\n",
    "\n",
    "def transformer(line):\n",
    "    direction, distance, color = re.findall(r'(L|R|U|D) (\\d+) \\((.*)\\)', line)[0]\n",
    "    return direction, int(distance), color\n",
    "    \n",
    "instructions = read_input(18, transformer)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05ebab75",
   "metadata": {},
   "source": [
    "To dig the original trench, based on the instructions, I keep track of every coordinate we run into in a set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "81e04603",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Direction:\n",
    "    LEFT = 'L'\n",
    "    RIGHT = 'R'\n",
    "    UP = 'U'\n",
    "    DOWN = 'D'\n",
    "    \n",
    "class Tile:\n",
    "    DUG = '#'\n",
    "    CLEAR = '.'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "1d593557",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dig(start, instructions):\n",
    "    digged = set([start])\n",
    "    \n",
    "    current = start\n",
    "    for direction, distance, _ in instructions:\n",
    "        for _ in range(distance):\n",
    "            match direction:\n",
    "                case Direction.LEFT:\n",
    "                    current -= 1\n",
    "                case Direction.RIGHT:\n",
    "                    current += 1\n",
    "                case Direction.UP:\n",
    "                    current += 1j\n",
    "                case Direction.DOWN:\n",
    "                    current -= 1j\n",
    "            digged.add(current)\n",
    "    return digged"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af32d2f2",
   "metadata": {},
   "source": [
    "After digging the boundaries, I create a grid with dug positions as `#` and non-dug positions as `.`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "3ba717c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_grid(boundaries):\n",
    "    grid = {}\n",
    "    min_x = int(min(coord.real for coord in boundaries))\n",
    "    max_x = int(max(coord.real for coord in boundaries))\n",
    "    min_y = int(min(coord.imag for coord in boundaries))\n",
    "    max_y = int(max(coord.imag for coord in boundaries))\n",
    "    \n",
    "    for y in range(max_y, min_y-1, -1):\n",
    "        for x in range(min_x, max_x+1):\n",
    "            pos = x + y * 1j\n",
    "            if pos in boundaries:\n",
    "                grid[pos] = Tile.DUG\n",
    "            else:\n",
    "                grid[pos] = Tile.CLEAR\n",
    "    return grid"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b90cc9c",
   "metadata": {},
   "source": [
    "I had once again trouble figuring out which positions are inside and which are outside the area. To shortcut this a bit, I'm looking at the directions of the first and last instruction.\n",
    "\n",
    "Since these instructions create a loop, I can use these to determine at least one tile that's inside the area. It works with 75% of the possible combos as I didn't want to figure out how to determine which side is inside if the start position is a flat.\n",
    "\n",
    "Turns out, with my input, the start was a corner so this worked.\n",
    "\n",
    "Generally, I hate doing these kind of things that rely on anything being a specific in the input. But today I'm lenient to myself because this stuff is hard, m'kay."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a86d9718",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_first_interior_position(instructions):\n",
    "    match (instructions[0][0], instructions[-1][0]):\n",
    "        case (Direction.RIGHT,Direction.UP):\n",
    "            return (1-1j)\n",
    "        case (Direction.RIGHT,Direction.DOWN):\n",
    "            return (1+1j)\n",
    "        case (Direction.RIGHT,Direction.RIGHT):\n",
    "            raise NotImplemented('Right + Right')\n",
    "\n",
    "        case (Direction.LEFT, Direction.DOWN):\n",
    "            return -1+1j\n",
    "        case (Direction.LEFT, Direction.UP):\n",
    "            return -1-1j\n",
    "        case (Direction.LEFT, Direction.LEFT):\n",
    "            raise NotImplemented('Left + Left')\n",
    "\n",
    "        case (Direction.DOWN, Direction.DOWN):\n",
    "            raise NotImplemented('Down + Down')\n",
    "        case (Direction.DOWN, Direction.RIGHT):\n",
    "            return -1-1j\n",
    "        case (Direction.DOWN, Direction.LEFT):\n",
    "            return 1-1j\n",
    "\n",
    "        case (Direction.UP, Direction.UP):\n",
    "            raise NotImplemented('Up + Up')\n",
    "        case (Direction.UP, Direction.RIGHT):\n",
    "            return 1-1j\n",
    "        case (Direction.UP, Direction.LEFT):\n",
    "            return -1-1j\n",
    "            \n",
    "        case _:\n",
    "            raise ValueError('Unknown combination of directions')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31845734",
   "metadata": {},
   "source": [
    " I also wrote a debug function to print my grids before and after filling them to see where issues were."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "70846dfa",
   "metadata": {},
   "outputs": [],
   "source": [
    "def debug(grid):\n",
    "    min_x = int(min(coord.real for coord in boundaries))\n",
    "    max_x = int(max(coord.real for coord in boundaries))\n",
    "    min_y = int(min(coord.imag for coord in boundaries))\n",
    "    max_y = int(max(coord.imag for coord in boundaries))\n",
    "    for y, row in enumerate(range(max_y, min_y -1, -1)):\n",
    "        for x, cell in enumerate(range(min_x, max_x+1)):\n",
    "            print(grid[x + y * -1j], end=\"\")\n",
    "        print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04b0dc12",
   "metadata": {},
   "source": [
    "To find out which tiles should be dug and which not, I start from a position I know is inside the grid and then go through all the neighbors, skipping those that are part of the boundary or already visited and digging holes in the rest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "77e6c3be",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dig_the_rest(start, boundaries, grid):\n",
    "    new_grid = grid.copy()\n",
    "    unfilled = set([start])\n",
    "    visited = set()\n",
    "    while unfilled:\n",
    "        start = unfilled.pop()\n",
    "        neighbors = [start + 1, start - 1, start + 1j, start - 1j]\n",
    "        for n in neighbors:\n",
    "            if n in boundaries or n in visited:\n",
    "                continue\n",
    "            unfilled.add(n)\n",
    "        visited.add(start)\n",
    "        new_grid[start] = Tile.DUG\n",
    "    return new_grid"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4d57610",
   "metadata": {},
   "source": [
    "To calculate the final result, I dig the boundaries, create the grid, find the first known spot inside the loop and dig the rest. I then use [Counter](https://docs.python.org/3/library/collections.html#collections.Counter) to calculate how many of the tiles in the grid are dug."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "7c2d42a3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution: 62500\n"
     ]
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "boundaries = dig(0, instructions)\n",
    "grid = create_grid(boundaries)\n",
    "first_interior = find_first_interior_position(instructions)\n",
    "\n",
    "filled = dig_the_rest(first_interior, boundaries, grid)\n",
    "part_1 = Counter(filled.values())[Tile.DUG]\n",
    "\n",
    "print(f'Solution: {part_1}')\n",
    "assert part_1 == 62500"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d9b90c8",
   "metadata": {},
   "source": [
    "## Part 2\n",
    "\n",
    ">The Elves were right to be concerned; the planned lagoon would be much too small.\n",
    ">\n",
    ">After a few minutes, someone realizes what happened; someone swapped the color and instruction parameters when producing the dig plan. They don't have time to fix the bug; one of them asks if you can extract the correct instructions from the hexadecimal codes.\n",
    ">\n",
    ">Each hexadecimal code is six hexadecimal digits long. The first five hexadecimal digits encode the distance in meters as a five-digit hexadecimal number. The last hexadecimal digit encodes the direction to dig: 0 means R, 1 means D, 2 means L, and 3 means U.\n",
    ">\n",
    ">So, in the above example, the hexadecimal codes can be converted into the true instructions:\n",
    ">\n",
    "> - #70c710 = R 461937\n",
    "> - #0dc571 = D 56407\n",
    "> - #5713f0 = R 356671\n",
    "> - #d2c081 = D 863240\n",
    "> - #59c680 = R 367720\n",
    "> - #411b91 = D 266681\n",
    "> - #8ceee2 = L 577262\n",
    "> - #caa173 = U 829975\n",
    "> - #1b58a2 = L 112010\n",
    "> - #caa171 = D 829975\n",
    "> - #7807d2 = L 491645\n",
    "> - #a77fa3 = U 686074\n",
    "> - #015232 = L 5411\n",
    "> - #7a21e3 = U 500254\n",
    ">\n",
    ">Digging out this loop and its interior produces a lagoon that can hold an impressive 952408144115 cubic meters of lava.\n",
    ">\n",
    ">Convert the hexadecimal color codes into the correct instructions; if the Elves follow this new dig plan, how many cubic meters of lava could the lagoon hold?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f67d3e0",
   "metadata": {},
   "source": [
    "Those are some big numbers out there."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "629f5a03",
   "metadata": {},
   "source": [
    "The part that I was able to figure out was how to convert the old instructions to the correct ones.\n",
    "\n",
    "For each color value in each instruction, I skip the `#`, convert the next 5 numbers to a decimal with `int(num, 16)` and convert the last digit to a direction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "83f7ca8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_correct_instructions(instructions): \n",
    "    correct_instructions = []\n",
    "    directions = {\n",
    "        0: 'R',\n",
    "        1: 'D',\n",
    "        2: 'L',\n",
    "        3: 'U'\n",
    "    }\n",
    "\n",
    "    for _, _, hexa in instructions:\n",
    "        distance = int(hexa[1:-1], 16)\n",
    "        direction = directions[int(hexa[-1])]\n",
    "        correct_instructions.append((direction, distance))    \n",
    "    return correct_instructions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18578729",
   "metadata": {},
   "source": [
    "After that, my math skills stop. I know from the size of this thing that looping over stuff isn't the way to go or we'll be here waiting for the results when next Christmas rolls over.\n",
    "\n",
    "I think it could be figurable using ranges but after some tinkering, I wasn't able to confidently get correct results."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8eff843c",
   "metadata": {},
   "source": [
    "## Shoelace algorithm\n",
    "\n",
    "I managed to solve the second part after getting a bit of hint. A friend mentioned the phrase [shoelace](https://en.wikipedia.org/wiki/Shoelace_formula) which enabled me to work it out.\n",
    "\n",
    "First, a little helper to calculate the next point. This time I'm using regular `(x,y)` coordinates to make the matrix math easier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "1ac697b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import cache\n",
    "\n",
    "@cache\n",
    "def get_next_point(current, instruction):\n",
    "    direction, distance = instruction\n",
    "    y, x = current\n",
    "    match direction:\n",
    "        case Direction.UP:\n",
    "            return y - distance, x\n",
    "        case Direction.RIGHT:\n",
    "            return y, x + distance\n",
    "        case Direction.LEFT:\n",
    "            return y, x - distance\n",
    "        case Direction.DOWN:\n",
    "            return y + distance, x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00d61a7c",
   "metadata": {},
   "source": [
    "To solve the second part, I first converted the instructions to be the correct ones.\n",
    "\n",
    "I then created a list of all the corner points of the dig.\n",
    "\n",
    "For each pair of `start -> end` lines, I calculate the matrix determinant as instructed in the Wikipedia article. I then round it up to an integer, take the absolute value (since area can't really be negative) and divide by two to get the shoelace area.\n",
    "\n",
    "I then add half of the boundaries + 1 to compensate for something."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "ecfaa96e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution: 122109860712709\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from itertools import pairwise\n",
    "\n",
    "p2_instructions = get_correct_instructions(instructions)\n",
    "\n",
    "current = (0, 0)\n",
    "points = [current]\n",
    "boundary_size = sum(distance for direction, distance in p2_instructions)\n",
    "for instruction in p2_instructions:\n",
    "    prev = current\n",
    "    current = get_next_point(current, instruction)\n",
    "    points.append(current)\n",
    "\n",
    "area = 0\n",
    "for start, end in pairwise(points):\n",
    "    ar = np.array([start, end])\n",
    "    det = np.linalg.det(ar)\n",
    "    area += det\n",
    "    \n",
    "shoelace_area = abs(round(area)) / 2\n",
    "part_2 = int(shoelace_area + boundary_size / 2 + 1)\n",
    "\n",
    "print(f'Solution: {part_2}')\n",
    "assert part_2 == 122109860712709"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76176ec0",
   "metadata": {},
   "source": [
    "## ~~One star today~~ Make that two!\n",
    "\n",
    "One star ain't bad. The best alcholic drink is a [1-star Jallu](https://en.wikipedia.org/wiki/Cut_brandy#Finland) so I'm always happy with one.\n",
    "\n",
    "After bit of help, I got the second star as well and am now at 34."
   ]
  }
 ],
 "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.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}