src/day_14.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c7caef84",
   "metadata": {},
   "source": [
    "# Day 14: Parabolic Reflector Dish\n",
    ">\n",
    ">You reach the place where all of the mirrors were pointing: a massive parabolic reflector dish attached to the side of another large mountain.\n",
    ">\n",
    ">The dish is made up of many small mirrors, but while the mirrors themselves are roughly in the shape of a parabolic reflector dish, each individual mirror seems to be pointing in slightly the wrong direction. If the dish is meant to focus light, all it's doing right now is sending it in a vague direction.\n",
    ">\n",
    ">This system must be what provides the energy for the lava! If you focus the reflector dish, maybe you can go where it's pointing and use the light to fix the lava production.\n",
    ">\n",
    ">Upon closer inspection, the individual mirrors each appear to be connected via an elaborate system of ropes and pulleys to a large metal platform below the dish. The platform is covered in large rocks of various shapes. Depending on their position, the weight of the rocks deforms the platform, and the shape of the platform controls which ropes move and ultimately the focus of the dish.\n",
    ">\n",
    ">In short: if you move the rocks, you can focus the dish. The platform even has a control panel on the side that lets you tilt it in one of four directions! The rounded rocks (O) will roll when the platform is tilted, while the cube-shaped rocks (#) will stay in place. You note the positions of all of the empty spaces (.) and rocks (your puzzle input). For example:\n",
    ">```\n",
    ">O....#....\n",
    ">O.OO#....#\n",
    ">.....##...\n",
    ">OO.#O....O\n",
    ">.O.....O#.\n",
    ">O.#..O.#.#\n",
    ">..O..#O..O\n",
    ">.......O..\n",
    ">#....###..\n",
    ">#OO..#....\n",
    ">```\n",
    ">Start by tilting the lever so all of the rocks will slide north as far as they will go:\n",
    ">```\n",
    ">OOOO.#.O..\n",
    ">OO..#....#\n",
    ">OO..O##..O\n",
    ">O..#.OO...\n",
    ">........#.\n",
    ">..#....#.#\n",
    ">..O..#.O.O\n",
    ">..O.......\n",
    ">#....###..\n",
    ">#....#....\n",
    ">```\n",
    ">You notice that the support beams along the north side of the platform are damaged; to ensure the platform doesn't collapse, you should calculate the total load on the north support beams.\n",
    ">\n",
    ">The amount of load caused by a single rounded rock (O) is equal to the number of rows from the rock to the south edge of the platform, including the row the rock is on. (Cube-shaped rocks (#) don't contribute to load.) So, the amount of load caused by each rock in each row is as follows:\n",
    ">```\n",
    ">OOOO.#.O.. 10\n",
    ">OO..#....#  9\n",
    ">OO..O##..O  8\n",
    ">O..#.OO...  7\n",
    ">........#.  6\n",
    ">..#....#.#  5\n",
    ">..O..#.O.O  4\n",
    ">..O.......  3\n",
    ">#....###..  2\n",
    ">#....#....  1\n",
    ">```\n",
    ">The total load is the sum of the load caused by all of the rounded rocks. In this example, the total load is 136.\n",
    ">\n",
    ">Tilt the platform so that the rounded rocks all roll north. Afterward, what is the total load on the north support beams?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df97cde1",
   "metadata": {},
   "source": [
    "## Read input\n",
    "\n",
    "We'll start by reading the input into a list of strings which is the default functionality in my `read_input` utility funtion.\n",
    "\n",
    "For part 2, I convert the individual lines to lists as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "3eafa1de",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import read_input\n",
    "\n",
    "p1_rocks = read_input(14)\n",
    "p2_rocks = read_input(14, list)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0f74ae4",
   "metadata": {},
   "source": [
    "## Part 1\n",
    "\n",
    "I wanted to try a solution where I don't need to change anything from the input: no shifting values around in lists, no changing coordinates.\n",
    "\n",
    "One thing I almost always do at the beginning is to model the available different values into constants so I don't end up using [magic numbers](https://en.wikipedia.org/wiki/Magic_number_(programming)) and to improve readability in general.\n",
    "\n",
    "To calculate the load after one tilt north, my aptly named function transposes the entire rock formation so that each column becomes a string. This is to make use of [str.rfind](https://docs.python.org/3/library/stdtypes.html#str.rfind) method.\n",
    "\n",
    "I go through each column rock by rock. For each round rock (`O`), I find the closest round or cube rock to the left from its position. If neither is found (`.rfind()` returns -1 if it doesn't find one), the rock is moved all the to the top. If one is found, I calculate the distance it needs to move as its starting position minus the position where there is something minus 1 (since we want it on the next index) plus any movement that has happened since the last cube was faced. \n",
    "\n",
    "The last addition, that I track with `previously_moved` is there because I don't actually move the rocks anywhere. So if one needed to move 2 spots to the top, it's still in the input data at its original spot and need to be taken into account.\n",
    "\n",
    "Finally, the load of a given rock is its new position subtracted from the total length as the smallest indices bear the highest load."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d2ac1e5b",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Rock:\n",
    "    ROUND = 'O'\n",
    "    CUBE = '#'\n",
    "    CLEAR = '.'\n",
    "    \n",
    "def calculate_load_after_tilt_north(rocks):\n",
    "    load = 0\n",
    "    rotated_rocks = [''.join(row) for row in zip(*rocks)]\n",
    "    for column in rotated_rocks:\n",
    "        previously_moved = 0\n",
    "        for index, rock in enumerate(column):\n",
    "            match rock:\n",
    "                case Rock.CUBE:\n",
    "                    previously_moved = 0\n",
    "                case Rock.ROUND:\n",
    "                    closest_cube = column[:index].rfind(Rock.ROUND)\n",
    "                    closest_round = column[:index].rfind(Rock.CUBE)\n",
    "                    closest_stop = max(closest_cube, closest_round)\n",
    "                    if closest_stop < 0:\n",
    "                        step = index\n",
    "                    else:\n",
    "                        step = index - closest_stop - 1 + previously_moved\n",
    "                    previously_moved = step\n",
    "                    load += len(rotated_rocks) - (index - step)\n",
    "                case _:\n",
    "                    continue\n",
    "    return load"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "dd72c64b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution: 105249\n"
     ]
    }
   ],
   "source": [
    "part_1 = calculate_load_after_tilt_north(p1_rocks)\n",
    "print(f'Solution: {part_1}')\n",
    "assert part_1 == 105249"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3bbe4c1b",
   "metadata": {},
   "source": [
    "## Part 2\n",
    "\n",
    ">The parabolic reflector dish deforms, but not in a way that focuses the beam. To do that, you'll need to move the rocks to the edges of the platform. Fortunately, a button on the side of the control panel labeled \"spin cycle\" attempts to do just that!\n",
    ">\n",
    ">Each cycle tilts the platform four times so that the rounded rocks roll north, then west, then south, then east. After each tilt, the rounded rocks roll as far as they can before the platform tilts in the next direction. After one cycle, the platform will have finished rolling the rounded rocks in those four directions in that order.\n",
    ">\n",
    ">Here's what happens in the example above after each of the first few cycles:\n",
    ">```\n",
    ">After 1 cycle:\n",
    ">.....#....\n",
    ">....#...O#\n",
    ">...OO##...\n",
    ">.OO#......\n",
    ">.....OOO#.\n",
    ">.O#...O#.#\n",
    ">....O#....\n",
    ">......OOOO\n",
    ">#...O###..\n",
    ">#..OO#....\n",
    ">\n",
    ">After 2 cycles:\n",
    ">.....#....\n",
    ">....#...O#\n",
    ">.....##...\n",
    ">..O#......\n",
    ">.....OOO#.\n",
    ">.O#...O#.#\n",
    ">....O#...O\n",
    ">.......OOO\n",
    ">#..OO###..\n",
    ">#.OOO#...O\n",
    ">\n",
    ">After 3 cycles:\n",
    ">.....#....\n",
    ">....#...O#\n",
    ">.....##...\n",
    ">..O#......\n",
    ">.....OOO#.\n",
    ">.O#...O#.#\n",
    ">....O#...O\n",
    ">.......OOO\n",
    ">#...O###.O\n",
    ">#.OOO#...O\n",
    ">```\n",
    ">This process should work if you leave it running long enough, but you're still worried about the north support beams. To make sure they'll survive for a while, you need to calculate the total load on the north support beams after 1000000000 cycles.\n",
    ">\n",
    ">In the above example, after 1000000000 cycles, the total load on the north support beams is 64.\n",
    ">\n",
    ">Run the spin cycle for 1000000000 cycles. Afterward, what is the total load on the north support beams?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de33c7d2",
   "metadata": {},
   "source": [
    "I tried to be clever in the first part and avoid moving things around because I was expecting some gargantuan number in the second part. I was right that the numbers grew a ton but I have initially no clue if my solution in first part would be helpful at all.\n",
    "\n",
    "My first instinct is that I need to figure out a way to calculate a rock's position after N cycles without actually going through the motions of calculating all the positions in each cycle.\n",
    "\n",
    "To do this, we need to actually tilt the platform and move rocks around. The part 1 would have been way easier and cleaner if I wasn't trying to be a clever boy."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa6cf5bb",
   "metadata": {},
   "source": [
    "## Tilting the platform\n",
    "\n",
    "To tilt the platform, I position the columns in a way that they read left-to-right. It means that when tilting north and south, I transpose the grid and for south and east, I reverse the columns.\n",
    "\n",
    "I then create a new rock grid and each column keep track of all the empty spaces that we can move to. If we run into a clear spot, we increase that count. If we run into a cube, we plot all the accumulated empty spots into the new grid and place a cube rock and reset the empty space counter. Finally, if we run into a round, we add it to the first open spot in the new grid.\n",
    "\n",
    "Finally, we reverse the transformations we did in the start and return the new rock formation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "8fdd5ca6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tilt(rocks, direction):\n",
    "    match direction:\n",
    "        case 'north':\n",
    "            rocks = list(zip(*rocks))\n",
    "            column_direction = 1\n",
    "        case 'south':\n",
    "            rocks = list(zip(*rocks))\n",
    "            column_direction = -1\n",
    "        case 'east':\n",
    "            column_direction = -1\n",
    "        case 'west':\n",
    "            column_direction = 1\n",
    "\n",
    "    new_rocks = []\n",
    "    for column in rocks:\n",
    "        new_column = []\n",
    "        empty_to_left = 0\n",
    "        for rock in column[::column_direction]:\n",
    "            match rock:\n",
    "                case Rock.CLEAR:\n",
    "                    empty_to_left += 1\n",
    "                case Rock.CUBE:\n",
    "                    new_column.extend([Rock.CLEAR] * empty_to_left + [rock])\n",
    "                    empty_to_left = 0\n",
    "                case Rock.ROUND:\n",
    "                    new_column.append(rock)\n",
    "        new_column.extend([Rock.CLEAR] * empty_to_left)\n",
    "        new_rocks.append(new_column[::column_direction])\n",
    "    \n",
    "    if direction in {'north', 'south'}:\n",
    "        return list(zip(*new_rocks))\n",
    "    else:\n",
    "        return new_rocks"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9cc93df",
   "metadata": {},
   "source": [
    "For a complete spint, we go counter clockwise, tilting once north, then west, then south and finally east. At the end of a full spin, we return the rocks. The biggest mistake I originally made here was going clockwise because I made **assumptions**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "4e25e3c9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def spin(rocks):\n",
    "    rocks = tilt(rocks, 'north')\n",
    "    rocks = tilt(rocks, 'west')\n",
    "    rocks = tilt(rocks, 'south')\n",
    "    rocks = tilt(rocks, 'east')\n",
    "    return rocks"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "236df93e",
   "metadata": {},
   "source": [
    "To make sure my tilts were correct, I built a debug printer that printed the grid in a similar fashion than it was in the puzzle page for easier comparison."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5d0ba0ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "def debug(rocks):\n",
    "    for row in rocks:\n",
    "        print(''.join(row))\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cd56ee50",
   "metadata": {},
   "source": [
    "To make it easy to compare a rock formation, I have a `serialize` function that turns the list of lists into a string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "34689a9d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def serialize(rocks):\n",
    "    return ''.join([''.join(row) for row in rocks])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5577e58",
   "metadata": {},
   "source": [
    "To find out the final position after 1,000,000,000 spins, I find the moment when the input is something we've seen before as with the deterministic tilts and spins, we know it will start to loop at that point.\n",
    "\n",
    "## So how does this cycle thing work\n",
    "\n",
    "Let's take a simpler example to look at: \n",
    "\n",
    "```\n",
    "[1, 3, 7, 5, 4, 7, 5, 4, 7, 5, 4, 7, 5]\n",
    "```\n",
    "\n",
    "This is a collection of inputs that when entered through a function, generates the next value. So we'd start with 1, run `func(1) -> 3`, `func(3) -> 7`, and so on.\n",
    "\n",
    "If we look at it from the bird's-eye view, we notice that once we get value `7`, we end up in a loop of `7 -> 5  -> 4` that repeats until the end.\n",
    "\n",
    "To find a cycle, we need to keep track of the inputs and their locations.\n",
    "\n",
    "```python\n",
    "{ 1: 0 } # After first \n",
    "{ 1: 0, 3: 1 } # After second\n",
    "{ 1: 0, 3: 1, 7:2 }\n",
    "{ 1: 0, 3: 1, 7:2, 5:3 }\n",
    "{ 1: 0, 3: 1, 7:2, 5:3, 4:4 }\n",
    "```\n",
    "\n",
    "Now, when we encounter `7` again, we can see that it's already in our collection. We can get the start index of the loop with `collection[7]` which is `2`. Our current iteration is `5` so the cycle size is `5-2 = 3`.\n",
    "\n",
    "Since not all things end cleanly matching the end of a cycle, we need to find out how much of the last broken cycle we need to execute.\n",
    "\n",
    "```\n",
    "      cycle    next             final\n",
    "      start    cycle            cycle\n",
    "       v        v                 v\n",
    "[1, 3, 7, 5, 4, 7, 5, 4, 7, 5, 4, 7, 5]\n",
    "```\n",
    "\n",
    "We take the entire length of the cycle (in this case, `13`), subtract how many we did before the cycle started (in our case `cycle_start = 2` and modulo with the cycle size (`3`). `(13 - 2) % 3 = 2`.\n",
    "\n",
    "So all in all, instead of running 13 iterations, we run 2 iterations at the start, then 3 as part of the loop and finally 2 at the end, total of 7. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "d01748ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "def spin_1000000000(rocks):\n",
    "    cycles = 1000000000\n",
    "    seen_formations = {}\n",
    "    cycle_count = 1\n",
    "    while True:\n",
    "        rocks = spin(rocks)\n",
    "        if serialize(rocks) in seen_formations:\n",
    "            cycle_start = seen_formations[serialize(rocks)]\n",
    "            cycle_size = cycle_count - cycle_start \n",
    "            to_spin = (cycles - cycle_count) % cycle_size\n",
    "            for _ in range(to_spin):\n",
    "                rocks = spin(rocks)\n",
    "            return rocks\n",
    "        seen_formations[serialize(rocks)] = cycle_count\n",
    "        cycle_count += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d1052e9",
   "metadata": {},
   "source": [
    "To calculate the load, I go through each position in the rock formation and for each round rock, calculate the value by subtracting the current row index from the total length."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "93c3cffb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_load(rocks):\n",
    "    load = 0\n",
    "    for y, row in enumerate(rocks):\n",
    "        for x, rock in enumerate(row):\n",
    "            if rock == Rock.ROUND:\n",
    "                load += len(rocks) - y\n",
    "    return load"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "ffd2f7cf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution: 88680\n"
     ]
    }
   ],
   "source": [
    "rocks = spin_1000000000(p2_rocks)\n",
    "\n",
    "part_2 = calculate_load(rocks)\n",
    "print(f'Solution: {part_2}')\n",
    "assert part_2 == 88680"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb487ec9",
   "metadata": {},
   "source": [
    "## Part 1 revisited\n",
    "\n",
    "With the new code written for part 2, part 1 becomes much cleaner."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "1e583d10",
   "metadata": {},
   "outputs": [],
   "source": [
    "rocks = tilt(p1_rocks, 'north')\n",
    "assert calculate_load(rocks) == 105249"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b4a5ec3",
   "metadata": {},
   "source": [
    "## Two stars!\n",
    "\n",
    "28/50. I'm very happy I haven't had to skip a single day yet. According to my previous years, around day 17 I've started to run into issues but let's see how this year pans out."
   ]
  }
 ],
 "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
}