ipynb/Advent-2023.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: right\" align=\"right\"><i>Peter Norvig, December 2023</i></div>\n",
    "\n",
    "# Advent of Code 2023\n",
    "\n",
    "I always enjoy doing [**Advent of Code**](https://adventofcode.com/) (AoC), but this year I had a lot going on in the beginning of December, and I wasn't able to get started until December 12th. I tried to do two puzzles a day, but couldn't keep up the pace and ended up completing only 40 of the 50 stars. \n",
    "\n",
    "I started by loading up my [**AdventUtils.ipynb**](AdventUtils.ipynb) notebook (same as last time except for the `current_year`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%run AdventUtils.ipynb\n",
    "current_year = 2023"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each day's solution consists of three parts, making use of my `parse` and `answer` utilities:\n",
    "- **Reading the day's input**. E.g. `document = parse(1)`. \n",
    "- **Solving Part One**. Find the solution and record it with, e.g., `answer(1.1, ...)`.\n",
    "- **Solving Part Two**. Find the solution and record it with, e.g., `answer(1.2, ...)`.\n",
    "\n",
    "To fully understand each day's puzzle, and to follow along the drama involving global snow production, elves, gondolas, water sources, and treasure maps, you need to read the day's puzzle description on the [**AoC**](https://adventofcode.com/) site, as linked in the header for each of my day's solutions, e.g. [**Day 1**](https://adventofcode.com/2023/day/1) below. Since you can't read Part 2 until you solve Part 1, I'll take some care to partially describe Part 2 in this notebook. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 1](https://adventofcode.com/2023/day/1): Trebuchet?!\n",
    "\n",
    "**Today's input** is a **calibration document.** We're asked to pick out the first and last digit in each line (ignoring other characters); this two-digit number is the **calibration value** for the line.\n",
    "\n",
    "My `parse` function can break the input into lines (and in later days we will see that it can do more).  `parse` shows the first few lines of the input file; this is helpful both for me as I write and debug the code and for you the reader trying to follow along. \n",
    "\n",
    "Note that, per [Eric Wastl's request](https://adventofcode.com/about#faq_copying), I do not post my personal input files; you'll have to get your own, and your answers won't be exactly the same as mine. I hope Eric doesn't mind that I show the first few lines of each input file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 1000 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "sdpgz3five4seven6fiveh\n",
      "876mbxbrntsfm\n",
      "fivek5mfzrdxfbn66nine8eight\n",
      "554qdg\n",
      "ninevsgxnine6threesix8\n",
      "4fivehmg614five\n",
      "three6sdnttwothree3\n",
      "two26four2\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "document = parse(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: What is the sum of all of the calibration values?\n",
    "\n",
    "That is, compute the calibration value for each line, and add up the results. Easy!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calibration_value(line: str) -> int:\n",
    "    \"\"\"First and last digit in line, taken as a two-digit integer.\"\"\"\n",
    "    digits = re.findall(r'\\d', line)\n",
    "    return 10 * int(digits[0]) + int(digits[-1])\n",
    "\n",
    "assert calibration_value('1abc2') == 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  1.1:   .0011 seconds, answer 54632           ok"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(1.1, 54632, lambda: sum(map(calibration_value, document)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the three arguments to `answer` are:\n",
    "  1. The puzzle we are answering, in the form *day*.*part*, which ranges from 1.1 to 25.2.\n",
    "  2. The correct answer.\n",
    "  3. A function to call to compute the answer (passed as a function so we can time how long it takes to run)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: What is the sum of all of the calibration values (including spelled-out digits)?\n",
    "\n",
    "In Part 2, we learn that the input line `two1nine` should have the calibration value `29`. I thought this would be easy: just look for spelled-out digits as well as 0-9 using `re.findall('\\d|zero|one|two|three|four|five|six|seven|eight|nine', line)`, and then translate the spelled-out digits. Unfortunately, I got the wrong answer, something that's very unusual for an AoC Day 1. In past years, Day 1 has been a straightforward warmup, and the tricky puzzles come later. My code was only a couple of lines, and got test cases right; I couldn't see any **bug**. I was stumped! (You can search within this notebook for \"**bug**\" to see all my major errors; minor typos have been silently corrected.)\n",
    "\n",
    "When in doubt, a good approach is to look at the input data. In doing so, I noticed the string `threetwone`. The last digit in this string is `one`, but using `re.findall`, I got the digit list `['three', 'two']`, and didn't get `'one'`, because it overlaps with `'two'`. There are several ways to trick the `re` module into handling overlaps; I chose to do two separate `findall` calls, one covering all the characters after the first digit, and one covering all the characters before the final digit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "digit_names = 'zero one two three four five six seven eight nine'.split()\n",
    "digit_regex = f'(\\d|{\"|\".join(digit_names)})'\n",
    "first_regex =        digit_regex + '.*'\n",
    "final_regex = '.*' + digit_regex\n",
    "digit_value = {s: i for i in range(10) for s in [str(i), digit_names[i]]}\n",
    "\n",
    "def calibration_value2(line: str) -> int:\n",
    "    \"\"\"First and last digit in line (including spelled-out digits), taken as a two-digit integer.\"\"\"\n",
    "    [first] = re.findall(first_regex, line)\n",
    "    [final] = re.findall(final_regex, line)\n",
    "    return 10 * digit_value[first] + digit_value[final]\n",
    "\n",
    "assert digit_value['seven'] == digit_value['7'] == 7\n",
    "assert calibration_value2('1abc2') == 12\n",
    "assert calibration_value2('threetwone') == 31"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that I use the term \"final\" rather than \"last.\" That makes code line up better because \"first\" and \"final\" have the same number of letters, and also I have found that the term \"last\" is best avoided because it is ambiguous: it can mean \"final\" or \"previous.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  1.2:   .0025 seconds, answer 54019           ok"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(1.2, 54019, lambda: sum(map(calibration_value2, document)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 3: Recap\n",
    "\n",
    "To be clear, here are all the steps I took to solve the day's puzzle:\n",
    "\n",
    "1. Ran `document = parse(1)` and examined the output. [LGTM](https://en.wiktionary.org/wiki/LGTM).\n",
    "2. Coded Part 1 and ran `sum(map(calibration_value, in1)`, seeing the output, 54632.\n",
    "3. Copy/pasted the output into the [AoC Day 1](https://adventofcode.com/2023/day/1) answer box and submitted it, and checked to see if it was the right answer.\n",
    "4. Recorded `answer(1.1, 54632, lambda: sum(map(calibration_value, in1))` in a cell, so we can re-run the notebook to check.\n",
    "7. Repeated steps 2–3 for Part 2, correcting a **bug** and resubmitting.\n",
    "8. Repeated step 4 for Part 2. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 2](https://adventofcode.com/2023/day/2): Cube Conundrum\n",
    "\n",
    "Each line of **today's input** describes the moves made in a game. The game involves grabbing handfuls of cubes from a bag and counting the number of cubes of each color in each handful."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 100 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Game 1: 4 green, 3 blue, 11 red; 7 red, 5 green, 10 blue; 3 green, 8 blue, 8 red; 4 red, 12 blue ...\n",
      "Game 2: 3 red, 1 blue, 2 green; 1 blue, 9 green; 1 red, 10 green\n",
      "Game 3: 5 green, 9 red, 4 blue; 3 green, 7 blue; 12 blue, 3 green, 3 red; 3 blue, 7 red, 2 green ...\n",
      "Game 4: 2 green, 2 blue; 12 red, 9 green, 2 blue; 13 green, 15 red, 4 blue; 14 red, 3 green, 5 b ...\n",
      "Game 5: 2 green, 6 blue; 1 red, 3 green, 5 blue; 3 green, 4 blue; 3 blue, 5 green, 1 red; 5 blue\n",
      "Game 6: 5 green, 1 blue, 3 red; 8 green, 15 red; 16 green, 5 red, 1 blue\n",
      "Game 7: 1 blue, 3 red, 11 green; 18 red, 16 blue, 5 green; 13 blue, 5 green; 1 red, 8 green, 15 blue\n",
      "Game 8: 1 green, 14 blue, 1 red; 10 blue; 1 green\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 100 Games:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Game(id=1, handfuls=[Cubes({'red': 11, 'green': 4, 'blue': 3}), Cubes({'blue': 10, 'red': 7, 'gr ...\n",
      "Game(id=2, handfuls=[Cubes({'red': 3, 'green': 2, 'blue': 1}), Cubes({'green': 9, 'blue': 1}), C ...\n",
      "Game(id=3, handfuls=[Cubes({'red': 9, 'green': 5, 'blue': 4}), Cubes({'blue': 7, 'green': 3}), C ...\n",
      "Game(id=4, handfuls=[Cubes({'green': 2, 'blue': 2}), Cubes({'red': 12, 'green': 9, 'blue': 2}),  ...\n",
      "Game(id=5, handfuls=[Cubes({'blue': 6, 'green': 2}), Cubes({'blue': 5, 'green': 3, 'red': 1}), C ...\n",
      "Game(id=6, handfuls=[Cubes({'green': 5, 'red': 3, 'blue': 1}), Cubes({'red': 15, 'green': 8}), C ...\n",
      "Game(id=7, handfuls=[Cubes({'green': 11, 'red': 3, 'blue': 1}), Cubes({'red': 18, 'blue': 16, 'g ...\n",
      "Game(id=8, handfuls=[Cubes({'blue': 14, 'green': 1, 'red': 1}), Cubes({'blue': 10}), Cubes({'gre ...\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "Game = namedtuple('Game', 'id, handfuls')\n",
    "\n",
    "class Cubes(Counter): \"\"\"A collection of cubes of  various colors.\"\"\"\n",
    "\n",
    "def parse_game(line: str) -> Game:\n",
    "    \"\"\"Construct a `Game` object from a line of text.\"\"\"\n",
    "    game_id, rest = line.split(':')\n",
    "    _, id = game_id.split()\n",
    "    return Game(int(id), [parse_handful(cubes) for cubes in rest.split(';')])\n",
    "\n",
    "def parse_handful(handful: str) -> Cubes:\n",
    "    \"\"\"Parse e.g. '3 blue, 1 brown' into `Cubes({'blue': 3, 'brown': 1})`.\"\"\"\n",
    "    pairs = map(str.split, handful.split(','))\n",
    "    return Cubes({color: int(n) for n, color in pairs})\n",
    "\n",
    "games = parse(2, parse_game)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Determine which games would have been possible if the bag had been loaded with only 12 red cubes, 13 green cubes, and 14 blue cubes. What is the sum of the IDs of those games?\n",
    "\n",
    "A game is possible if each handful has no more cubes of any color than the number in the target bag."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "target_bag = parse_handful('12 red, 13 green, 14 blue')\n",
    "\n",
    "def possible(game: Game, target: Cubes) -> bool:\n",
    "    \"\"\"Could this game result from the target bag?\"\"\"\n",
    "    return all(handful[color] <= target[color]\n",
    "               for handful in game.handfuls \n",
    "               for color in handful)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  2.1:   .0002 seconds, answer 1734            ok"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(2.1, 1734, \n",
    "       lambda: sum(game.id for game in games if possible(game, target_bag)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: For each game, find the minimum set of cubes that must have been present. What is the sum of the power of these sets?\n",
    "\n",
    "The **power** of a set of cubes is defined as \"the numbers of red, green, and blue cubes multiplied together.\" For each game we're looking for the power of the **minimum set**: the set that has only as many cubes (of each color) as the highest number among all the handfuls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimum_set(game: Game) -> Cubes:\n",
    "    \"\"\"The smallest set of cubes that could produce all the handfuls in `game`.\"\"\"\n",
    "    return Cubes({color: max(handful[color] for handful in game.handfuls) \n",
    "                  for color in ('red', 'green', 'blue')})\n",
    "\n",
    "def power(cubes: Cubes) -> int: return prod(cubes.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  2.2:   .0005 seconds, answer 70387           ok"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(2.2, 70387, lambda: sum(power(minimum_set(game)) for game in games))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 3](https://adventofcode.com/2023/day/3): Gear Ratios\n",
    "\n",
    "**Today's input** is a schematic, a two-dimensional map that contains numbers and symbols. In my `AdventUtils` I have a class, `Grid` for 2D layouts like this, but I decided not to use it for today's puzzle, mainly because I wanted to maintain each row as a string, to make it easy to find the part numbers with a regular expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 140 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "...766.......821.547.....577......................................387.....................56.... ...\n",
      "...........................%...../.....981..........627..../..........-.....623......610..-..... ...\n",
      "...$...........716..&336.......470.325.................*.84........$..34....*.....+.....#.....*7 ...\n",
      ".117../359.#...............595............129..963#..722..........128........192.313........31.. ...\n",
      "............298.....922...*.......482.......*..................*......./........................ ...\n",
      ".732..................*..815..920*......113.827.........453.571.356..902......693...147......... ...\n",
      "...*..........451-.442..................*...................................+....*....*.......91 ...\n",
      "....844.587.....................347...425.....974......348.........$615....174.330.............. ...\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "schematic = parse(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: What is the sum of all of the part numbers in the schematic?\n",
    "\n",
    "A **part number** is a string of digits where at least one of the digits is adjacent (orthogonally or diagonally) to a **symbol** (other than a period or digit).\n",
    "\n",
    "First we'll find all the numbers in the schematic (recording the value of the number as well as its row and the start and stop of the columns it occupies). Then for each schematic number we'll examine the adjacent positions to find which numbers are actually part numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "SchematicNumber = namedtuple('SchematicNumber', 'value, row, col, stop')\n",
    "\n",
    "def find_numbers(schematic) -> List[SchematicNumber]:\n",
    "    \"\"\"Extract all the numbers (with their positions from the schematic.\"\"\"\n",
    "    return [SchematicNumber(int(m.group()), r, m.start(), m.start() + len(m.group()))\n",
    "            for r, row in enumerate(schematic)\n",
    "            for m in re.finditer(r'\\d+', row)]\n",
    "\n",
    "def is_part_number(n: SchematicNumber, schematic) -> bool:\n",
    "    \"\"\"Is this a part number (adjacent to a symbol)?\"\"\"\n",
    "    return any(schematic[r][c] not in '.0123456789' \n",
    "               for r, c in adjacent_positions(n, schematic))\n",
    "\n",
    "def adjacent_positions(n: SchematicNumber, schematic) -> List[Point]:\n",
    "    \"\"\"The (row, column) positions that surround `n` in schematic.\"\"\"\n",
    "    return cross_product(clip_range(n.row - 1, n.row + 2, len(schematic)),\n",
    "                         clip_range(n.col - 1, n.stop + 1, len(schematic[0])))\n",
    "\n",
    "def clip_range(start, stop, maximum) -> range:\n",
    "    \"\"\"Compute range(start, stop), except don't go below zero or above maximum.\"\"\"\n",
    "    return range(max(0, start), min(stop, maximum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  3.1:   .0040 seconds, answer 559667          ok"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(3.1, 559667, lambda: sum(n.value for n in find_numbers(schematic) \n",
    "                                if is_part_number(n, schematic)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: What is the sum of all of the gear ratios in your engine schematic?\n",
    "\n",
    "A **gear** is a `*` symbol that is adjacent to exactly two numbers. A **gear ratio** is the product of those two numbers. \n",
    "\n",
    "I'll get some re-use from the code for Part 1, but unfortunately, I can't use exactly the same structure. In Part 1 we iterated over all numbers and found ones adjacent to a symbol. In Part 2 we'll have to first iterate over all numbers and find ones that are adjacent to a `*`, then place those numbers into a table keyed by the position of the `*`, then search the table for entries with exactly two numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gear_ratios(schematic) -> List[int]:\n",
    "    \"\"\"Return a list of pairs of numbers that form gears.\"\"\"\n",
    "    table = defaultdict(list) # Table of {(row, col): [number, ...]}\n",
    "    for n in find_numbers(schematic):\n",
    "        for r, c in adjacent_positions(n, schematic):\n",
    "            if schematic[r][c] == '*':\n",
    "                table[r, c].append(n)\n",
    "    return [numbers[0].value * numbers[1].value \n",
    "            for numbers in table.values() \n",
    "            if len(numbers) == 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  3.2:   .0041 seconds, answer 86841457        ok"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(3.2, 86841457, lambda: sum(gear_ratios(schematic)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 4](https://adventofcode.com/2023/day/4): Scratchcards\n",
    "\n",
    "Each line of **today's input** represents a **scratchcard**: a card id followed by a set of winning numbers (in a lottery) and a set of numbers that you have on the card."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 203 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Card   1: 87 75 80 68 71 57 58 59 70 48 | 56 67 75 76 31 49 48 22 43 68 98 86 70 91 27 46  4 87  ...\n",
      "Card   2: 95 97 90 91 79 71 60 87 46 80 | 28 90 55 87 82 34 44 96 77 15 22 63 31 33  5 99 36 91  ...\n",
      "Card   3: 23 73 50 78 93 30 56 10  8 64 | 61 48 87 46 12 75 92 37 62 45 24 81 79 55 76 82  9  1  ...\n",
      "Card   4: 16 50 13 24 94 27 74 58 15 53 | 58 53 20 57 69 28 47  2 41  4 66 61 15 44 24 68 50 74  ...\n",
      "Card   5: 39 53 29 10 84 22 83  4  5 32 | 50 28 45  5  6 65 18  7 92 83  3 55 81 26 80 39 44 60  ...\n",
      "Card   6: 84 12 96 93 72 97 91 76  7 82 | 85 15 29 33 37 60 14 30 63 73 38 62 77 44 86 39 51  2  ...\n",
      "Card   7: 78 12  1 50 48 62 33  8 83 99 | 12 50 79 48 59 81 26 14  5 11 37  8 36 91 95 20 46 44  ...\n",
      "Card   8: 55 58  8 36 16 23 88 73 45 65 | 19 10 34 64 52 27 75 22 33 58 74 45 16 11 63 56 12 14  ...\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 203 Cards:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Card(id=1, winning=(87, 75, 80, 68, 71, 57, 58, 59, 70, 48), have=(56, 67, 75, 76, 31, 49, 48, 2 ...\n",
      "Card(id=2, winning=(95, 97, 90, 91, 79, 71, 60, 87, 46, 80), have=(28, 90, 55, 87, 82, 34, 44, 9 ...\n",
      "Card(id=3, winning=(23, 73, 50, 78, 93, 30, 56, 10, 8, 64), have=(61, 48, 87, 46, 12, 75, 92, 37 ...\n",
      "Card(id=4, winning=(16, 50, 13, 24, 94, 27, 74, 58, 15, 53), have=(58, 53, 20, 57, 69, 28, 47, 2 ...\n",
      "Card(id=5, winning=(39, 53, 29, 10, 84, 22, 83, 4, 5, 32), have=(50, 28, 45, 5, 6, 65, 18, 7, 92 ...\n",
      "Card(id=6, winning=(84, 12, 96, 93, 72, 97, 91, 76, 7, 82), have=(85, 15, 29, 33, 37, 60, 14, 30 ...\n",
      "Card(id=7, winning=(78, 12, 1, 50, 48, 62, 33, 8, 83, 99), have=(12, 50, 79, 48, 59, 81, 26, 14, ...\n",
      "Card(id=8, winning=(55, 58, 8, 36, 16, 23, 88, 73, 45, 65), have=(19, 10, 34, 64, 52, 27, 75, 22 ...\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "ScratchCard = namedtuple('Card', 'id, winning, have')\n",
    "\n",
    "def parse_card(line: str) -> ScratchCard:\n",
    "    \"\"\"Construct a `Card` object from a line of text.\"\"\"\n",
    "    game_id, rest = line.split(':')\n",
    "    _, id = game_id.split()\n",
    "    win, have = rest.split('|')\n",
    "    return ScratchCard(int(id), ints(win), ints(have))\n",
    "\n",
    "scratchcards = parse(4, parse_card)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: How many points are the cards worth in total?\n",
    "\n",
    "Count the number of winning numbers that you have. If there are no winning numbers, the card is worth no points. Otherwise, it is worth 2 raised to the power of the number of matches minus 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def worth(card: ScratchCard) -> int:\n",
    "    \"\"\"A card is worth 0 if no matches, else 2 ^ (matches - 1).\"\"\"\n",
    "    wins = len(set(card.winning) & set(card.have))\n",
    "    return 0 if not wins else 2 ** (wins - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  4.1:   .0004 seconds, answer 25174           ok"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(4.1, 25174, lambda: sum(map(worth, scratchcards)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: Under the new rules, how many total scratchcards do you end up with?\n",
    "\n",
    "Part 2's lesson is: [RTFM](https://en.wikipedia.org/wiki/RTFM)! It turns out the rules were written on the back of the cards all along! The rules are to consider each card in order, and if a card has *n* wins, then you win a copy of the next *n* cards (and they can win subsequent cards). The question is how many cards do you end up with (including the original cards).\n",
    "\n",
    "So I'll start with a `Counter` of cards and add to the counters of the following cards for each winner. It is more efficient to have a `Counter` of cards rather than keeping a list of cards, because I only need to process each card once; if I had a list of cards and ended up with a million copies of a card, I would have to process it a million times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_cards(original_cards: Sequence[ScratchCard]) -> Counter[ScratchCard]:\n",
    "    \"\"\"Consider each of the original cards; if it has n wins, add copies of the next n cards.\n",
    "    How many copies? The number of copies of the original card in the Counter.\"\"\"\n",
    "    cards = Counter(original_cards)\n",
    "    for i, card in enumerate(original_cards):\n",
    "        wins = len(set(card.winning) & set(card.have))\n",
    "        for won_card in original_cards[i + 1 : i + wins + 1]:\n",
    "            cards[won_card] += cards[card]\n",
    "    return cards"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  4.2:   .0008 seconds, answer 6420979         ok"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(4.2, 6420979, lambda: sum(process_cards(scratchcards).values()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 5](https://adventofcode.com/2023/day/5): If You Give A Seed A Fertilizer\n",
    "\n",
    "**Today's input** is in the form of an **almanac** that is separated into paragraphs, not lines. Fortunately, my `parse` function is prepared to handle that. One complication is that the paragraph that starts with `'seeds:'` is treated differently than the other paragraphs. The `'seeds:'` paragraph has a set of seed numbers, while the other paragraphs have a name and aset of range mappings, one per line.\n",
    "\n",
    "A range mapping is used to convert a number from one format to another. It consists of three numbers: a destination start number, a source start number, and a range length, but I think it is simpler to deal with a range and an offset: the range tells you what numbers the mapping applies to, and the offset says by how much an applicable number should be changed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 219 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "seeds: 4106085912 135215567 529248892 159537194 1281459911 114322341 1857095529 814584370 299985 ...\n",
      "\n",
      "seed-to-soil map:\n",
      "1640984363 3136305987 77225710\n",
      "3469528922 1857474741 56096642\n",
      "278465165 2901870617 105516220\n",
      "1442950910 1913571383 198033453\n",
      "463085535 1458252975 13696838\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 8 tuples:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "('seeds', (4106085912, 135215567, 529248892, 159537194, 1281459911, 114322341, 1857095529, 81458 ...\n",
      "('seed-to-soil map:', [Mapping(range=range(3136305987, 3213531697), offset=-1495321624), Mapping ...\n",
      "('soil-to-fertilizer map:', [Mapping(range=range(1166448955, 1572765384), offset=-652755518), Ma ...\n",
      "('fertilizer-to-water map:', [Mapping(range=range(2789153677, 2824651774), offset=-1514486428),  ...\n",
      "('water-to-light map:', [Mapping(range=range(2139469351, 2393005045), offset=1207201748), Mappin ...\n",
      "('light-to-temperature map:', [Mapping(range=range(1572780528, 1660502295), offset=138502360), M ...\n",
      "('temperature-to-humidity map:', [Mapping(range=range(2063893326, 2069824476), offset=337416221) ...\n",
      "('humidity-to-location map:', [Mapping(range=range(2260659770, 3187696779), offset=695156401), M ...\n"
     ]
    }
   ],
   "source": [
    "Mapping = namedtuple('Mapping', 'range, offset')\n",
    "\n",
    "def parse_almanac(paragraph) -> tuple:\n",
    "    \"\"\"Parse a paragraph which can be either a list of seeds or a map.\"\"\"\n",
    "    if paragraph.startswith('seeds:'):\n",
    "        return ('seeds', ints(paragraph))\n",
    "    else:\n",
    "        name, *mappings = paragraph.splitlines()\n",
    "        return (name, [Mapping(range(src, src + length), dest - src)\n",
    "                       for (dest, src, length) in map(ints, mappings)])\n",
    "\n",
    "almanac = parse(5, parse_almanac, paragraphs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: What is the lowest location number that corresponds to any of the initial seed numbers?\n",
    "\n",
    "The idea is to start with a seed number, use the `seed-to-soil map` to convert to a soil number, then convert the soil number to a fertilizer number, and so on, until we get a location number. Then, choose the lowest of all the location numbers. \n",
    "\n",
    "Given a list of mappings, if a number is in the range of one of the mappings, then the number is converted by adding the offset. If the number is not contained in any mapping, the conversion leaves it unchanged. (The puzzle description promises that no number will be contained in multiple mappings. Also, we don't have to look at the names of the mappings, because the puzzle promises that they appear in the correct order.)\n",
    "\n",
    "For example, consider `Mapping(range(50, 100), offset=2)`. This mapping converts the number 79 to 81, because 79 is in the range and the offset adds 2. On the other hand, this mapping leaves 49 unchanged, because 49 is not in the range."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def convert(number: int, mappings: List[Mapping]) -> int:\n",
    "    \"\"\"Convert number if it is contained in one of the range mappings; else leave unchanged.\"\"\"\n",
    "    return first(number + m.offset for m in mappings if number in m.range) or number\n",
    "\n",
    "def multi_convert(number: int, almanac):\n",
    "    \"\"\"Convert number using successive range mappings in almanac (but not 'seeds').\"\"\"\n",
    "    for name, mappings in almanac:\n",
    "        if name != 'seeds':\n",
    "            number = convert(number, mappings)\n",
    "    return number\n",
    "\n",
    "def lowest_location(almanac):\n",
    "    \"\"\"What is the lowest location number that corresponds to one of the seed numbers in almanac?\"\"\"\n",
    "    name, seeds = almanac[0]\n",
    "    return min(multi_convert(seed, almanac) for seed in seeds)\n",
    "\n",
    "assert convert(79, [Mapping(range(50, 100), offset=2)]) == 81\n",
    "assert convert(49, [Mapping(range(50, 100), offset=2)]) == 49"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  5.1:   .0002 seconds, answer 324724204       ok"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(5.1, 324724204, lambda: lowest_location(almanac))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: What is the lowest location number that corresponds to any of the initial seed numbers (interpreting seeds as ranges)?\n",
    "\n",
    "In Part 2 the interpretation has changed: the list of numbers in the `seeds` field is not just a list of seed numbers; instead the values come in pairs, and for each pair the first value is the start of a range and the second value is the length of the range. \n",
    "\n",
    "So now there are *billions* of seeds rather than dozens, and it would be slow to process them individually. Instead, we can process **ranges** of seed numbers. The complication is that now a mapping might convert some of the numbers in a range, but not all of them.  For example, the mapping `Mapping(range(5, 10), offset=100)` converts the range `range(1, 10)` into two ranges:\n",
    "\n",
    "    range(1, 5)  → range(1, 5)\n",
    "    range(5, 10) → range(105, 110)\n",
    "\n",
    "I will define `convert_ranges(ranges, mappings)` to convert a collection of ranges, according to the mappings. I do this by keeping a set of `ranges`, popping one off at a time, finding a mapping that intersects with the range, and adding the conversion of that intersection to `result`, while also adding any non-intersecting range(s) back into the set of `ranges` yet to be processed. (*Note*: did you know that all empty ranges (e.g. `range(0, 0)` or `range(10, 9)`) are equal to each other? Thus even if I put several of them into the set, only one appears in the set.)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def convert_ranges(ranges: Collection[range], mappings: List[Mapping]) -> Set[range]:\n",
    "    \"\"\"Convert a set of ranges into another set of ranges, as specified by the mappings.\"\"\"\n",
    "    ranges = set(ranges) # Make `ranges` be a set if it is not already\n",
    "    result = set()       # This will be the output set of ranges\n",
    "    while ranges:\n",
    "        r = ranges.pop()\n",
    "        m = find_intersecting_mapping(r, mappings)\n",
    "        if m:\n",
    "            start, stop = max(r.start, m.range.start), min(r.stop, m.range.stop)\n",
    "            result.add(range(start + m.offset, stop + m.offset))\n",
    "            if r.start < start:\n",
    "                ranges.add(range(r.start, start))\n",
    "            if stop < r.stop:\n",
    "                ranges.add(range(stop, r.stop))\n",
    "        else:\n",
    "            result.add(r)\n",
    "    return result\n",
    "\n",
    "def find_intersecting_mapping(r: range, mappings) -> Optional[Mapping]: \n",
    "    \"\"\"If there is a mapping that intersects with range r, return it.\"\"\"\n",
    "    return first(m for m in mappings if (m.range.start in r) or (r.start in m.range))\n",
    "    \n",
    "test_maps = [Mapping(range(15, 5), offset=2), Mapping(range(5, 10), offset=100)]\n",
    "assert find_intersecting_mapping(range(1, 10), test_maps) == Mapping(range(5, 10), offset=100)\n",
    "assert set(convert_ranges({range(1, 10)}, test_maps)) == {range(1, 5), range(105, 110)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I should note that I originally had a **bug** above; I had written `ranges.add(range(stop, r.stop + 1))` where the `'+ 1'` is incorrect. I suspected an off-by-one error, and using assertions helped find it. \n",
    "\n",
    "Now defining `multi_convert_ranges` and `lowest_location_with_ranges` is pretty easy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def multi_convert_ranges(ranges: Collection[range], almanac):\n",
    "    \"\"\"Convert ranges using all the range mappings in almanac (except 'seeds') successively.\"\"\"\n",
    "    num_seeds = sum(map(len, ranges))\n",
    "    for name, mappings in almanac:\n",
    "        if name != 'seeds':\n",
    "            ranges = list(convert_ranges(ranges, mappings))\n",
    "            assert sum(map(len, ranges)) == num_seeds, f\"was {num_seeds} seeds; now {sum(map(len, ranges))}\"\n",
    "    return ranges\n",
    "\n",
    "def lowest_location_with_ranges(almanac):\n",
    "    \"\"\"What is the lowest location number that corresponds to one of the seed numbers in almanac?\"\"\"\n",
    "    name, pairs = almanac[0]\n",
    "    ranges = {range(start, start + length) for (start, length) in batched(pairs, 2)}\n",
    "    converted_ranges = multi_convert_ranges(ranges, almanac)\n",
    "    return min(r.start for r in converted_ranges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's the final answer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  5.2:   .0018 seconds, answer 104070862       ok"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(5.2, 104070862, lambda: lowest_location_with_ranges(almanac))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 6](https://adventofcode.com/2023/day/6): Wait For It \n",
    "\n",
    "**Today's input** is a record of past boat races, given the best known times and corresponding distances for past races."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 2 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Time:        40     81     77     72\n",
      "Distance:   219   1012   1365   1089\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 2 tuples:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "(40, 81, 77, 72)\n",
      "(219, 1012, 1365, 1089)\n"
     ]
    }
   ],
   "source": [
    "race_times, race_distances = parse(6, ints)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Determine the number of ways you could beat the record in each race. What do you get if you multiply these numbers together?\n",
    "\n",
    "In these boat races you get a fixed amount of time during which your boat has to travel as far as it can, and you win if your boat goes the farthest. For each whole millisecond you spend at the beginning of the race holding down the button, the boat's speed increases by one millimeter per millisecond (but the boat has that much less time to move at that speed).\n",
    "\n",
    "That means that if the race is for *t* milliseconds and you hold the button for *h* milliseconds, the boat will travel *h* × (*t* - *h*) millimeters.\n",
    "\n",
    "I can solve the puzzle by iterating over all possible hold durations and checking which ones beat the record. I do this even though I know–*absolutley know*–that in Part 2 the numbers will be much bigger and this approach will not be viable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def travel(hold: int, duration: int) -> int:\n",
    "    \"\"\"How far will the boat travel in `duration` total msecs if you hold for `hold` msecs?\"\"\"\n",
    "    return hold * max(0, duration - hold)\n",
    "\n",
    "assert travel(2, 7) == 10\n",
    "assert travel(3, 7) == 12\n",
    "assert travel(7, 7) == 0\n",
    "\n",
    "def ways_to_win(duration: int, record_distance: int) -> int:\n",
    "    \"\"\"How many different hold durations will beat the record distance for this race duration?\"\"\"\n",
    "    return quantify(travel(hold, duration) > record_distance \n",
    "                    for hold in range(1, duration))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  6.1:   .0001 seconds, answer 861300          ok"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(6.1, 861300, lambda: prod(ways_to_win(t, d) for t, d in zip(race_times, race_distances)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: How many ways can you beat the record in this one much longer race?\n",
    "\n",
    "In Part 2, we learn that the spaces between numbers in the input were inadvertent, and actually the digits should all be concatenated together, and there is just one (much longer) race with one (much longer) record distance. How long?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40817772"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def catnums(numbers) -> int: return int(cat(map(str, numbers)))\n",
    "\n",
    "catnums(race_times)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The race is 40 million milliseconds long (about 11 hours). Honestly, I was expecting it to be billions. For 40 million, I *could* use the same code as Part 1; it would probably take less than a minute to run, which is not terrible, but so far all my solutions run in under 1/100 of a second, so I don't want to spoil that now.\n",
    "\n",
    "I'll go ahead and solve the inequality where *t* is the time of the race, *r* is the record distance, and *h* is a variable indicating how long to hold the button. We end up with a quadratic inequality in *h* which we can solve using the [quadratic equation](https://en.wikipedia.org/wiki/Quadratic_equation) to find the values of *h* that give a distance greater than the record distance:\n",
    "\n",
    "- $h (t - h) - r > 0$\n",
    "- $-h^2 + th - r > 0$\n",
    "- Apply the quadratic formula, $(-b±\\sqrt{b^2-4ac})/(2a)$, with $a = -1, b = t, c = -r$ :\n",
    "- $(t - \\sqrt{t^2 - 4 r}) / 2 < h < (t + \\sqrt{t^2 - 4 r}) / 2$\n",
    "\n",
    "These values of *h* might not be integers, so round the lower one up and the higher one down to get the lowest and highest values of *h* that beat the record. With that we can quickly compute the number of ways to win:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ways_to_win2(t: int, r: int) -> int:\n",
    "    \"\"\"How many different hold durations will beat the record distance for this race duration?\"\"\"\n",
    "    radicand = t ** 2 - 4 * r\n",
    "    if radicand < 0:\n",
    "        return 0\n",
    "    else:\n",
    "        h_lo =  ceil((t - sqrt(radicand)) / 2)\n",
    "        h_hi = floor((t + sqrt(radicand)) / 2)\n",
    "        return h_hi - h_lo + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  6.2:   .0000 seconds, answer 28101347        ok"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(6.2, 28101347, lambda: ways_to_win2(catnums(race_times), catnums(race_distances)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I was a bit worried about a possible round-off error from the square root, but I got the right answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 7](https://adventofcode.com/2023/day/7): Camel Cards\n",
    "\n",
    "Today we're playing an Elven version of poker. Each line contains a poker hand, and the bid placed by the holder of that hand. We'll parse those lines, then put them into a `{hand: bid}` dictionary called `bids`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 1000 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "88223 818\n",
      "66JQ9 398\n",
      "6T9AT 311\n",
      "53TT3 43\n",
      "J6266 762\n",
      "5TTAA 647\n",
      "44JTT 779\n",
      "T4T66 496\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 1000 lists:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "['88223', '818']\n",
      "['66JQ9', '398']\n",
      "['6T9AT', '311']\n",
      "['53TT3', '43']\n",
      "['J6266', '762']\n",
      "['5TTAA', '647']\n",
      "['44JTT', '779']\n",
      "['T4T66', '496']\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "bids  = {hand: int(bid) for (hand, bid) in parse(7, str.split)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Find the rank of the hands. What are the total winnings?\n",
    "\n",
    "Note that Elven poker is simplified in several ways: there are no straights nor flushes (and thus no need for  suits), and in case two hands have the same **hand type** (pair, full house, etc.), then the tie is broken by considering the cards in lexicographical order (without rearranging the cards), and thus `82111` is better than `73999` because `8` is bigger than `7`, whereas in normal poker the later would win, because three 9s beats three 1s.\n",
    "\n",
    "The **rank** of a hand is determined by its **strength** (hand type plus tiebreaker) relative to the other hands: the worst hand has rank 1, the best rank 1000 (because there are 1000 hands). The **total winnings** is defined as the sum of each hand's rank times it's bid. \n",
    "\n",
    "I have some experience writing code to rank poker hands; you can see the [video](https://www.youtube.com/watch?v=PI8Fo1vzUPM) or the [class](https://www.udacity.com/course/design-of-computer-programs--cs212) or the [notebook](https://github.com/norvig/pytudes/blob/main/ipynb/poker.ipynb). I discovered an interesting fact: if you ignore straights and flushes, then each hand type corresponds to a [**partition**](https://en.wikipedia.org/wiki/Partition_(number_theory)) of the integer 5, and the sorted order of the parititions is the same as the order of the poker hand types! For example, the five cards in the hand `777A7` form the partition `[4, 1]` because there are four cards of one kind and one card of another kind, and this is not as good as the partition `[5]` for five of a kind, but is better the the partition `[3, 2]` for a full house. The following chart lists all the hand types and their partitions: \n",
    "\n",
    "\n",
    "| Type|  Example &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;|Partition |\n",
    "|-|---|---|\n",
    "| Five of a kind |`AAAAA`| 5 |\n",
    "| Four of a kind |`77727`|  4, 1|\n",
    "| Full house | `63633`|     3, 2|\n",
    "| Three of a kind | `666AK`| 3, 1, 1|\n",
    "| Two pair |  `T9T9A`|       2, 2, 1  |\n",
    "| One pair |  `33AKQ`|          2, 1, 1, 1|\n",
    "| High card | `2739K`|         1, 1, 1, 1, 1|\n",
    "\n",
    "It is easy to code up the strength of a hand:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "Strength = Tuple[List[int], List[int]] # (hand-type, tie-breaker)\n",
    "\n",
    "def strength(hand: str, order='..23456789TJQKA') -> Strength:\n",
    "    \"\"\"A tuple indicating the strength of a poker hand.\"\"\"\n",
    "    return hand_type(hand), [order.index(c) for c in hand]\n",
    "\n",
    "def hand_type(hand) -> List[int]: return sorted(Counter(hand).values(), reverse=True)\n",
    "\n",
    "assert hand_type('77727') == [4, 1]\n",
    "assert strength('77727')  == ([4, 1], [7, 7, 7, 2, 7])\n",
    "assert strength('63633')  == ([3, 2], [6, 3, 6, 3, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With that, it is also easy to determine the total winnings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def total_winnings(bids) -> int:\n",
    "    \"\"\"The total winnings is the sum of each hand's ranking times it's bid.\"\"\"\n",
    "    ranking = sorted(bids, key=strength)\n",
    "    return sum(i * bids[hand] for (i, hand) in enumerate(ranking, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  7.1:   .0033 seconds, answer 249726565       ok"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(7.1, 249726565, lambda: total_winnings(bids))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I initially had a **bug**; I forgot the \"`, 1`\" in `enumerate`, so the rank of the worst hand was 0, when it should be 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: Using the new joker rule, what are the new total winnings?\n",
    "\n",
    "In Part 2, the \"`J`\" now stands for \"Joker,\" not \"Jack.\" A joker can pretend to be whatever card is best for the purpose of determining hand type, but it has the lowest value when considering tie breakers. There is a shortcut: we only need to consider replacing a Joker(s) with one of the cards already in the hand, because introducing a different card could never lead to the best possible type (although if this game considered straights and flushes, it could do so). \n",
    "\n",
    "I'll refactor `total_winnings` to accept a `strength` function as an argument:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def total_winnings(bids, strength=strength) -> int:\n",
    "    \"\"\"The total winnings is the sum of each hand's ranking times it's bid.\"\"\"\n",
    "    return sum(i * bids[hand] \n",
    "               for (i, hand) in enumerate(sorted(bids, key=strength), 1))\n",
    "\n",
    "def joker_strength(hand, order='J.23456789T.QKA') -> Strength:\n",
    "    \"\"\"Strength when a Joker can pretend to be any card in the hand.\"\"\"\n",
    "    hands = {hand.replace('J', c) for c in hand}\n",
    "    best_type = max(map(hand_type, hands))\n",
    "    return best_type, [order.index(c) for c in hand]\n",
    "\n",
    "assert joker_strength('24J77') == ([3, 1, 1], [2, 4, 0, 7, 7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  7.2:   .0062 seconds, answer 251135960       ok"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(7.2, 251135960, lambda: total_winnings(bids, strength=joker_strength))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 8](https://adventofcode.com/2023/day/8): Haunted Wasteland\n",
    "\n",
    "**Today's input** consists of two documents to help navigate across Desert Island: (1) a network map of nodes and the nodes they lead to if you take a left or right branch, and (2) a list of left/right instructions.   I'll parse each line of the input into atoms, then package them up in a `Documents` named tuple, with the `instructions` field holding a string of `'LRLR...'` instructions, and the `network` field holding a dict of `{node: (left_node, right_node)}` entries.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 788 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "LLRRRLLRRRLRRRLRLRLLRRLRRRLLLRLRRRLRRRLRLLRRLRRRLLRRLRRLRLRRRLRRLLRLRRLRRRLRRLLRRRLRLLLRLRRRLRRL ...\n",
      "\n",
      "BQV = (HFG, GDR)\n",
      "VQT = (JLQ, TNJ)\n",
      "SGR = (TLQ, FGP)\n",
      "BXN = (TTQ, HJH)\n",
      "FXV = (RDS, NGH)\n",
      "MXR = (BXN, PXF)\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 788 tuples:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "('LLRRRLLRRRLRRRLRLRLLRRLRRRLLLRLRRRLRRRLRLLRRLRRRLLRRLRRLRLRRRLRRLLRLRRLRRRLRRLLRRRLRLLLRLRRRLR ...\n",
      "()\n",
      "('BQV', 'HFG', 'GDR')\n",
      "('VQT', 'JLQ', 'TNJ')\n",
      "('SGR', 'TLQ', 'FGP')\n",
      "('BXN', 'TTQ', 'HJH')\n",
      "('FXV', 'RDS', 'NGH')\n",
      "('MXR', 'BXN', 'PXF')\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "Documents = namedtuple('Documents', 'instructions, network')\n",
    "\n",
    "def make_documents(tuples) -> Documents:\n",
    "    \"\"\"Reformat tuples into the two kinds of documents: instructions and network node map.\"\"\"\n",
    "    ([instructions], (), *network) = tuples\n",
    "    return Documents(instructions, {node: (L, R) for (node, L, R) in network})\n",
    "        \n",
    "docs = make_documents(parse(8, atoms))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Starting at AAA, follow the left/right instructions. How many steps are required to reach ZZZ?\n",
    "\n",
    "Start at node `AAA` and if the next direction is `L`, take the left node; if it is `R`, take the right node. Continue until we reach node `ZZZ`. If we exhaust the instructions, cycle through to the start of the instructions again (so, e.g. the instructions `'LR'` mean to alternate left and right branches). I will design `navigate` to yield each node as it goes, because I might need the nodes in Part 2, even though in this part I only need to count the number of nodes visited (with `quantify`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "def navigate(docs) -> Iterator[str]:\n",
    "    \"\"\"Using the docs instructions and network map, yield the path of nodes from AAA to ZZZ.\"\"\"\n",
    "    instructions = cycle(docs.instructions)\n",
    "    node = 'AAA'\n",
    "    while node != 'ZZZ':\n",
    "        (L, R) = docs.network[node]\n",
    "        node = L if next(instructions) == 'L' else R\n",
    "        yield node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  8.1:   .0025 seconds, answer 12361           ok"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(8.1, 12361, lambda: quantify(navigate(docs)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: Simultaneously start on every node that ends with A. How many steps does it take before you're only on nodes that end with Z? \n",
    "\n",
    "In Part 2 the puzzle is to simultaneously start at every node that ends in `A` and continue until all the paths simultaneously arrive at a node that ends in `Z`. We are warned that \"It's going to take **significantly more steps** to escape!\" That clue, combined with the fact that we cycle through the instructions, suggests to me that the right approach is to see how many steps it takes for each start node to reach a node ending in `Z`, and then somehow do a least common multiple computation to figure out when all the cycles line up. How long could cycles be? The number of distinct possible states is the number of nodes times the length of the instructions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(263, 786, 206718)"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M = len(docs.instructions)\n",
    "N = len(docs.network)\n",
    "\n",
    "M, N, M * N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So no matter where we start, there will be a repeated cycle in a little more than 200,000 steps (or it could be a lot less). I'll refactor `navigate` to allow different start and ending nodes (keeping it backwards compatible with the previous version by default), but not to handle multiple simultaneous moves; that I'll try to handle outside of `navigate`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def navigate(docs, node='AAA', ending='ZZZ') -> Iterator[str]:\n",
    "    \"\"\"Using the docs instructions and network map, yield the path of nodes \n",
    "    from the start `node` to a node whose name ends in `ending`.\"\"\"\n",
    "    instructions = cycle(docs.instructions)\n",
    "    while not node.endswith(ending):\n",
    "        (L, R) = docs.network[node]\n",
    "        node = L if next(instructions) == 'L' else R\n",
    "        yield node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I'll see how many nodes there are that end in `A`, and how many steps each one takes to end in `Z`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'DPA': 20777,\n",
       " 'QLA': 19199,\n",
       " 'VJA': 18673,\n",
       " 'GTA': 16043,\n",
       " 'AAA': 12361,\n",
       " 'XQA': 15517}"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def navigate_steps(docs) -> dict:\n",
    "    \"\"\"How many steps does each '..A' node take to reach a '..Z' node?\"\"\"\n",
    "    return {node: quantify(navigate(docs, node, 'Z'))\n",
    "            for node in docs.network\n",
    "            if node.endswith('A')}\n",
    "\n",
    "navigate_steps(docs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're only guaranteed to repeat a cycle if we arrive at the same node at the same point in the instructions list. Let's see where we are in the instructions list by taking these numbers modulo `M`, the number of instructions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 0, 0, 0, 0]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[steps % M for steps in navigate_steps(docs).values()]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Awesome! We've reached a cycle in all six paths; we don't need to look any further. [Eric Wastl](http://was.tl/) designed the puzzle to be kind!\n",
    "\n",
    "In Python 3.9 there is a multi-argument `math.lcm` function, but prior versions can use `functools.reduce` to compute the `lcm` of the numbers above:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  8.2:   .0292 seconds, answer 18215611419223  ok"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(8.2, 18215611419223, lambda: functools.reduce(lcm, navigate_steps(docs).values()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I would say that 18 trillion steps counts as **significantly more**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 9](https://adventofcode.com/2023/day/9): Mirage Maintenance \n",
    "\n",
    "In **today's input**, each line is a series of measurements  of sand instability near an oasis. We can parse each line as a sequence of ints:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 200 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "-7 -12 -15 -4 52 210 556 1204 2291 3968 6387 9684 13958 19246 25494 32524 39997 47372 53861 5838 ...\n",
      "26 33 38 39 24 -37 -200 -556 -1249 -2520 -4807 -8956 -16641 -31137 -58573 -109554 -200280 -35049 ...\n",
      "10 8 -4 -34 -93 -195 -357 -599 -944 -1418 -2050 -2872 -3919 -5229 -6843 -8805 -11162 -13964 -172 ...\n",
      "21 39 67 108 165 241 339 462 613 795 1011 1264 1557 1893 2275 2706 3189 3727 4323 4980 5701\n",
      "3 1 1 3 7 13 21 31 43 57 73 91 111 133 157 183 211 241 273 307 343\n",
      "18 31 60 117 214 379 701 1432 3189 7329 16639 36626 77951 160976 324057 638253 1232796 2338487 4 ...\n",
      "15 31 52 76 95 91 35 -105 -328 -491 -43 2534 10778 32073 80618 182013 380053 746451 1394354 2496 ...\n",
      "5 18 50 114 230 437 813 1520 2903 5696 11440 23315 47743 97340 196095 388084 751768 1423532 2638 ...\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 200 tuples:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "(-7, -12, -15, -4, 52, 210, 556, 1204, 2291, 3968, 6387, 9684, 13958, 19246, 25494, 32524, 39997 ...\n",
      "(26, 33, 38, 39, 24, -37, -200, -556, -1249, -2520, -4807, -8956, -16641, -31137, -58573, -10955 ...\n",
      "(10, 8, -4, -34, -93, -195, -357, -599, -944, -1418, -2050, -2872, -3919, -5229, -6843, -8805, - ...\n",
      "(21, 39, 67, 108, 165, 241, 339, 462, 613, 795, 1011, 1264, 1557, 1893, 2275, 2706, 3189, 3727,  ...\n",
      "(3, 1, 1, 3, 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157, 183, 211, 241, 273, 307, 343)\n",
      "(18, 31, 60, 117, 214, 379, 701, 1432, 3189, 7329, 16639, 36626, 77951, 160976, 324057, 638253,  ...\n",
      "(15, 31, 52, 76, 95, 91, 35, -105, -328, -491, -43, 2534, 10778, 32073, 80618, 182013, 380053, 7 ...\n",
      "(5, 18, 50, 114, 230, 437, 813, 1520, 2903, 5696, 11440, 23315, 47743, 97340, 196095, 388084, 75 ...\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "oasis_report = parse(9, ints)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Extrapolate the next value for each row. What is the sum?\n",
    "\n",
    "Our job is to predict the next number on each line. The puzzle suggests doing this with a [difference table](https://www.quora.com/How-do-you-use-a-difference-table-to-predict-the-next-term-of-the-sequence-4-1-14-47-104-191-314) (which means that the input numbers are succesive terms from a polynomial of some unknown degree). The function `deltas` consructs the next row of the difference table, and `extrapolate` computes the next number in a sequence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "def deltas(row: List[int]) -> List[int]:\n",
    "    \"\"\"Succesive differences bewteen each integer in row.\"\"\"\n",
    "    return [row[i] - row[i - 1] for i in range(1, len(row))]\n",
    "\n",
    "def extrapolate(row: List[int]) -> int:\n",
    "    \"\"\"The next integer in row, according to difference table computation.\"\"\"\n",
    "    return 0 if not any(row) else row[-1] + extrapolate(deltas(row))\n",
    "\n",
    "assert deltas([1, 4, 9, 16, 25]) == [3, 5, 7, 9]\n",
    "assert extrapolate([1, 4, 9, 16, 25]) == 36"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  9.1:   .0029 seconds, answer 1938731307      ok"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(9.1, 1938731307, lambda: sum(map(extrapolate, oasis_report)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2:  Extrapolate the previous value for each history. What is the sum?\n",
    "\n",
    "Surprisingly, Part 2 is no harder than Part 1; it just involves extrapolating to the left of the row (the previous number in the sequence) rather than to the right (the next number). This felt like a Day 2 puzzle, not a Day 9."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def extrapolate_previous(row) -> int:\n",
    "    \"\"\"The previous integer in row, according to difference table computation.\"\"\"\n",
    "    return 0 if not any(row) else row[0] - extrapolate_previous(deltas(row))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle  9.2:   .0028 seconds, answer 948             ok"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(9.2, 948, lambda: sum(map(extrapolate_previous, oasis_report)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 10](https://adventofcode.com/2023/day/10): Pipe Maze\n",
    "\n",
    "**Today's input** is a map of the Hot Springs area. The important feature of the map is a continuous loop of pipe, some sections going straight, and some making 90 degree elbow turns. We can parse the map as strings and then use `Grid` to make it conveniently accessible as a 2D grid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 140 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "|-L.FL-FJFL.|7FJ7F|F7-7F77.FL7---.7FF77--.|-F|FF--7FF7F-7F--77FFFJFJF7.F-LF7LFJJ.F|.|77F7F---7FL ...\n",
      "|7JF77-|L7J-F-JJL7|-|LJLF-|7.|.LLLJ7|-7.LFJFF--JF7L7|||FJ|F-J77L|F7.L-FJF----L7.FF.FJ-J-L-7|L|LJ ...\n",
      "LJ-LL|F7|LL7LLL-|-F7||..||..FJ.FJJF-7JJ|.7JLL--7|L7LJLJ|FJL-77|..FFJ7FJ7L7-|-JL.F--7LJJ|LJJ.F-|L ...\n",
      "|.FJ.|F7-7L77|||L7JL-7LF777-JJ.|7F-L7JFJ7|F-|.LLJ|L---7||F--J7JFLF|JF-.--7||J.|F-.7LLLFF7||7F777 ...\n",
      "F-7LF||.FLJL-7|FF|L7FL-L||F-7|FL7LJ|L7L|.LLJ|FJJLF---7|||L---7L7|L|7||FLFLJ|-FF-7|777FJ7|-FFJ|L7 ...\n",
      "F-JF-L7--J|JLL7-|LJ|F|J7L|J.J-|F7J7F|JF-7.|LF7F77L--7||LJF---JL-JJ|LJ7FJL7L|JLFJF|7FF7.-JJFL7|-F ...\n",
      "L7J|7||J--L-F7.||LFL-JF7.F7.|.FL7.FF7L|7F|FF-7F-7F7FJLJF7L----7JFFJJ.J|7L|7L7JLL|JFFJ7.|.|F-J|FJ ...\n",
      "L7.L-FJJJF|FJ-.|JF--J7FJ7LLJ-..LJF||L-7F-7-L7|L7|||L--7|L-----J-FF-F7FL77|---F7JLL-|JF-77FL-7LJF ...\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "maze = Grid(parse(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: How many steps along the loop does it take to get from the starting position to the point farthest from the starting position?\n",
    "\n",
    "Our task is to find all the positions that form the pipe loop, and then say how many steps away is halfway through the loop. I'll define `pipes` to be a dict that maps the character for a pipe piece to the directions it connects (for example, a `|` pipe connects north and south). Then I use `pipe_path` to loop through, extending the path by one position each time, until the path returns to the start. The function `extend_pipe` finds the position of the next piece of pipe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pipe_path(maze: Grid) -> List[Point]:\n",
    "    \"\"\"Find a sequence of points that form the pipe's continuous loop path.\"\"\" \n",
    "    start = first(pos for pos in maze if maze[pos] == 'S')\n",
    "    path = [start]\n",
    "    while path[-1] != start or len(path) == 1:\n",
    "        path.append(extend_pipe(path, maze))\n",
    "    return path\n",
    "\n",
    "def extend_pipe(path, maze) -> Point:\n",
    "    \"\"\"Find the position in the maze that extends the pipe.\"\"\"\n",
    "    pos = path[-1]\n",
    "    double_back = None if len(path) < 2 else path[-2] ## Don't immediately double back\n",
    "    for dir in pipes[maze[pos]]:\n",
    "        pos2 = add(dir, pos)\n",
    "        if neg(dir) in pipes[maze[pos2]] and pos2 != double_back:\n",
    "            return pos2     \n",
    "\n",
    "pipes = {'|': (North, South),\n",
    "         '-': (East,  West),\n",
    "         'L': (North, East),\n",
    "         'J': (North, West),\n",
    "         '7': (South, West),\n",
    "         'F': (South, East),\n",
    "         'S': (North, South, East, West)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 10.1:   .0271 seconds, answer 7066            ok"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(10.1, 7066, lambda: len(pipe_path(maze)) // 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: Calculate the area within the pipe loop. How many tiles are enclosed by the loop?\n",
    "\n",
    "You'd think that this could be easily solved with a flood fill. However, the puzzle description says that there doesn't even need to be a full tile path to the outside for tiles to count as outside the loop–squeezing between pipes is also allowed! Here, `I `is  within the loop and `O` is  outside the loop:\n",
    "\n",
    "    ..........\n",
    "    .S------7.\n",
    "    .|F----7|.\n",
    "    .||OOOO||.\n",
    "    .||OOOO||.\n",
    "    .|L-7F-J|.\n",
    "    .|II||II|.\n",
    "    .L--JL--J.\n",
    "    ..........\n",
    "\n",
    "This had me stumped. Maybe I could do a flood fill of the *inside* by traversing the pipe clockwise and flood filling to every position to the right of the pipe? But figuring that out seemed tricky for the corner pieces. I decided to pass on this puzzle, and maybe come back to it later. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 10.2:   .0000 seconds, answer unknown        "
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(10.2, unknown)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 11](https://adventofcode.com/2023/day/11): Cosmic Expansion \n",
    "\n",
    "**Today's input** is another 2D map, this time of galaxies as recorded by the Elf's telescope."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 140 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      ".......................#.........#...............#....................................#......... ...\n",
      ".#........#.................................................................#................... ...\n",
      ".............................#..............................................................#... ...\n",
      "...............#.....................................#.......................................... ...\n",
      ".......#....................................#.............#..............#......#............... ...\n",
      ".......................................#.................................................#...... ...\n",
      "..........................#......#.............................................................. ...\n",
      "...................#........................................................#................... ...\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "galaxies = Grid(parse(11), skip='.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Expand the universe, then find the distance between every pair of galaxies. What is the sum of these lengths?\n",
    "\n",
    "The puzzle says that 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. After accounting for this expansion, we're asked to find the $L^1$ or \"[taxi distance](https://en.wikipedia.org/wiki/Taxicab_geometry)\" between each pair of galaxies, and add them up.\n",
    "\n",
    "I'll do that by finding the regular taxi distance between pairs of points, and adding one more unit for each intervening X position that does not contain a galaxy (that is, each empty column), and the same for each intervening Y position (empty row)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "def galaxy_quest(galaxies):\n",
    "    \"\"\"The total taxi distance between all pairs of galaxies, allowing for expansion.\"\"\"\n",
    "    x_galaxies, y_galaxies = set(Xs(galaxies)), set(Ys(galaxies))\n",
    "    def galaxy_distance(p: Point, q: Point):\n",
    "        \"\"\"L^1 distance, plus 1 unit for each empty row or column between the two points.\"\"\"\n",
    "        empty_cols = len(set(cover(X_(p), X_(q))) - x_galaxies)\n",
    "        empty_rows = len(set(cover(Y_(p), Y_(q))) - y_galaxies)\n",
    "        return taxi_distance(p, q) + empty_cols + empty_rows\n",
    "    return sum(galaxy_distance(p, q) for p, q in combinations(galaxies, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 11.1:   .3273 seconds, answer 10173804        ok"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(11.1, 10173804, lambda: galaxy_quest(galaxies))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: Expand the universe according to the new rules, then find the distance between every pair of galaxies. What is the sum of these lengths?\n",
    "\n",
    "Under the new rules, each empty row or column expands to a *million* rows or columns, not just 2. If I had done Part 1 by maintaining an *m*×*n*  grid, I'd be in trouble now, because the new expanded grid would be a trillion times larger. Fortunately I didn't do that, so the changes are easy: `galaxy_quest` takes an optional argument specifying the expansion factor; by default it is 2 for  backwards compatability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "def galaxy_quest(galaxies, expansion=2) -> int:\n",
    "    \"\"\"The total taxi distance between all pairs of galaxies, allowing for expansion.\"\"\"\n",
    "    x_galaxies, y_galaxies = set(Xs(galaxies)), set(Ys(galaxies))\n",
    "    def galaxy_distance(p: Point, q: Point):\n",
    "        \"\"\"L^1 distance, plus 1 unit for each empty row or column between the two points.\"\"\"\n",
    "        empty_cols = len(set(cover(X_(p), X_(q))) - x_galaxies)\n",
    "        empty_rows = len(set(cover(Y_(p), Y_(q))) - y_galaxies)\n",
    "        return taxi_distance(p, q) + (expansion - 1) * (empty_cols + empty_rows)\n",
    "    return sum(galaxy_distance(p, q) for p, q in combinations(galaxies, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 11.2:   .3320 seconds, answer 634324905172    ok"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(11.2, 634324905172, lambda: galaxy_quest(galaxies, expansion=1_000_000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had a **bug**: I was originally multiplying the number of intervening empty columns plus rows by `expansion`, but it should be `(expansion - 1)`, because the regular taxi distance takes care of one of the units. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 12](https://adventofcode.com/2023/day/12): Hot Springs \n",
    "\n",
    "Each line of **today's input** is a **condition record** for a sequence of hot springs, telling which of the springs on that line might be damaged. Each record is encoded in a partially redundant format: the first (non-numeric) part of the line \"`???.### 1,1,3`\" means that the condition of the first three springs is unknown, then 1 is operational, then 3 are damaged. The `1,1,3` gives the size of each contiguous group of damaged springs (in order).  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 1000 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "..???#??.?????? 4,3\n",
      "##??#??#?..??? 9,1,1\n",
      ".?##?#?????..? 5,1,1,1\n",
      "???#?##??? 4,4\n",
      "?.??#?????#???? 8,1\n",
      ".?#?.???##??##? 3,6\n",
      "??????#??? 3,2\n",
      "?##??##???.??.?#? 3,4,1,2,2\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 1000 tuples:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "('..???#??.??????', (4, 3))\n",
      "('##??#??#?..???', (9, 1, 1))\n",
      "('.?##?#?????..?', (5, 1, 1, 1))\n",
      "('???#?##???', (4, 4))\n",
      "('?.??#?????#????', (8, 1))\n",
      "('.?#?.???##??##?', (3, 6))\n",
      "('??????#???', (3, 2))\n",
      "('?##??##???.??.?#?', (3, 4, 1, 2, 2))\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "def parse_condition_record(line: str) -> Tuple[str, Tuple[int]]:\n",
    "    \"\"\"The first half of line is a string; then a tuple of ints.\"\"\"\n",
    "    springs, runs = line.split()\n",
    "    return springs, ints(runs)\n",
    "\n",
    "records = parse(12, parse_condition_record)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "### Part 1: For each row, count all of the different arrangements of operational and damaged springs that meet the given criteria. What is the sum of those counts?\n",
    "\n",
    "For example, the only arrangement that matches the record \"`???.### 1,1,3`\" is \"`#.#.###`\". And for the record \"`??...?? 1, 1` there are four arrangments: the first damaged spring can be either of the first two positions; for each of those cases the other damaged spring can be in either of the last two positions.\n",
    "\n",
    "One way to handle this would be to try every possible way of substituting either '`.`' or '`#`' for each '`?`'. If there are $n$ question marks, that gives $2^n$ strings to consider. I'd rather avoid exponential computation, which can come back to get you in Part 2.\n",
    "\n",
    "Another way to handle this is similar to interpreting a regular expression match, but with choices in both the springs string (a '`?`' can be either a damaged or undamaged spring) and in the tuple of ints (there can be one or more undamaged springs between each number). We can follow the basic pattern of a recursive regular expression matcher. On each recursive call we take care of the first number in the tuple of runs. If that number is *R*, then we have a valid arrangement either if the first *R* characters can be considered damaged (and the next character, if there is one, as undamaged) and we then go on to the next number in the tuple of runs; or if we consider the first character as undamaged (and then look at the next character).\n",
    "\n",
    "We use `@cache` to hopefully turn most of the exponential work into near-linear work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "@cache\n",
    "def arrangements(springs: str, runs: Tuple[int]) -> int:\n",
    "    \"\"\"Count the number of arranagements of `springs` that is consistent with `runs`.\"\"\"\n",
    "    if not runs:\n",
    "        return (0 if '#' in springs else 1) # One arrangement with no springs / no runs\n",
    "    elif possible_damage(springs) < sum(runs):\n",
    "        return 0 # Not enough damaged springs left to match runs\n",
    "    else: \n",
    "        R, rest = runs[0], runs[1:]\n",
    "        # Consider the case where first R characters in springs are damaged\n",
    "        damaged = (0 if (possible_damage(springs[:R]) != R or springs[R:].startswith('#'))\n",
    "                   else arrangements(springs[R + 1:], rest))\n",
    "        # Consider the case where first character in springs is undamaged\n",
    "        undamaged = (0 if springs[0] == '#' else arrangements(springs[1:], runs))\n",
    "        return damaged + undamaged\n",
    "\n",
    "def possible_damage(springs: str) -> int: \n",
    "    \"\"\"The number of damaged springs ('#') plus possibly damaged springs ('?').\"\"\"\n",
    "    return springs.count('#') + springs.count('?')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 12.1:   .0148 seconds, answer 7843            ok"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(12.1, 7843, lambda: sum(arrangements(s, r) for s, r in records))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: Unfold your condition records; what is the new sum of possible arrangement counts?\n",
    "\n",
    "In Part 2, we learn that the records should be **unfolded**, which means made 5 times longer: the string of springs should be repeated 5 times, separated by '`?`', and the tuple of runs just repeated 5 times. I'm glad I chose the approach I did, and not the $2^n$ approach! I can use my approach unchanged; all I need to do is `unfold` the records:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unfold(records) -> str: return [('?'.join(5 * [s]), 5 * r) for s, r in records]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 12.2:   .3497 seconds, answer 10153896718999  ok"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(12.2, 10153896718999, lambda: sum(arrangements(s, r) for s, r in unfold(records)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had a **bug** where I initially wrote `'?'.join(5 * s)` when it should be `'?'.join(5 * [s])`. The former puts a question mark between every character of 5 copies of `s`; what we want is to put it between each of the 5 copies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "arrangements.cache_clear() # Don't need the cache any more."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 13](https://adventofcode.com/2023/day/13): Point of Incidence\n",
    "\n",
    "**Today's input** is another series of 2D maps, this time of patterns of ash (`.`) and rock (`#`) on the valley floor. There's no advantage in putting the rows into a `Grid` structure; I'll leave each map as a list of rows, where each row is a string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 1357 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "##..####..##..#\n",
      "#.##.#..##..##.\n",
      "##..###.##..##.\n",
      ".#..#.#........\n",
      "######.########\n",
      "##..##...####..\n",
      "##..###.#....#.\n",
      ".###..#.######.\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 100 lists:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "['##..####..##..#', '#.##.#..##..##.', '##..###.##..##.', '.#..#.#........', '######.########',  ...\n",
      "['##.##...#....', '#####.#......', '...##..#.####', '....#....#..#', '.##.....#....', '#.###.#.. ...\n",
      "['..#...####...#...', '....#.#..#.#.....', '..##.######.##...', '...#.######.#....', '#.###..##. ...\n",
      "['..##..#......', '##...#.#.##.#', '.####.##....#', '#.##.#...##..', '#....#..####.', '..##..#.# ...\n",
      "['####.......#..#..', '.......####....##', '....####.##.##.##', '######..####..###', '.##...##.. ...\n",
      "['##..##..##..###', '.####....####..', '.#.#.#..#.#.#..', '.#.#.####.#.#..', '#..###..###..##',  ...\n",
      "['..##............#', '......##.#..##...', '##..###.####.###.', '#....##########..', '.####..#.. ...\n",
      "['...###....###..', '##...#....#...#', '..#.#.#..#.#.#.', '...#.#.##.#.#..', '####........###',  ...\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "patterns = parse(13, str.split, sections=paragraphs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Find the line of reflection in each of the patterns in your notes. What number do you get after summarizing all of your notes?\n",
    "\n",
    "The valley is full of mirrors, so some maps actually have a mirror placed horizontally so that the rows above reflect the rows below. If there are exactly *m* rows above (or below) the mirror, then the *m* rows below (or above) must mirror those rows, but the other rows can be anything. Consider this map:\n",
    "\n",
    "    #...##..#\n",
    "    #....#..#\n",
    "    ..##..###\n",
    "    #####.##.   < mirror between these 2 lines; \n",
    "    #####.##.   < this is position 4 (4 rows above the mirror)\n",
    "    ..##..###\n",
    "    #....#..#\n",
    "\n",
    "There are only 3 lines below the mirror position, so they must match only 3 of the lines above; the other line above is unconstrained.\n",
    "\n",
    "It is also possible that the mirror is placed vertically, in which case we're dealing with mirrored columns rather than rows. I will deal with that by rotating the pattern, that is, transposing rows and columns with my utility function `T`, so I only have to write code to find a mirror between rows.\n",
    "\n",
    "The puzzle instructions say to **summarize** the maps by adding up the column mirror positions plus 100 times the row mirror positions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mirror_summary(patterns: List[List[str]]) -> int:\n",
    "    \"\"\"100 * mirror column positions plus mirror row positions.\"\"\"\n",
    "    return sum(100 * mirror_position(pattern) + mirror_position(T(pattern))\n",
    "               for pattern in patterns)\n",
    "    \n",
    "def mirror_position(pattern: List[str]) -> int:\n",
    "    \"\"\"Position of a horizontal mirror between rows, or 0.\"\"\"\n",
    "    return first(i for i in range(1, len(pattern)) if is_mirror(pattern, i)) or 0\n",
    "\n",
    "def is_mirror(pattern, i) -> bool: \n",
    "    \"\"\"Do the rows above position i mirror the rows below?\"\"\"\n",
    "    m = min(i, len(pattern) - i) # Number of rows to match\n",
    "    return pattern[i - m : i] == pattern[i : i + m][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 13.1:   .0018 seconds, answer 33780           ok"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(13.1, 33780, lambda: mirror_summary(patterns))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: In each pattern, fix the smudge and find the different line of reflection. What number do you get after summarizing the new reflection line in each pattern in your notes?\n",
    "\n",
    "In Part 2, we are told that each mirror has exactly one smudge where an ash or rock should be the opposite type. Our mission is to recompute the `mirror_summary` number after fixing the smudge on each mirror. \n",
    "\n",
    "I'll refactor `mirror_summary` and `mirror_position` by interjecting a dependency: an optional argument specifying the mirror test to use. By default it will be `is_mirror` (as in Part 1), but for Part 2 I'll introduce `is_smudged_mirror`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mirror_summary(patterns: List[List[str]], mirror_test=is_mirror) -> int:\n",
    "    \"\"\"100 * mirror column positions plus mirror row positions.\"\"\"\n",
    "    return sum(100 * mirror_position(pattern, mirror_test) \n",
    "                   + mirror_position(T(pattern), mirror_test)\n",
    "               for pattern in patterns)\n",
    "    \n",
    "def mirror_position(pattern: List[str], mirror_test=is_mirror) -> int:\n",
    "    \"\"\"Position of a horizontal mirror between rows, or 0.\"\"\"\n",
    "    return first(i for i in range(1, len(pattern)) if mirror_test(pattern, i)) or 0\n",
    "\n",
    "def is_smudged_mirror(pattern, i):\n",
    "    \"\"\"Do rows above row i almost mirror the rows below (except for exactly 1 smudge)?\"\"\"\n",
    "    m = min(i, len(pattern) - i)\n",
    "    smudges = 0\n",
    "    for r in range(m):\n",
    "        row1, row2 = pattern[i - 1 - r], pattern[i + r]\n",
    "        smudges += quantify(a != b for a, b in zip(row1, row2))\n",
    "        if smudges > 1:   # If there is more than 1 smudge, bail out early\n",
    "            return False\n",
    "    return (smudges == 1) # Return true if exactly one smudge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 13.2:   .0076 seconds, answer 23479           ok"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(13.2, 23479, lambda: mirror_summary(patterns, is_smudged_mirror))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 14](https://adventofcode.com/2023/day/14): Parabolic Reflector Dish\n",
    "\n",
    "**Today's input** is another 2D grid, showing the positions of rounded (`O`) and cube-shaped (`#`) rocks on a platform. We'll put the rocks into a grid, and skip the non-rock positions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 100 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "O.O#..O.#...#..O.O#..O#...O..O.#...O#.OO.O...#....#.O.##..####.OOO....OO......##..........#O.#O.O.#.\n",
      "..O.#..#O...#..#.....O..O..OO..#.O..O#..#O#...#......O.O.O......#..OO##...O..#.O.O..#...#O....O.OO..\n",
      "....O#O#.O#...#..O.O#..#.....O....#.....OOO#OO.#....#...#.O.OOOO..#O.O##....##..O.....##.OOO.#..##..\n",
      "OO...OO...#..OOO..#....O.#.......##O....#..O.O#..#.O.#..O.#O.#.#..#....#...O.......O#O.....OOO###...\n",
      "..#...#...O.O....#..O.....#...OO.##O...#O...#.#.O#O.OO.OO.O...#O#...#.#...#.....O..#..O##.##.OO..#.O\n",
      "..#.#.O.#OO#...#.#O##O.OO..#......#OO....O........#OO#..O.O.....#.....O.O..O.#O#..O......O....O.##.#\n",
      ".....O..O......O...#.#.#.....#OOO##O.#O...O...O.O..#...#O##.OO......O......OO..O#..##......#OO#..O..\n",
      "...#...O.#O.......#.O....#..#.....#.O.#.....#..O..#.....O#..O#.O.O......O###O#..O...OO..##........##\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "platform = Grid(parse(14), skip='.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Tilt the platform so that the rounded rocks all roll north. Afterward, what is the total load on the north support beams?\n",
    "\n",
    "Tilt the platform and roll the rounded rocks as far as they can go–until they are stopped by another rock or the edge of the platform. This feels like playing [2048](https://play2048.co/), so I'm guessing that in Part 2 we will have to tilt in directions other than North. Therefore I'll parameterize `tilt_platform` and `roll_rock` to take a direction of tilt. Note that in `tilt_platform` I have to sort the rounded rocks so that the ones closer to the edge move out of the way first, and I make a copy of the platform to avoid altering the original input. The dict `edge_key` tells how to sort the rounded rocks.\n",
    "\n",
    "The **total load** is defined as the sum of the row number of each rounded rock, where the bottom row is row number one, and row numbers go up from there. I'm not sure whether `total_load` needs to be parameterized with a direction, so I won't do it yet. [YAGNI](https://en.wikipedia.org/wiki/You_aren%27t_gonna_need_it#:~:text=%22You%20aren't%20gonna%20need,add%20functionality%20until%20deemed%20necessary.)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tilt_platform(platform: Grid, direction=North) -> Grid:\n",
    "    \"\"\"Tilt the platform and roll rounded rocks in `direction`.\"\"\"\n",
    "    copy = platform.copy()\n",
    "    for pos in sorted(platform.findall('O'), key=edge_key[direction]):\n",
    "        roll_rock(pos, copy, direction)\n",
    "    return copy\n",
    "\n",
    "def roll_rock(pos: Point, grid: Grid, direction):\n",
    "    \"\"\"Roll one rounded rock in position `pos` as far as it will go.\"\"\"\n",
    "    del grid[pos]   # Remove the rock from its old position\n",
    "    pos2 = add(pos, direction)\n",
    "    # Keep rolling as long as pos2 is not off the edge and does not contain another rock\n",
    "    while grid.in_range(pos2) and pos2 not in grid:\n",
    "        pos, pos2 = pos2, add(pos, direction)\n",
    "    grid[pos] = 'O' # Place the rock in its new position\n",
    "\n",
    "# `edge_key` says what function to sort points on, given the direction of tilt.\n",
    "edge_key = {North: Y_,\n",
    "            West:  X_,\n",
    "            South: lambda r: -Y_(r),\n",
    "            East:  lambda r: -X_(r)}\n",
    "\n",
    "def total_load(platform: Grid) -> int:\n",
    "    \"\"\"Sum of row numbers of rounded rocks, counting the bottom row as 1.\"\"\"\n",
    "    num_rows = Y_(platform.size)\n",
    "    return sum(num_rows - Y_(p) for p in platform.findall('O'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 14.1:   .0203 seconds, answer 108813          ok"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(14.1, 108813, lambda: total_load(tilt_platform(platform, North)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: Run the spin cycle for 1,000,000,000 cycles. Afterward, what is the total load?\n",
    "\n",
    "A **spin cycle** means tilting the platform North, West, South, and East, in that order. So I was right in anticipating this! I can implement a spin cycle easily enough:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "def spin_cycle(platform: Grid, n=1) -> Grid:\n",
    "    \"\"\"Tilt the platform in each direction, repeat `n` times.\"\"\"\n",
    "    for _ in range(n):\n",
    "        for direction in (North, West, South, East):\n",
    "            platform = tilt_platform(platform, direction)\n",
    "    return platform"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But I don't want to run this a billion times! I suspect that the pattern of rocks will repeat after a certain number of steps. Let's find out if that is true. `find_spin_repetition` continually does spin cycles, and finds two times when the result is the same (the rounded rocks are in the same positions). It returns the two times and the state of the platform. It stores the history of tilted platforms in the dict `history`, but since a grid is not hashable, it uses a frozen set of the rounded rocks as the key in the history dict."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_spin_repetition(platform: Grid) -> Tuple[int, int, Grid]:\n",
    "    \"\"\"Apply spin_cycle until we find a repetition in history of tilted platforms,\n",
    "    then return the two time steps when this repetition occurs and the resulting platform.\"\"\"\n",
    "    history = {}\n",
    "    for t in count_from(0):\n",
    "        round_rocks = frozenset(platform.findall('O'))\n",
    "        if round_rocks in history:\n",
    "            return history[round_rocks], t, platform\n",
    "        history[round_rocks] = t\n",
    "        platform = spin_cycle(platform)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try it (and look at just the numbers, not the resulting platform):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(88, 97)"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_spin_repetition(platform)[:2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Great!** It took less than 100 spin cycles to find the repetition. Now `big_spin_cycle` does the same thing as `spin_cycle`, but relies on repetition to automatically skip ahead. Once I find the first two repetition times, I create a `range` of all the repetition times up to `n`, then see where the last repetition point is, and do any remaining `spin_cycle` operations to get the final platform grid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "def big_spin_cycle(platform: Grid, n=10**9) -> Grid:\n",
    "    \"\"\"Tilt the platform in each direction, repeat `n` times. Use repetitions for efficiency.\"\"\"\n",
    "    t1, t2, t_platform = find_spin_repetition(platform)\n",
    "    repetitions = range(t1, n, t2 - t1)\n",
    "    return spin_cycle(t_platform, n - repetitions[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 14.2:  7.3388 seconds, answer 104533          ok"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(14.2, 104533, lambda: total_load(big_spin_cycle(platform)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 15](https://adventofcode.com/2023/day/15): Lens Library\n",
    "\n",
    "**Today's input** is a comma-separated string of **steps** intended to bring the Lava Production Facility online by maniopulating boxes of lenses. I'll parse the input by splitting it on commas:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 1 str:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "vvn-,dpf=4,dlm-,pc=6,rrlt=5,slk=2,tql-,xt-,th=2,thls-,hjnq-,tspf-,sgtjx-,dpqgcl=9,gg-,cnqm-,rt-, ...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 4000 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "vvn-\n",
      "dpf=4\n",
      "dlm-\n",
      "pc=6\n",
      "rrlt=5\n",
      "slk=2\n",
      "tql-\n",
      "xt-\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "lens_steps = parse(15, sections=lambda text: text.split(','))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Run the HASH algorithm on each step. What is the sum of the results?\n",
    "\n",
    "The puzzle instructions describe the HASH algorithm, which operates on the ASCII code for each character in the string. So just hash the steps and add up the sum. (Suspiciously easy for Day 15.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "def HASH(string: str) -> int:\n",
    "    \"\"\"Compute the HASH value of the string, according to the puzzle instructions.\"\"\"\n",
    "    value = 0\n",
    "    for ch in string:\n",
    "        value += ord(ch)\n",
    "        value *= 17\n",
    "        value = value % 256\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 15.1:   .0019 seconds, answer 497373          ok"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(15.1, 497373, lambda: sum(map(HASH, lens_steps)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: Follow the initialization sequence. What is the focusing power of the resulting lens configuration?\n",
    "\n",
    "Part 2 requires a lot of attention to detail, but nothing algorithmicly difficult. The steps describe how to add lenses (each with a label and a focal length number) to a series of 256 boxes:\n",
    "- The instruction `cm-` means to remove a lens with label `cm` from the box numbered by `HASH('cm')`.\n",
    "- The insruction `rn=1` means to place a lens with label `rn` in the box numbered by `HASH('rn')`; if there was a lens with that label, replace it; otherwise put the new lens at the back of the box.\n",
    "\n",
    "I considered implementing a box as a list, so a box with two lenses would be `[('rn', 1), ('cm', 2]`; but I decided it would be slightly easier as a dict: `{'rn': 1, 'cm': 2}`. This works because a new lens always goes to the back of the box, and that's how dicts work.\n",
    "\n",
    "The **focusing power** of a box is the product of the box number × slot number × focal length number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "Box = dict\n",
    "\n",
    "def initialization_sequence(steps: List[str]) -> List[Box]:\n",
    "    \"\"\"Follow each step, adding, replacing, or removing lenses from boxes.\"\"\"\n",
    "    boxes = [Box() for _ in range(256)]\n",
    "    for step in steps:\n",
    "        label, op, f = parse_step(step)\n",
    "        box = boxes[HASH(label)]\n",
    "        if op == '-' and label in box:\n",
    "            del box[label]\n",
    "        elif op == '=':\n",
    "            box[label] = f\n",
    "    return boxes\n",
    "\n",
    "def parse_step(step: str) -> Tuple[str, str, Union[str, int]]:\n",
    "    \"\"\"Parse the label, opcode, and f-number from the step.\"\"\"\n",
    "    if '-' in step:\n",
    "        return tuple(step.partition('-'))\n",
    "    else:\n",
    "        op, _, n = step.partition('=')\n",
    "        return op, '=', int(n)\n",
    "    \n",
    "def focusing_power(boxes) -> int:\n",
    "    \"\"\"The focusing power is the sum of (box number * slot number * f number) for all lenses.\"\"\"\n",
    "    return sum(b * slot * f\n",
    "              for (b, box) in enumerate(boxes, 1)\n",
    "              for (slot, f) in enumerate(box.values(), 1))\n",
    "    \n",
    "assert parse_step('rn=1') == ('rn', '=', 1)\n",
    "assert parse_step('cm-')  == ('cm', '-', '')\n",
    "assert 145 == focusing_power([Box(rn=1, cm=2), Box(), Box(), Box(ot=7, ab=5, pc=6)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 15.2:   .0030 seconds, answer 259356          ok"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(15.2, 259356, lambda: focusing_power(initialization_sequence(lens_steps)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At first I  had a **bug** where I thought the box number was selected by the hash of the **step**; actually it is the hash of the **label**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 16](https://adventofcode.com/2023/day/16): The Floor Will Be Lava \n",
    "\n",
    "**Today's input** is another 2D map, this time of a **contraption** containing empty space (`.`), mirrors (`/` and `\\`), and splitters (`|` and `-`). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 110 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "\\|.....-.....\\....../.....-....................................../....-.............|.......|... ...\n",
      "...............|...|...........-............../......../..|.........|..../....-.-.|...........|. ...\n",
      ".........|....\\......-..............................|.....\\..........\\........../.../...../..\\.. ...\n",
      "...-................................................./.-...-..................../....../..|....| ...\n",
      "\\...|...|-.............................................................................-........ ...\n",
      "...............|.....|.......\\..|.....-................................|.........../............ ...\n",
      ".\\....\\............./............|...........\\...|.....................\\.-.\\......-............| ...\n",
      "./..........................\\..\\.........|.-...............................|........|..-....-... ...\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "contraption = Grid(parse(16))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: How many positions end up being energized?\n",
    "\n",
    "A beam of light enters in the top-left corner heading East, bounces 90 degrees off of mirrors, and when it hits the flat side of a splitter, splits into two beams heading out the pointy ends of the splitter. We are asked how many positions are **energized** (have a beam pass through them). To allow some generality for Part 2, I'll design `energize` to yield a list of positions, and to do it on each time step. The subfunction `propagate_beam` will take a beam and propagate it one step along. This might result in no beams (if it goes off the contraption), one beam (if it goes straight or turns), or two beams (if it splits).\n",
    "\n",
    "I will account for the possibility that the beam enters an infinite loop: `energize` will keep the set of all beams `seen` in the past, and only propagate ones that haven't been seen before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "Beam = namedtuple('Beam', 'pos, dir')\n",
    "\n",
    "def energize(contraption: Grid, start=Beam((0, 0), East)) -> Set[Point]:\n",
    "    \"\"\"Find all the positions that this beam will visit as it bounces around the contraption.\"\"\"\n",
    "    seen: Set[Beam] = set()\n",
    "    Q = [start]\n",
    "    while Q:\n",
    "        beam = Q.pop()\n",
    "        if beam not in seen and beam.pos in contraption:\n",
    "            seen.add(beam)\n",
    "            Q.extend(propagate_beam(contraption, beam))\n",
    "    return {beam.pos for beam in seen}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "def propagate_beam(contraption: Grid, beam: Beam) -> List[Beam]:\n",
    "    \"\"\"Return the beam[s] that this beam will produce in the next step.\"\"\"\n",
    "    ch = contraption[beam.pos]\n",
    "    directions = (\n",
    "        []             if ch is None else                               # off the edge\n",
    "        [North, South] if ch == '|' and beam.dir in (East, West) else   # split\n",
    "        [East, West]   if ch == '-' and beam.dir in (North, South) else # split\n",
    "        [mirrors[ch][beam.dir]] if ch in ('/', '\\\\') else               # mirror\n",
    "        [beam.dir])                                                     # go straight\n",
    "    return [Beam(add(beam.pos, dir), dir) for dir in directions]\n",
    "\n",
    "mirrors = {'/':  {East: North, North: East, South: West, West: South},\n",
    "           '\\\\': {East: South, South: East, North: West, West: North}}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 16.1:   .0189 seconds, answer 7060            ok"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(16.1, 7060, lambda: len(energize(contraption)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had a **bug** where I had the wrong direction for one of the entries in the `mirrors` table. I spent too long writing simple tests (since deleted) to verify that my function definitions were correct (they were), when I should have been verifying my table data.\n",
    "\n",
    "### Part 2: Find the initial beam configuration that energizes the largest number of tiles; how many positions are energized in that configuration?\n",
    "\n",
    "For Part 2 we have to consider a beam entering from any of the perimeter positions and find the one that reaches the most positions. I'll just try every possibility in turn. That will take a few seconds, but I don't see an easy way to get the run time under a second."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 16.2:  6.2780 seconds, answer 7493            ok"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def perimeter_beams(contraption: Grid) -> List[Beam]:\n",
    "    \"\"\"All the beams that start on the perimeter and point in.\"\"\"\n",
    "    X, Y = contraption.size\n",
    "    return ([Beam((x, 0),   South) for x in range(X)] +\n",
    "            [Beam((x, Y-1), North) for x in range(X)] +\n",
    "            [Beam((0, y),   East)  for y in range(Y)] +\n",
    "            [Beam((X-1, y), West)  for y in range(Y)])\n",
    "\n",
    "answer(16.2, 7493, lambda: max(len(energize(contraption, b)) \n",
    "                               for b in perimeter_beams(contraption)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 17](https://adventofcode.com/2023/day/17): Clumsy Crucible\n",
    "\n",
    "Another **day**, another grid **input**. This time a grid of digts representing heat loss numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 141 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "441132215352334323215454261221632644656445213353552622323563332336541646635131673357444214232225 ...\n",
      "312215453552151141123312226465513535442234626625432245665237412214265255271211437124272714461512 ...\n",
      "443151214341313223414136533512615424112315121662431175772242275162553116674144511314266234544414 ...\n",
      "332214452151354115414225115552132652315225662141412737534647165564417642465472123263413564732546 ...\n",
      "111231515424424415511526233341223214634136446246727762247242464222611262622274375355571732753224 ...\n",
      "222225252444221146565351533441332342414266522175136523742733276476524466411723627531552427377723 ...\n",
      "323342345314322115664521625442132322465333737135734316666533727547452174462247456315755746534352 ...\n",
      "533112512521213133314236121416355315432552125712563416375132723612753244752652255465377557637522 ...\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 141 tuples:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "(4, 4, 1, 1, 3, 2, 2, 1, 5, 3, 5, 2, 3, 3, 4, 3, 2, 3, 2, 1, 5, 4, 5, 4, 2, 6, 1, 2, 2, 1, 6, 3, ...\n",
      "(3, 1, 2, 2, 1, 5, 4, 5, 3, 5, 5, 2, 1, 5, 1, 1, 4, 1, 1, 2, 3, 3, 1, 2, 2, 2, 6, 4, 6, 5, 5, 1, ...\n",
      "(4, 4, 3, 1, 5, 1, 2, 1, 4, 3, 4, 1, 3, 1, 3, 2, 2, 3, 4, 1, 4, 1, 3, 6, 5, 3, 3, 5, 1, 2, 6, 1, ...\n",
      "(3, 3, 2, 2, 1, 4, 4, 5, 2, 1, 5, 1, 3, 5, 4, 1, 1, 5, 4, 1, 4, 2, 2, 5, 1, 1, 5, 5, 5, 2, 1, 3, ...\n",
      "(1, 1, 1, 2, 3, 1, 5, 1, 5, 4, 2, 4, 4, 2, 4, 4, 1, 5, 5, 1, 1, 5, 2, 6, 2, 3, 3, 3, 4, 1, 2, 2, ...\n",
      "(2, 2, 2, 2, 2, 5, 2, 5, 2, 4, 4, 4, 2, 2, 1, 1, 4, 6, 5, 6, 5, 3, 5, 1, 5, 3, 3, 4, 4, 1, 3, 3, ...\n",
      "(3, 2, 3, 3, 4, 2, 3, 4, 5, 3, 1, 4, 3, 2, 2, 1, 1, 5, 6, 6, 4, 5, 2, 1, 6, 2, 5, 4, 4, 2, 1, 3, ...\n",
      "(5, 3, 3, 1, 1, 2, 5, 1, 2, 5, 2, 1, 2, 1, 3, 1, 3, 3, 3, 1, 4, 2, 3, 6, 1, 2, 1, 4, 1, 6, 3, 5, ...\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "heat_loss = Grid(parse(17, digits))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Directing the crucible from the lava pool to the machine parts factory, but not moving more than three consecutive blocks in the same direction, what is the least heat loss it can incur?\n",
    "\n",
    "Our task is to find the lowest-cost path from the upper left (lava pool) to the lower right (machine parts factory). I notice:\n",
    "- If the allowable movements were just `South` and `East`, this would be a simple dynamic programming problem.\n",
    "- If the allowable movements were any of the four directions, this would be a `GridProblem` from my AdventUtils.\n",
    "- Rather, there are some idiosyncratic rules: movement can be straight, but no more than 3 straight moves in a row, or it can be a 90 degree turn at any time. That means that a state in the search space must contain not jsut the current locatioon, but also the curent direction and how many moves have been made in that direction.\n",
    "\n",
    "I can implement this as a subclass of my `SearchProblem` and apply `A_star_search`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "State = namedtuple('State', 'pos, dir, n')\n",
    "\n",
    "class HeatLossProblem(SearchProblem):\n",
    "    \"\"\"Path search on a grid; 4 direction moves, but can't move straight more than 3 times in a row.\"\"\"\n",
    "    \n",
    "    def actions(self, state) -> List[Vector]:\n",
    "        \"\"\"Actions are directions. Can turn 90 degrees, or go straight (can't reverse).\n",
    "        Can't go straight more than 3 times in a row.\"\"\"\n",
    "        dirs = [make_turn(state.dir, 'right'), make_turn(state.dir, 'left')]\n",
    "        if state.n < 3: \n",
    "            dirs.append(state.dir)\n",
    "        return [dir for dir in dirs if add(state.pos, dir) in self.grid]\n",
    "        \n",
    "    def result(self, state, action): \n",
    "        \"\"\"Move state's position by action, and keep track of `n` in a row.\"\"\"\n",
    "        return State(add(state.pos, action), action, \n",
    "                     n=(1 if action != state.dir else state.n + 1))\n",
    "        \n",
    "    def is_goal(self, state): return state.pos == self.goal\n",
    "        \n",
    "    def action_cost(self, state1, action, state2): return self.grid[state2.pos]\n",
    "        \n",
    "    def h(self, node): return taxi_distance(node.state.pos, self.goal)\n",
    "    \n",
    "\n",
    "def heat_loss_search(heat_loss: Grid):\n",
    "    \"\"\"Do A* search from top left to bottom right of grid, following rules.\"\"\"\n",
    "    problem = HeatLossProblem(grid=heat_loss, initial=State((0, 0), East, 0), goal=max(heat_loss))\n",
    "    return A_star_search(problem)\n",
    "\n",
    "node = heat_loss_search(heat_loss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 17.1:  3.2620 seconds, answer 859             ok"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(17.1, 859, lambda: heat_loss_search(heat_loss).path_cost)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had a **bug** where I forgot to make sure that `actions` don't move off the grid; in my `GridProblem` class that is taken care of automatically, but I forgot that I had to take care of it myself in this custom new class.\n",
    "\n",
    "### Part 2: Directing the ultra crucible from the lava pool to the machine parts factory, what is the least heat loss it can incur?\n",
    "\n",
    "In Part 2, we switch to **ultra crucibles**. Once an ultra crucible starts moving in a direction, it needs to move a minimum of four blocks in that direction before it can turn (or even before it can stop at the end). However, it will eventually start to get wobbly: an ultra crucible can move a maximum of ten consecutive blocks without turning."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UltraHeatLossProblem(HeatLossProblem):\n",
    "    \"\"\"Path search on a grid; 4 direction moves, must move straight 4 to 10 times.\"\"\"\n",
    "    \n",
    "    def actions(self, state) -> List[Vector]:\n",
    "        \"\"\"Actions are directions. Can turn 90 degrees, or go straight (can't reverse).\"\"\"\n",
    "        dirs = ([state.dir] if state.n < 10 else []) # Maybe go straight?\n",
    "        if state.n >= 4:\n",
    "            dirs.extend([make_turn(state.dir, 'right'), make_turn(state.dir, 'left')])\n",
    "        return [dir for dir in dirs if add(state.pos, dir) in self.grid]\n",
    "        \n",
    "    def is_goal(self, state): return state.pos == self.goal and state.n >= 4\n",
    "\n",
    "def heat_loss_search(heat_loss: Grid, problem_class=HeatLossProblem) -> Node:\n",
    "    \"\"\"Do A* search from top left to bottom right of grid, following rules.\"\"\"\n",
    "    problem = problem_class(grid=heat_loss, initial=State((0, 0), East, 0), goal=max(heat_loss))\n",
    "    return A_star_search(problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unfortunately, my first try had a **bug**. I came up with an answer of 1005, and AOC said that was too low; I thought maybe I had confused a `<` for a `<=` and tried again, getting 1030, which AOC said was too high. So I've got fairly tight bounds, but I'd like to debug this, first by going back to the examples from the puzzle description:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".........1323\n",
      "32154535.5623\n",
      "32552456.4254\n",
      "34465858.5452\n",
      "45466578.....\n",
      "143859879845.\n",
      "445787698776.\n",
      "363787797965.\n",
      "465496798688.\n",
      "456467998645.\n",
      "122468686556.\n",
      "254654888773.\n",
      "432267465553.\n"
     ]
    }
   ],
   "source": [
    "example1 = Grid(parse('''\\\n",
    "2413432311323\n",
    "3215453535623\n",
    "3255245654254\n",
    "3446585845452\n",
    "4546657867536\n",
    "1438598798454\n",
    "4457876987766\n",
    "3637877979653\n",
    "4654967986887\n",
    "4564679986453\n",
    "1224686865563\n",
    "2546548887735\n",
    "4322674655533''', digits))\n",
    "\n",
    "example2 = Grid(parse('''\\\n",
    "111111111111\n",
    "999999999991\n",
    "999999999991\n",
    "999999999991\n",
    "999999999991''', digits))\n",
    "\n",
    "def show_path(grid, ch='.', klass=UltraHeatLossProblem) -> int:\n",
    "    \"\"\"Show the path to the goal on the grid, and return the path cost.\"\"\"\n",
    "    node = heat_loss_search(grid, klass)\n",
    "    copy = grid.copy()\n",
    "    copy.update({state.pos: ch for state in path_states(node)})\n",
    "    copy.print()\n",
    "    return node.path_cost\n",
    "    \n",
    "assert show_path(example1) == 94"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "........1111\n",
      "9999999.9991\n",
      "9999999.9991\n",
      "9999999.9991\n",
      "9999999.....\n"
     ]
    }
   ],
   "source": [
    "assert show_path(example2) == 71"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Those both look exactly right, and yet I get the wrong answer on the real input. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 17.2: 11.2230 seconds, answer 1030            WRONG; expected answer is unknown"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(17.2, unknown, lambda: heat_loss_search(heat_loss, UltraHeatLossProblem).path_cost)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 18](https://adventofcode.com/2023/day/18): \n",
    "\n",
    "The elves have a **dig plan** to dig a lagoon to hold lava. Each line of the plan contains a direction (U/D/L/R for Up/Down/Left/Right), a number, and a hexadecimal color code. I'll parse that into a three-tuple:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 604 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "R 11 (#00b1d2)\n",
      "U 10 (#0afb33)\n",
      "R 2 (#10afc2)\n",
      "U 12 (#2f8191)\n",
      "R 9 (#2fa802)\n",
      "D 2 (#413001)\n",
      "R 10 (#6b5602)\n",
      "D 4 (#14b421)\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 604 tuples:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "('R', 11, '00b1d2')\n",
      "('U', 10, '0afb33')\n",
      "('R', 2, '10afc2')\n",
      "('U', 12, '2f8191')\n",
      "('R', 9, '2fa802')\n",
      "('D', 2, '413001')\n",
      "('R', 10, '6b5602')\n",
      "('D', 4, '14b421')\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "def parse_dig_instruction(line: str) -> Tuple[str, int, str]:\n",
    "    \"\"\"Parse an instruction in the dig plan.\"\"\"\n",
    "    dir, n, color = line.split()\n",
    "    return dir, int(n), color[2:-1] # skip the \"(#\" and \")\" from the color\n",
    "\n",
    "dig_plan = parse(18, parse_dig_instruction)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: If the elves follow their dig plan, how many cubic meters of lava could it hold?\n",
    "\n",
    "The plan has the elves digging a **trench loop**–a winding path of holes in the ground that eventually doubles back to the start. The puzzle is asking what the area will be if the elves then excavate all the area within the boundaries of the trench.\n",
    "\n",
    "My function **dig** will follow a dig plan by starting with a Grid that contains the digger in a hole in the ground; we'll arbitrarily call that position (0, 0). Then we follow instructions one at a time, adding holes to the grid as we go. Finally, call `flood_fill`, which maintains a queue of positions inside the trench loop, and floods from each position to all its neighbors, stopping when it reaches a previously-dug position."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dig(dig_plan) -> Grid:\n",
    "    \"\"\"Execute all the steps in dig_plan and return a grid of holes.\"\"\"\n",
    "    pos = (0, 0)\n",
    "    grid = Grid({pos: '#'}, default='.')\n",
    "    for dir, n, color in dig_plan:\n",
    "        for _ in range(n):\n",
    "            pos = add(pos, arrow_direction[dir])\n",
    "            grid[pos] = '#'\n",
    "    return grid\n",
    "            \n",
    "def flood_fill(grid: Grid, start=(1, 1)) -> Grid:\n",
    "    \"\"\"Dig holes in all the positions reachable from the start position.\"\"\"\n",
    "    queue = [start]\n",
    "    while queue:\n",
    "        pos = queue.pop()\n",
    "        if pos not in grid:\n",
    "            grid[pos] = '#'\n",
    "            queue.extend(grid.neighbors(pos))\n",
    "    return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 18.1:   .1602 seconds, answer 61865           ok"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(18.1, 61865, lambda: len(flood_fill(dig(dig_plan))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: 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?\n",
    "\n",
    "The first five hex digits are to be converted to a distance; this means there will be hundreds of billions of holes. So we can't use the code from Part 1. A better approach would be to intersect rectangles: if I have the instructions `R 461937; D 56407` that means I've formed two sides of a 461937 × 56407 rectangle; I need to compute where the other two sides end up, and whether this is on the inside or outside of the trench loop. Then when other rectangles are added, intersect them to add and subtract holes from the total.  I think I could make this work, but it is tricky; I'll pass for now and hope to come back."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 18.2:   .0000 seconds, answer unknown        "
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(18.2, unknown)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 19](https://adventofcode.com/2023/day/19): Aplenty\n",
    "\n",
    "**Today's input** describes a workflow to sort a \"relentless avalanche of machine parts\" into accept and reject piles. The first paragraph of the input describes the rules of the workflow. For example,\n",
    "\n",
    "     px{a<2006:qkq,m>2090:A,rfg}\n",
    "\n",
    "is a workflow named \"px\" that consists of three rules, to be taken in order: first, if a part has an \"a\" rating less than 2006, then workflow \"qkq\" should be used; otherwise if the part has an \"m\" rating greater than 2900, then the part should be accepted; otherwise workflow \"rfg\" applies.  After the rules, the second paragraph of the input lists parts with their ratings on the four attributes (which they call categories). I'll parse the first paragraph into a dict of `{name: (Rule, ...)}` and the second paragraph into a tuple of `Rating`s. (The input format strictly lists the attribute values in the order `x, m, a, s`, so I can just extract the `ints` from each line and feed them into a `Rating` object.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 724 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "gl{x<3407:mnr,pb}\n",
      "msm{x>3867:A,R}\n",
      "qcn{s>1407:A,s>1324:R,x>3615:R,R}\n",
      "bp{s<304:R,x<3585:fr,bhm}\n",
      "tdq{x<2920:R,xk}\n",
      "qfh{s<3501:bxd,zbz}\n",
      "pd{x>3157:qlc,m>2947:cx,m<2822:hph,ffk}\n",
      "pj{m>3577:A,R}\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 1 dict, 1 tuple:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "{'gl': (Rule(category='x', op='<', amount=3407, result='mnr'), 'pb'), 'msm': (Rule(category='x', ...\n",
      "(Rating(x=590, m=690, a=867, s=1366), Rating(x=1880, m=905, a=1184, s=14), Rating(x=1820, m=1050 ...\n"
     ]
    }
   ],
   "source": [
    "Rule   = namedtuple('Rule', 'category, op, amount, result')\n",
    "Rating = namedtuple('Rating', 'x, m, a, s')\n",
    "\n",
    "def parse_ratings_or_workflow(paragraph: str) -> Union[Dict[str, Tuple[Rule]], Tuple[Rating]]:\n",
    "    \"\"\"There are two different paragraphs in today's input.\n",
    "    The first is parsed into a {name: (Rule, ...)]} dic.\n",
    "    The second is parsed into a tuple of Ratings.\"\"\"\n",
    "    if not paragraph.startswith('{'):\n",
    "        return {name: mapt(parse_rule, rules.split(','))\n",
    "                for name, rules in re.findall('([a-z]+)[{](.+)[}]', paragraph)}\n",
    "    else:\n",
    "        return parse(paragraph, lambda line: Rating(*ints(line)))\n",
    "\n",
    "def parse_rule(rule: str) -> Union[Rule, str]: \n",
    "    \"\"\"Parse a rule of the form 'x<123:name', or just 'name'.\"\"\"\n",
    "    if ':' in rule:\n",
    "        lhs, rhs = rule.split(':')\n",
    "        return Rule(lhs[0], lhs[1], int(lhs[2:]), rhs)\n",
    "    else:\n",
    "        return rule\n",
    " \n",
    "workflows, ratings = parse(19, parse_ratings_or_workflow, paragraphs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: What do you get if you add together all of the rating numbers for all of the parts that ultimately get accepted?\n",
    "\n",
    "The puzzle description says to start with the workflow name `in` and go from there until a part is accepted or rejected. I do that for all the parts, then sum up the ratings of the accepted ones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_accepted(rating, workflows, name='in') -> bool:\n",
    "    \"\"\"Is this rating accepted by the workflows, starting with this workflow name?\"\"\"\n",
    "    if name == 'A':\n",
    "        return True\n",
    "    elif name == 'R':\n",
    "        return False\n",
    "    else:\n",
    "        for rule in workflows[name]:\n",
    "            if isinstance(rule, str):\n",
    "                return is_accepted(rating, workflows, rule)\n",
    "            else:\n",
    "                compare = (operator.gt if rule.op == '>' else operator.lt)\n",
    "                if compare(getattr(rating, rule.category), rule.amount):\n",
    "                    return is_accepted(rating, workflows, rule.result)\n",
    "    raise ValueError('One of the rules must result in a name.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 19.1:   .0007 seconds, answer 532551          ok"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(19.1, 532551, \n",
    "       lambda: sum(sum(r) for r in ratings if is_accepted(r, workflows)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had a **bug** where I was asking for `sum(r for ...)` when it should be `sum(sum(r) for ...)`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: How many distinct combinations of ratings will be accepted by the Elves' workflows?\n",
    "\n",
    "In Part 2, the Elves want to consider all combinations of (x, m, a, s) values from 1 to 4000 and precompute how many of them are acceptable. That's 256 trillion combinations–too many to exhaustively enumerate. Instead, I'll deal with multiple ratings at once. Each `Rating` object will have attribute values that are **ranges**, not integers. I'll start with a rating that represents every possible combination: it has `range(1, 4001)` for all 4 values. My function `count_accepted` will take a combination-rating as input, along with the workflows and a \"name\", which can be either 'A' or 'R' or a workflow name. The function returns the number of combinations for 'A', zero for 'R', and for a workflow name it goes through the sequence of rules for that name, counting up the number of combinations that pass each test, and continuing on to the next rule with the combinations that fail the test. At the end it returns the total number of accepted combinations.  The function `split_rating` is used to get the passed and failed combinations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_accepted(rating, workflows, name='in') -> int:\n",
    "    \"\"\"How many combinations in `rating` are accepted by this workflow, starting with this thing?\n",
    "    A `thing` can be 'A' or 'R' or a rule name, or a sequence of rules.\"\"\"\n",
    "    if name == 'A':            # accept all combinations\n",
    "        return prod(map(len, rating)) # Combinations = product of ranges\n",
    "    elif name == 'R':          # reject all combinations\n",
    "        return 0    \n",
    "    else: \n",
    "        accepted = 0\n",
    "        for rule in workflows[name]:\n",
    "            if isinstance(rule, str): # Applies to all possible combinations in `ratings`\n",
    "                accepted += count_accepted(rating, workflows, rule)\n",
    "            else: # Need to split `rating` into combinations that pass andd fail the test\n",
    "                passed, rating = split_rating(rating, rule)\n",
    "                accepted += count_accepted(passed, workflows, rule.result) \n",
    "        return accepted\n",
    "\n",
    "def split_rating(rating, rule) -> Tuple[Rating, Rating]:\n",
    "    \"\"\"Use the rule's test to split ratings into two: (passed_rating, failed_rating).\n",
    "    Do this by replacing the `category` attribute of `rating` with a new range, two ways.\"\"\"\n",
    "    category, op, amount, _ = rule\n",
    "    def new_rating(start, stop): \n",
    "        new_range = range_intersection(getattr(rating, category), range(start, stop))\n",
    "        return rating._replace(**{category: new_range})\n",
    "    if rule.op == '<':\n",
    "        return new_rating(1, amount), new_rating(amount, rating_stop)\n",
    "    else:\n",
    "        return new_rating(amount + 1, rating_stop), new_rating(1, amount + 1)\n",
    "\n",
    "# Constants\n",
    "rating_stop = 4001\n",
    "all_ratings = Rating(*4*[range(1, rating_stop)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 19.2:   .0045 seconds, answer 134343280273968 ok"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(19.2, 134343280273968, lambda: count_accepted(all_ratings, workflows))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 20](https://adventofcode.com/2023/day/20): Pulse Propagation\n",
    "\n",
    "**Today's input** is a **module configuration** file where each line describes a **module** in a communication network. I'll parse each line into a tuple of the first character (which tells the type of the module), followed by the atoms in the line. Later we'll rearrange these atoms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 58 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "%cg -> fb, rc\n",
      "%jz -> lf\n",
      "%gf -> ld\n",
      "%gz -> mz, gv\n",
      "%qd -> ll, mr\n",
      "%pd -> sq, ll\n",
      "%lf -> mg\n",
      "&mk -> kl\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 58 tuples:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "('%', 'cg', 'fb', 'rc')\n",
      "('%', 'jz', 'lf')\n",
      "('%', 'gf', 'ld')\n",
      "('%', 'gz', 'mz', 'gv')\n",
      "('%', 'qd', 'll', 'mr')\n",
      "('%', 'pd', 'sq', 'll')\n",
      "('%', 'lf', 'mg')\n",
      "('&', 'mk', 'kl')\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "configuration = parse(20, lambda line: (line[0], *atoms(line)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Determine the number of low pulses and high pulses that would be sent after pushing the button 1000 times, waiting for all pulses to be fully handled after each push of the button. What do you get if you multiply the total number of low pulses sent by the total number of high pulses sent?\n",
    "\n",
    "Read the puzzle description to get the complicated rules for how pulses propagate through the network of modules. One important point: the `Module` object is mutable–it contains state that changes when pulses come in. A module of type `%` has an on-or-off state that flips when it gets a low pulse; a `&` module remembers the last pulse from each of its inputs, and sends a low pulse only when all the inputs have most recently sent high pulses. My `push_button` function does the real work (much of it by calling `process_pulse`); the function yields each pulse. In Part 1 all we do is ocunt the low and high pulses, but in Part 2 we might need to do something else with them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 20.1:   .0865 seconds, answer 980457412       ok"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LO, HI  = -1,  1\n",
    "ON, OFF =  1, -1\n",
    "\n",
    "# Types\n",
    "Signal = Literal[LO, HI]\n",
    "Switch = Literal[ON, OFF]\n",
    "Name   = str\n",
    "Pulse  = namedtuple('Pulse', 'src, signal, dest')\n",
    "\n",
    "@dataclass\n",
    "class Module:\n",
    "    type: str\n",
    "    name: str\n",
    "    dest: Sequence[str]\n",
    "    state: Union[int, None, Dict[Name, Signal]]\n",
    "\n",
    "def push_button(modules: Dict[Name, Module], n=1) -> Iterable[Pulse]: \n",
    "    \"\"\"Push the button n times, yielding all the pulses that get processed.\"\"\"\n",
    "    pulses = deque()\n",
    "    for _ in range(n):\n",
    "        pulses.append(Pulse('button', LO, 'broadcaster'))\n",
    "        while pulses:\n",
    "            pulse = pulses.popleft()\n",
    "            yield pulse\n",
    "            pulses.extend(process_pulse(pulse, modules))\n",
    "\n",
    "def make_modules(configuration: Tuple[List[str]]) -> Dict[Name, Module]:\n",
    "    \"\"\"Use the configuration description to build a dict of modules.\"\"\"\n",
    "    return initialize_modules(\n",
    "            {name: Module(type, name, dest, None)\n",
    "             for (type, name, *dest) in configuration})\n",
    "                      \n",
    "def initialize_modules(modules: Dict[Name, Module]):\n",
    "    \"\"\"Every module's state is set to OFF/LO.\"\"\"\n",
    "    for (name, m) in modules.items():\n",
    "        if m.type == '%':\n",
    "            m.state = OFF\n",
    "        elif m.type == '&':\n",
    "            m.state = {m0: LO for m0 in modules if name in modules[m0].dest}\n",
    "    return modules\n",
    "\n",
    "def process_pulse(pulse: Pulse, modules) -> List[Pulse]:\n",
    "    \"\"\"Process a pulse: perhaps mutate the destination module's state and/or send more pulses.\n",
    "    Any pulses to be sent are returned as a list.\"\"\"\n",
    "    m: Module = modules.get(pulse.dest)\n",
    "    if pulse.dest not in modules:\n",
    "        return []\n",
    "    elif m.type == '%':\n",
    "        if pulse.signal == LO:\n",
    "            m.state *= -1\n",
    "            return [Pulse(m.name, m.state, dest) for dest in m.dest]\n",
    "        else:\n",
    "            return []\n",
    "    elif m.type == '&':\n",
    "        m.state[pulse.src] = pulse.signal\n",
    "        output = LO if set(m.state.values()) == {HI} else HI\n",
    "        return [Pulse(m.name, output, dest) for dest in m.dest]\n",
    "    elif m.type == 'b':\n",
    "        return [Pulse(m.name, pulse.signal, dest) for dest in m.dest]\n",
    "    else:\n",
    "        return []\n",
    "\n",
    "def pulse_product(configuration) -> int:\n",
    "    pulses = push_button(make_modules(configuration), 1000)\n",
    "    counts = Counter(pulse.signal for pulse in pulses)\n",
    "    return counts[LO] * counts[HI]\n",
    "                    \n",
    "answer(20.1, 980457412, lambda: pulse_product(configuration))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had a number of small **bugs** before I got this to work: I didn't realize that a destination module might not be defined in the configuration file; I started to define a pulse with just a signal and destination, without the source; I had two separate typos where I confused module and pulse, asking for the wrong field from the wrong one.\n",
    "\n",
    "### Part 2: Waiting for all pulses to be fully handled after each button press, what is the fewest number of button presses required to deliver a single low pulse to the module named rx?\n",
    "\n",
    "Now we're asked to look for a time when we get a single low pulse from the `rx` module. I ran the code for a long time and didn't get an answer. I suspect this is another one of those find-least-common-multiple-of-several-large-integer problems. I may come back to this Part, but this is not my favorite type of puzzle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 6.77 s, sys: 21.9 ms, total: 6.8 s\n",
      "Wall time: 6.89 s\n"
     ]
    }
   ],
   "source": [
    "def rx_pulses(configuration, N=100_000) -> int:\n",
    "    modules = make_modules(configuration)\n",
    "    for press in range(1, N):\n",
    "        if quantify(pulse.signal == LO and pulse.dest == 'rx' for pulse in push_button(modules)):\n",
    "            return press\n",
    "\n",
    "%time rx_pulses(configuration)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 20.2:   .0000 seconds, answer unknown        "
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(20.2, unknown)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 21](https://adventofcode.com/2023/day/21): Step Counter\n",
    "\n",
    "**Today's input** is yet another 2D map of a garden, showing the starting position (`S`), garden plots (`.`), and rocks (`#`). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 131 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "................................................................................................ ...\n",
      "....##.#...##..#.......................#.#...###............#..........##..............#.......# ...\n",
      ".#...##.................#.......#....#.#....##..#....##...#...................#...#.......#..... ...\n",
      "........#.#..#..###.......#.......#......#.............####.............#.................#.##.. ...\n",
      "..............#......#..#.................#.##......#..#..................#..#..#..##...#...#..# ...\n",
      ".#..#..#.#.........#....#.....#.........##........#.............................#....#.......#.. ...\n",
      ".......##......#....................#.#.....#.........#......................#.....#.#......#... ...\n",
      "...#.....##..#..#.###....#.........#..#...#....##.#.............#.#.#.........#.#............... ...\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "garden = Grid(parse(21))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Starting from the garden plot marked S on your map, how many garden plots could the Elf reach in exactly 64 steps?\n",
    "\n",
    "The elf can move in any of the four orthogonal directions, but not on to rocks. It is easy to keep track of the set of all possible positions and update that set for each of the 64 steps:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [],
   "source": [
    "def steps(garden: Grid, n=64) -> Set[Point]:\n",
    "    \"\"\"The positions that can be reached in exactly `n` steps.\"\"\"\n",
    "    rocks = set(garden.findall('#'))\n",
    "    result: Set[Point] = set(garden.findall('S'))\n",
    "    for step in range(n):\n",
    "        result = union(map(garden.neighbors, result)) - rocks\n",
    "    return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 21.1:   .1627 seconds, answer 3637            ok"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(21.1, 3637, lambda: len(steps(garden, 64)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: Starting from the garden plot marked S on your infinite map, how many garden plots could the Elf reach in exactly 26501365 steps?\n",
    "\n",
    "In Part 2 the number of steps has increased from 64 to 26 million, and the map has increased to infinite size (repetitive tiling of the original map). It is not feasible to run for that number of steps, so what I need to do is:\n",
    "1) (Note that the reachable tiles are partitioned into those reachable in an even number of steps and in an odd number of steps.\n",
    "2) Determine how many tiles on the single copy of the map are reachable in an even/odd number of steps.\n",
    "3) Determine how many time steps it takes to explore the whole single copy.\n",
    "4) Do division (with remainder) to determine the total number of copies that will be completely filled.\n",
    "5) Look at the remainder and deal with the copies on the perimeter that will be partially filled.\n",
    "\n",
    "All in all, it seems tedious, and I'm behind schedule by a few days, so I'll skip it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 21.2:   .0000 seconds, answer unknown        "
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(21.2, unknown)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 22](https://adventofcode.com/2023/day/21): Sand Slabs\n",
    "\n",
    "**Today's input** gives the coordinates of rectangular bricks of compacted sand that are falling towards the ground. Each input line gives the starting x,y,z coordinates followed by the ending x,y,z coordinates of a brick (we'll denote the ending positions by capital letters in the `Brick` class):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 1273 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "2,4,151~4,4,151\n",
      "5,4,169~5,7,169\n",
      "3,5,167~3,7,167\n",
      "4,6,197~4,8,197\n",
      "6,5,98~6,7,98\n",
      "3,8,7~5,8,7\n",
      "8,2,293~8,5,293\n",
      "2,1,76~2,4,76\n",
      "...\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Parsed representation ➜ 1273 Bricks:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Brick(x=2, y=4, z=151, X=4, Y=4, Z=151)\n",
      "Brick(x=5, y=4, z=169, X=5, Y=7, Z=169)\n",
      "Brick(x=3, y=5, z=167, X=3, Y=7, Z=167)\n",
      "Brick(x=4, y=6, z=197, X=4, Y=8, Z=197)\n",
      "Brick(x=6, y=5, z=98, X=6, Y=7, Z=98)\n",
      "Brick(x=3, y=8, z=7, X=5, Y=8, Z=7)\n",
      "Brick(x=8, y=2, z=293, X=8, Y=5, Z=293)\n",
      "Brick(x=2, y=1, z=76, X=2, Y=4, Z=76)\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "Brick = namedtuple('Brick', 'x, y, z, X, Y, Z')\n",
    "\n",
    "bricks = parse(22, lambda line: Brick(*ints(line)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Figure how the blocks will settle. How many bricks could be safely chosen as the one to get disintegrated?\n",
    "\n",
    "The puzzle is asking us to:\n",
    "1) Have all the bricks fall downward  until they settle into a stack: each brick is stopped by either the floor below (which is at height 0) or by another brick. (To make this work, I'll drop the bricks in sorted order, lowest bottom first.)\n",
    "2) Once they have settled, determine which bricks in the stack are supported by which other ones.\n",
    "3) Count how many bricks could be removed, Jenga style, without causing any other brick to fall. A brick can be removed if it is not the only brick supporting some other brick. So I will keep track of a dict of `{top_brick: [bricks_supporting_it_directly_below,...]}`.\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [],
   "source": [
    "def removable(bricks) -> Set[Brick]:\n",
    "    \"\"\"Have all the bricks settle into a stack, then return\n",
    "    the ones that can be disintegrated (they are not the sole support of any brick).\"\"\"\n",
    "    stack = settle(bricks)\n",
    "    support = supported_by(stack)\n",
    "    unsafe = {bot for top in support for bot in support[top] if len(support[top]) == 1}\n",
    "    return stack - unsafe\n",
    "\n",
    "def settle(bricks: Collection[Brick]) -> Set[Brick]:\n",
    "    \"\"\"Make all the bricks fall as far as they will go.\"\"\"\n",
    "    heights = defaultdict(int) # heights[x, y] is the tallest occupied z point above (x, y)\n",
    "    return {drop(brick, heights) for brick in sorted(bricks, key=lambda s: s.z)}\n",
    "\n",
    "def drop(brick, heights) -> Brick:\n",
    "    \"\"\"Drop brick as far down as it can go before it hits the floor or some brick below it.\n",
    "    Mutate `heights` to account for this brick. Return the brick in its new position.\"\"\"\n",
    "    h = max(heights[p] for p in bottom(brick)) # Highest height below brick\n",
    "    for p in bottom(brick):\n",
    "        heights[p] = h + 1 + brick.Z - brick.z\n",
    "    return brick._replace(z=h + 1, Z=h + 1 + brick.Z - brick.z)\n",
    "\n",
    "@cache\n",
    "def bottom(brick) -> Set[Point]:\n",
    "    \"\"\"The set of bottom (x, y) points in a brick.\"\"\"\n",
    "    return {(x, y) for x in range(brick.x, brick.X + 1) for y in range(brick.y, brick.Y + 1)}\n",
    "    \n",
    "def supported_by(stack: Collection[Brick]) -> Dict[Brick, List[Brick]]:\n",
    "    \"\"\"A dict of {top_brick: [bricks_supporting_it_directly_below,...]}.\"\"\"\n",
    "    support = defaultdict(list)\n",
    "    for bot, top in combinations(sorted(stack, key=lambda b: b.z), 2):\n",
    "        if bot.Z + 1 == top.z and not bottom(bot).isdisjoint(bottom(top)):\n",
    "            support[top].append(bot)\n",
    "    return support"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 22.1:   .0560 seconds, answer 439             ok"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(22.1, 439, lambda: len(removable(bricks)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had a **bug** with an off-by-one error in `drop`, and one place where I wrote `bricks` where I meant `stack`.\n",
    "\n",
    "\n",
    "### Part 2: For each brick, determine how many other bricks would fall if that brick were disintegrated. What is the sum of the number of other bricks that would fall?\n",
    "\n",
    "I could analyze the `supported_by` dict and recursively determine which bricks would fall. That would probably run in under a second, but would require a lot of new code to debug. Instead I'll define `settle_count` to be a slight variation of `settle` that, instead of returning the settled bricks, just returns the count of how many moved from their original position. Then I define `count_falls` to settle the bricks once, then one at a time remove a brick and call `settle_counts` to see how many other bricks move (and then put the removed brick back and move on to the next brick). This takes 3 or 4 seconds to run, but reuses more code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 22.2:  3.5921 seconds, answer 43056           ok"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def settle_count(bricks: Collection[Brick]) -> int:\n",
    "    \"\"\"Count how many bricks move as the bricks settles.\"\"\"\n",
    "    heights = defaultdict(int) # heights[x, y] is the tallest occupied z point above (x, y)\n",
    "    return quantify(drop(brick, heights) != brick \n",
    "                    for brick in sorted(bricks, key=lambda s: s.z))\n",
    "    \n",
    "def count_falls(bricks) -> int:\n",
    "    \"\"\"The sum of the number of bricks that fall when briacks are removed (and replaced) one at a time.\"\"\"\n",
    "    stack = settle(bricks)\n",
    "    result = 0\n",
    "    for brick in stack:\n",
    "        stack.remove(brick)\n",
    "        result += settle_count(stack)\n",
    "        stack.add(brick)\n",
    "    return result\n",
    "    \n",
    "answer(22.2, 43056, lambda: count_falls(bricks))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 23](https://adventofcode.com/2023/day/23): A Long Walk\n",
    "\n",
    "**Today's input** is yet another 2D map of paths (`.`), forest (`#`), and steep icy slopes (`^`, `>`, `v`, and `<`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "Puzzle input ➜ 141 strs:\n",
      "────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "#.############################################################################################## ...\n",
      "#.#...###...#...#...#...#.....###.....#...###...#...#...#.....#...#.......#...#...........#..... ...\n",
      "#.#.#.###.#.#.#.#.#.#.#.#.###.###.###.#.#.###.#.#.#.#.#.#.###.#.#.#.#####.#.#.#.#########.#.#### ...\n",
      "#...#.#...#.#.#.#.#.#.#.#...#.###.#...#.#...#.#.#.#.#.#.#...#.#.#.#.#.....#.#.#.......#...#.#... ...\n",
      "#####.#.###.#.#.#.#.#.#.###.#.###.#.###.###.#.#.#.#.#.#.###.#.#.#.#.#.#####.#.#######.#.###.#.## ...\n",
      "#.....#...#.#.#...#.#.#...#.#.>.>.#...#.#...#.#...#.#.#.#...#.#.#...#...###.#.#...#...#.....#... ...\n",
      "#.#######.#.#.#####.#.###.#.###v#####.#.#.###.#####.#.#.#.###.#.#######.###.#.#.#.#.###########. ...\n",
      "#.#...#...#.#.....#.#.#...#.#...#...#...#...#.#...#.#.#...#...#.......#...#.#...#.#.....#....... ...\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "maze = Grid(parse(23))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1: Find the longest hike you can take through the hiking trails listed on your map. How many steps long is the longest hike?\n",
    "\n",
    "The rules are that you can never step onto the same tile twice, and you can hike on paths (`.`) and go from there to any adjacent non-forest position, but if you step on a slope you must continue in the slope's direction.\n",
    "\n",
    "I'll define `longest-hike` to hike through the maze, returning the longest path from start to end. Note:\n",
    "- Usually we're looking for the [shortest path](https://en.wikipedia.org/wiki/Shortest_path_problem) and we can just drop longer paths; not so here.\n",
    "- To avoid infinite loops, I need to keep track of the previously-seen positions along the path, and not repeat a position.\n",
    "- For efficiency, I only want to maintain a single set of previously-seen positions, not multiple ones.\n",
    "- That suggests a depth-first recursive search, where I add a position to the set of `seen` positions before the recursive calls, and remove it after. I'll implement depth-first search with a local function, `dfs`, inside `longest_hike`.\n",
    "- We search from the first  `'.'` position in the maze to the last (reading top-to-bottom, left-to-right).\n",
    "- Sometimes there are multiple paths from start to end, and the `max` in `dfs` will pick the longest one. But sometimes there is no path. I could have `dfs` return `None` in that case, but that would complicate the logic. So I'll just have it return negative infinity. (Note I imported `math.inf`.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [],
   "source": [
    "def longest_hike(maze: Grid) -> int:\n",
    "    \"\"\"The length of the longest hike through the maze, or `-inf` if no path.\n",
    "    Do depth-first search, avoiding previously-seen positions, find longest path length.\"\"\"\n",
    "    start = first(maze.findall('.'))\n",
    "    end   = last(maze.findall('.')) \n",
    "    seen  = set()\n",
    "    def dfs(p: Point) -> int:\n",
    "        \"\"\"Depth-first search from position `p` to `end`, not repeating `seen`.\"\"\"\n",
    "        if p == end:\n",
    "            return 0\n",
    "        else:\n",
    "            seen.add(p)\n",
    "            longest = max([dfs(p2) + 1 for p2 in maze_moves(maze, p) - seen], \n",
    "                          default=-inf)\n",
    "            seen.remove(p)\n",
    "            return longest\n",
    "    return dfs(start)\n",
    "\n",
    "def maze_moves(maze: Grid, p: Point) -> Set[Point]:\n",
    "    \"\"\"The legal moves from a point on the grid.\n",
    "    Just downhill if on an arrow; otherwise to any neighboring non-barrier position.\"\"\"\n",
    "    ch = maze[p]\n",
    "    if ch in '^v><': # Must go downhill in arrow's direction\n",
    "        return {add(p, arrow_direction[ch])}\n",
    "    else:            # Can go any direction that is not into a barrier\n",
    "        return {p2 for p2 in maze.neighbors(p) if maze[p2] != '#'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Theoretically, that should do it, but practically, I'll increase Python's recursion limit first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 23.1:   .6492 seconds, answer 2030            ok"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sys.setrecursionlimit(10_000)\n",
    "\n",
    "answer(23.1, 2030, lambda: longest_hike(maze))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had a **bug** where I initially wrote `if ch in arrow_directions` in `maze_moves`, but I forgot that my dict `arrow_directions` from [AdventUtils](AdventUtils.ipynb) contains `'.'` as an \"arrow\" with direction zero, so that didn't work. Another **bug** was that initially I hadn't thought about the possibility that there could be no legal moves from some position; I added the `default=-inf` after `max` complained about getting an empty sequence.\n",
    "\n",
    "### Part 2: Find the longest hike you can take through the surprisingly dry hiking trails listed on your map. How many steps long is the longest hike?\n",
    "\n",
    "For Part 2 the icy slopes are surprisingly dry, and you can  move in any direction through them. That seemingly should add  to the length of the longest path, because there are more choices, but should it add very much? Unfortunately yes. From a quick glance at the original maze (always look at your data), I noticed that the arrow characters tend to flow downhill to the east and south:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'#': 10533, '.': 9230, '>': 58, 'v': 60})"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Counter(maze.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "My quick glance was on to something–the icy slopes flow downhill *exclusively* to the east and south, funneling paths in that direction. So replacing the icy slopes with open positions will mean a *lot* more possibilities for paths that double back to the north and west.\n",
    "\n",
    "Still, I can try pushing forward. I'll define `surprisingly_dry` to replace the icy slopes with regular path characters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [],
   "source": [
    "def surprisingly_dry(maze: Grid) -> Grid:\n",
    "    \"\"\"Replace the arrows in maze with `.` characters.\"\"\"\n",
    "    copy = maze.copy()\n",
    "    for p in maze.findall('<>^v'):\n",
    "        copy[p] = '.'\n",
    "    return copy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I can show that my code works on the example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [],
   "source": [
    "example_maze = Grid(parse(\"\"\"\\\n",
    "#.#####################\n",
    "#.......#########...###\n",
    "#######.#########.#.###\n",
    "###.....#.>.>.###.#.###\n",
    "###v#####.#v#.###.#.###\n",
    "###.>...#.#.#.....#...#\n",
    "###v###.#.#.#########.#\n",
    "###...#.#.#.......#...#\n",
    "#####.#.#.#######.#.###\n",
    "#.....#.#.#.......#...#\n",
    "#.#####.#.#.#########v#\n",
    "#.#...#...#...###...>.#\n",
    "#.#.#v#######v###.###v#\n",
    "#...#.>.#...>.>.#.###.#\n",
    "#####v#.#.###v#.#.###.#\n",
    "#.....#...#...#.#.#...#\n",
    "#.#########.###.#.#.###\n",
    "#...###...#...#...#.###\n",
    "###.###.#.###v#####v###\n",
    "#...#...#.#.>.>.#.>.###\n",
    "#.###.###.#.###.#.#v###\n",
    "#.....###...###...#...#\n",
    "#####################.#\"\"\"))\n",
    "\n",
    "assert longest_hike(example_maze) == 94\n",
    "assert longest_hike(surprisingly_dry(example_maze)) == 154"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But running `longest_hike` on `surprisingly_dry(maze)` did not terminate after two or three minutes of run time. That's too long! I've got to change something!\n",
    "\n",
    "My quick glance also noticed that the maze seems to have a lot of long corridors where you only have one choice of where to move next. Let's count how many moves are available from each position of the surprisingly dry maze:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({1: 2, 2: 9312, 3: 18, 4: 16})"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dry = surprisingly_dry(maze)\n",
    "\n",
    "Counter(len(maze_moves(dry, p)) for p in dry.findall('.'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Wow!** I didn't expect that! This is telling me that:\n",
    "- There are two positions (the start and end) that have only one neighbor to move to.\n",
    "- There are 9312 positions that have two neighbors. In other words, they are in a corridor, and if you entered from one side, the only choice for where to go next is to exit the other side.\n",
    "- There are only 18 + 16 = 34 positions where there is an actual choice of where to go next (3-way or 4-way intersections).\n",
    "- I should be able to reduce the whole problem to a graph with just 36 vertexes (the start, end, and 34 branch points).\n",
    "- My quick glance spotted some long horizontal and vertical corridors, but a closer look reveals that there are also long twisting corridors.\n",
    "\n",
    "Now I need to convert a maze into a graph of vertexes, with different costs between them. I'll use my `Graph` class from `AdventUtils`, and add a `cost` attribute: a dict where `graph.cost[p, q]` is the cost of getting from point `p` to point `q`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maze_to_graph(maze: Grid) -> Graph:\n",
    "    \"\"\"Convert a maze to a graph, using only the points that have choices.\"\"\"\n",
    "    choice_points = {p for p in maze.findall('.') if len(maze_moves(maze, p)) != 2}\n",
    "    graph = Graph({p: set() for p in choice_points}, cost=defaultdict(int))\n",
    "    for p in choice_points:\n",
    "        for neighbor in maze_moves(maze, p):\n",
    "            cost, q = follow_corridor(maze, p, neighbor)\n",
    "            if q not in choice_points:\n",
    "                print('path', p, q, 'cost', cost, 'invalid')\n",
    "            graph[p].add(q)\n",
    "            graph.cost[p, q] = cost\n",
    "    return graph\n",
    "\n",
    "def follow_corridor(maze, prev: Point, neighbor: Point, cost_so_far=1) -> Tuple[int, Point]:\n",
    "    \"\"\"Follow along a corridor as long as there are no choices.\n",
    "    Return the cost to get to the last point in the corridor, and the point.\"\"\"\n",
    "    options = [q for q in maze_moves(maze, neighbor) if q != prev]\n",
    "    if len(options) == 1:\n",
    "        return follow_corridor(maze, neighbor, the(options), cost_so_far + 1)\n",
    "    else:\n",
    "        return cost_so_far, neighbor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see that the graph has only 36 vertexes, and each one has 3 or 4 choices (except for start and end):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(31, 5): {(11, 9), (39, 35), (53, 13)},\n",
       " (81, 85): {(61, 89), (75, 105), (87, 63), (111, 89)},\n",
       " (123, 33): {(107, 11), (107, 37), (135, 59)},\n",
       " (135, 59): {(109, 55), (123, 33), (123, 89)},\n",
       " (109, 135): {(77, 137), (113, 107), (137, 131)},\n",
       " (33, 63): {(7, 61), (37, 77), (39, 35), (59, 59)},\n",
       " (75, 11): {(53, 13), (85, 41), (107, 11)},\n",
       " (111, 89): {(81, 85), (109, 55), (113, 107), (123, 89)},\n",
       " (1, 0): {(11, 9)},\n",
       " (109, 55): {(87, 63), (107, 37), (111, 89), (135, 59)},\n",
       " (53, 13): {(31, 5), (53, 31), (75, 11)},\n",
       " (75, 105): {(53, 107), (77, 137), (81, 85), (113, 107)},\n",
       " (39, 35): {(19, 37), (31, 5), (33, 63), (53, 31)},\n",
       " (113, 107): {(75, 105), (109, 135), (111, 89), (129, 99)},\n",
       " (53, 31): {(39, 35), (53, 13), (59, 59), (85, 41)},\n",
       " (107, 11): {(75, 11), (107, 37), (123, 33)},\n",
       " (43, 127): {(15, 101), (31, 113), (59, 135)},\n",
       " (7, 61): {(5, 87), (19, 37), (33, 63)},\n",
       " (53, 107): {(31, 113), (59, 135), (61, 89), (75, 105)},\n",
       " (31, 113): {(15, 101), (37, 77), (43, 127), (53, 107)},\n",
       " (137, 131): {(109, 135), (129, 99), (139, 140)},\n",
       " (87, 63): {(59, 59), (81, 85), (85, 41), (109, 55)},\n",
       " (85, 41): {(53, 31), (75, 11), (87, 63), (107, 37)},\n",
       " (123, 89): {(111, 89), (129, 99), (135, 59)},\n",
       " (129, 99): {(113, 107), (123, 89), (137, 131)},\n",
       " (59, 59): {(33, 63), (53, 31), (61, 89), (87, 63)},\n",
       " (139, 140): {(137, 131)},\n",
       " (15, 101): {(5, 87), (31, 113), (43, 127)},\n",
       " (77, 137): {(59, 135), (75, 105), (109, 135)},\n",
       " (59, 135): {(43, 127), (53, 107), (77, 137)},\n",
       " (37, 77): {(5, 87), (31, 113), (33, 63), (61, 89)},\n",
       " (11, 9): {(1, 0), (19, 37), (31, 5)},\n",
       " (5, 87): {(7, 61), (15, 101), (37, 77)},\n",
       " (61, 89): {(37, 77), (53, 107), (59, 59), (81, 85)},\n",
       " (19, 37): {(7, 61), (11, 9), (39, 35)},\n",
       " (107, 37): {(85, 41), (107, 11), (109, 55), (123, 33)}}"
      ]
     },
     "execution_count": 127,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = maze_to_graph(surprisingly_dry(maze))\n",
    "graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can compute the maximum cost path in the graph with a recursive depth-first search:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_cost_graph_path(graph: Graph) -> int:\n",
    "    \"\"\"The maximum cost of paths through the graph, or `-inf` if no path.\"\"\"\n",
    "    start = min(graph)\n",
    "    end   = max(graph)\n",
    "    seen  = set()\n",
    "    def dfs(p: Point) -> int:\n",
    "        \"\"\"Depth-first search from position `p` to `end`, not repeating `seen`.\"\"\"\n",
    "        if p == end:\n",
    "            return 0\n",
    "        else:\n",
    "            seen.add(p)\n",
    "            longest = max([dfs(p2) + graph.cost[p, p2] \n",
    "                           for p2 in graph[p] if p2 not in seen], \n",
    "                          default=-inf)\n",
    "            seen.remove(p)\n",
    "            return longest + 1\n",
    "    return dfs(start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unfortunately, there is a **bug** and I get the wrong answer on both the example maze and the real maze."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Puzzle 23.2: 30.6098 seconds, answer 6424            WRONG; expected answer is unknown"
      ]
     },
     "execution_count": 129,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer(23.2, unknown, lambda: max_cost_graph_path(maze_to_graph(surprisingly_dry(maze))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also unfortunately, I ran out of time, so I'll stop here. I regret I didn't get to finish. Maybe next year."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Puzzle  1.1:   .0011 seconds, answer 54632           ok,\n",
       " Puzzle  1.2:   .0025 seconds, answer 54019           ok,\n",
       " Puzzle  2.1:   .0002 seconds, answer 1734            ok,\n",
       " Puzzle  2.2:   .0005 seconds, answer 70387           ok,\n",
       " Puzzle  3.1:   .0040 seconds, answer 559667          ok,\n",
       " Puzzle  3.2:   .0041 seconds, answer 86841457        ok,\n",
       " Puzzle  4.1:   .0004 seconds, answer 25174           ok,\n",
       " Puzzle  4.2:   .0008 seconds, answer 6420979         ok,\n",
       " Puzzle  5.1:   .0002 seconds, answer 324724204       ok,\n",
       " Puzzle  5.2:   .0018 seconds, answer 104070862       ok,\n",
       " Puzzle  6.1:   .0001 seconds, answer 861300          ok,\n",
       " Puzzle  6.2:   .0000 seconds, answer 28101347        ok,\n",
       " Puzzle  7.1:   .0033 seconds, answer 249726565       ok,\n",
       " Puzzle  7.2:   .0062 seconds, answer 251135960       ok,\n",
       " Puzzle  8.1:   .0025 seconds, answer 12361           ok,\n",
       " Puzzle  8.2:   .0292 seconds, answer 18215611419223  ok,\n",
       " Puzzle  9.1:   .0029 seconds, answer 1938731307      ok,\n",
       " Puzzle  9.2:   .0028 seconds, answer 948             ok,\n",
       " Puzzle 10.1:   .0271 seconds, answer 7066            ok,\n",
       " Puzzle 10.2:   .0000 seconds, answer unknown        ,\n",
       " Puzzle 11.1:   .3273 seconds, answer 10173804        ok,\n",
       " Puzzle 11.2:   .3320 seconds, answer 634324905172    ok,\n",
       " Puzzle 12.1:   .0148 seconds, answer 7843            ok,\n",
       " Puzzle 12.2:   .3497 seconds, answer 10153896718999  ok,\n",
       " Puzzle 13.1:   .0018 seconds, answer 33780           ok,\n",
       " Puzzle 13.2:   .0076 seconds, answer 23479           ok,\n",
       " Puzzle 14.1:   .0203 seconds, answer 108813          ok,\n",
       " Puzzle 14.2:  7.3388 seconds, answer 104533          ok,\n",
       " Puzzle 15.1:   .0019 seconds, answer 497373          ok,\n",
       " Puzzle 15.2:   .0030 seconds, answer 259356          ok,\n",
       " Puzzle 16.1:   .0189 seconds, answer 7060            ok,\n",
       " Puzzle 16.2:  6.2780 seconds, answer 7493            ok,\n",
       " Puzzle 17.1:  3.2620 seconds, answer 859             ok,\n",
       " Puzzle 17.2: 11.2230 seconds, answer 1030            WRONG; expected answer is unknown,\n",
       " Puzzle 18.1:   .1602 seconds, answer 61865           ok,\n",
       " Puzzle 18.2:   .0000 seconds, answer unknown        ,\n",
       " Puzzle 19.1:   .0007 seconds, answer 532551          ok,\n",
       " Puzzle 19.2:   .0045 seconds, answer 134343280273968 ok,\n",
       " Puzzle 20.1:   .0865 seconds, answer 980457412       ok,\n",
       " Puzzle 20.2:   .0000 seconds, answer unknown        ,\n",
       " Puzzle 21.1:   .1627 seconds, answer 3637            ok,\n",
       " Puzzle 21.2:   .0000 seconds, answer unknown        ,\n",
       " Puzzle 22.1:   .0560 seconds, answer 439             ok,\n",
       " Puzzle 22.2:  3.5921 seconds, answer 43056           ok,\n",
       " Puzzle 23.1:   .6492 seconds, answer 2030            ok,\n",
       " Puzzle 23.2: 30.6098 seconds, answer 6424            WRONG; expected answer is unknown]"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(answers.values())"
   ]
  }
 ],
 "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.8.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}