src/day_11.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c927806b",
   "metadata": {},
   "source": [
    "># Day 11: Cosmic Expansion ---\n",
    ">\n",
    ">You continue following signs for \"Hot Springs\" and eventually come across an observatory. The Elf within turns out to be a researcher studying cosmic expansion using the giant telescope here.\n",
    ">\n",
    ">He doesn't know anything about the missing machine parts; he's only visiting for this research project. However, he confirms that the hot springs are the next-closest area likely to have people; he'll even take you straight there once he's done with today's observation analysis.\n",
    ">\n",
    ">Maybe you can help him with the analysis to speed things up?\n",
    ">\n",
    ">The researcher has collected a bunch of data and compiled the data into a single giant image (your puzzle input). The image includes empty space (.) and galaxies (#). For example:\n",
    ">```\n",
    ">...#......\n",
    ">.......#..\n",
    ">#.........\n",
    ">..........\n",
    ">......#...\n",
    ">.#........\n",
    ">.........#\n",
    ">..........\n",
    ">.......#..\n",
    ">#...#.....\n",
    ">```\n",
    ">The researcher is trying to figure out the sum of the lengths of the shortest path between every pair of galaxies. However, there's a catch: the universe expanded in the time it took the light from those galaxies to reach the observatory.\n",
    ">\n",
    ">Due to something involving gravitational effects, only some space expands. In fact, the result is that any rows or columns that contain no galaxies should all actually be twice as big.\n",
    ">\n",
    ">In the above example, three columns and two rows contain no galaxies:\n",
    ">```\n",
    ">   v  v  v\n",
    "> ...#......\n",
    "> .......#..\n",
    "> #.........\n",
    ">>..........<\n",
    "> ......#...\n",
    "> .#........\n",
    "> .........#\n",
    ">>..........<\n",
    "> .......#..\n",
    "> #...#.....\n",
    ">   ^  ^  ^\n",
    ">```\n",
    ">These rows and columns need to be twice as big; the result of cosmic expansion therefore looks like this:\n",
    ">```\n",
    ">....#........\n",
    ">.........#...\n",
    ">#............\n",
    ">.............\n",
    ">.............\n",
    ">........#....\n",
    ">.#...........\n",
    ">............#\n",
    ">.............\n",
    ">.............\n",
    ">.........#...\n",
    ">#....#.......\n",
    ">```\n",
    ">Equipped with this expanded universe, the shortest path between every pair of galaxies can be found. It can help to assign every galaxy a unique number:\n",
    ">```\n",
    ">....1........\n",
    ">.........2...\n",
    ">3............\n",
    ">.............\n",
    ">.............\n",
    ">........4....\n",
    ">.5...........\n",
    ">............6\n",
    ">.............\n",
    ">.............\n",
    ">.........7...\n",
    ">8....9.......\n",
    ">```\n",
    ">In these 9 galaxies, there are 36 pairs. Only count each pair once; order within the pair doesn't matter. For each pair, find any shortest path between the two galaxies using only steps that move up, down, left, or right exactly one . or # at a time. (The shortest path between two galaxies is allowed to pass through another galaxy.)\n",
    ">\n",
    ">For example, here is one of the shortest paths between galaxies 5 and 9:\n",
    ">```\n",
    ">....1........\n",
    ">.........2...\n",
    ">3............\n",
    ">.............\n",
    ">.............\n",
    ">........4....\n",
    ">.5...........\n",
    ">.##.........6\n",
    ">..##.........\n",
    ">...##........\n",
    ">....##...7...\n",
    ">8....9.......\n",
    ">```\n",
    ">This path has length 9 because it takes a minimum of nine steps to get from galaxy 5 to galaxy 9 (the eight locations marked # plus the step onto galaxy 9 itself). Here are some other example shortest path lengths:\n",
    ">\n",
    ">- Between galaxy 1 and galaxy 7: 15\n",
    ">- Between galaxy 3 and galaxy 6: 17\n",
    ">- Between galaxy 8 and galaxy 9: 5\n",
    ">\n",
    ">In this example, after expanding the universe, the sum of the shortest path between all 36 pairs of galaxies is 374.\n",
    ">\n",
    ">Expand the universe, then find the length of the shortest path between every pair of galaxies. What is the sum of these lengths?\n",
    ">"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78033900",
   "metadata": {},
   "source": [
    "Coordinates in space! I get to continue with the beloved Complex Number Coordinate System with dictionaries and show the true power of them in this puzzle.\n",
    "\n",
    "In hindsight, this might have been the easiest one for me so far this year, mainly because the System carries all the challenging parts on its shoulders like it's nobody's business. After yesterday, this feels amazing."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04a7ad81",
   "metadata": {},
   "source": [
    "## Read input\n",
    "\n",
    "To create the galaxy, I read all the input cells and if the cell is a `#`, I calculate its position in Complex Number Coordinate System with the formula of `x + y * -1j` and use that as a key in our dictionary.\n",
    "\n",
    "You may already see why this is very efficient in this puzzle. I don't care about the empty space: no memory is allocated to that so it can expand as much as it wants."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d77c6dae",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import read_input\n",
    "\n",
    "GALAXY = '#'\n",
    "\n",
    "raw_space = read_input(11)\n",
    "\n",
    "space = {}\n",
    "for y, row in enumerate(raw_space):\n",
    "    for x, cell in enumerate(row):\n",
    "        if cell == GALAXY:\n",
    "            space[x + y * -1j] = GALAXY"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88fa8218",
   "metadata": {},
   "source": [
    "To expand the space, I loop through each row and each column and check if they have any galaxies. If they don't , I mark that as an expandable row or column.\n",
    "\n",
    "To do the actual expansion then, I go through each galaxy, see how many expandable rows and columns are before it and update its position with an addition of old coordinate and how much we need to shift. Then I mark a new galaxy there on a new space dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8c8de306",
   "metadata": {},
   "outputs": [],
   "source": [
    "def expand_space(space):\n",
    "    min_y = int(min(coord.imag for coord in space))\n",
    "    max_x = int(max(coord.real for coord in space))\n",
    "    \n",
    "    should_expand_rows = []\n",
    "    for y in range(0, min_y, -1):\n",
    "        has_galaxies = any(cell for cell in space if int(cell.imag) == y)\n",
    "        if not has_galaxies:\n",
    "            should_expand_rows.append(y)\n",
    "        \n",
    "    should_expand_columns = []\n",
    "    for x in range(max_x):\n",
    "        has_galaxies = any(cell for cell in space if int(cell.real) == x)\n",
    "        if not has_galaxies:\n",
    "            should_expand_columns.append(x)\n",
    "\n",
    "    new_space = {}\n",
    "    for galaxy in space:\n",
    "        shift_right = len([column for column in should_expand_columns if galaxy.real > column])\n",
    "        shift_down = len([row for row in should_expand_rows if galaxy.imag < row])\n",
    "        new_space[galaxy + (shift_right + shift_down * -1j)] = GALAXY\n",
    "        \n",
    "    return new_space"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5c25a0a",
   "metadata": {},
   "source": [
    "Calculating the shortest distance uses [Manhattan distance](https://en.wikipedia.org/wiki/Taxicab_geometry), also known as taxicab geometry. Since we are in a grid where you can only move to orthogonal spaces, the distance between two coordinates is the sum of the absolute values of each coordinate subtracted from each other: `|x1 - x2| + |y1 - y2|` and in my system, `real` part is `x` and `imag` part is `y`. I need to convert it to `int` at the end because `real` and `imag` return floats."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "f7f2fab2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_distance(one, another):\n",
    "    return int(abs(one.real - another.real) + abs(one.imag - another.imag))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5704f775",
   "metadata": {},
   "source": [
    "To calculate the sum of all shortest distances, I use [itertools.combinations](https://docs.python.org/3/library/itertools.html#itertools.combinations) to create all unordered, non-repeated 2-item pairs from the space (when using a dictionary like this, it returns the keys)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "44600542",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution: 9724940\n"
     ]
    }
   ],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "new_space = expand_space(space)\n",
    "\n",
    "part_1 = 0\n",
    "for one, another in combinations(new_space, 2):\n",
    "    distance = calculate_distance(one, another)\n",
    "    part_1 += distance\n",
    "\n",
    "print(f'Solution: {part_1}')\n",
    "assert part_1 == 9724940"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1bd8fd52",
   "metadata": {},
   "source": [
    "## Part 2\n",
    "\n",
    ">The galaxies are much older (and thus much farther apart) than the researcher initially estimated.\n",
    ">\n",
    ">Now, instead of the expansion you did before, make each empty row or column one million times larger. That is, each empty row should be replaced with 1000000 empty rows, and each empty column should be replaced with 1000000 empty columns.\n",
    ">\n",
    ">(In the example above, if each empty row or column were merely 10 times larger, the sum of the shortest paths between every pair of galaxies would be 1030. If each empty row or column were merely 100 times larger, the sum of the shortest paths between every pair of galaxies would be 8410. However, your universe will need to expand far beyond these values.)\n",
    ">\n",
    ">Starting with the same initial image, expand the universe according to these new rules, then find the length of the shortest path between every pair of galaxies. What is the sum of these lengths?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a94f4c3a",
   "metadata": {},
   "source": [
    "I see what you tried to do there trick master. But your tricks have no power here as I don't store any empty space.\n",
    "\n",
    "The only change I had to make to `expand_space` to make it `expand_space_more` was to accept a `multiplier` argument and use that to multiply how much we shift right or down. We subtract 1 from the multiplier because one space already exists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d5be997f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def expand_space_more(space, multiplier):\n",
    "    min_y = int(min(coord.imag for coord in space))\n",
    "    max_x = int(max(coord.real for coord in space))\n",
    "    \n",
    "    should_expand_rows = []\n",
    "    for y in range(0, min_y, -1):\n",
    "        has_galaxies = any(cell for cell in space if int(cell.imag) == y)\n",
    "        if not has_galaxies:\n",
    "            should_expand_rows.append(y)\n",
    "        \n",
    "    should_expand_columns = []\n",
    "    for x in range(max_x):\n",
    "        has_galaxies = any(cell for cell in space if int(cell.real) == x)\n",
    "        if not has_galaxies:\n",
    "            should_expand_columns.append(x)\n",
    "\n",
    "    new_space = {}\n",
    "    for galaxy in space:\n",
    "        shift_right = len([column for column in should_expand_columns if galaxy.real > column]) * (multiplier - 1)\n",
    "        shift_down = len([row for row in should_expand_rows if galaxy.imag < row]) * (multiplier -1)\n",
    "        new_space[galaxy + (shift_right + shift_down * -1j)] = GALAXY\n",
    "        \n",
    "    return new_space"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95cd12cd",
   "metadata": {},
   "source": [
    "The actual solution then is exactly the same as the first part, just with a \"bigger space\" which in our case, means the keys in our dictionary are larger numbers and nothing else. There's effectively zero performance penalty from growing the multiplier, as long as the resulting numbers fit the space complex numbers can handle.\n",
    "\n",
    "For once, my loops are not dependent on the problem space size."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "1dab29c6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution: 569052586852\n"
     ]
    }
   ],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "bigger_space = expand_space_more(space, 1_000_000)\n",
    "\n",
    "part_2 = 0\n",
    "for one, another in combinations(bigger_space, 2):\n",
    "    distance = calculate_distance(one, another)\n",
    "    part_2 += distance\n",
    "\n",
    "print(f'Solution: {part_2}')\n",
    "assert part_2 == 569052586852"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2faea9d",
   "metadata": {},
   "source": [
    "## Helper printer function\n",
    "\n",
    "To make debugging easier, I created a `print_space` function but did not end up needing it since the puzzle was a one hit wonder."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "29c8e167",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_space(space):\n",
    "    for y in range(0, min(int(c.imag) for c in space) - 1, -1):\n",
    "        for x in range(max(int(c.real) for c in space) + 1):\n",
    "            if (x + y*1j) in space:\n",
    "                print(GALAXY, end=\"\")\n",
    "            else:\n",
    "                print('.', end=\"\")\n",
    "        print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf33997a",
   "metadata": {},
   "source": [
    "## Two stars\n",
    "\n",
    "Loved today's puzzle. Especially when the second part was revealed and I noticed my system handles it with no problems. We are now at 22/50 stars. _It's beginning to look a lot like Christmas_ 🎶"
   ]
  }
 ],
 "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
}