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/)! You'll have to look at the [Advent of Code website](https://adventofcode.com/2020) if you want the full description of each puzzle; this notebook gives only a brief summary. \n",
    "\n",
    "For each day from 1 to 25, I'll write **four pieces of code**, each in a separate notebook cell. 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). Most days the data comes from a file, read via the function `data` (which has optional arguments to say how to split the data into sections/records and how to parse each one), but some days the data is so small I just copy and paste it.\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)`: executes the call `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, reduce\n",
    "from typing      import Dict, Tuple, Set, List, Iterator, Optional, Union, Sequence\n",
    "from contextlib  import contextmanager\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",
    "    with open(f'data/advent2020/input{day}.txt') as f:\n",
    "        sections = f.read().rstrip().split(sep)\n",
    "        return list(map(parser, sections))\n",
    "     \n",
    "def do(day, *answers) -> List[int]:\n",
    "    \"E.g., do(3) returns [day3_1(in3), 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",
    "        else:\n",
    "            got.append(None)\n",
    "    return got"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "Number = Union[float, int]\n",
    "Atom = Union[Number, str]\n",
    "Char = str # Type used to indicate a single character\n",
    "\n",
    "cat = ''.join\n",
    "flatten = chain.from_iterable\n",
    "\n",
    "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 prod(numbers) -> Number:\n",
    "    \"The product of an iterable of numbers.\" \n",
    "    return reduce(operator.mul, numbers, 1)\n",
    "\n",
    "def dot(A, B) -> Number: \n",
    "    \"The dot product of two vectors of numbers.\"\n",
    "    return sum(a * b for a, b in zip(A, B))\n",
    "\n",
    "def ints(text: str) -> Tuple[int]:\n",
    "    \"Return a tuple of all the integers in text.\"\n",
    "    return mapt(int, re.findall('-?[0-9]+', text))\n",
    "\n",
    "def lines(text: str) -> List[str]:\n",
    "    \"Split the text into a list of lines.\"\n",
    "    return text.strip().splitlines()\n",
    "\n",
    "def mapt(fn, *args): \n",
    "    \"Do map(fn, *args) and make the result a tuple.\"\n",
    "    return tuple(map(fn, *args))\n",
    "\n",
    "def atoms(text: str, ignore=r'', sep=None) -> Tuple[Atom]:\n",
    "    \"Parse text (with regex `ignore` ignored) into atoms separated by `sep`\"\n",
    "    text = re.sub(ignore, '', text)\n",
    "    return mapt(atom, text.split(sep))\n",
    "\n",
    "def atom(text: str, types=(int, str)):\n",
    "    \"Parse text into one of the given types.\"\n",
    "    for typ in types:\n",
    "        try:\n",
    "            return typ(text)\n",
    "        except ValueError:\n",
    "            pass\n",
    "\n",
    "@contextmanager\n",
    "def binding(**kwds):\n",
    "    \"Bind global variables within a context; revert to old values on exit.\"\n",
    "    old_values = {k: globals()[k] for k in kwds}\n",
    "    try:\n",
    "        globals().update(kwds)\n",
    "        yield # Stuff within the context gets run here.\n",
    "    finally:\n",
    "        globals().update(old_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notes:\n",
    "- Since I'm not even attempting to compete to be among the first 100 people to find a solution, I'll take the time to write docstrings; to use reasonable variable names (not single-letter names); and to give type annotations for most functions (but not the `day` functions, which all return `int`, except `day21_2`).\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",
    "- Some days I will re-use code that was defined on a previous day.\n",
    "- I will give a few tests using `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",
    "    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",
    "\n",
    "def day4_1(passports): return quantify(passports, required_fields.issubset)    "
   ]
  },
  {
   "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 all(field in passport and 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",
    "    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": [
    "Group = List[str]\n",
    "\n",
    "in6: List[Group] = data(6, lines, sep='\\n\\n')"
   ]
  },
  {
   "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): \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",
    "    \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 num_contained_in(rules, target='shiny gold') -> int:\n",
    "    \"How many bags are contained (recursively) in the target bag?\"\n",
    "    return sum(n + n * num_contained_in(rules, inner) \n",
    "               for (inner, n) in rules[target].items() if n > 0)\n",
    "\n",
    "day7_2 = num_contained_in"
   ]
  },
  {
   "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 638 instructions and at most one way to alter each instruction), and run each altered program to see if it terminates (that too takes no more than 638 steps each)."
   ]
  },
  {
   "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",
    "    \"The number of arrangements that go from prev to the end of `jolts`.\"\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",
    "  - A seat becomes empty 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": [
    "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": 46,
   "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": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2299, 2047]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "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, not a global constant.\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": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "in12: List[Instruction] = data(12, lambda line: (line[0], int(line[1:])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "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": 50,
   "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": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[439, 12385]"
      ]
     },
     "execution_count": 51,
     "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": 52,
   "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,\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,x,37)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "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": 54,
   "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": 55,
   "metadata": {},
   "outputs": [],
   "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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[174, 780601154795940]"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "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": 57,
   "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": 58,
   "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 + 2 ** 20) == '000000000000000100000000000011111111'\n",
    "\n",
    "def day14_1(program): return sum(run_docking(program).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "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": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[11884151942312, 2625449018811]"
      ]
     },
     "execution_count": 60,
     "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": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "in15 = 10,16,6,0,1,17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "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 asks 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": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day15_2(starting): return day15_1(starting, nth=30_000_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 7.31 s, sys: 114 ms, total: 7.42 s\n",
      "Wall time: 7.42 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[412, 243]"
      ]
     },
     "execution_count": 64,
     "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",
    "The input to this puzzle has three parts: some rules for valid fields; your ticket; and a set of nearby tickets. The puzzle is to figure out what field number corresponds to what field name (class, row, seat, etc.). The input looks like:\n",
    "\n",
    "    class: 1-3 or 5-7\n",
    "    row: 6-11 or 33-44\n",
    "\n",
    "    your ticket:\n",
    "    7,1,14\n",
    "\n",
    "    nearby tickets:\n",
    "    7,3,47\n",
    "    40,4,50\n",
    "\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": 65,
   "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",
    "    return TicketData(fields=dict(map(parse_ticket_line, fieldstr)), \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, lines, sep='\\n\\n'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "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": 67,
   "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 = {i: set(fields) for i in range(len(your))}\n",
    "    while any(len(possible[i]) > 1 for i 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 possible.items()}\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 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": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[21071, 3429967441937]"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(16, 21071, 3429967441937)"
   ]
  },
  {
   "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 (actually, make it `d` dimensions in general). My implementation represents a generation as the set of active cell coordinates.\n",
    "\n",
    "1. Starting with your given initial configuration, simulate six cycles. How many cubes are left in the active state after the sixth cycle?\n",
    "2. Simulate six cycles in a 4-dimensional space. How many cubes are left in the active state after the sixth cycle?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "in17: Picture = lines('''\n",
    "##.#....\n",
    "...#...#\n",
    ".#.#.##.\n",
    "..#.#...\n",
    ".###....\n",
    ".##.#...\n",
    "#.##..##\n",
    "#.####..\n",
    "''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "Cell  = Tuple[int,...]\n",
    "\n",
    "def day17_1(picture, d=3, n=6):\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))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day17_2(picture): return day17_1(picture, d=4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[291, 1524]"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(17, 291, 1524)"
   ]
  },
  {
   "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.\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": 73,
   "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": 74,
   "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": 75,
   "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": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3885386961962, 112899558798666]"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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": 77,
   "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.replace(':', ' ').replace('\"', ' '))\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, lines, sep='\\n\\n'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "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": 79,
   "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": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[190, 311]"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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": 81,
   "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, lines, sep='\\n\\n'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For Part 1, I can find the corners without knowing where all the other tiles go. 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": 82,
   "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": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[15670959891893, None]"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(20, 15670959891893)   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Family holiday preparations kept me from doing **Part 2** on the night it was released, and unfortunately I didn't feel like coming back to it later: it seemed too tedious for too little reward. I thought it was inelegant that a solid block of `#` pixels would be considered a sea monster with waves. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 21: Allergen Assessment\n",
    "\n",
    "This is another Sudoku-like problem, similar to Day 16, involving ingredients and allergens. Crucially, each allergen is found in exactly one ingredient, but a food may not list every allergen. I can reuse the function `eliminate_others`, but the rest I need to define here. `day21_2` is the only `day` function that does not return an `int`.\n",
    "\n",
    "1. Determine which ingredients cannot possibly contain any of the allergens in your list. How many times do any of those ingredients appear?\n",
    "2. What is your canonical dangerous ingredient list?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day21_1(foods):\n",
    "    \"How many times does an ingredient with an allergen appear?\"\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}}; each set should have len 1.\"\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_others(possible, a)\n",
    "    return possible"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day21_2(foods) -> str:\n",
    "    \"What are the bad ingredients, sorted by the allergen name that contains them?\"\n",
    "    bad = bad_ingredients(in21)\n",
    "    return ','.join(first(bad[a]) for a in sorted(bad))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2282, 'vrzkz,zjsh,hphcb,mbdksj,vzzxl,ctmzsr,rkzqs,zmhnj']"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(21, 2282, 'vrzkz,zjsh,hphcb,mbdksj,vzzxl,ctmzsr,rkzqs,zmhnj')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 22: Crab Combat\n",
    "\n",
    "Part 1 is the card game *War* (here called *Combat*) with no ties. Part 2 is a more complex recursive version of the game.\n",
    "\n",
    "1. Play a game of Combat using the two decks you just dealt. What is the winning player's score?\n",
    "2. Play a game of Recursive Combat. What is the winning player's score?\n",
    "\n",
    "Each player holds a *deal* of cards, which I will represent as a `deque` so I can deal from the top and add cards to the bottom."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "Deal  = Union[tuple, deque] # Cards are a tuple on input; a deque internally \n",
    "Deals = Tuple[Deal, Deal]   # Cards are split into two piles for the two players.\n",
    "\n",
    "in22: Deals = (\n",
    "    (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))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day22_1(deals): return combat_score(combat(deals))\n",
    "\n",
    "def combat(deals: Deals) -> Deals:\n",
    "    \"Given two deals, play Combat and return the final deals (one of which will be empty).\"\n",
    "    deals = mapt(deque, deals)\n",
    "    while all(deals):\n",
    "        topcards = mapt(deque.popleft, deals)\n",
    "        winner = 0 if topcards[0] > topcards[1] else 1\n",
    "        deals[winner].extend(sorted(topcards, reverse=True))\n",
    "    return deals\n",
    "\n",
    "def combat_score(deals: Deals) -> int:\n",
    "    \"The winner's cards, each multiplied by their reverse index number, and summed.\"\n",
    "    winning = deals[0] or deals[1]\n",
    "    return dot(winning, range(len(winning), 0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day22_2(deals): return combat_score(recursive_combat(deals))\n",
    "   \n",
    "def recursive_combat(deals: Deals) -> Deals:\n",
    "    \"A game of Recursive Combat.\"\n",
    "    deals = mapt(deque, deals)\n",
    "    previously = set()\n",
    "    while all(deals):\n",
    "        if seen(deals, previously):\n",
    "            return (deals[0], ())\n",
    "        topcards = mapt(deque.popleft, deals)\n",
    "        if all(len(deals[p]) >= topcards[p] for p in (0, 1)):\n",
    "            deals2 = [tuple(deals[p])[:topcards[p]] for p in (0, 1)]\n",
    "            result = recursive_combat(deals2)\n",
    "            winner = 0 if result[0] else 1\n",
    "        else:\n",
    "            winner = 0 if topcards[0] > topcards[1] else 1\n",
    "        deals[winner].extend([topcards[winner], topcards[1 - winner]])\n",
    "    return deals\n",
    "\n",
    "def seen(deals, previously) -> bool:\n",
    "    \"Return True if we have seen this pair of deals previously; else just remember it.\"\n",
    "    hasht = mapt(tuple, deals)\n",
    "    if hasht in previously:\n",
    "        return True\n",
    "    else:\n",
    "        previously.add(hasht)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[31809, 32835]"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(22, 31809, 32835)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 23: Crab Cups\n",
    "\n",
    "A game involving moving around some cups that are labelled with positive integers.\n",
    "\n",
    "1. Using your labeling, simulate 100 moves. What are the labels on the cups after cup 1?\n",
    "2. With 1 million cups and 10 million moves, determine which two cups will end up immediately clockwise of cup 1. What do you get if you multiply their labels together?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "in23 = '872495136'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "Cup = int # The label on a cup (not the index of the cup in the list of cups)\n",
    "\n",
    "def day23_1(cupstr: str, n=100):\n",
    "    \"Return the int representing the cups, in order, after cup 1; resulting from n moves.\"\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",
    "    return cups[(cups.index(current) + 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)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Cup = int # The label on a cup (not the index of the cup in the list of cups)\n",
    "\n",
    "def day23_1(cupstr: str, n=100):\n",
    "    \"Return the int representing the cups, in order, after cup 1; resulting from n moves.\"\n",
    "    return after(1, play_cups(cupstr, n))\n",
    "\n",
    "def play_cups(cupstr: str, n=100, maxcup=0):\n",
    "    cups = list(map(int, cupstr))\n",
    "    if maxcup > max(cups):\n",
    "        cups.append(range(max(cups) + 1, maxcup + 1))\n",
    "    current = cups[0][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 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",
    "    return cups[(cups.index(current) + 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",
    "def day23_2(cupstr): \n",
    "    cups = play_cups(cupstr, 1_000_000, 100_000_000)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[278659341, None]"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(23, 278659341)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For Part 1, I aimed to be very explicit in my code, and the solution works fine for 9 cups and 100 moves (although it did end up being more lines of code than I wanted/expected). \n",
    "\n",
    "However, my approach would not be efficient enough to do Part 2; thus it was a poor choice. For now I'll skip Part 2; maybe I'll come back to it later. I had an idea for a representation where each entry in `cups` is either a `list` or a `range` of cups; that way we are only breaking up and/or shifting small lists, not million-element lists. A skip list might also be a good approach."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 24: Lobby Layout\n",
    "\n",
    "This puzzle involves a hexagonal grid. The input is a list of directions to follow to identify a destination hex tile that should be flipped from white to black. I recall that Amit Patel of Red Blob Games has [covered hex grids topic thoroughly](https://www.redblobgames.com/grids/hexagons/); I followed his recommendation to use a (pointy) **axial coordinate** system. \n",
    "\n",
    "1. Go through the renovation crew's list and determine which tiles they need to flip. After all of the instructions have been followed, how many tiles are left with the black side up?\n",
    "2. Another version of *Life*, but on a hex grid, where a tile is live (black) if it was white and has two black neighbors, or it was black and has 1 or 2 black neighbors. How many tiles will be black after 100 days (generations)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [],
   "source": [
    "in24 = data(24)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day24_1(lines: List[str]):\n",
    "    \"How many tiles are flipped an odd number of times?\"\n",
    "    counts = Counter(map(follow_hex, lines))\n",
    "    return quantify(counts[tile] % 2 for tile 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('e|w|ne|sw|se|nw', line)\n",
    "\n",
    "def follow_hex(directions: str):\n",
    "    \"What (x, y) location do you end up at after following directions?\"\n",
    "    x, y = 0, 0\n",
    "    for dir in parse_hex(directions):\n",
    "        dx, dy = hexdirs[dir]\n",
    "        x += dx\n",
    "        y += dy\n",
    "    return (x, y)\n",
    "\n",
    "assert parse_hex('wsweesene') == ['w', 'sw', 'e', 'e', 'se', 'ne']\n",
    "assert follow_hex('eeew') == (2, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll use `binding` to temporarily redefine `next_generation` and `cell_deltas` to work with this problem; then call `life`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [],
   "source": [
    "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 = {tile for tile in counts if counts[tile] % 2}\n",
    "    with binding(next_generation=next_generation24, \n",
    "                 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) -> Iterable[Cell]:\n",
    "    \"The neighbors are the 6 surrounding hex squares.\"\n",
    "    return hexdirs.values()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[420, 4206]"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(24, 420, 4206)        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 25: Combo Breaker\n",
    "\n",
    "This puzzle involves breaking a cryptographic protocol (whose details I won't describe here).\n",
    "\n",
    "1. What encryption key is the handshake trying to establish?\n",
    "2. The last rule of AoC: there is no Part 2 for Day 25."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [],
   "source": [
    "in25 = 1965712, 19072108"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "def transform(subj) -> Iterator[int]:\n",
    "    \"A stream of transformed values, according to the protocol.\"\n",
    "    val = 1\n",
    "    while True:\n",
    "        val = (val * subj) % 20201227\n",
    "        yield val\n",
    "\n",
    "def day25_1(keys):\n",
    "    \"Find the loopsize for the first key; transform the other key that number of times.\"\n",
    "    loopsize = first(i for i, val in enumerate(transform(7)) if val == keys[0])  \n",
    "    return   first(val for i, val in enumerate(transform(keys[1])) if i == loopsize)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[16881444, None]"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "do(25, 16881444)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Postmortem: Timing\n",
    "\n",
    "Advent of Code suggests that each day's puzzle should run in [15 seconds or less](https://adventofcode.com/2020/about).\n",
    "I met that goal, with days 11 and 15 taking about 8 seconds each, days 22 and 25 about 2 seconds, and the rest if the days (and the overall average) being under a second per day. (However, I skipped Part 2 on days 20 and 23.)\n",
    "\n",
    "Here's a report. Stars in the first column indicate run times on a log scale: 0 stars for under 1/100 seconds up to 4 stars for 10 seconds or more:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    Day  Secs.  Answers\n",
      "    ===  =====  =======\n",
      "      1  0.000  [787776, 262738554]\n",
      "      2  0.000  [383, 272]\n",
      "      3  0.000  [167, 736527114]\n",
      "      4  0.001  [237, 172]\n",
      "      5  0.000  [906, 519]\n",
      "      6  0.001  [6530, 3323]\n",
      "      7  0.001  [103, 1469]\n",
      "      8  0.008  [1521, 1016]\n",
      "      9  0.003  [776203571, 104800569]\n",
      "     10  0.000  [2346, 6044831973376]\n",
      " *** 11  8.271  [2299, 2047]\n",
      "     12  0.001  [439, 12385]\n",
      "     13  0.000  [174, 780601154795940]\n",
      "   * 14  0.063  [11884151942312, 2625449018811]\n",
      " *** 15  7.480  [412, 243]\n",
      "  ** 16  0.145  [21071, 3429967441937]\n",
      "  ** 17  0.273  [291, 1524]\n",
      "     18  0.005  [3885386961962, 112899558798666]\n",
      "  ** 19  0.262  [190, 311]\n",
      "     20  0.001  [15670959891893, None]\n",
      "     21  0.001  [2282, 'vrzkz,zjsh,hphcb,mbdksj,vzzxl,ctmzsr,rkzqs,zmhnj']\n",
      " *** 22  2.246  [31809, 32835]\n",
      "     23  0.000  [278659341, None]\n",
      "  ** 24  0.724  [420, 4206]\n",
      " *** 25  1.827  [16881444, None]\n",
      "CPU times: user 21.3 s, sys: 62.1 ms, total: 21.3 s\n",
      "Wall time: 21.3 s\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "def timing(days=range(1, 26)):\n",
    "    \"Report on timing of `do(day)` for all days.\"\n",
    "    print('    Day  Secs.  Answers')\n",
    "    print('    ===  =====  =======')    \n",
    "    for day in days:\n",
    "        t0 = time.time()\n",
    "        answers = do(day)\n",
    "        t = time.time() - t0\n",
    "        if answers != [None, None]:\n",
    "            stars = '*' * int(3 + math.log(t, 10))\n",
    "            print(f'{stars:>4} {day:2} {t:6.3f}  {answers}')\n",
    "\n",
    "%time timing()"
   ]
  },
  {
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}