ipynb/Advent-2020.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: right\" align=\"right\"><i>Peter Norvig<br>December 2020</i></div>\n",
    "\n",
    "# Advent of Code 2020\n",
    "\n",
    "This year I return to [Advent of Code](https://adventofcode.com), as I did in [2016](Advent+of+Code), [17](Advent+2017), and [18](Advent-2018.ipynb). Thank you, [Eric Wastl](http://was.tl/)! This notebook describes each day's puzzle only briefly; you'll have to look at the [Advent of Code website](https://adventofcode.com/2020) if you want the full details. Each puzzle has a part 1 and a part 2.\n",
    "\n",
    "For each day from 1 to 25, I'll write **four pieces of code** with the following format (and perhaps some auxiliary code). For example, on day 3:\n",
    "- `in3: List[str] = data(3)`: the day's input data, parsed into an appropriate form (here, a list of string lines). Some days the data is so small I just copy and paste it. But most days the data comes from a file, read via the function `data(day, parser, sep)`, which breaks the file into sections/records separated by `sep` (newline by default), and applies a `parser` to each section (default is to leave the section as a `str`).\n",
    "- `def day3_1(nums): ...   `: a function that takes the day's data as input and returns the answer for part 1.\n",
    "- `def day3_2(nums): ...   `: a function that takes the day's data as input and returns the answer for part 2.\n",
    "- `do(3)`: runs `day3_1(in3)`. I'll then use the result to hopefully unlock part 2 and define `day3_2`, which also gets run when I call `do(3)` again. Once I verify both answers, I'll change `do(3)` to `do(3, 167, 736527114)` to serve as a unit test.\n",
    "\n",
    "# Day 0: Imports and Utility Functions\n",
    "\n",
    "Preparations prior to Day 1:\n",
    "- Some imports.\n",
    "- A way to read the day's data file and to print/check the output.\n",
    "- Some utilities that are likely to be useful."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__  import annotations\n",
    "from collections import Counter, defaultdict, namedtuple, deque\n",
    "from itertools   import permutations, combinations, product, chain\n",
    "from functools   import lru_cache\n",
    "from typing      import Dict, Tuple, Set, List, Iterator, Optional, Union\n",
    "\n",
    "import operator\n",
    "import math\n",
    "import ast\n",
    "import sys\n",
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def data(day: int, parser=str, sep='\\n') -> list:\n",
    "    \"Split the day's input file into sections separated by `sep`, and apply `parser` to each.\"\n",
    "    sections = open(f'data/advent2020/input{day}.txt').read().rstrip().split(sep)\n",
    "    return [parser(section) for section in sections]\n",
    "     \n",
    "def do(day, *answers) -> Dict[int, int]:\n",
    "    \"E.g., do(3) returns {1: day3_1(in3), 2: day3_2(in3)}. Verifies `answers` if given.\"\n",
    "    g = globals()\n",
    "    got = []\n",
    "    for part in (1, 2):\n",
    "        fname = f'day{day}_{part}'\n",
    "        if fname in g: \n",
    "            got.append(g[fname](g[f'in{day}']))\n",
    "            if len(answers) >= part: \n",
    "                assert got[-1] == answers[part - 1], (\n",
    "                    f'{fname}(in{day}) got {got[-1]}; expected {answers[part - 1]}')\n",
    "    return got"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quantify(iterable, pred=bool) -> int:\n",
    "    \"Count the number of items in iterable for which pred is true.\"\n",
    "    return sum(1 for item in iterable if pred(item))\n",
    "\n",
    "def first(iterable, default=None) -> object:\n",
    "    \"Return first item in iterable, or default.\"\n",
    "    return next(iter(iterable), default)\n",
    "\n",
    "def rest(sequence) -> object: return sequence[1:]\n",
    "\n",
    "def multimap(items: Iterable[Tuple]) -> dict:\n",
    "    \"Given (key, val) pairs, return {key: [val, ....], ...}.\"\n",
    "    result = defaultdict(list)\n",
    "    for (key, val) in items:\n",
    "        result[key].append(val)\n",
    "    return result\n",
    "\n",
    "def prod(numbers) -> float: # Will be math.prod in Python 3.8, but I'm in 3.7\n",
    "    \"The product of an iterable of numbers.\" \n",
    "    result = 1\n",
    "    for n in numbers:\n",
    "        result *= n\n",
    "    return result\n",
    "\n",
    "def ints(text: str) -> Tuple[int]:\n",
    "    \"Return a tuple of all the integers in text.\"\n",
    "    return tuple(map(int, re.findall('-?[0-9]+', text)))\n",
    "\n",
    "def atoms(text: str, ignore=r'', sep=None) -> Tuple[Union[int, str]]:\n",
    "    \"Parse text into atoms (numbers or strs), possibly ignoring a regex.\"\n",
    "    if ignore:\n",
    "        text = re.sub(ignore, '', text)\n",
    "    return tuple(map(atom, text.split(sep)))\n",
    "\n",
    "def atom(text: str) -> Union[float, int, str]:\n",
    "    \"Parse text into a single float or int or str.\"\n",
    "    try:\n",
    "        val = float(text)\n",
    "        return round(val) if round(val) == val else val\n",
    "    except ValueError:\n",
    "        return text\n",
    "    \n",
    "def dotproduct(A, B) -> float: return sum(a * b for a, b in zip(A, B))\n",
    "\n",
    "def mapt(fn, *args):\n",
    "    \"map(fn, *args) and return the result as a tuple.\"\n",
    "    return tuple(map(fn, *args))\n",
    "\n",
    "cat = ''.join\n",
    "flatten = chain.from_iterable\n",
    "Char = str # Type used to indicate a single character"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notes:\n",
    "- Since I'm not even attempting to compete for speed, I'll take the time to use reasonable variable names (not single-letter names), and to give type annotations for most of the functions I define (but not the `day` functions, which all return `int`).\n",
    "- Traditionally, a lot of AoC problems are solved by one of the following two forms:\n",
    "  - `quantify(inputs, P)`: How many of your input items have property P?\n",
    "  - `sum(map(F, inputs))`: What is the sum of the result of applying F to each input item?\n",
    "- I will feel free to re-use a definition that I define one day in a subsequent day's puzzle.\n",
    "- I will define a few test cases with `assert`, but far fewer test cases than if I was programming seriously."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 1: Report Repair\n",
    "\n",
    "1. Find the two entries in your expense report (a file of integers) that sum to 2020; what do you get if you multiply them together?\n",
    "2.  In your expense report, what is the product of the three entries that sum to 2020?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "in1: Set[int] = set(data(1, int))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day1_1(nums):\n",
    "    \"Find 2 distinct numbers that sum to 2020, and return their product.\"\n",
    "    return first(x * y \n",
    "                 for x in nums \n",
    "                 for y in nums & {2020 - x} \n",
    "                 if x != y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day1_2(nums):\n",
    "    \"Find 3 distinct numbers that sum to 2020, and return their product.\"\n",
    "    return first(x * y * z \n",
    "                 for x, y in combinations(nums, 2) \n",
    "                 for z in nums & {2020 - x - y} \n",
    "                 if x != z != y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[787776, 262738554]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(1, 787776, 262738554)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 2: Password Philosophy\n",
    "\n",
    "1. A password policy is of the form \"`1-3 b: cdefg`\" meaning that the password must contain 1 to 3 instances of `b`; `cdefg` is invalid under this policy. How many passwords in your input file are valid according to their policies?\n",
    "-  JK! The policy actually means that exactly one of positions 1 and 3 (1-based) must contain the letter `b`. How many passwords are valid according to the new interpretation of the policies?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "Policy = Tuple[int, int, Char, str]\n",
    "\n",
    "def parse_password_policy(line: str) -> Policy:\n",
    "    \"Given '1-3 b: cdefg', return (1, 3, 'b', 'cdefg').\"\n",
    "    a, b, L, pw = re.findall(r'[^-:\\s]+', line)\n",
    "    return (int(a), int(b), L, pw)\n",
    "\n",
    "in2: List[tuple] = data(2, parse_password_policy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valid_password(policy) -> bool: \n",
    "    \"Does policy's pw have between a and b instances of letter L?\"\n",
    "    a, b, L, pw = policy\n",
    "    return a <= pw.count(L) <= b\n",
    "\n",
    "def day2_1(policies): return quantify(policies, valid_password)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day2_2(policies): return quantify(policies, valid_password_2)\n",
    "\n",
    "def valid_password_2(policy) -> bool: \n",
    "    \"Does line's pw have letter L at position a or b (1-based), but not both?\"\n",
    "    a, b, L, pw = policy\n",
    "    return (L == pw[a - 1]) ^ (L == pw[b - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[383, 272]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(2, 383, 272)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 3: Toboggan Trajectory\n",
    "\n",
    "The input file is a map of a field that looks like this:\n",
    "\n",
    "    ..##.......\n",
    "    #...#...#..\n",
    "    .#....#..#.\n",
    "    ..#.#...#.#\n",
    "    .#...##..#.\n",
    "    \n",
    "where each `#` is a tree and the pattern in each row implicitly repeats to the right. We'll call a list of row-strings a *picture*.\n",
    "\n",
    "1. Starting at the top-left corner of your map and following a slope of down 1 and right 3, how many trees would you encounter?\n",
    "2. What do you get if you multiply together the number of trees encountered on each of the slopes 1/1, 1/3, 1/5, 1/7, 2/1?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "Picture = List[str]\n",
    "\n",
    "in3: Picture = data(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day3_1(picture, dx=3, dy=1, tree='#'): \n",
    "    \"How many trees are on the coordinates on the slope dy/dx?\"\n",
    "    return quantify(row[(dx * y) % len(row)] == tree\n",
    "                    for y, row in enumerate(picture[::dy]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day3_2(picture):\n",
    "    \"What is the product of the number of trees on these five slopes?\"\n",
    "    def t(dx, dy): return day3_1(picture, dx, dy)\n",
    "    return t(1, 1) * t(3, 1) * t(5, 1) * t(7, 1) * t(1, 2) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[167, 736527114]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(3, 167, 736527114)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 4: Passport Processing\n",
    "\n",
    "The input is a file of passport data that looks like this (each passport is a series of field:value pairs separated from the next passport by a blank line):\n",
    "\n",
    "    ecl:gry pid:860033327 eyr:2020 hcl:#fffffd\n",
    "    byr:1937 iyr:2017 cid:147 hgt:183cm\n",
    "\n",
    "    iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884 hcl:#cfa07d byr:1929\n",
    "\n",
    "    hcl:#ae17e1 iyr:2013\n",
    "    eyr:2024 ecl:brn pid:760753108 byr:1931 hgt:179cm\n",
    "    \n",
    "    \n",
    "1. Count the number of valid passports &mdash; those that have all seven required fields (`byr, ecl, eyr, hcl, hgt, iyr, pid`). \n",
    "2. Count the number of valid passports &mdash; those that have valid values for all required fields (see the rules in `valid_fields`). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "Passport = dict # e.g. {'iyr': '2013', ...}\n",
    "\n",
    "def parse_passport(text: str) -> Passport:\n",
    "    \"Make a dict of the 'key:val' entries in text.\"\n",
    "    return Passport(re.findall(r'([a-z]+):([^\\s]+)', text))\n",
    "\n",
    "assert parse_passport('''a:1 b:two\\nsee:3''') == {'a': '1', 'b': 'two', 'see': '3'}\n",
    "\n",
    "in4: List[Passport] = data(4, parse_passport, '\\n\\n') # Passports are separated by blank lines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "required_fields = {'byr', 'ecl', 'eyr', 'hcl', 'hgt', 'iyr', 'pid'}\n",
    "valid_passport  = required_fields.issubset\n",
    "\n",
    "def day4_1(passports): return quantify(passports, valid_passport)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day4_2(passports): return quantify(passports, valid_passport_fields)\n",
    "\n",
    "def valid_passport_fields(passport) -> bool:\n",
    "    '''Validate fields according to the following rules:\n",
    "    byr (Birth Year) - four digits; at least 1920 and at most 2002.\n",
    "    iyr (Issue Year) - four digits; at least 2010 and at most 2020.\n",
    "    eyr (Expr. Year) - four digits; at least 2020 and at most 2030.\n",
    "    hgt (Height) - a number followed by either cm or in:\n",
    "      If cm, the number must be at least 150 and at most 193.\n",
    "      If in, the number must be at least 59 and at most 76.\n",
    "    hcl (Hair Color) - a '#' followed by exactly six characters 0-9 or a-f.\n",
    "    ecl (Eye Color) - exactly one of: amb blu brn gry grn hzl oth.\n",
    "    pid (Passport ID) - a nine-digit number, including leading zeroes.\n",
    "    cid (Country ID) - ignored, missing or not.'''\n",
    "    return (valid_passport(passport)\n",
    "            and all(field_validator[field](passport[field])\n",
    "                    for field in required_fields))\n",
    "\n",
    "field_validator = dict(\n",
    "    byr=lambda v: 1920 <= int(v) <= 2002,\n",
    "    iyr=lambda v: 2010 <= int(v) <= 2020,\n",
    "    eyr=lambda v: 2020 <= int(v) <= 2030,\n",
    "    hcl=lambda v: re.match('#[0-9a-f]{6}$', v),\n",
    "    ecl=lambda v: re.match('(amb|blu|brn|gry|grn|hzl|oth)$', v),\n",
    "    pid=lambda v: re.match('[0-9]{9}$', v),\n",
    "    hgt=lambda v: ((v.endswith('cm') and 150 <= int(v[:-2]) <= 193) or\n",
    "                   (v.endswith('in') and  59 <= int(v[:-2]) <=  76)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[237, 172]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(4, 237, 172)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 5: Binary Boarding\n",
    "\n",
    "The input is a list of boarding passes, such as `'FBFBBFFRLR'`. Each boarding pass corrsponds to a *seat ID* using an encoding where B and F stand for the back and front half of the remaining part of the plane; R and L stand for right and left half of a row. (The encoding is the same as substituting 0 for F or L, and 1 for B or R, and treating the result as a binary number.)\n",
    "\n",
    "1. What is the highest seat ID on a boarding pass?\n",
    "-  What is the one missing seat ID, between the minimum and maximum IDs, that is not on the list of boarding passes?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "ID = int # A type\n",
    "\n",
    "def seat_id(seat: str, table=str.maketrans('FLBR', '0011')) -> ID:\n",
    "    \"Treat a seat description as a binary number; convert to int.\"\n",
    "    return ID(seat.translate(table), base=2)\n",
    "\n",
    "assert seat_id('FBFBBFFRLR') == 357\n",
    "\n",
    "in5: List[ID] = data(5, seat_id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "day5_1 = max # Find the maximum seat id."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day5_2(ids):\n",
    "    \"The one missing seat id.\"\n",
    "    [missing] = set(range(min(ids), max(ids))) - set(ids)\n",
    "    return missing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[906, 519]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(5, 906, 519)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 6: Custom Customs\n",
    "\n",
    "Each passenger fills out a customs form; passengers are arranged in groups. The \"yes\" answer are recorded; each person on one line, each group separated by a blank line. E.g.:\n",
    "\n",
    "    abc\n",
    "\n",
    "    a\n",
    "    b\n",
    "    c\n",
    "\n",
    "    ab\n",
    "    ac\n",
    "    \n",
    "1. For each group, count the number of questions to which *anyone* answered \"yes\". What is the sum of those counts?\n",
    "2. For each group, count the number of questions to which *everyone* answered \"yes\". What is the sum of those counts?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "in6: List[List[str]] = data(6, str.splitlines, sep='\\n\\n')\n",
    "\n",
    "assert in6[1] == ['arke', 'qzr', 'plmgnr', 'uriq'] # A group is a list of strs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day6_1(groups): \n",
    "    \"For each group, compute the number of letters that ANYONE got. Sum them.\"\n",
    "    return sum(len(set(cat(group)))\n",
    "               for group in groups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day6_2(groups: List[List[str]]): \n",
    "    \"For each group, compute the number of letters that EVERYONE got. Sum them.\"\n",
    "    return sum(len(set.intersection(*map(set, group)))\n",
    "               for group in groups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6530, 3323]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(6, 6530, 3323)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 7: Handy Haversacks\n",
    "\n",
    "There are strict luggage processing rules for what color bags must contain what other bags. For example:\n",
    "\n",
    "    light red bags contain 1 bright white bag, 2 muted yellow bags.\n",
    "    dark orange bags contain 3 bright white bags, 4 muted yellow bags.\n",
    "    bright white bags contain 1 shiny gold bag.\n",
    "    \n",
    "1. How many bag colors must eventually contain at least one shiny gold bag?\n",
    "2. How many individual bags must be inside your single shiny gold bag?\n",
    "\n",
    "I wasn't quite sure, but it turns out that \"light red\" and \"dark red\" are different colors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "Bag = str\n",
    "BagRules = Dict[Bag, Dict[Bag, int]] # {outer: {inner: count, ...}, ...}\n",
    "\n",
    "def parse_bag_rule(line: str) -> Tuple[Bag, Dict[Bag, int]]:\n",
    "    \"Return (outer_bag, {inner_bag: num, ...})\"\n",
    "    line = re.sub(' bags?|[.]', '', line) # Remove redundant info\n",
    "    outer, inner = line.split(' contain ')\n",
    "    return outer, dict(map(parse_inner, inner.split(', ')))\n",
    "\n",
    "def parse_inner(text) -> Tuple[Bag, int]:\n",
    "    \"Return the color and number of inner bags.\"\n",
    "    n, bag = text.split(maxsplit=1)\n",
    "    return bag, (0 if n == 'no' else int(n))\n",
    "\n",
    "assert parse_inner('3 muted gray') == ('muted gray', 3)\n",
    "\n",
    "assert (dict([parse_bag_rule(\"shiny gold bags contain 4 bright blue bags\")])\n",
    "        == {'shiny gold': {'bright blue': 4}})\n",
    "\n",
    "in7: BagRules = dict(data(7, parse_bag_rule))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day7_1(rules, target='shiny gold'):\n",
    "    \"How many colors of bags can contain the target color bag?\"\n",
    "    @lru_cache(None)\n",
    "    def contains(bag, target) -> bool:\n",
    "        \"Does this bag contain the target (perhaps recursively)?\"\n",
    "        contents = rules.get(bag, {})\n",
    "        return (target in contents\n",
    "                or any(contains(inner, target) for inner in contents))\n",
    "    return quantify(contains(bag, target) for bag in rules)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day7_2(rules, target='shiny gold'): \n",
    "    return num_contained_in(target, rules)\n",
    "\n",
    "def num_contained_in(target, rules) -> int:\n",
    "    \"How many bags are contained (recursively) in the target bag?\"\n",
    "    return sum(n + n * num_contained_in(bag, rules) \n",
    "               for (bag, n) in rules[target].items() if n > 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[103, 1469]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(7, 103, 1469)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 8: Handheld Halting\n",
    "\n",
    "The puzzle input is a program in an assembly language with three instructions: `jmp, acc, nop`. Since there is no conditional branch instruction, a program that executes any instruction twice will infinite loop; terminating programs will execute each instruction at most once.\n",
    "\n",
    "1. Immediately before any instruction is executed a second time, what value is in the accumulator register?\n",
    "2. Fix the program so that it terminates normally by changing exactly one jmp to nop or nop to jmp. What is the value of the accumulator register after the program terminates?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "Instruction = Tuple[str, int] # e.g. ('jmp', +4)\n",
    "Program = List[Instruction]\n",
    "\n",
    "in8: Program = data(8, atoms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day8_1(program):\n",
    "    \"Execute the program until it loops; then return accum.\"\n",
    "    pc = accum = 0\n",
    "    executed = set() # Set of instruction addresses executed so far\n",
    "    while True:\n",
    "        if pc in executed:\n",
    "            return accum\n",
    "        executed.add(pc)\n",
    "        opcode, arg = program[pc]\n",
    "        pc += 1\n",
    "        if opcode == 'acc':\n",
    "            accum += arg\n",
    "        if opcode == 'jmp':\n",
    "            pc = pc - 1 + arg"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had to think about what to do for Part 2. Do I need to make a flow graph of where the loops are? That sounds hard. But I soon realized that I can just use brute force&mdash;try every alteration of an instruction (there are only $O(n)$ of them), and run each altered program to see if it terminates (that too takes only $O(n)$ time)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day8_2(program): \n",
    "    \"Return the accumulator from the first altered program that terminates.\"\n",
    "    programs = altered_programs(program)\n",
    "    return first(accum for (terminates, accum) in map(run_program, programs)\n",
    "                 if terminates)\n",
    "\n",
    "def altered_programs(program, other=dict(jmp='nop', nop='jmp')) -> Iterator[Program]:\n",
    "    \"All ways to swap a nop for a jmp or vice-versa.\"\n",
    "    for i, (opcode, arg) in enumerate(program):\n",
    "        if opcode in other:\n",
    "            yield [*program[:i], (other[opcode], arg), *program[i + 1:]]\n",
    "\n",
    "def run_program(program) -> Tuple[bool, int]:\n",
    "    \"Run the program until it loops or terminates; return (terminates, accum)\"\n",
    "    pc = accum = 0\n",
    "    executed = set() # Set of instruction addresses executed so far\n",
    "    while 0 <= pc < len(program):\n",
    "        if pc in executed:\n",
    "            return False, accum # program loops\n",
    "        executed.add(pc)\n",
    "        opcode, arg = program[pc]\n",
    "        pc += 1\n",
    "        if opcode == 'acc':\n",
    "            accum += arg\n",
    "        if opcode == 'jmp':\n",
    "            pc = pc - 1 + arg\n",
    "    return True, accum # program terminates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1521, 1016]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(8, 1521, 1016)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 9: Encoding Error\n",
    "\n",
    "Given a list of numbers:\n",
    "\n",
    "1. Find the first number in the list (after the preamble of 25 numbers) which is not the sum of two of the 25 numbers before it.\n",
    "2. Find a contiguous subsequence of numbers in your list which sum to the number from step 1; add the smallest and largest numbers in this subsequence.\n",
    "\n",
    "I could do this efficiently in $O(n)$ as in Day 1, but $n$ is so small I'll just use brute force."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "in9: List[int] = data(9, int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day9_1(nums, p=25):\n",
    "    \"\"\"Find the first number in the list of numbers (after a preamble of p=25 numbers) \n",
    "    which is not the sum of two of the p numbers before it.\"\"\"\n",
    "    return first(x for i, x in enumerate(nums) \n",
    "                 if i > p and x not in twosums(nums[i-p:i]))\n",
    "\n",
    "def twosums(nums): return map(sum, combinations(nums, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day9_2(nums, target=day9_1(in9)):\n",
    "    \"Find a contiguous subsequence of nums that sums to target; add their max and min.\"\n",
    "    subseq = find_subseq(nums, target)\n",
    "    return max(subseq) + min(subseq)\n",
    "\n",
    "def find_subseq(nums, target) -> Optional[deque]:\n",
    "    \"Find a contiguous subsequence of nums that sums to target.\"\n",
    "    subseq = deque()\n",
    "    total = 0\n",
    "    for x in nums:\n",
    "        if total < target:\n",
    "            subseq.append(x)\n",
    "            total += x\n",
    "        if total == target and len(subseq) >= 2:\n",
    "            return subseq\n",
    "        while total > target:\n",
    "            total -= subseq.popleft()\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[776203571, 104800569]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(9, 776203571, 104800569)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 10: Adapter Array\n",
    "\n",
    "You are given a bunch of *joltage adapters*, each with a listed joltage output; each can take an input source that is 1, 2, or 3 jolts lower than the output. There is a charging outlet rated 0 jolts, and you want to chargwe a device that is 3 jolts higher than the maximum adapter.\n",
    "\n",
    "1. Find a chain that uses all of your adapters to connect the charging outlet to your device's built-in adapter and count the joltage differences between the charging outlet, the adapters, and your device. What is the number of 1-jolt differences multiplied by the number of 3-jolt differences?\n",
    "2. What is the total number of distinct ways you can arrange the adapters to connect the charging outlet to your device?\n",
    "\n",
    "Note: at first I thought this was a search problem. But then I realized that the only possibility is to increase joltage from source to adapter, so that means the adapters must appear in sorted order. For part 2, some  adapters can be left out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "in10: List[int] = data(10, int) # Input is the joltage of each adapter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day10_1(jolts):\n",
    "    \"\"\"Arrange the joltages in order; count the number of each size difference;\n",
    "    return the product of 1- and 3-jolt differences.\"\"\"\n",
    "    jolts = [0] + sorted(jolts) + [max(jolts) + 3]\n",
    "    diffs = Counter(jolts[i + 1] - jolts[i] \n",
    "                    for i in range(len(jolts) - 1))\n",
    "    assert {1, 2, 3}.issuperset(diffs)\n",
    "    return diffs[1] * diffs[3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day10_2(jolts): return arrangements(tuple(sorted(jolts)), 0)\n",
    "\n",
    "@lru_cache(None)\n",
    "def arrangements(jolts, prev) -> int:\n",
    "    first, rest = jolts[0], jolts[1:]\n",
    "    if first - prev > 3:\n",
    "        return 0\n",
    "    elif not rest:\n",
    "        return 1\n",
    "    else:\n",
    "        return (arrangements(rest, first) + # Use first\n",
    "                arrangements(rest, prev))   # Skip first\n",
    "    \n",
    "assert arrangements((3, 6, 9, 12), 0) == 1\n",
    "assert arrangements((3, 6, 9, 13), 0) == 0\n",
    "assert arrangements((1, 2, 3,  4), 0) == 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2346, 6044831973376]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(10, 2346, 6044831973376)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 11: Seating System\n",
    "\n",
    "This is a version of Conway's *Life*, except that:\n",
    "- The world is bounded, not infinite. \n",
    "- Cells (seats) have three states, not two: *floor* as well as the traditional *occupied* and *empty*.\n",
    "- The rules for what changes between occupied and empty in the next generation are different: \n",
    "\n",
    "   - If a seat is empty (`L`) and there are no occupied seats adjacent to it, the seat becomes occupied.\n",
    "   - If a seat is occupied (`#`) and four or more seats adjacent to it are also occupied, the seat becomes empty.\n",
    "   - Otherwise, the seat's state does not change.\n",
    "\n",
    "   \n",
    "1. Simulate your seating area by applying the seating rules repeatedly until no seats change state. How many seats end up occupied?\n",
    "2. Same problem, but with two rule changes:\n",
    "  - When considering adjacency, if there is a *floor* cell in some direction, skip over that to the next visible seat in that direction. \n",
    "  - Empty a seat only when there are 5 occupied neighbors, not 4. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "in11: List[str] = data(11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "Seats = List[str]\n",
    "\n",
    "floor, empty, occupied, off = \".L#?\"\n",
    "\n",
    "Contents = Char # The contents of each location is one of the above 4 characters\n",
    "\n",
    "crowded = 4\n",
    "    \n",
    "deltas = ((-1, -1), (0, -1), (1, -1),\n",
    "          (-1,  0),          (1,  0),\n",
    "          (-1, +1), (0, +1), (1, +1))\n",
    "    \n",
    "def next_generation(seats) -> Seats:\n",
    "    \"The next generation, according to the rules.\"\n",
    "    return [cat(self.next_generation_at(x, y) for x in range(len(self[y])))\n",
    "            for y in range(len(self))]\n",
    "\n",
    "def next_generation_at(seats, x, y) -> Contents:\n",
    "    \"The contents of location (x, y) in the next generation.\"\n",
    "    old = seats[y][x]\n",
    "    N   = self.neighbors(x, y).count(occupied)\n",
    "    return (occupied if old is empty    and N == 0       else\n",
    "            empty    if old is occupied and N >= crowded else\n",
    "            old)\n",
    "\n",
    "def neighbors(seats, x, y) -> List[Contents]: \n",
    "    \"The contents of the 8 neighboring locations.\"\n",
    "    return [seats.at(x + dx, y + dy) for dx, dy in self.deltas]\n",
    "\n",
    "    def count(self, kind: Contents) -> int: return cat(self).count(kind)\n",
    "    \n",
    "    def at(self, x, y) -> Contents:\n",
    "        \"The contents of location (x, y): empty, occupied, floor, or off?\"\n",
    "        if 0 <= y < len(self) and 0 <= x < len(self[y]):\n",
    "            return self[y][x]\n",
    "        else:\n",
    "            return off\n",
    "        \n",
    "    def run(self) -> Layout:\n",
    "        \"Run until equilibrium.\"\n",
    "        new = self\n",
    "        while True:\n",
    "            new, old = new.next_generation(), new\n",
    "            if new == old:\n",
    "                return new\n",
    "\n",
    "def day11_1(seats): return Layout(seats).run().count(occupied)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'Layout' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<timed eval>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-45-f21637961bca>\u001b[0m in \u001b[0;36mday11_1\u001b[0;34m(seats)\u001b[0m\n\u001b[1;32m     45\u001b[0m                 \u001b[0;32mreturn\u001b[0m \u001b[0mnew\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     46\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 47\u001b[0;31m \u001b[0;32mdef\u001b[0m \u001b[0mday11_1\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseats\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mLayout\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseats\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrun\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcount\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0moccupied\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'Layout' is not defined"
     ]
    }
   ],
   "source": [
    "%time day11_1(in11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "floor, empty, occupied, off = \".L#?\"\n",
    "\n",
    "Contents = Char # The contents of each location is one of the above 4 characters\n",
    "\n",
    "class Layout(list):\n",
    "    \"A layout of seats (occupied or not) and floor space.\"\n",
    "    \n",
    "    crowded = 4\n",
    "    \n",
    "    deltas = ((-1, -1), (0, -1), (1, -1),\n",
    "              (-1,  0),          (1,  0),\n",
    "              (-1, +1), (0, +1), (1, +1))\n",
    "    \n",
    "    def next_generation(self) -> Layout:\n",
    "        \"The next generation, according to the rules.\"\n",
    "        seats = (cat(self.next_generation_at(x, y) for x in range(len(self[y])))\n",
    "                 for y in range(len(self)))\n",
    "        return type(self)(seats)\n",
    "\n",
    "    def next_generation_at(self, x, y) -> Contents:\n",
    "        \"The contents of location (x, y) in the next generation.\"\n",
    "        old = self[y][x]\n",
    "        N   = self.neighbors(x, y).count(occupied)\n",
    "        return (occupied if old is empty    and N == 0            else\n",
    "                empty    if old is occupied and N >= self.crowded else\n",
    "                old)\n",
    "\n",
    "    def neighbors(self, x, y) -> List[Contents]: \n",
    "        \"The contents of the 8 neighboring locations.\"\n",
    "        return [self.at(x + dx, y + dy) for dx, dy in self.deltas]\n",
    "\n",
    "    def count(self, kind: Contents) -> int: return cat(self).count(kind)\n",
    "    \n",
    "    def at(self, x, y) -> Contents:\n",
    "        \"The contents of location (x, y): empty, occupied, floor, or off?\"\n",
    "        if 0 <= y < len(self) and 0 <= x < len(self[y]):\n",
    "            return self[y][x]\n",
    "        else:\n",
    "            return off\n",
    "        \n",
    "    def run(self) -> Layout:\n",
    "        \"Run until equilibrium.\"\n",
    "        new = self\n",
    "        while True:\n",
    "            new, old = new.next_generation(), new\n",
    "            if new == old:\n",
    "                return new\n",
    "\n",
    "def day11_1(seats): return Layout(seats).run().count(occupied)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day11_2(seats): return Layout2(seats).run().count(occupied)\n",
    "\n",
    "class Layout2(Layout):\n",
    "    \"A layout of seats (occupied or not) and floor space, with new rules.\"\n",
    "\n",
    "    crowded = 5\n",
    "    \n",
    "    def neighbors(self, x, y) -> List[Contents]:\n",
    "        \"The contents of the nearest visible seat in each of the 8 directions.\"\n",
    "        return [self.visible(x, dx, y, dy) for dx, dy in self.deltas]\n",
    "    \n",
    "    def visible(self, x, dx, y, dy) -> Contents:\n",
    "        \"The contents of the first visible seat in direction (dx, dy).\"\n",
    "        for i in range(1, sys.maxsize):\n",
    "            x += dx; y += dy\n",
    "            if not (0 <= y < len(self) and 0 <= x < len(self[y])):\n",
    "                return off\n",
    "            if self[y][x] is not floor:\n",
    "                return self[y][x]                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<timed eval>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-2-5d65e361ebd2>\u001b[0m in \u001b[0;36mdo\u001b[0;34m(day, *answers)\u001b[0m\n\u001b[1;32m     11\u001b[0m         \u001b[0mfname\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34mf'day{day}_{part}'\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     12\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mfname\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mg\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 13\u001b[0;31m             \u001b[0mgot\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mg\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mfname\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mg\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34mf'in{day}'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     14\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0manswers\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m>=\u001b[0m \u001b[0mpart\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     15\u001b[0m                 assert got[-1] == answers[part - 1], (\n",
      "\u001b[0;32m<ipython-input-48-1c61a3432152>\u001b[0m in \u001b[0;36mday11_2\u001b[0;34m(seats)\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32mdef\u001b[0m \u001b[0mday11_2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseats\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mLayout2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseats\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrun\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcount\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0moccupied\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;32mclass\u001b[0m \u001b[0mLayout2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mLayout\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0;34m\"A layout of seats (occupied or not) and floor space, with new rules.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-47-354e88a843f1>\u001b[0m in \u001b[0;36mrun\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     43\u001b[0m         \u001b[0mnew\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     44\u001b[0m         \u001b[0;32mwhile\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 45\u001b[0;31m             \u001b[0mnew\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mold\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnew\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnext_generation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mnew\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     46\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mnew\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0mold\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     47\u001b[0m                 \u001b[0;32mreturn\u001b[0m \u001b[0mnew\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-47-354e88a843f1>\u001b[0m in \u001b[0;36mnext_generation\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     16\u001b[0m         seats = (cat(self.next_generation_at(x, y) for x in range(len(self[y])))\n\u001b[1;32m     17\u001b[0m                  for y in range(len(self)))\n\u001b[0;32m---> 18\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mtype\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseats\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     19\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     20\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mnext_generation_at\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0mContents\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-47-354e88a843f1>\u001b[0m in \u001b[0;36m<genexpr>\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m     15\u001b[0m         \u001b[0;34m\"The next generation, according to the rules.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     16\u001b[0m         seats = (cat(self.next_generation_at(x, y) for x in range(len(self[y])))\n\u001b[0;32m---> 17\u001b[0;31m                  for y in range(len(self)))\n\u001b[0m\u001b[1;32m     18\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mtype\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseats\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     19\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-47-354e88a843f1>\u001b[0m in \u001b[0;36m<genexpr>\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m     14\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mnext_generation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0mLayout\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     15\u001b[0m         \u001b[0;34m\"The next generation, according to the rules.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 16\u001b[0;31m         seats = (cat(self.next_generation_at(x, y) for x in range(len(self[y])))\n\u001b[0m\u001b[1;32m     17\u001b[0m                  for y in range(len(self)))\n\u001b[1;32m     18\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mtype\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseats\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-47-354e88a843f1>\u001b[0m in \u001b[0;36mnext_generation_at\u001b[0;34m(self, x, y)\u001b[0m\n\u001b[1;32m     21\u001b[0m         \u001b[0;34m\"The contents of location (x, y) in the next generation.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     22\u001b[0m         \u001b[0mold\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0my\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 23\u001b[0;31m         \u001b[0mN\u001b[0m   \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mneighbors\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcount\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0moccupied\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     24\u001b[0m         return (occupied if old is empty    and N == 0            else\n\u001b[1;32m     25\u001b[0m                 \u001b[0mempty\u001b[0m    \u001b[0;32mif\u001b[0m \u001b[0mold\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0moccupied\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0mN\u001b[0m \u001b[0;34m>=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcrowded\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-48-1c61a3432152>\u001b[0m in \u001b[0;36mneighbors\u001b[0;34m(self, x, y)\u001b[0m\n\u001b[1;32m      8\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mneighbors\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0mList\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mContents\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      9\u001b[0m         \u001b[0;34m\"The contents of the nearest visible seat in each of the 8 directions.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 10\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvisible\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdy\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mdx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdy\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdeltas\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     11\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     12\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mvisible\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdy\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0mContents\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-48-1c61a3432152>\u001b[0m in \u001b[0;36m<listcomp>\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m      8\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mneighbors\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0mList\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mContents\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      9\u001b[0m         \u001b[0;34m\"The contents of the nearest visible seat in each of the 8 directions.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 10\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvisible\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdy\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mdx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdy\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdeltas\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     11\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     12\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mvisible\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdy\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0mContents\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-48-1c61a3432152>\u001b[0m in \u001b[0;36mvisible\u001b[0;34m(self, x, dx, y, dy)\u001b[0m\n\u001b[1;32m     12\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mvisible\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdy\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0mContents\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m         \u001b[0;34m\"The contents of the first visible seat in direction (dx, dy).\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 14\u001b[0;31m         \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msys\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmaxsize\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     15\u001b[0m             \u001b[0mx\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0mdx\u001b[0m\u001b[0;34m;\u001b[0m \u001b[0my\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0mdy\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     16\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m \u001b[0;34m<=\u001b[0m \u001b[0my\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0;36m0\u001b[0m \u001b[0;34m<=\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0my\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "%time do(11, 2299, 2047)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I have to confess that I \"cheated\" here: after seeing the problem description for Part 2, I went back and refactored the code for Part 1 in two places:\n",
    "- `Layout`: Introduced the `crowded` attribute; it had been an inline literal `4`. Also made `deltas` an attribute.\n",
    "- `next_generation`: Changed `Layout(seats)` to  `type(self)(seats)`.\n",
    "\n",
    "There was more refactoring and less reuse in Part 2 than I would have liked, but I don't feel like I made bad choices in Part 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 12: Rain Risk \n",
    "\n",
    "Another problem involving interpreting a kind of assembly language, with navigation instructions for a ship. \n",
    "\n",
    "1. Figure out where the navigation instructions lead. What is the Manhattan distance between that location and the ship's starting position?\n",
    "2. Figure out where the navigation instructions *actually* lead, with the updated interpretation. What is the Manhattan distance between that location and the ship's starting position?\n",
    "\n",
    "The difference between Part 1 and Part 2 comes down to the initial value of the heading/waypoint, and whether the N/E/W/S commands alter the location or the waypoint. Everything else is the same between the two parts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "in12: List[Instruction] = data(12, lambda line: (line[0], int(line[1:])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "Point = Heading = Tuple[int, int]\n",
    "\n",
    "directions = dict(N=(0, 1), E=(1, 0), S=(0, -1), W=(-1, 0))\n",
    "\n",
    "def navigate(instructions, loc=(0, 0), heading=directions['E']) -> Point:\n",
    "    \"Follow instructions to change ship's loc and heading; return final loc.\"\n",
    "    for op, n in instructions:\n",
    "        if   op == 'R': heading = turn(n, *heading)\n",
    "        elif op == 'L': heading = turn(-n, *heading)\n",
    "        elif op == 'F': loc = go(n, *loc, *heading)\n",
    "        else:           loc = go(n, *loc, *directions[op])\n",
    "    return loc\n",
    "\n",
    "def turn(degrees, x, y) -> Heading:\n",
    "    \"Turn `degrees` from the current (x, y) heading.\"\n",
    "    return (x, y) if degrees % 360 == 0 else turn(degrees - 90, y, -x)\n",
    "            \n",
    "def go(n, x, y, dx, dy) -> Point: \n",
    "    \"Go n steps in the (dx, dy) direction from (x, y).\"\n",
    "    return (x + n * dx, y + n * dy)\n",
    "\n",
    "def manhatten_distance(point) -> int: return sum(map(abs, point))\n",
    "\n",
    "def day12_1(instructions): return manhatten_distance(navigate(instructions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "def navigate2(instructions, loc=(0, 0), way=(10, 1)) -> Point:\n",
    "    \"Follow updated instructions to change ship's loc and waypoint; return final loc.\"\n",
    "    for op, n in instructions:\n",
    "        if   op == 'R': way = turn(n, *way)\n",
    "        elif op == 'L': way = turn(-n, *way)\n",
    "        elif op == 'F': loc = go(n, *loc, *way)\n",
    "        else:           way = go(n, *way, *directions[op])\n",
    "    return loc\n",
    "\n",
    "def day12_2(instructions): return manhatten_distance(navigate2(instructions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[439, 12385]"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(12, 439, 12385)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 13: Shuttle Search\n",
    "\n",
    "A bus with ID *d* leaves the terminal at times 0, *d*, 2*d*, 3*d*, ... You are given bus IDs and an earliest time you can leave.\n",
    "1. What is the ID of the earliest bus you can take, multiplied by the number of minutes you'll need to wait for that bus?\n",
    "2. What is the earliest timestamp such that all of the listed bus IDs depart at offsets matching their positions in the list?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 0\n",
    "in13: Tuple[ID] = (29,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,577,\n",
    "    x,x,x,x,x,x,x,x,x,x,x,x,13,17,x,x,x,x,19,x,x,x,23,x,x,x,x,x,x,x,601,x,x,x,x,x,x,\n",
    "    x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day13_1(ids, start=1000001):\n",
    "    \"Find the id of the earliest bus after start; return id * wait.\"\n",
    "    ids = set(ids) - {x}\n",
    "    id  = min(ids, key=lambda id: wait(id, start))\n",
    "    return id * wait(id, start)\n",
    "\n",
    "def wait(id, t): \n",
    "    \"How long you have to wait from t for bus id.\"\n",
    "    return 0 if t % id == 0 else id - t % id"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a brute-force solution for Part 2 that works for the simple test cases:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day13_2(ids):\n",
    "    \"Find the time where all the buses arrive at the right offsets.\"\n",
    "    schedule = {t: id for t, id in enumerate(ids) if id != x}\n",
    "    step = schedule[0]\n",
    "    return first(t for t in range(0, sys.maxsize, step) \n",
    "                 if all(wait(schedule[i], t) == i for i in schedule))\n",
    "\n",
    "assert day13_2((7,13,x,x,59,x,31,19)) == 1068781\n",
    "assert day13_2((1789,37,47,1889)) == 1202161486"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, it is clear this will be too slow for the real input data. Instead of looking at every multiple of the first number, I'll incrementally update the `step` as we go through the numbers. Out of all the puzzles so far, this is the one I had to think most carefully about. For each bus id, we want to find a time where we get that id right, then step the time by a multiple of all the ids encountered so far:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[174, 780601154795940]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def day13_2(ids):\n",
    "    \"Find the time where all the buses arrive at the right offsets.\"\n",
    "    time = 0\n",
    "    step = 1\n",
    "    schedule = {t: id for t, id in enumerate(ids) if id != x}\n",
    "    for t in schedule:\n",
    "        while wait(schedule[t], time + t):\n",
    "            time += step\n",
    "        step *= schedule[t]\n",
    "    return time\n",
    "\n",
    "do(13, 174, 780601154795940)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 14: Docking Data\n",
    "\n",
    "Another \"interpret assembly code\" puzzle, with two different versions of the instructions (which I won't describe here).\n",
    "\n",
    "1. Execute the initialization program. What is the sum of all values left in memory after it completes?\n",
    "2. Execute the initialization program using an emulator for a version 2 decoder chip. What is the sum of all values left in memory after it completes?\n",
    "\n",
    "A *mask* is a bit string but with three possible values at each position, 01X. I could make it into two bitstrings, but I choose to leave it as a `str`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_docking(line: str) -> tuple:\n",
    "    \"Parse 'mask = XX10' to ('mask', 'XX10') and 'mem[8] = 11' to (8, 11)\"\n",
    "    if line.startswith('mask'):\n",
    "        return ('mask', line.split()[-1])\n",
    "    else:\n",
    "        return ints(line)\n",
    "\n",
    "in14 = data(14, parse_docking)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "Memory = Dict[int, int]\n",
    "\n",
    "def run_docking(program) -> Memory:\n",
    "    \"Execute the program and return memory.\"\n",
    "    mask = bin36(0)\n",
    "    mem  = defaultdict(int)\n",
    "    for addr, val in program:\n",
    "        if addr == 'mask':\n",
    "            mask = val\n",
    "        else:\n",
    "            mem[addr] = int(cat(m if m in '01' else v\n",
    "                                for m, v in zip(mask, bin36(val))),\n",
    "                            base=2)\n",
    "    return mem\n",
    "\n",
    "def bin36(i) -> str: return f'{i:036b}'\n",
    "\n",
    "assert bin36(255) == '000000000000000000000000000011111111'\n",
    "\n",
    "def day14_1(program): return sum(run_docking(program).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day14_2(program): return sum(run_docking2(program).values())\n",
    "    \n",
    "def run_docking2(program) -> Memory:\n",
    "    \"Execute the program using version 2 instructions and return memory.\"\n",
    "    mask = bin36(0)\n",
    "    mem  = defaultdict(int)\n",
    "    for addr, val in program:\n",
    "        if addr == 'mask':\n",
    "            mask = val\n",
    "        else:\n",
    "            addr = cat(a if m == '0' else '1' if m == '1' else '{}'\n",
    "                       for m, a in zip(mask, bin36(addr)))\n",
    "            for bits in product('01', repeat=addr.count('{')):\n",
    "                mem[int(addr.format(*bits), base=2)] = val\n",
    "    return mem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[11884151942312, 2625449018811]"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(14, 11884151942312, 2625449018811)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 15: Rambunctious Recitation\n",
    "\n",
    "This puzzle involves a game where players speak a new number each turn, based on previous numbers.\n",
    "\n",
    "1. Given your starting numbers, what will be the 2020th number spoken?\n",
    "2. Given your starting numbers, what will be the 30,000,000th number spoken?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "in15 = 10,16,6,0,1,17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day15_1(starting: Tuple[int], nth=2020) -> int:\n",
    "    \"Return the nth (1-based) number spoken.\"\n",
    "    last = starting[-1]\n",
    "    # `spoken` is a mapping of {number: turn_when_last_spoken}\n",
    "    spoken = defaultdict(int, {n: t for t, n in enumerate(starting[:-1])})\n",
    "    for t in range(len(starting), nth):\n",
    "        new = 0 if last not in spoken else t - 1 - spoken[last]\n",
    "        spoken[last] = t - 1\n",
    "        last = new\n",
    "    return last\n",
    "    \n",
    "assert day15_1((0, 3, 6), 2020) == 436"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2 involves no changes, but looks for the 30 millionth number. If it had been 3 million, I'd think \"no problem!\" If it had been 30 billion, I'd think \"I need a more efficient solution!\" As it is, I'll run it and see how long it takes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day15_2(starting): return day15_1(starting, nth=30_000_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 11.7 s, sys: 330 ms, total: 12 s\n",
      "Wall time: 12.2 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[412, 243]"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time do(15, 412, 243)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's reasonable; I won't bother trying to find a more efficient approach."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 16: Ticket Translation\n",
    "\n",
    "1. Consider the validity of the nearby tickets you scanned. What is the sum of the values that are are not valid for any field?\n",
    "2. Discard invalid tickets. Use the remaining valid tickets to determine which field is which. Look for the six fields on your ticket that start with the word departure. What do you get if you multiply those six values together?\n",
    "\n",
    "First parse the input file, introducing the class `TicketData` to hold the three parts of the input file (the fields, your ticket, and nearby tickets), and the class `Sets` for a tuple of ranges or other set-like objects, so that we can easily test a number is an element of any one of a number of possibilities. For Part 1, just go through the ticket values and see which values are not in any range. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "TicketData = namedtuple('TicketData', 'fields, your, nearby')\n",
    "\n",
    "Ticket = ints # A ticket is a tuple of ints\n",
    "\n",
    "class Sets(tuple):\n",
    "    \"A tuple of set-like objects (such as ranges); supports `in`.\"\n",
    "    def __contains__(self, item): return any(item in s for s in self)\n",
    "    \n",
    "def parse_ticket_sections(fieldstr: str, your: str, nearby: str) -> TicketData:\n",
    "    fields = dict(map(parse_ticket_line, fieldstr))\n",
    "    return TicketData(fields=fields, \n",
    "                      your=Ticket(your[1]), \n",
    "                      nearby=[Ticket(line) for line in nearby[1:]])\n",
    "\n",
    "def parse_ticket_line(line: str) -> Tuple[str, Sets]:\n",
    "    \"Parse 'row: 10-20 or 30-40' to ('row', Sets((range(10, 21), range(30, 41)))).\"\n",
    "    field = line.split(':')[0]\n",
    "    a, b, c, d = ints(line.replace('-', ' '))\n",
    "    return field, Sets((range(a, b + 1), range(c, d + 1)))\n",
    "\n",
    "in16 = parse_ticket_sections(*data(16, str.splitlines, sep='\\n\\n'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day16_1(ticket_data):\n",
    "    \"The sum of the invalid entries in the nearby tickets.\"\n",
    "    ranges = Sets(ticket_data.fields.values())\n",
    "    return sum(v for ticket in ticket_data.nearby for v in ticket\n",
    "               if v not in ranges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, we're playing a simplified variant of Sudoku:\n",
    "- First find the valid tickets. \n",
    "- Then start with the assumption that any field name is `possible` for any index number in the tickets.\n",
    "- Determine what field names are invalid for what ticket index numbers.\n",
    "- Remove the field name from the possibilities for that index, and\n",
    "   - If there is only one possible field name left, then remove it from all other index positions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valid_ticket(ticket, ranges) -> bool: return all(v in ranges for v in ticket)\n",
    "    \n",
    "def decode_tickets(ticket_data) -> Dict[str, int]:\n",
    "    \"Return a mapping of {field_name: field_number} (index into ticket).\"\n",
    "    fields, your, nearby = ticket_data\n",
    "    ranges   = Sets(ticket_data.fields.values())\n",
    "    valid    = [t for t in nearby + [your] if valid_ticket(t, ranges)]\n",
    "    possible = [set(fields) for _ in range(len(your))]\n",
    "    while any(len(p) > 1 for p in possible):\n",
    "        for field_name, i in invalid_fields(valid, fields):\n",
    "            possible[i] -= {field_name}\n",
    "            if len(possible[i]) == 1:\n",
    "                eliminate_others(possible, i)\n",
    "    return {field: i for i, [field] in enumerate(possible)}\n",
    "\n",
    "def invalid_fields(valid, fields) -> Iterable[Tuple[str, int]]:\n",
    "    \"Yield (field_name, field_number) for all invalid fields.\"\n",
    "    return ((field_name, i) for ticket in valid for i in range(len(ticket))\n",
    "            for field_name in fields \n",
    "            if ticket[i] not in fields[field_name])\n",
    "\n",
    "def eliminate_others(possible, i):\n",
    "    \"Eliminate possible[i] from all other possible[j].\"\n",
    "    for j in range(len(possible)):\n",
    "        if j != i:\n",
    "            possible[j] -= possible[i]\n",
    "\n",
    "def day16_2(ticket_data):\n",
    "    \"The product of the 6 fields that start with 'departure'.\"\n",
    "    code = decode_tickets(ticket_data)\n",
    "    return prod(ticket_data.your[code[field]] \n",
    "                for field in code if field.startswith('departure'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[21071, 3429967441937]"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 17: Conway Cubes\n",
    "\n",
    "Now we are explicitly playing *Life*, but in three dimensions not two. I've coded this before; I'll adapt my [old version](Life.ipynb) to three dimensions. My implementation represents a generation as the set of active cell coordinates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "in17: Picture = '''\n",
    "##.#....\n",
    "...#...#\n",
    ".#.#.##.\n",
    "..#.#...\n",
    ".###....\n",
    ".##.#...\n",
    "#.##..##\n",
    "#.####..'''.strip().splitlines()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[291, 1524]"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "### New - Thu\n",
    "\n",
    "Cell  = Tuple[int,...]\n",
    "\n",
    "def day17_1(picture, n=6, d=3):\n",
    "    \"How many cells are active in the nth generation?\"\n",
    "    return len(life(parse_cells(picture, d), n))\n",
    "\n",
    "def parse_cells(picture, d=3, active='#') -> Set[Cell]:\n",
    "    \"Convert a 2-d picture into a set of d-dimensional active cells.\"\n",
    "    return {(x, y, *(0,) * (d - 2))\n",
    "            for (y, row) in enumerate(picture)\n",
    "            for x, cell in enumerate(row) if cell is active}\n",
    "\n",
    "def life(cells, n) -> Set[Cell]:\n",
    "    \"Play n generations of Life.\"\n",
    "    for g in range(n):\n",
    "        cells = next_generation(cells)\n",
    "    return cells\n",
    "\n",
    "def next_generation(cells) -> Set[Cell]:\n",
    "    \"\"\"The set of live cells in the next generation.\"\"\"\n",
    "    return {cell for cell, count in neighbor_counts(cells).items()\n",
    "            if count == 3 or (count == 2 and cell in cells)}\n",
    "\n",
    "@lru_cache()\n",
    "def cell_deltas(d: int): \n",
    "    return set(filter(any, product((-1, 0, +1), repeat=d)))\n",
    "\n",
    "def neighbor_counts(cells) -> Dict[Cell, int]:\n",
    "    \"\"\"A Counter of the number of live neighbors for each cell.\"\"\"\n",
    "    return Counter(flatten(map(neighbors, cells)))\n",
    "\n",
    "def neighbors(cell) -> List[cell]:\n",
    "    \"All adjacent neighbors of cell in three dimensions.\"\n",
    "    return [tuple(map(operator.add, cell, delta)) \n",
    "            for delta in cell_deltas(len(cell))]\n",
    "\n",
    "def day17_2(picture): return day17_1(picture, d=4)\n",
    "\n",
    "do(17, 291, 1524)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2 asks us to move to 4 dimensions. I'll generalize the previous code to work in 3 or 4 dimensions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "ename": "IndentationError",
     "evalue": "unexpected indent (<ipython-input-72-c39437b1efce>, line 10)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-72-c39437b1efce>\"\u001b[0;36m, line \u001b[0;32m10\u001b[0m\n\u001b[0;31m    \"How many cells are active in the nth generation in a d-dimensional world?\"\u001b[0m\n\u001b[0m    ^\u001b[0m\n\u001b[0;31mIndentationError\u001b[0m\u001b[0;31m:\u001b[0m unexpected indent\n"
     ]
    }
   ],
   "source": [
    "def parse_cells(picture, d=3, active='#') -> Set[Cell]:\n",
    "    \"Convert a 2-d picture into a set of d-dimensional active cells.\"\n",
    "    return {(x, y, *(d - 2) * (0,) )\n",
    "            for (y, row) in enumerate(picture)\n",
    "            for x, cell in enumerate(row) if cell is active}\n",
    "\n",
    "def day17_1(picture): return day17_2(picture, n=6, d=3)\n",
    "\n",
    "\n",
    "    \"How many cells are active in the nth generation in a d-dimensional world?\"\n",
    "    cells = parse_cells(picture, d=d)\n",
    "    for g in range(n):\n",
    "        cells = next_generation(cells)\n",
    "    return len(cells)\n",
    "\n",
    "deltas = [set(product((-1, 0, +1), repeat=d)) - {(0,) * d}\n",
    "          for d in range(5)]\n",
    "\n",
    "def neighbors(cell) -> List[cell]:\n",
    "    \"All adjacent neighbors of cell in all dimensions.\"\n",
    "    return [tuple(map(operator.add, cell, delta)) \n",
    "            for delta in deltas[len(cell)]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 18: Operation Order\n",
    "\n",
    "At first I thought I could just apply `eval` to each line, but alas, the operation order is non-standard. I could have used a parsing framework, but I decided to do it all from scratch.\n",
    "\n",
    "1. All operations are done left-to-right. Evaluate the expression on each line of the homework; what is the sum of the resulting values?\n",
    "2. Addition is done before multiplication. What do you get if you add up the results of evaluating the homework problems using these new rules?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_expr(line) -> tuple: \n",
    "    \"Parse an expression: '2 + 3 * 4' => (2, '+', 3, '*', 4).\"\n",
    "    return ast.literal_eval(re.sub('([+*])', r\",'\\1',\", line))\n",
    "\n",
    "in18 = data(18, parse_expr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operators = {'+': operator.add, '*': operator.mul}\n",
    "\n",
    "def evaluate(expr) -> int:\n",
    "    \"Evaluate an expression under left-to-right rules.\"\n",
    "    if isinstance(expr, int):\n",
    "        return expr\n",
    "    else:\n",
    "        a, op, b, *rest = expr\n",
    "        x = operators[op](evaluate(a), evaluate(b))\n",
    "        return x if not rest else evaluate((x, *rest))\n",
    "    \n",
    "def day18_1(exprs): return sum(map(evaluate, exprs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate2(expr) -> int:\n",
    "    \"Evaluate an expression under addition-first rules.\"\n",
    "    if isinstance(expr, int):\n",
    "        return expr\n",
    "    elif '*' in expr:\n",
    "        i = expr.index('*')\n",
    "        return evaluate2(expr[:i]) * evaluate2(expr[i + 1:])\n",
    "    else:\n",
    "        return sum(evaluate2(x) for x in expr if x is not '+')\n",
    "    \n",
    "def day18_2(exprs): return sum(map(evaluate2, exprs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "do(18, 3885386961962, 112899558798666)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 19\n",
    "\n",
    "A grep-like pattern matcher, where a *message* is a sequence of characters (all `'a'` or `'b'`) and a *pattern* I will represent as a list of items, where each item can be a character, a rule number (which is associated with a pattern), or a *choice* of two or more patterns. The input has two sections: first \"rule number: pattern\" lines, then messages, one per line. \n",
    "\n",
    "I will define `match` to return the remaining string in the message if part or all of the message is matched, or `None` if it fails.\n",
    "\n",
    "1. How many messages completely match rule 0?\n",
    "2. Two of the rules are wrong. After updating rules 8 and 11, how many messages completely match rule 0?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "Message = str   # A string we are trying to match, e.g. \"ababba\"\n",
    "Choice  = tuple # A choice of any of the elements, e.g. Choice(([5, 6], [7]))\n",
    "Pattern = List[Union[Char, int, Choice]]\n",
    "\n",
    "def parse_messages(rules, messages) -> Tuple[Dict[int, Pattern], List[Message]]:\n",
    "    \"Return a dict of {rule_number: pattern} and a list of messages.\"\n",
    "    return dict(map(parse_rule, rules)), messages\n",
    "\n",
    "def parse_rule(line):\n",
    "    \"Parse '1: 2 3' => (1, [2, 3]); '4: 5, 6 | 7' => (4, Choice(([5, 6], [7]))).\"\n",
    "    n, *rhs = atoms(line, ignore='[:\"]')\n",
    "    if '|' in rhs:\n",
    "        i = rhs.index('|')\n",
    "        rhs = [Choice((rhs[:i], rhs[i + 1:]))]\n",
    "    return n, rhs\n",
    "                  \n",
    "in19 = parse_messages(*data(19, str.splitlines, sep='\\n\\n'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day19_1(inputs):\n",
    "    \"How many messages completely match rule 0?\"\n",
    "    rules, messages = inputs\n",
    "    return quantify(match(rules[0], msg, rules) == '' \n",
    "                    for msg in messages)\n",
    "\n",
    "def match(pat, msg, rules) -> Optional[Message]:\n",
    "    \"If a prefix of msg matches pat, return remaining str; else None\"\n",
    "    if pat and not msg:              # Failed to match whole pat\n",
    "        return None \n",
    "    elif not pat:                    # Matched whole pat\n",
    "        return msg \n",
    "    elif pat[0] == msg[0]:           # Matched first char; continue\n",
    "        return match(pat[1:], msg[1:], rules)\n",
    "    elif isinstance(pat[0], int):    # Look up the rule number \n",
    "        return match(rules[pat[0]] + pat[1:], msg, rules)\n",
    "    elif isinstance(pat[0], Choice): # Match any of the choices\n",
    "        for choice in pat[0]:\n",
    "            m = match(choice + pat[1:], msg, rules)\n",
    "            if m is not None:\n",
    "                return m\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, I coded the two changed rules by hand, taking care to avoid infinite left-recursion:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day19_2(inputs):\n",
    "    \"How many messages completely match rule 0, with new rules 8 and 11?\"\n",
    "    rules, messages = inputs\n",
    "    rules2 = {**rules, 8: [42, maybe(8)], 11: [42, maybe(11), 31]}\n",
    "    return day19_1((rules2, messages))\n",
    "             \n",
    "def maybe(n): return Choice(([], [n]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "do(19, 190, 311)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 20: Jurassic Jigsaw\n",
    "\n",
    "You are given a bunch of picture tiles, which can be put together to form a larger picture, where the edges of tiles match their neighbors.\n",
    "\n",
    "1. Assemble the tiles into an image. What do you get if you multiply together the IDs of the four corner tiles?\n",
    "2. In the assembled image, how many `#` pixels are not part of a sea monster (which is a specific shape)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def jigsaw_tiles(sections: List[List[str]]) -> Dict[ID, Picture]:\n",
    "    \"Return a dict of {tile_id: tile_picture}.\"\n",
    "    return {first(ints(header)): tile\n",
    "            for (header, *tile) in sections}\n",
    "    \n",
    "in20 = jigsaw_tiles(data(20, str.splitlines, sep='\\n\\n'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For Part 1, it is guaranteed that \"the outermost edges won't line up with any other tiles,\" but all the inside edges will. We'll define `edge_count` to count how many times an edge appears on any tile (using a `canonical` orientation, because tiles might be flipped). Then the corner tiles are ones that have two edges that have an edge count of 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Edge = str\n",
    "\n",
    "def day20_1(tiles: Dict[ID, Picture]):\n",
    "    \"The product of the ID's of the 4 corner tiles.\"\n",
    "    edge_count = Counter(canonical(e) for id in tiles for e in edges(tiles[id]))\n",
    "    is_outermost = lambda edge: edge_count[canonical(edge)] == 1\n",
    "    is_corner = lambda tile: quantify(edges(tile), is_outermost) == 2\n",
    "    corners = [id for id in tiles if is_corner(tiles[id])]\n",
    "    return prod(corners)\n",
    "     \n",
    "def edges(tile) -> Iterable[Edge]:\n",
    "    \"The 4 edges of a tile.\"\n",
    "    for i in (0, -1): \n",
    "        yield tile[i] # top/bottom\n",
    "        yield cat(row[i] for row in tile) # left/right\n",
    "        \n",
    "def canonical(edge) -> Edge: return min(edge, edge[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "do(20, 15670959891893)   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Holiday preparations kept me from doing Part 2 on the night of the 19th, and unfortunately I didn't feel like coming back to it later: it seemed too tedious for too little reward. And I thought it was inelegant that a solid block of `#` pixels would be considered a sea monster with waves. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Timing\n",
    "\n",
    "Advent of Code [states that each day's puzzle should run in 15-seconds or less](https://adventofcode.com/2020/about)).\n",
    "I met that goal, with only days 11 and 15 taking more than a second. Here's a report, with stars in the first column indicating run times on a logarithmic base-10 scale: zero stars for under 1/100 seconds up to 4 stars for over 10 seconds:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def timing(days=range(1, 26)):\n",
    "    \"Report on timing of `do(day)` for all days.\"\n",
    "    results = []\n",
    "    for day in days:\n",
    "        t0 = time.time()\n",
    "        answers = do(day)\n",
    "        t = time.time() - t0\n",
    "        if answers:\n",
    "            stars = '*' * int(3 + math.log(t, 10))\n",
    "            print(f'{stars:>4} {day:2}: {t:6.3f} sec ⇒ {answers}')\n",
    "\n",
    "%time timing()   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Ingredient = str\n",
    "Allergen   = str\n",
    "Food       = namedtuple('Food', 'I, A') # I for set of ingredients; A for set of allergens\n",
    "\n",
    "def parse_food(line) -> Food:\n",
    "    \"Parse 'xtc wkrp (contains fish, nuts)' => Food({'xtc', 'wkrp'}, {'fish', 'nuts'})\"\n",
    "    ingredients, allergens = line.split('(contains')\n",
    "    return Food(set(atoms(ingredients)), set(atoms(allergens, ignore='[,)]')))\n",
    "\n",
    "in21 = data(21, parse_food)\n",
    "\n",
    "def day21_1(foods):\n",
    "    bad = bad_ingredients(foods)\n",
    "    allergens = set(flatten(bad.values()))\n",
    "    return sum(len(food.I - allergens) for food in foods)\n",
    "\n",
    "def bad_ingredients(foods) -> Dict[Allergen, Set[Ingredient]]:\n",
    "    \"A dict of {allergen: {set_of_ingredients_it_could_be}}\"\n",
    "    # Each allergen is found in exactly one ingredient.\n",
    "    all_I = set(flatten(food.I for food in foods))\n",
    "    all_A = set(flatten(food.A for food in foods))\n",
    "    possible = {a: set(all_I) for a in all_A}\n",
    "    while any(len(possible[a]) > 1 for a in possible):\n",
    "        for food in foods:\n",
    "            for a in food.A:\n",
    "                possible[a] &= food.I\n",
    "                if len(possible[a]) == 1:\n",
    "                    eliminate_others21(possible, a)\n",
    "    return possible\n",
    "\n",
    "def eliminate_others21(possible, a):\n",
    "    \"Eliminate possible[a] from all other allergens.\"\n",
    "    for a2 in possible:\n",
    "        if a2 != a:\n",
    "            possible[a2] -= possible[a]\n",
    "            \n",
    "def day21_2(foods) -> str:\n",
    "    bad = bad_ingredients(in21)\n",
    "    return ','.join(first(g[x]) for x in sorted(g))\n",
    "\n",
    "do(21, 2282, 'vrzkz,zjsh,hphcb,mbdksj,vzzxl,ctmzsr,rkzqs,zmhnj')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 22: Crab Combat \n",
    "\n",
    "The card game *War*.\n",
    "\n",
    "1. Play the small crab in a game of Combat using the two decks you just dealt. What is the winning player's score?\n",
    "\n",
    "Card = int\n",
    "Player = int\n",
    "Deal = Tuple[Card]\n",
    "\n",
    "in22 = ((12, 40, 50, 4, 24, 15, 22, 43, 18, 21, 2, 42, 27, 36, 6, 31, 35, 20, 32, 1, 41, 14, 9, 44, 8), \n",
    "        (30, 10, 47, 29, 13, 11, 49, 7, 25, 37, 33, 48, 16, 5, 45, 19, 17, 26, 46, 23, 34, 39, 28, 3, 38))\n",
    "        \n",
    "def day22_1(deals): return combat_score(combat(deals))\n",
    "\n",
    "def combat_score(deals) -> int:\n",
    "    deal = deals[0] or deals[1]\n",
    "    return dotproduct(deal, reversed(range(1, len(deal) + 1)))\n",
    "    \n",
    "def combat(deals: Tuple[Deal]) -> Tuple[Player, Deal]:\n",
    "    deals = mapt(deque, deals)\n",
    "    while deals[0] and deals[1]:\n",
    "        tops = mapt(deque.popleft, deals)\n",
    "        winner = 0 if  tops[0] > tops[1] else 1\n",
    "        deals[winner].extend(sorted(tops)[::-1])\n",
    "    return deals\n",
    "    \n",
    "def day22_2(deals): return combat_score(recursive_combat(deals))\n",
    "    \n",
    "def recursive_combat(deals) -> Tuple[Deal, Deal]:\n",
    "    \"A game of Recursive Combat\"\n",
    "    printv('recursive game', mapt(len, deals))\n",
    "    assert sum(map(len, deals)) <= 50\n",
    "    previous = set()\n",
    "    P = (0, 1)\n",
    "    while deals[0] and deals[1]:\n",
    "        if sum(mapt(len, deals)) <= 11:\n",
    "            printv('  deals', deals)\n",
    "        if deals in previous:\n",
    "            printv('recursive game ends in repeat')\n",
    "            return (deals[0], ())\n",
    "        previous.add(deals)\n",
    "        tops  = mapt(first, deals)\n",
    "        deals = mapt(rest, deals)\n",
    "        if all(len(deals[p]) >= tops[p] for p in P):\n",
    "            rec = recursive_combat(tuple(deals[p][:tops[p]] for p in P))\n",
    "            winner = 0 if rec[0] else 1\n",
    "        else:\n",
    "            winner = 0 if  tops[0] > tops[1] else 1\n",
    "        def bounty(p): return (tops[winner], tops[1 - winner]) if p == winner else ()\n",
    "        deals = tuple(deals[p] + bounty(p) for p in P)\n",
    "    printv('game ends')\n",
    "    return deals\n",
    "\n",
    "verbose = False\n",
    "n = [0]\n",
    "def printv(*args): \n",
    "    n[0] += 1\n",
    "    #if n[0] > 100: 1/0\n",
    "    verbose and print(*args)\n",
    "\n",
    "#do(22) \n",
    "\n",
    "assert (recursive_combat(((9, 2, 6, 3, 1), (5, 8, 4, 7, 10)))\n",
    "        == ((), (7, 5, 6, 2, 4, 1, 10, 8, 9, 3)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 23: Crab Cups"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Day 23: Crab Cups\n",
    "\n",
    "in23 = '872495136'\n",
    "\n",
    "Cup = int\n",
    "\n",
    "def day23_1(cupstr: str, n=100):\n",
    "    cups = list(map(int, cupstr))\n",
    "    current = cups[0]\n",
    "    for i in range(n):\n",
    "        picked = pickup(cups, current)\n",
    "        dest = destination(cups, current)\n",
    "        place(cups, picked, dest)\n",
    "        current = clockwise(cups, current)\n",
    "    return after(1, cups)\n",
    "\n",
    "def pickup(cups, current) -> List[Cup]:\n",
    "    \"Return the 3 cups clockwise of current; remove them from cups.\"\n",
    "    i = cups.index(current)\n",
    "    picked, cups[i+1:i+4] = cups[i+1:i+4], []\n",
    "    extra = 3 - len(picked)\n",
    "    if extra:\n",
    "        picked += cups[:extra]\n",
    "        cups[:extra] = []\n",
    "    return picked\n",
    "        \n",
    "def destination(cups, current) -> Cup: \n",
    "    \"The cup with label one less than current, or max(cups).\"\n",
    "    return max((c for c in cups if c < current), default=max(cups))\n",
    "\n",
    "def clockwise(cups, current) -> Cup:\n",
    "    \"The cup one clockwise of current.\"\n",
    "    i = cups.index(current)\n",
    "    return cups[(i + 1) % len(cups)]\n",
    "\n",
    "def place(cups, picked, dest):\n",
    "    \"Put `picked` after `dest`\"\n",
    "    i = cups.index(dest) + 1\n",
    "    cups[i:i] = picked\n",
    "    \n",
    "def after(cup, cups) -> int:\n",
    "    \"All the cups after `cup`, in order.\"\n",
    "    i = cups.index(cup) + 1\n",
    "    string = cat(map(str, cups + cups))\n",
    "    return int(string[i:i+len(cups)])\n",
    "    \n",
    "do(23)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "foo = [0,1,2,3,4]\n",
    "foo[0:0] = ['hello', 'world']\n",
    "foo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "in24 = data(24)\n",
    "\n",
    "def day24_1(lines: List[str]):\n",
    "    \"How many tiles are flipped an odd number of times?\"\n",
    "    counts = Counter(map(follow_hex, lines)).values()\n",
    "    return quantify(v % 2 for v in counts)\n",
    "\n",
    "hexdirs = dict(e=(1, 0), w=(-1, 0), ne=(1, -1), sw=(-1, 1), se=(0, 1), nw=(0, -1))\n",
    "\n",
    "def parse_hex(line) -> List[str]: return re.findall('|'.join(hexdirs), line)\n",
    "\n",
    "def follow_hex(line):\n",
    "    x, y = 0, 0\n",
    "    for d in parse_hex(line):\n",
    "        dx, dy = hexdirs[d]\n",
    "        x += dx \n",
    "        y += dy\n",
    "    return (x, y)\n",
    "\n",
    "#####################\n",
    "\n",
    "def day24_2(lines: List[str], days=100):\n",
    "    \"How many tiles are black after 100 days of Life?\"\n",
    "    counts = Counter(map(follow_hex, lines))\n",
    "    blacks = {c for c in counts if counts[c] % 2}\n",
    "    with binding(next_generation=next_generation24, cell_deltas=cell_deltas24):\n",
    "        return len(life(blacks, 100))\n",
    "\n",
    "def next_generation24(cells) -> Set[Cell]:\n",
    "    \"\"\"The set of live cells in the next generation.\"\"\"\n",
    "    counts = neighbor_counts(cells)\n",
    "    return ({c for c in cells if counts[c] in (1, 2)} |\n",
    "            {c for c in counts if c not in cells and counts[c] == 2})\n",
    "\n",
    "@lru_cache()\n",
    "def cell_deltas24(d: int): \n",
    "    return set(hexdirs.values())\n",
    "    return set(filter(any, product((-1, 0, +1), repeat=d)))\n",
    "\n",
    "do(24)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cell_deltas(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test = Counter(mapt(follow_hex, '''sesenwnenenewseeswwswswwnenewsewsw\n",
    "neeenesenwnwwswnenewnwwsewnenwseswesw\n",
    "seswneswswsenwwnwse\n",
    "nwnwneseeswswnenewneswwnewseswneseene\n",
    "swweswneswnenwsewnwneneseenw\n",
    "eesenwseswswnenwswnwnwsewwnwsene\n",
    "sewnenenenesenwsewnenwwwse\n",
    "wenwwweseeeweswwwnwwe\n",
    "wsweesenenewnwwnwsenewsenwwsesesenwne\n",
    "neeswseenwwswnwswswnw\n",
    "nenwswwsewswnenenewsenwsenwnesesenew\n",
    "enewnwewneswsewnwswenweswnenwsenwsw\n",
    "sweneswneswneneenwnewenewwneswswnese\n",
    "swwesenesewenwneswnwwneseswwne\n",
    "enesenwswwswneneswsenwnewswseenwsese\n",
    "wnwnesenesenenwwnenwsewesewsesesew\n",
    "nenewswnwewswnenesenwnesewesw\n",
    "eneswnwswnwsenenwnwnwwseeswneewsenese\n",
    "neswnwewnwnwseenwseesewsenwsweewe\n",
    "wseweeenwnesenwwwswnew'''.splitlines()))\n",
    "test2 = {c for c in test if test[c] % 2}\n",
    "len(test2)\n",
    "test2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "{i: len(life(test2, i)) for i in range(7)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from contextlib import contextmanager\n",
    "\n",
    "@contextmanager\n",
    "def binding(**kwds):\n",
    "    \"Bind global variables in a context; revert to old values on exit.\"\n",
    "    temp = {k: globals()[k] for k in kwds}\n",
    "    try:\n",
    "        globals().update(kwds)\n",
    "        yield\n",
    "    finally:\n",
    "        globals().update(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "foo = 42\n",
    "print(foo)\n",
    "with bind(foo=1):\n",
    "    print(foo)\n",
    "    1/0\n",
    "print(foo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "foo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "in25 = 1965712, 19072108\n",
    "\n",
    "def transform(subj) -> Iterator[int, int]: \n",
    "    val = 1\n",
    "    for i in range(1, sys.maxsize):\n",
    "        val = (val * subj) % 20201227\n",
    "        yield i, val\n",
    "        \n",
    "def nth_transform(subj, n):  return first(val for i, val in transform(subj) if i == n)\n",
    "def transform_to(subj, val): return first(i   for i, val in transform(subj) if val == final)\n",
    "\n",
    "def day25_1(keys):\n",
    "    loopsize = transform_to(7, keys[0])\n",
    "    return nth_transform(keys[1], loopsize)\n",
    "\n",
    "do(25, 16881444)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "last(transform(17807724, 8)), last(transform(5764801, 11))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "import re\n",
    "\n",
    "def words(text): return re.findall(\"[a-z']+\", text.lower())\n",
    "\n",
    "def top(lyrics: str, n=10):\n",
    "    \"Top n most common words in lyrics.\"\n",
    "    return Counter(words(lyrics)).most_common(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "top('''Na na na na, na na na na, hey hey, goodbye\n",
    "He'll never love you, the way that I love you\n",
    "'Cause if he did, no no, he wouldn't make you cry\n",
    "He might be thrillin' baby but a-my love\n",
    "(My love, my love)\n",
    "So dog-gone willin', so kiss him\n",
    "(I wanna see you kiss him, wanna see you kiss him)\n",
    "Go on and kiss him goodbye, now\n",
    "Na na na na, hey hey, goodbye\n",
    "Na na na na, na na na na, hey hey, goodbye\n",
    "Listen to me now\n",
    "He's never near you to comfort and cheer you\n",
    "When all those sad tears are fallin' baby from your eyes\n",
    "He might be thrillin' baby but a-my love\n",
    "(My love, my love)\n",
    "So dog-gone willin', so kiss him\n",
    "(I wanna see you kiss him, I wanna see you kiss him)\n",
    "Go on and kiss him goodbye, na na na na, na na na\n",
    "Na na na na, hey hey, goodbye\n",
    "Hey hey, goodbye\n",
    "Na na na na, na na na na, hey hey, goodbye\n",
    "Na na na na, na na na na, hey hey, goodbye\n",
    "Na na na na, na na na na, hey hey, goodbye\n",
    "Hey hey, goodbye\n",
    "Na na na na, na na na na, hey hey, goodbye\n",
    "Na na na na, na na na na, hey hey, goodbye\n",
    "Na na na na, na na na na, hey hey, goodbye\n",
    "Hey hey, goodbye\n",
    "Na na na na, na na na na, hey hey, goodbye\n",
    "Na na na na, na na na na, hey hey, goodbye\n",
    "Na na na na, na na na na, hey hey, goodbye''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "top('''Ain't no sunshine when she's gone\n",
    "It's not warm when she's away\n",
    "Ain't no sunshine when she's gone\n",
    "And she's always gone too long\n",
    "Anytime she's goes away\n",
    "Wonder this time where she's gone\n",
    "Wonder if she's gone to stay\n",
    "Ain't no sunshine when she's gone\n",
    "And this house just ain't no home\n",
    "Anytime she goes away\n",
    "And I know, I know, I know, I know\n",
    "I know, I know, I know, I know, I know\n",
    "I know, I know, I know, I know, I know\n",
    "I know, I know, I know, I know, I know\n",
    "I know, I know, I know, I know, I know\n",
    "I know, I know\n",
    "Hey I oughta leave young thing alone\n",
    "But ain't no sunshine when she's gone, woh woh\n",
    "Ain't no sunshine when she's gone\n",
    "Only darkness every day\n",
    "Ain't no sunshine when she's gone\n",
    "And this house just ain't no home\n",
    "Anytime she goes away\n",
    "Anytime she goes away\n",
    "Anytime she goes away\n",
    "Anytime she goes away''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "top('''Duke, Duke, Duke, Duke of Earl\n",
    "Duke, Duke, Duke of Earl\n",
    "Duke, Duke, Duke of Earl\n",
    "Duke, Duke, Duke of Earl\n",
    "Duke, Duke, Duke of Earl\n",
    "Duke, Duke, Duke of Earl\n",
    "Duke, Duke, Duke of Earl\n",
    "Duke, Duke, Duke of Earl\n",
    "As I walk through this world\n",
    "Nothing can stop the Duke of Earl\n",
    "And-a you, you are my girl\n",
    "And no one can hurt you, oh no\n",
    "Yes-a, I, oh I'm gonna love you, oh oh\n",
    "Come on let me hold you darlin'\n",
    "'Cause I'm the Duke of Earl\n",
    "So hey yea yea yeah\n",
    "And when I hold you\n",
    "You'll be my Duchess, Duchess of Earl\n",
    "We'll walk through my dukedom\n",
    "And a paradise we will share\n",
    "Yes-a, I, oh I'm gonna love you, oh oh\n",
    "Nothing can stop me now\n",
    "'Cause I'm the Duke of Earl\n",
    "So hey yeah yeah yeah\n",
    "Well, I, oh I'm gonna love you, oh oh\n",
    "Nothing can stop me now\n",
    "'Cause I'm the Duke of Earl\n",
    "So hey yeah yeah yeah''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cut(times=15):\n",
    "    nums = {1}\n",
    "    for _ in range(times):\n",
    "        nums |= {n + 3 for n in nums}\n",
    "    return nums\n",
    "    \n",
    "cut()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "'''Her true love, Marian, has issued a challenge. Robin must fire as many arrows as she can, such that each arrow is closer to the center of the target than the previous arrow. For example, if Robin fires three arrows, each closer to the center than the previous, but the fourth arrow is farther than the third, then she is done with the challenge and her score is four.'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "arrow()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "from typing import Iterable\n",
    "from statistics import mean\n",
    "Point = complex\n",
    "\n",
    "def sample_circle() -> Point:\n",
    "    \"\"\"Uniform sampling of a point within a circle of radius 1, via rejection.\"\"\"\n",
    "    point = Point(random.random(), random.random())\n",
    "    return point if abs(point) <= 1 else sample_circle()\n",
    "            \n",
    "def sample_arrows() -> Iterable[Point]:\n",
    "    \"\"\"Uniform rejection sampling of a point within a circle of radius 1.\"\"\"\n",
    "    arrows = []\n",
    "    while True:\n",
    "        arrows.append(abs(sample_arrow()))\n",
    "        if arrows != sorted(arrows, reverse=True):\n",
    "            return arrows        \n",
    "        \n",
    "%time mean(len(sample_arrows()) for _ in range(1_000_000))\n",
    "\n",
    "That answer is approximately $e$ (2.718281828...). Could $e$ be the exact answer? The Taylor series for $e^x$ is as follows:\n",
    "\n",
    "   $$e^x = \\sum_{i=0}^{\\infty} x^n / n! $$\n",
    "   \n",
    "and thus\n",
    "\n",
    "   $$e = e^1 = \\sum_{i=0}^{\\infty} 1 / n! $$\n",
    "   \n",
    "That makes so much sense now! I worked hard to make sure that we were sampling points uniformly across all the area of the circle\n",
    "\n",
    "def sample_arrows2() -> Iterable[Point]:\n",
    "    \"\"\"Uniform rejection sampling of a point within a circle of radius 1.\"\"\"\n",
    "    arrows = []\n",
    "    while True:\n",
    "        arrows.append(abs(int(10 * abs(sample_arrow()))))\n",
    "        if not monotonic(arrows):\n",
    "            return arrows  \n",
    "        \n",
    "def monotonic(items): \n",
    "    pairs = (items[i:i + 2] for i in range(len(items) - 1))\n",
    "    return all(a > b for a, b in pairs)   \n",
    "\n",
    "%time mean(len(sample_arrows2()) for _ in range(1_000_000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That answer is approximately $e$ (2.718281828...). Could $e$ be the exact answer? The Taylor series for $e^x$ is as follows:\n",
    "\n",
    "   $$e^x = \\sum_{i=0}^{\\infty} x^n / n! $$\n",
    "   \n",
    "and thus\n",
    "\n",
    "   $$e = e^1 = \\sum_{i=0}^{\\infty} 1 / n! $$\n",
    "   \n",
    "That makes so much sense now! I worked hard to make sure that we were sampling points uniformly across all the area of the circle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from statistics import mean\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 100\n",
    "\n",
    "def candidates(N): return [random.randrange(1000) for _ in range(N)]\n",
    "\n",
    "def hiring(candidates, test_amount=math.exp(-1), ratio=1.0):\n",
    "    i = round(test_amount * len(candidates))\n",
    "    bar = max(candidates[:i])\n",
    "    return next((c for c in candidates[i:] if c > bar), candidates[-1])\n",
    "\n",
    "def score(test_amount=math.exp(-1), ratio=1.0, trials=10_000):\n",
    "    return mean(hiring(candidates(N), test_amount, ratio) for _ in range(trials))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "X = [i / 1000 for i in range(10, 500, 10)]\n",
    "Y = [score(test_amount=x, trials=3000) for x in X]\n",
    "plt.plot(X, Y, 'o-')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ants(n, trials=10_000): \n",
    "    return mean(max(random.random() for a in range(n)) \n",
    "                for t in range(trials))\n",
    "\n",
    "X = range(1, 100)\n",
    "Y = [ants(x) for x in X]\n",
    "plt.plot(X, Y, '.:')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[f'{n:3d}: {abs(ants(n, 100_000) - n/(n+1)):.4f} ' for n in range(1, 20)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lingo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "from statistics import mean\n",
    "from collections import defaultdict\n",
    "\n",
    "def read_dict(text):\n",
    "    W = re.findall(r'^[A-Z]{5}$', text, re.M)\n",
    "    D = defaultdict(list)\n",
    "    for w in W:\n",
    "        D[w[0]].append(w)\n",
    "    return W, D\n",
    "\n",
    "alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "\n",
    "W, D = read_dict(open('enable1.txt').read().upper())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(W), {L: len(D[L]) for L in alphabet}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unique_guesses(n=4):\n",
    "    random.shuffle(W)\n",
    "    letters, words = set(), []\n",
    "    for word in W:\n",
    "        S = set(word)\n",
    "        if len(S) == 5 and letters.isdisjoint(S):\n",
    "            words.append(word)\n",
    "            letters |= S\n",
    "            if len(words) == n:\n",
    "                return words\n",
    "    return unique_guesses(n, W)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[unique_guesses() for _ in range(10)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def possibles(guesses, secret):\n",
    "    L = secret[0]\n",
    "    return [w for w in W[L] if feasible(w, guesses)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reply(guess, secret):\n",
    "    regex, ins, outs = '', set(), set()\n",
    "    for g, s in list(zip(guess, secret)):\n",
    "        if g == s or g in secret:\n",
    "            regex += (g if g == s else '.')\n",
    "            ins.add(g)\n",
    "            secret = secret.replace(g, '', 1)\n",
    "        else:\n",
    "            regex += '.'\n",
    "            outs.add(g)\n",
    "    return regex, ins, outs\n",
    "\n",
    "def replies(guesses, secret):\n",
    "    return [reply(guess, secret) for guess in guesses]\n",
    "\n",
    "def consolidate(replies):\n",
    "    exacts = ''.join(max(reg[i] for reg, _, _ in replies) for i in range(5))\n",
    "    if '.' not in exacts:\n",
    "        return exacts, set(exacts)\n",
    "    letters = set().union(*(L for _, L, _ in replies))\n",
    "    return exacts, letters\n",
    "\n",
    "def average_score(guesses):\n",
    "    return mean(score(guesses, L) for L in alphabet)\n",
    "\n",
    "def startswith(L, W=W):\n",
    "    return [w for w in W if w.startswith(L)]\n",
    "\n",
    "def matches(exacts, letters, L, W):\n",
    "    return [w for w in startswith(L, W) and match(w, exacts, letters)]\n",
    "\n",
    "def match(word, exacts, letters):\n",
    "    \n",
    "    \n",
    "\n",
    "p = pick_unique()\n",
    "n = len(set(''.join(p)))\n",
    "r = replies(p, 'ALOHA')  \n",
    "c = consolidate(r)\n",
    "m = matches(*c, 'A', W)\n",
    "p, n, r, c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "re.findall('.Z...', Wtext)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Counter(''.join(W)).most_common(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'fuss'.replace('s', '', 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pick()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}