day11.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c7d922ba",
   "metadata": {},
   "source": [
    "# Day 11: Dumbo Octopus\n",
    "\n",
    "You enter a large cavern full of rare bioluminescent dumbo octopuses! They seem to not like the Christmas lights on your submarine, so you turn them off for now.\n",
    "\n",
    "There are 100 octopuses arranged neatly in a 10 by 10 grid. Each octopus slowly gains energy over time and flashes brightly for a moment when its energy is full. Although your lights are off, maybe you could navigate through the cave without disturbing the octopuses if you could predict when the flashes of light will happen.\n",
    "\n",
    "Each octopus has an energy level - your submarine can remotely measure the energy level of each octopus (your puzzle input). For example:\n",
    "\n",
    "```text\n",
    "5483143223\n",
    "2745854711\n",
    "5264556173\n",
    "6141336146\n",
    "6357385478\n",
    "4167524645\n",
    "2176841721\n",
    "6882881134\n",
    "4846848554\n",
    "5283751526\n",
    "```\n",
    "\n",
    "The energy level of each octopus is a value between 0 and 9. Here, the top-left octopus has an energy level of 5, the bottom-right one has an energy level of 6, and so on.\n",
    "\n",
    "You can model the energy levels and flashes of light in steps. During a single step, the following occurs:\n",
    "\n",
    "    First, the energy level of each octopus increases by 1.\n",
    "    Then, any octopus with an energy level greater than 9 flashes. This increases the energy level of all adjacent octopuses by 1, including octopuses that are diagonally adjacent. If this causes an octopus to have an energy level greater than 9, it also flashes. This process continues as long as new octopuses keep having their energy level increased beyond 9. (An octopus can only flash at most once per step.)\n",
    "    Finally, any octopus that flashed during this step has its energy level set to 0, as it used all of its energy to flash.\n",
    "\n",
    "Adjacent flashes can cause an octopus to flash on a step even if it begins that step with very little energy. Consider the middle octopus with 1 energy in this situation:\n",
    "\n",
    "Before any steps:\n",
    "```text\n",
    "11111\n",
    "19991\n",
    "19191\n",
    "19991\n",
    "11111\n",
    "```\n",
    "\n",
    "After step 1:\n",
    "```text\n",
    "34543\n",
    "40004\n",
    "50005\n",
    "40004\n",
    "34543\n",
    "```\n",
    "\n",
    "After step 2:\n",
    "```text\n",
    "45654\n",
    "51115\n",
    "61116\n",
    "51115\n",
    "45654\n",
    "```\n",
    "\n",
    "An octopus is highlighted when it flashed during the given step.\n",
    "\n",
    "Here is how the larger example above progresses:\n",
    "\n",
    "Before any steps:\n",
    "```text\n",
    "5483143223\n",
    "2745854711\n",
    "5264556173\n",
    "6141336146\n",
    "6357385478\n",
    "4167524645\n",
    "2176841721\n",
    "6882881134\n",
    "4846848554\n",
    "5283751526\n",
    "```\n",
    "\n",
    "After step 1:\n",
    "```text\n",
    "6594254334\n",
    "3856965822\n",
    "6375667284\n",
    "7252447257\n",
    "7468496589\n",
    "5278635756\n",
    "3287952832\n",
    "7993992245\n",
    "5957959665\n",
    "6394862637\n",
    "```\n",
    "\n",
    "After step 2:\n",
    "```text\n",
    "8807476555\n",
    "5089087054\n",
    "8597889608\n",
    "8485769600\n",
    "8700908800\n",
    "6600088989\n",
    "6800005943\n",
    "0000007456\n",
    "9000000876\n",
    "8700006848\n",
    "```\n",
    "\n",
    "After step 3:\n",
    "```text\n",
    "0050900866\n",
    "8500800575\n",
    "9900000039\n",
    "9700000041\n",
    "9935080063\n",
    "7712300000\n",
    "7911250009\n",
    "2211130000\n",
    "0421125000\n",
    "0021119000\n",
    "```\n",
    "\n",
    "After step 4:\n",
    "```text\n",
    "2263031977\n",
    "0923031697\n",
    "0032221150\n",
    "0041111163\n",
    "0076191174\n",
    "0053411122\n",
    "0042361120\n",
    "5532241122\n",
    "1532247211\n",
    "1132230211\n",
    "```\n",
    "\n",
    "After step 5:\n",
    "```text\n",
    "4484144000\n",
    "2044144000\n",
    "2253333493\n",
    "1152333274\n",
    "1187303285\n",
    "1164633233\n",
    "1153472231\n",
    "6643352233\n",
    "2643358322\n",
    "2243341322\n",
    "```\n",
    "\n",
    "After step 6:\n",
    "```text\n",
    "5595255111\n",
    "3155255222\n",
    "3364444605\n",
    "2263444496\n",
    "2298414396\n",
    "2275744344\n",
    "2264583342\n",
    "7754463344\n",
    "3754469433\n",
    "3354452433\n",
    "```\n",
    "\n",
    "After step 7:\n",
    "```text\n",
    "6707366222\n",
    "4377366333\n",
    "4475555827\n",
    "3496655709\n",
    "3500625609\n",
    "3509955566\n",
    "3486694453\n",
    "8865585555\n",
    "4865580644\n",
    "4465574644\n",
    "```\n",
    "\n",
    "After step 8:\n",
    "```text\n",
    "7818477333\n",
    "5488477444\n",
    "5697666949\n",
    "4608766830\n",
    "4734946730\n",
    "4740097688\n",
    "6900007564\n",
    "0000009666\n",
    "8000004755\n",
    "6800007755\n",
    "```\n",
    "\n",
    "After step 9:\n",
    "```text\n",
    "9060000644\n",
    "7800000976\n",
    "6900000080\n",
    "5840000082\n",
    "5858000093\n",
    "6962400000\n",
    "8021250009\n",
    "2221130009\n",
    "9111128097\n",
    "7911119976\n",
    "```\n",
    "\n",
    "After step 10:\n",
    "```text\n",
    "0481112976\n",
    "0031112009\n",
    "0041112504\n",
    "0081111406\n",
    "0099111306\n",
    "0093511233\n",
    "0442361130\n",
    "5532252350\n",
    "0532250600\n",
    "0032240000\n",
    "```\n",
    "\n",
    "After step 10, there have been a total of 204 flashes. Fast forwarding, here is the same configuration every 10 steps:\n",
    "\n",
    "After step 20:\n",
    "```text\n",
    "3936556452\n",
    "5686556806\n",
    "4496555690\n",
    "4448655580\n",
    "4456865570\n",
    "5680086577\n",
    "7000009896\n",
    "0000000344\n",
    "6000000364\n",
    "4600009543\n",
    "```\n",
    "\n",
    "After step 30:\n",
    "```text\n",
    "0643334118\n",
    "4253334611\n",
    "3374333458\n",
    "2225333337\n",
    "2229333338\n",
    "2276733333\n",
    "2754574565\n",
    "5544458511\n",
    "9444447111\n",
    "7944446119\n",
    "```\n",
    "\n",
    "After step 40:\n",
    "```text\n",
    "6211111981\n",
    "0421111119\n",
    "0042111115\n",
    "0003111115\n",
    "0003111116\n",
    "0065611111\n",
    "0532351111\n",
    "3322234597\n",
    "2222222976\n",
    "2222222762\n",
    "```\n",
    "\n",
    "After step 50:\n",
    "```text\n",
    "9655556447\n",
    "4865556805\n",
    "4486555690\n",
    "4458655580\n",
    "4574865570\n",
    "5700086566\n",
    "6000009887\n",
    "8000000533\n",
    "6800000633\n",
    "5680000538\n",
    "```\n",
    "\n",
    "After step 60:\n",
    "```text\n",
    "2533334200\n",
    "2743334640\n",
    "2264333458\n",
    "2225333337\n",
    "2225333338\n",
    "2287833333\n",
    "3854573455\n",
    "1854458611\n",
    "1175447111\n",
    "1115446111\n",
    "```\n",
    "\n",
    "After step 70:\n",
    "```text\n",
    "8211111164\n",
    "0421111166\n",
    "0042111114\n",
    "0004211115\n",
    "0000211116\n",
    "0065611111\n",
    "0532351111\n",
    "7322235117\n",
    "5722223475\n",
    "4572222754\n",
    "```\n",
    "\n",
    "After step 80:\n",
    "```text\n",
    "1755555697\n",
    "5965555609\n",
    "4486555680\n",
    "4458655580\n",
    "4570865570\n",
    "5700086566\n",
    "7000008666\n",
    "0000000990\n",
    "0000000800\n",
    "0000000000\n",
    "```\n",
    "\n",
    "After step 90:\n",
    "```text\n",
    "7433333522\n",
    "2643333522\n",
    "2264333458\n",
    "2226433337\n",
    "2222433338\n",
    "2287833333\n",
    "2854573333\n",
    "4854458333\n",
    "3387779333\n",
    "3333333333\n",
    "```\n",
    "\n",
    "After step 100:\n",
    "```text\n",
    "0397666866\n",
    "0749766918\n",
    "0053976933\n",
    "0004297822\n",
    "0004229892\n",
    "0053222877\n",
    "0532222966\n",
    "9322228966\n",
    "7922286866\n",
    "6789998766\n",
    "```\n",
    "After 100 steps, there have been a total of 1656 flashes.\n",
    "\n",
    "Given the starting energy levels of the dumbo octopuses in your cavern, simulate 100 steps. **How many total flashes are there after 100 steps?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8b157921",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Python imports\n",
    "from pathlib import Path\n",
    "from typing import Callable, Dict, Generator, Iterable, List, Tuple\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "# Paths to data\n",
    "testpath = Path(\"day11_test.txt\")\n",
    "flashtestpath = Path(\"day11_flashtest.txt\")\n",
    "datapath = Path(\"day11_data.txt\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9de2bfbb",
   "metadata": {},
   "source": [
    "`numpy` is our friend throughout all of this. We can load data using the `np.genfromtxt()` function I saw on Reddit the other day."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3ee6f1a7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_input(fpath: Path) -> np.array:\n",
    "    \"\"\"Return octopus states as an array of ints\n",
    "    \n",
    "    :param fpath:  Path to data file\n",
    "    \"\"\"\n",
    "    return np.genfromtxt(fpath, dtype=int, delimiter=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17f8c1bd",
   "metadata": {},
   "source": [
    "To update the array, we need to know the location of the flashing octopus. To avoid edge effects, we use `np.pad()` to pad the outside of the array, and increment the row and column of the flashing octopus, then increment the 3x3 matrix with the octopus at its centre, and return the array without the pad.\n",
    "\n",
    "For the main algorithm, we implement the procedure from the puzzle text. We initialise a tally of octopus flashes and, at each step, increment the octopus state and then generate a mask of all array elements greater than 9 (these flash). We also keep a Boolean array of all elements that flashed in this step.\n",
    "\n",
    "If any octopuses have flashed, we increment the count, then update all the neighbours and set all the octopuses that flashed to zero. We then check again to see if any other octopuses have been caused to flash, and repeat (mask, increment flash count, update) until no more octopuses flash.\n",
    "\n",
    "At the end of the process, we return the current octopus energy state array and the count of flashes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "12044a98",
   "metadata": {},
   "outputs": [],
   "source": [
    "def update_neighbours(arr: np.array, row: int, col: int) -> np.array:\n",
    "    \"\"\"Returns array with all neighbours at (row, col) incremented\n",
    "    \n",
    "    :param arr:  array of octopus states\n",
    "    :param row:  row of flashing octopus\n",
    "    :param col:  col of flashing octopus\n",
    "    \"\"\"\n",
    "    padded = np.pad(arr, 1)\n",
    "    row, col = row+1, col+1\n",
    "    padded[row-1:row+2, col-1:col+2] += 1\n",
    "    return padded[1:-1, 1:-1]\n",
    "\n",
    "def get_octopus_flashcount(arr: np.array, steps: int) -> Tuple[np.array, int]:\n",
    "    \"\"\"Returns octopus energy array and count of octopus flashes\n",
    "    \n",
    "    :param arr:  octopus energy state array\n",
    "    :param steps:  number of steps to run\n",
    "    \"\"\"\n",
    "    flashcount = 0  # tally of octopuses that flashed\n",
    "    \n",
    "    # Iterate over the required number of steps\n",
    "    for step in range(steps):\n",
    "        arr += 1  # increment elements in array\n",
    "        flashmask = arr > 9  # mask of octopuses that flash\n",
    "        flashed = flashmask  # mask of octupuses that flashed in this step\n",
    "        \n",
    "        # It is possible that the first lot of flashing octopuses can\n",
    "        # cause other octopuses to flash, so we need to iterate until\n",
    "        # the cascade of flashing stops\n",
    "        while flashmask.sum():\n",
    "            flashcount += flashmask.sum()  # count octopuses currently flashing\n",
    "            rows, cols = np.where(flashmask)  # get locations of flashing octopuses\n",
    "            for row, col in list(zip(rows, cols)):  # update status array\n",
    "                arr = update_neighbours(arr, row, col)\n",
    "            arr[flashed] = 0  # reset octopuses that originally flashed\n",
    "            flashmask = arr > 9  # mask of octopuses that now flash\n",
    "            flashed += flashmask  # update mask of octopuses that flashed in this step\n",
    "\n",
    "    return arr, flashcount"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "620e8117",
   "metadata": {},
   "source": [
    "Trying this on the small test array:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a509a127",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[4, 5, 6, 5, 4],\n",
       "        [5, 1, 1, 1, 5],\n",
       "        [6, 1, 1, 1, 6],\n",
       "        [5, 1, 1, 1, 5],\n",
       "        [4, 5, 6, 5, 4]]),\n",
       " 9)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = load_input(flashtestpath)\n",
    "get_octopus_flashcount(data, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b070adc",
   "metadata": {},
   "source": [
    "Then the large test array:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9dd9947e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[0, 3, 9, 7, 6, 6, 6, 8, 6, 6],\n",
       "        [0, 7, 4, 9, 7, 6, 6, 9, 1, 8],\n",
       "        [0, 0, 5, 3, 9, 7, 6, 9, 3, 3],\n",
       "        [0, 0, 0, 4, 2, 9, 7, 8, 2, 2],\n",
       "        [0, 0, 0, 4, 2, 2, 9, 8, 9, 2],\n",
       "        [0, 0, 5, 3, 2, 2, 2, 8, 7, 7],\n",
       "        [0, 5, 3, 2, 2, 2, 2, 9, 6, 6],\n",
       "        [9, 3, 2, 2, 2, 2, 8, 9, 6, 6],\n",
       "        [7, 9, 2, 2, 2, 8, 6, 8, 6, 6],\n",
       "        [6, 7, 8, 9, 9, 9, 8, 7, 6, 6]]),\n",
       " 1656)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = load_input(testpath)\n",
    "get_octopus_flashcount(data, 100)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20a22959",
   "metadata": {},
   "source": [
    "Then the puzzle data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "bf1a243e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[5, 5, 6, 8, 4, 5, 5, 9, 7, 6],\n",
       "        [5, 6, 8, 6, 4, 0, 0, 0, 9, 7],\n",
       "        [6, 8, 5, 8, 0, 0, 0, 0, 0, 9],\n",
       "        [8, 7, 2, 4, 0, 0, 0, 0, 0, 0],\n",
       "        [1, 4, 2, 3, 5, 0, 0, 0, 0, 0],\n",
       "        [1, 5, 2, 2, 3, 4, 5, 9, 8, 0],\n",
       "        [2, 5, 2, 2, 2, 2, 2, 7, 5, 5],\n",
       "        [0, 6, 3, 2, 2, 2, 2, 7, 4, 4],\n",
       "        [0, 0, 5, 3, 2, 2, 2, 6, 4, 4],\n",
       "        [0, 0, 0, 3, 2, 2, 7, 5, 4, 4]]),\n",
       " 1743)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = load_input(datapath)\n",
    "get_octopus_flashcount(data, 100)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78056bc8",
   "metadata": {},
   "source": [
    "## Puzzle 2:\n",
    "\n",
    "It seems like the individual flashes aren't bright enough to navigate. However, you might have a better option: the flashes seem to be synchronizing!\n",
    "\n",
    "In the example above, the first time all octopuses flash simultaneously is step 195:\n",
    "\n",
    "After step 193:\n",
    "```text\n",
    "5877777777\n",
    "8877777777\n",
    "7777777777\n",
    "7777777777\n",
    "7777777777\n",
    "7777777777\n",
    "7777777777\n",
    "7777777777\n",
    "7777777777\n",
    "7777777777\n",
    "```\n",
    "\n",
    "After step 194:\n",
    "```text\n",
    "6988888888\n",
    "9988888888\n",
    "8888888888\n",
    "8888888888\n",
    "8888888888\n",
    "8888888888\n",
    "8888888888\n",
    "8888888888\n",
    "8888888888\n",
    "8888888888\n",
    "```\n",
    "\n",
    "After step 195:\n",
    "```text\n",
    "0000000000\n",
    "0000000000\n",
    "0000000000\n",
    "0000000000\n",
    "0000000000\n",
    "0000000000\n",
    "0000000000\n",
    "0000000000\n",
    "0000000000\n",
    "0000000000\n",
    "```\n",
    "\n",
    "If you can calculate the exact moments when the octopuses will all flash simultaneously, you should be able to navigate through the cavern. **What is the first step during which all octopuses flash?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "44663980",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_octopus_sync(arr: np.array) -> Tuple[np.array, int]:\n",
    "    \"\"\"Returns octopus energy array and steps to convergence\n",
    "    \n",
    "    :param arr:  octopus energy state array\n",
    "    :param steps:  number of steps to run\n",
    "    \"\"\"    \n",
    "    step = 0  # Count of steps taken\n",
    "    \n",
    "    # Iterate until all values in the status array are zero\n",
    "    while arr.sum():\n",
    "        arr += 1  # increment elements in array\n",
    "        flashmask = arr > 9  # mask of octopuses that flash\n",
    "        flashed = flashmask  # mask of octupuses that flashed in this step\n",
    "        \n",
    "        # It is possible that the first lot of flashing octopuses can\n",
    "        # cause other octopuses to flash, so we need to iterate until\n",
    "        # the cascade of flashing stops\n",
    "        while flashmask.sum():\n",
    "            rows, cols = np.where(flashmask)  # get locations of flashing octopuses\n",
    "            for row, col in list(zip(rows, cols)):  # update status array\n",
    "                arr = update_neighbours(arr, row, col)\n",
    "            arr[flashed] = 0  # reset octopuses that originally flashed\n",
    "            flashmask = arr > 9  # mask of octopuses that now flash\n",
    "            flashed += flashmask  # update mask of octopuses that flashed in this step\n",
    "        step += 1\n",
    "\n",
    "    return arr, step"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e22f3a1c",
   "metadata": {},
   "source": [
    "Trying this out on the test data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "33d74016",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]),\n",
       " 195)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = load_input(testpath)\n",
    "get_octopus_sync(data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "540fd8d5",
   "metadata": {},
   "source": [
    "And then solving the puzzle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b389b30e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]),\n",
       " 364)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = load_input(datapath)\n",
    "get_octopus_sync(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "542c549e",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}