solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Advent of Code 2018](https://adventofcode.com/2018)\n",
    "\n",
    "- [Day 1](#Day-1-Chronal-Calibration) Chronal Calibration\n",
    "- [Day 2](#Day-2-Inventory-Management-System) Inventory Management System\n",
    "- [Day 3](#Day-3-No-Matter-How-You-Slice-It)  No Matter How You Slice It\n",
    "- [Day 4](#Day-4-Repose-Record) Repose Record\n",
    "- [Day 5](#Day-5-Alchemical-Reduction) Alchemical Reduction\n",
    "- [Day 6](#Day-6-Chronal-Coordinates) Chronal Coordinates\n",
    "- [Day 7](#Day-7-The-Sum-of-Its-Parts) The Sum of Its Parts\n",
    "- [Day 8](#Day-8-Memory-Maneuver) Memory Maneuver\n",
    "- [Day 9](#Day-9-Marble-Mania) Marble Mania\n",
    "- [Day 10](#Day-10-The-Stars-Align) The Stars Align\n",
    "- [Day 11](#Day-11-Chronal-Charge) Chronal Charge\n",
    "- [Day 12](#Day-12-Subterranean-Sustainability) Subterranean Sustainability\n",
    "- [Day 13](#Day-13-Mine-Cart-Madness) Mine Cart Madness\n",
    "- [Day 14](#Day-14-Chocolate-Charts) Chocolate Charts\n",
    "- [Day 15](#Day-15-Beverage-Bandits) Beverage Bandits\n",
    "- [Day 16](#Day-16-Chronal-Classification) Chronal Classification\n",
    "- [Day 17](#Day-17-Reservoir-Research) Reservoir Research\n",
    "- [Day 18](#Day-18-Settlers-of-The-North-Pole) Settlers of The North Pole\n",
    "- [Day 19](#Day-19-Go-With-The-Flow) Go With The Flow\n",
    "- [Day 20](#Day-20-A-Regular-Map) A Regular Map\n",
    "- [Day 21](#Day-21-Chronal-Conversion) Chronal Conversion\n",
    "- [Day 22](#Day-22-Mode-Maze) Mode Maze\n",
    "- [Day 23](#Day-23-Experimental-Emergency-Teleportation) Experimental Emergency Teleportation\n",
    "- [Day 24](#Day-24-Immune-System-Simulator-20XX) Immune System Simulator 20XX\n",
    "- [Day 25](#Day-25-Four-Dimensional-Adventure) Four Dimensional Adventure\n",
    "\n",
    "I'm going to have a go at the Advent of Code 2018 puzzles using a Jupyter notebook.\n",
    "First, let's import some standard modules."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "import dataclasses\n",
    "import functools\n",
    "import itertools as its\n",
    "import math\n",
    "import operator\n",
    "import re\n",
    "import string\n",
    "import typing\n",
    "from pprint import pprint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also, here are some general purpose functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day(day):\n",
    "    'Load the input for `day`'\n",
    "    return open(f'input/{day}').read()\n",
    "\n",
    "def ilen(xs):\n",
    "    'Return the length of an iterable'\n",
    "    return sum(1 for _ in iter(xs))\n",
    "\n",
    "def last(xs):\n",
    "    'Return the last element of an iterable sequence.'\n",
    "    xs = iter(xs)\n",
    "    return collections.deque(xs, maxlen=1)[0]\n",
    "\n",
    "def ints(s):\n",
    "    'Return a tuple of integer tokens in `s`.'\n",
    "    return tuple(int(x) for x in re.findall(r'[-+]?\\d+', s))\n",
    "\n",
    "def array(data):\n",
    "    'Convert the data into a tuple of int-tuples.'\n",
    "    return tuple(ints(line) for line in data.splitlines())\n",
    "\n",
    "def swap(xs, i, j):\n",
    "    'Swap items in a sequence.'\n",
    "    xs[i], xs[j] = xs[j], xs[i]\n",
    "\n",
    "def nth(xs, n):\n",
    "    'Return the nth element of a sequence.'\n",
    "    return next(its.islice(xs, n, None))\n",
    "\n",
    "def take(xs, n=None):\n",
    "    '''Return (up to) first `n` items of a sequence\n",
    "    or the whole sequence if `n` is `None`\n",
    "    '''\n",
    "    return list(xs) if n is None else [x for x, _ in zip(xs, range(n))]\n",
    "\n",
    "def overlapping(xs, n):\n",
    "    '''Generate overlapping n-tuples from `xs`\n",
    "\n",
    "    overlapping('ABCDEFG', 3) --> ABC BCD CDE DEF EFG\n",
    "    '''\n",
    "    if isinstance(xs, collections.abc.Sequence):\n",
    "        yield from (xs[i:i+n] for i in range(len(xs) + 1 - n))\n",
    "    else:\n",
    "        result = collections.deque(maxlen=n)\n",
    "        for x in xs:\n",
    "            result.append(x)\n",
    "            if len(result) == n:\n",
    "                yield tuple(result)\n",
    "                \n",
    "def pairwise(iterable):\n",
    "    's -> (s0,s1), (s1,s2), (s2, s3), ...'\n",
    "    return overlapping(iterable, 2)\n",
    "\n",
    "def unfold(fn, x):\n",
    "    while True:\n",
    "        yield x\n",
    "        x = fn(x)\n",
    "\n",
    "def chunked(xs, n):\n",
    "    'Collect `xs` into chunks of length `n`'\n",
    "    return zip(*[iter(xs)] * n)\n",
    "\n",
    "def manhattan_distance(P, Q):\n",
    "    'Return the city block distance from `P` to `Q`'\n",
    "    return sum(math.fabs(p-q) for p,q in zip(P, Q))\n",
    "\n",
    "def neighbours4(x, y):\n",
    "    'Return the horizontal and vertical neighbours of `(x, y)`'\n",
    "    return (x,y-1),(x-1,y),(x+1,y),(x,y+1)\n",
    "\n",
    "def neighbours8(x, y):\n",
    "    'Return the horizontal, vertical and diagonal neighbours of `(x, y)`'\n",
    "    return ((x-1,y-1),(x-1,y),(x-1,y+1),\n",
    "            (x,y-1),(x,y+1),\n",
    "            (x+1,y-1),(x+1,y),(x+1,y+1))\n",
    "\n",
    "def unique(xs):\n",
    "    'Return `True` iff no elements of `xs` are repeated'\n",
    "    return len(xs) == len(set(xs))\n",
    "\n",
    "def mapt(f, xs):\n",
    "    return tuple(map(f, xs))\n",
    "\n",
    "def render_grid(grid, fill_ch=' '):\n",
    "    '''Convert `grid` into a printable form\n",
    "    \n",
    "    grid - maps 2D points to single chars\n",
    "    fill_ch - used for chars not in the grid\n",
    "    '''\n",
    "    xlo, xhi = min(map(first, grid)), max(map(first, grid))\n",
    "    ylo, yhi = min(map(second, grid)), max(map(second, grid))\n",
    "    return ncat(cat(grid.get((x,y), fill_ch)\n",
    "                    for x in range(xlo, xhi+1))\n",
    "                for y in range(ylo, yhi+1))\n",
    "\n",
    "def draw_grid(grid, fill_ch=' '):\n",
    "    print(render_grid(grid, fill_ch))       \n",
    "\n",
    "flatten = its.chain.from_iterable\n",
    "cat = ''.join\n",
    "ncat = '\\n'.join\n",
    "first = operator.itemgetter(0)\n",
    "second = operator.itemgetter(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's another general purpose function -- albeit a more sophisticated one, which I didn't need until Day 22."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "def a_star(start, heuristic, moves, weights=lambda _: 1):\n",
    "    '''A-star graph search\n",
    "\n",
    "    - start: initial state\n",
    "    - heuristic(s): estimates path length from state s to finish\n",
    "    - moves(s): neighbours of s\n",
    "    - weights(s): costs of stepping from s\n",
    "\n",
    "    Returns the shortest path to the finish and its cost, on success.\n",
    "    None otherwise.\n",
    "    '''\n",
    "    costs  = {start: 0}\n",
    "    prev   = {start: None}\n",
    "    fringe = [(heuristic(start), start)]\n",
    "    heapq.heapify(fringe)\n",
    "\n",
    "    def path(s):\n",
    "        return [] if s is None else path(prev[s]) + [s]\n",
    "\n",
    "    while fringe:\n",
    "        priority, state = heapq.heappop(fringe)\n",
    "        if heuristic(state) == 0:\n",
    "            return costs[state], path(state)\n",
    "        for next_, weight in zip(moves(state), weights(state)):\n",
    "            next_cost = costs[state] + weight\n",
    "            if next_ not in costs or next_cost < costs[next_]:\n",
    "                costs[next_] = next_cost\n",
    "                heapq.heappush(fringe, (next_cost + heuristic(next_), next_))\n",
    "                prev[next_] = state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 1](https://adventofcode.com/2018/day/1) Chronal Calibration\n",
    "The input is a series of integers, one per line. These integers represent frequency deltas. Part one requires the final frequency. That is, the sum of these integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "599"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deltas = ints(day(1)) \n",
    "sum(deltas)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two explains the frequency deltas cycle repeatedly. We are asked to find the first frequency which is reached a second time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "81204"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "seen = set()\n",
    "for freq in its.accumulate(its.cycle(deltas)):\n",
    "    if freq in seen:\n",
    "        break\n",
    "    seen.add(freq)\n",
    "\n",
    "freq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 2](https://adventofcode.com/2018/day/2) Inventory Management System\n",
    "The input is a list of strings representing box ids."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "box_ids = day(2).split()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to know the counts of letters in these ids -- specifically, how many ids have letters repeated 2 and/or 3 times? `Counter` can help here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "box_counts = [collections.Counter(box_id) for box_id in box_ids]\n",
    "x2 = sum(2 in box_count.values() for box_count in box_counts)\n",
    "x3 = sum(3 in box_count.values() for box_count in box_counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're asked for the product of the repeat counts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5681"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x2 * x3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two asks for something quite different: to identify a pair of ids which differ by a single character."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "250"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(box_ids)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For such a low number of ids, we simply check every pair."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def diffs(b, B):\n",
    "    'Return the number of characters which differ in the inputs'\n",
    "    return sum(c != C for c, C in zip(b, B))\n",
    "\n",
    "diff_by_one = [p for p in its.combinations(box_ids, 2) if diffs(*p) == 1]\n",
    "\n",
    "# Check there's just one pair which fits the criteria\n",
    "assert len(diff_by_one) == 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're asked for the letters common to this pair."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'uqyoeizfvmbistpkgnocjtwld'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cat(c for c, C in zip(*diff_by_one[0]) if c == C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 3](https://adventofcode.com/2018/day/3) No Matter How You Slice It\n",
    "This puzzle is about *claim*s, which are regions in a grid. Each grid square is specified by an id, then left, top, width, height values. We could write a regex to parse/check, but simply extracting `ints` gets us there."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(123, 3, 2, 5, 4)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "claim = \"#123 @ 3,2: 5x4\"\n",
    "ints(claim) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part one, we want to know how many squares on the grid are covered by more than one claim. Let's find the total area of all the claims."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "492476"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "claims = array(day(3))\n",
    "sum(c[3]*c[4] for c in claims)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given this figure, we can just count the number of claims in each cell. We can then read the number of squares with 2 or more claims."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "112378"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def rectangle(id_, L, T, W, H):\n",
    "    'Generate the points within a claim'\n",
    "    return its.product(range(L, L+W), range(T, T+H))\n",
    "\n",
    "grid = collections.Counter(\n",
    "    p for claim in claims for p in rectangle(*claim))\n",
    "\n",
    "sum(N > 1 for N in grid.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part two, we want the id of the claim which doesn't overlap any other claim. That's the claim for which cell counts are all `1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "603"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "non_overlaps = [claim[0] for claim in claims\n",
    "                if all(grid[p] == 1 for p in rectangle(*claim))]\n",
    "\n",
    "assert len(non_overlaps) == 1, \"Multiple answers to Day 3 part 2\"\n",
    "non_overlaps[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 4](https://adventofcode.com/2018/day/4) Repose Record\n",
    "It's not entirely clear what's wanted here. Are we only concerned with guards being asleep during the midnight hour? Or, when we sort the inputs, are these the only times guards are asleep? Let's investigate by sorting the records, noting that the result is time-ordered."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1518-01-29 23:57] Guard #2417 begins shift\n",
      "[1518-01-30 00:13] falls asleep\n",
      "[1518-01-30 00:50] wakes up\n",
      "[1518-01-31 00:00] Guard #1301 begins shift\n",
      "[1518-01-31 00:24] falls asleep\n",
      "[1518-01-31 00:54] wakes up\n",
      "[1518-01-31 23:59] Guard #401 begins shift\n",
      "[1518-02-01 00:42] falls asleep\n",
      "[1518-02-01 00:51] wakes up\n",
      "[1518-02-02 00:03] Guard #2207 begins shift\n",
      "[1518-02-02 00:10] falls asleep\n",
      "[1518-02-02 00:49] wakes up\n",
      "[1518-02-03 00:03] Guard #3541 begins shift\n",
      "[1518-02-03 00:22] falls asleep\n",
      "[1518-02-03 00:56] wakes up\n",
      "[1518-02-04 00:03] Guard #2207 begins shift\n",
      "[1518-02-04 00:09] falls asleep\n",
      "[1518-02-04 00:26] wakes up\n",
      "[1518-02-04 00:42] falls asleep\n",
      "[1518-02-04 00:58] wakes up\n",
      "[1518-02-05 00:00] Guard #2663 begins shift\n",
      "[1518-02-05 00:44] falls asleep\n",
      "[1518-02-05 00:50] wakes up\n",
      "[1518-02-05 23:57] Guard #2207 begins shift\n",
      "[1518-02-06 00:54] falls asleep\n",
      "[1518-02-06 00:59] wakes up\n",
      "[1518-02-07 00:00] Guard #1301 begins shift\n",
      "[1518-02-07 00:44] falls asleep\n",
      "[1518-02-07 00:53] wakes up\n",
      "[1518-02-08 00:03] Guard #1327 begins shift\n",
      "[1518-02-08 00:07] falls asleep\n",
      "[1518-02-08 00:22] wakes up\n",
      "[1518-02-08 00:31] falls asleep\n",
      "[1518-02-08 00:51] wakes up\n",
      "[1518-02-08 23:58] Guard #2411 begins shift\n",
      "[1518-02-09 00:34] falls asleep\n",
      "[1518-02-09 00:50] wakes up\n",
      "[1518-02-10 00:00] Guard #2411 begins shift\n",
      "[1518-02-10 00:42] falls asleep\n",
      "[1518-02-10 00:49] wakes up\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "sort: fflush failed: 'standard output'\n",
      "sort: write error\n"
     ]
    }
   ],
   "source": [
    "! sort < input/4 | head -n 40"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now my questions about the input are clarified. Every night just a single guard is on duty and that guard only sleeps during the midnight hour.\n",
    "\n",
    "We scan through the sorted records and keep a counter for each guard. That counter records minutes in the midnight hour the guard was asleep. For example, `sleeping[42][5] == 3` would mean guard `#42` was asleep on 3 nights between `00:05` and `00:06`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(39, 10), (40, 10), (41, 10), (42, 10), (36, 9)]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sleeping = collections.defaultdict(collections.Counter)\n",
    "\n",
    "for record in sorted(day(4).splitlines()):\n",
    "    yy,mm,dd,hh,mm,*rest = ints(record)\n",
    "    if 'shift'  in record:\n",
    "        guard = rest[0]\n",
    "    elif 'asleep' in record:\n",
    "        assert hh == 0, f\"Guard falls asleep at time {hh}:{mm}!\"\n",
    "        asleep = mm\n",
    "    else:\n",
    "        assert 'wakes' in record, record\n",
    "        assert hh == 0, f\"Guard wakes at time {hh}:{mm}!\"\n",
    "        sleeping[guard].update(range(asleep, mm))\n",
    "\n",
    "# Let's have a look at some data & check it looks OK. \n",
    "sleeping[2417].most_common(5) # Guard 2417 is the first in our ordered input"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part one, we're after the guard who slept the longest and the minute they were most often asleep. The answer wanted is the product of the guard's id and the minute."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(45, 15), (44, 14)]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "guard, asleep = max(sleeping.items(), key=lambda i: sum(i[1].values()))\n",
    "asleep.most_common(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's good -- we have a unique choice for the minute the guard was most often asleep. We can get the answer directly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "119835"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "guard * asleep.most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two asks: Of all guards, which guard is most frequently asleep on the same minute? The answer is in our `sleeping` dict."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12725"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sleepiest_minute(guard_mins):\n",
    "    guard, mins = guard_mins\n",
    "    minute, freq = mins.most_common(1).pop()\n",
    "    return freq, minute, guard\n",
    "\n",
    "freq, minute, guard = max(map(sleepiest_minute, sleeping.items()))\n",
    "guard * minute"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 5](https://adventofcode.com/2018/day/5) Alchemical Reduction\n",
    "Pairs of characters are repeatedly removed from a polymer -- represented as a string. First, find all possible pairs, and create a function to destroy these pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "import string\n",
    "az, AZ = string.ascii_lowercase, string.ascii_uppercase\n",
    "removes = [cat(p) for p in zip(az, AZ)] + [cat(p) for p in zip(AZ, az)]\n",
    "react_sub = re.compile('|'.join(removes)).sub\n",
    "\n",
    "def react_fn(s):\n",
    "    return react_sub('', s)\n",
    "\n",
    "assert react_fn('abBA') == 'aA'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we keep processing the polymer until there's nothing to remove."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 3.85 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "9562"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def react(polymer, react_fn=react_fn):\n",
    "    'Apply `react_fn` until `polymer` stabilises, returning the stable form'\n",
    "    return next(p for p, n in pairwise(unfold(react_fn, polymer))\n",
    "                if p == n)\n",
    "\n",
    "assert react('dabAcCaCBAcCcaDA') == 'dabCBAcaDA'\n",
    "\n",
    "polymer = day(5).strip() # (strip in case a newline appeared in the file)\n",
    "%time len(react(polymer))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part two, we see what happens if we remove all instances of a unit before reacting. Which unit results in the biggest reaction?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 1min 43s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "9560"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inputs = (re.sub(x, '', polymer, re.I) for x in AZ)\n",
    "%time min(len(react(p)) for p in inputs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 6](https://adventofcode.com/2018/day/6) Chronal Coordinates\n",
    "We are filling an infinite grid, stepping in horizontal or vertical direction. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3894"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coords = set(ints(row) for row in day(6).splitlines())\n",
    "\n",
    "# Find the X and Y ranges of the pts\n",
    "x, X = min(map(first,  coords)), max(map(first,  coords))\n",
    "y, Y = min(map(second, coords)), max(map(second, coords))\n",
    "\n",
    "def on_edge(pt):\n",
    "    'Return `True` if `pt` is on the bounding box of `coords`'\n",
    "    return pt[0] in {x, X} or pt[1] in {y, Y}\n",
    "\n",
    "def closest(pt, coords, dist=manhattan_distance):\n",
    "    'Return the `coords` closest to `pt`'\n",
    "    def key(p): return dist(p, pt)\n",
    "    d, result = next(its.groupby(sorted(coords, key=key), key=key))\n",
    "    return tuple(result)\n",
    "\n",
    "# Find the closest coord to each point in the bounding box of `coords`\n",
    "closest_coords = {p: closest(p, coords) \n",
    "                  for p in its.product(range(x, X+1), range(y, Y+1))}\n",
    "\n",
    "# We are looking for the coord surrounded by the largest contained region. \n",
    "\n",
    "# We can eliminate any coord which is closest to a point on \n",
    "# the bounding box -- such points are not contained\n",
    "infinite_extent = set(\n",
    "    flatten(vs for p, vs in closest_coords.items() if on_edge(p)))\n",
    "\n",
    "# Now count up points closest to `coords` -- this gives us areas of\n",
    "# contained regions\n",
    "areas = collections.Counter(\n",
    "    v for v, *tied in closest_coords.values()\n",
    "    if not tied and v not in infinite_extent)\n",
    "\n",
    "coord, biggest_area = areas.most_common(1)[0]\n",
    "biggest_area"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part two, we want to find the region in which all points have a total Manhattan distance from `pts` of less than 10000."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11299.0"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min(sum(manhattan_distance(p, q) for q in coords) \n",
    "    for p in closest_coords if on_edge(p)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since 11299 > 10000, this check confirms the region is strictly within the bounding box of the coords."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "39398"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ilen(p for p in its.product(range(x, X+1), range(y, Y+1))\n",
    "     if sum(manhattan_distance(p, q) for q in coords) < 10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 7](https://adventofcode.com/2018/day/7) The Sum of Its Parts\n",
    "Part one is a topological sort, with the minor twist of ordering dependencies alphabetically when there's a choice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Y', 'J')"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Each row in the input looks something like\n",
    "row = 'Step Y must be finished before step J can begin.'\n",
    "# We can extract the dependency like this\n",
    "select = operator.itemgetter(1, 7)\n",
    "select(row.split())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'CHILFNMORYKGAQXUVBZPSJWDET'"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edges = sorted(select(row.split()) for row in day(7).splitlines())\n",
    "\n",
    "graph = collections.defaultdict(list,\n",
    "    {v: mapt(second, deps) for v, deps in its.groupby(edges, key=first)})\n",
    "\n",
    "in_degrees = collections.Counter(map(second, edges))\n",
    "ready = set(graph) - set(in_degrees)\n",
    "topo = []\n",
    "while ready:\n",
    "    v = min(ready)\n",
    "    topo.append(v)\n",
    "    ready.remove(v)\n",
    "    in_degrees.subtract(collections.Counter(graph[v]))\n",
    "    ready |= {v for v, n in in_degrees.items() \n",
    "              if n==0 and v not in topo}\n",
    "    \n",
    "cat(topo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two adds extra workers (elves) and assigns times to the steps. We are asked for the time to complete the tasks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "891"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "in_degrees = collections.Counter(map(second, edges))\n",
    "ready = set(graph) - set(in_degrees)\n",
    "workers = 5\n",
    "\n",
    "def t_step(S):\n",
    "    'Step A takes 61 seconds, B 62 seconds etc.'\n",
    "    return 61 + ord(S) - ord('A')\n",
    "\n",
    "t = 0\n",
    "work = []\n",
    "topo = []\n",
    "\n",
    "while ready or work:\n",
    "    if ready and workers:\n",
    "        workers -= 1\n",
    "        v = min(ready)\n",
    "        ready.remove(v)\n",
    "        work.append((t + t_step(v), v))\n",
    "    else:\n",
    "        workers += 1\n",
    "        work.sort(reverse=True)\n",
    "        t, v = work.pop()\n",
    "        topo.append(v)\n",
    "        in_degrees.subtract(collections.Counter(graph[v]))\n",
    "        ready |= {v for v, n in in_degrees.items() \n",
    "                  if n==0 and v not in topo and v not in mapt(second, work)}\n",
    "\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 8](https://adventofcode.com/2018/day/8) Memory Maneuver\n",
    "A list of integers defines a tree structure. Part one asks us to total up the metadata stored in the tree nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "44838"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def traverse(tree_data, i, metadata_callback):\n",
    "    '''Traverse `tree_data` from index `i` calling `metadata_callback`\n",
    "    \n",
    "    Returns the index into `tree_data` after traversing\n",
    "    '''\n",
    "    # Read the header ...\n",
    "    children, metas = tree_data[i], tree_data[i+1]\n",
    "    i += 2\n",
    "    # ... and the children\n",
    "    for _ in range(children):\n",
    "        i = traverse(tree_data, i, metadata_callback)\n",
    "    # ... and metadata\n",
    "    metadata_callback(tree_data[i: i+metas])\n",
    "    return i + metas\n",
    "\n",
    "metadata = []\n",
    "\n",
    "# Check the example\n",
    "traverse(ints('2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2'), 0, metadata.extend)\n",
    "assert sum(metadata) == 138\n",
    "\n",
    "metadata.clear()\n",
    "traverse(ints(day(8)), 0, metadata.extend)\n",
    "sum(metadata)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two asks for the value of the root node, which is recursively evaluated from its children, considering the metadata as indices into these children."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "22198"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def tree_value(tree_data, i):\n",
    "    children, metas = tree_data[i], tree_data[i+1]\n",
    "    i += 2\n",
    "    child_values = {}\n",
    "    for j in range(children):\n",
    "        i, v = tree_value(tree_data, i)\n",
    "        child_values[j+1] = v\n",
    "    \n",
    "    md = tree_data[i: i+metas]\n",
    "    if children:\n",
    "        value = sum(child_values.get(m, 0) for m in md)\n",
    "    else:\n",
    "        value = sum(md)\n",
    "    return i + metas, value\n",
    "\n",
    "assert tree_value(ints('2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2'), 0)[1] == 66\n",
    "tree_value(ints(day(8)), 0)[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 9](https://adventofcode.com/2018/day/9) Marble Mania\n",
    "Inserting numbers into a circular buffer, following some bizarre rules."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_marbles():\n",
    "    marbles, pos = [0], 0\n",
    "    for N in its.count(1):\n",
    "        if N % 23:\n",
    "            pos = (pos + 2) % len(marbles)\n",
    "            marbles.insert(pos, N)\n",
    "            yield 0\n",
    "        else:\n",
    "            pos = (pos - 7) % len(marbles)\n",
    "            yield N + marbles.pop(pos)\n",
    "\n",
    "def marbles_game(players, marbles):\n",
    "    scores = collections.Counter()\n",
    "    for score, player in zip(\n",
    "        its.islice(play_marbles(), marbles), its.cycle(range(players))):\n",
    "        scores[player] += score\n",
    "    return max(scores.values())\n",
    "\n",
    "assert marbles_game(10, 1618) == 8317\n",
    "assert marbles_game(13, 7999) == 146373\n",
    "assert marbles_game(17, 1104) == 2764\n",
    "assert marbles_game(30, 5807) == 37305"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 675 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "416424"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# My input: 413 players; last marble is worth 71082 points\n",
    "%time marbles_game(413, 71082)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the second part, I wrote a [C++ program](./day9/main.cpp) using a doubly-linked list so I could insert and delete nodes in constant time. This gave the answer `3498287922`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 10](https://adventofcode.com/2018/day/10) The Stars Align\n",
    "Points move in a grid until they form a message."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(range(141, 203), range(133, 143))"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pts_vs = array(day(10))\n",
    "\n",
    "def lights(pts_vs):\n",
    "    'Generate the light positions from the `pts_vs` point+velocity 4-tuples.'\n",
    "    posns = [(its.count(x, vx), its.count(y, vy)) for x, y, vx, vy in pts_vs]\n",
    "    while True:\n",
    "        yield [(next(x), next(y)) for x, y in posns]\n",
    "\n",
    "def bounding_box(pts):\n",
    "    'Return the axis-aligned box which bounds `pts` as an X-range, Y-range pair'\n",
    "    xs, ys = mapt(first, pts), mapt(second, pts)\n",
    "    return range(min(xs), max(xs)+1), range(min(ys), max(ys)+1)\n",
    "\n",
    "def area(box):\n",
    "    w, h = box\n",
    "    return len(w) * len(h)\n",
    "\n",
    "this_pts, next_pts = its.tee(lights(pts_vs))\n",
    "next(next_pts)\n",
    "\n",
    "# We'll assume the message appears when the bounding box of \n",
    "# the points reaches a minimum -- when we print the result\n",
    "# we'll know if we were right :-)\n",
    "for seconds, (this, next_) in enumerate(zip(this_pts, next_pts)):\n",
    "    if area(bounding_box(this)) < area(bounding_box(next_)):\n",
    "        break\n",
    "\n",
    "# Check the bounding box looks sane\n",
    "bounding_box(this)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "******  *****   *****   *****   *****   *****   ******    **  \n",
      "*       *    *  *    *  *    *  *    *  *    *       *   *  * \n",
      "*       *    *  *    *  *    *  *    *  *    *       *  *    *\n",
      "*       *    *  *    *  *    *  *    *  *    *      *   *    *\n",
      "*****   *****   *****   *****   *****   *****      *    *    *\n",
      "*       *       *  *    *    *  *  *    *  *      *     ******\n",
      "*       *       *   *   *    *  *   *   *   *    *      *    *\n",
      "*       *       *   *   *    *  *   *   *   *   *       *    *\n",
      "*       *       *    *  *    *  *    *  *    *  *       *    *\n",
      "*       *       *    *  *****   *    *  *    *  ******  *    *\n"
     ]
    }
   ],
   "source": [
    "# Yes, that looks good. Render the message\n",
    "draw_grid({p: '*' if p in this else ' '\n",
    "          for p in its.product(*bounding_box(this))})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two of the question asks how long it would take to get this answer. I went back and modified my `for` loop to enumerate the zipped values, making the answer available."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10027"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "seconds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 11](https://adventofcode.com/2018/day/11) Chronal Charge\n",
    "We are asked to find the 3x3 square in a 300x300 grid with the largest total power level. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The power level for cell (x, y) is calculated from its coords\n",
    "# and a \"serial number\"\n",
    "def hundreds(n):\n",
    "    'Return the hundreds digit in the decimal representation of `n`'\n",
    "    return (n//100)%10\n",
    "\n",
    "def power_level(serial_number, x, y):\n",
    "    rack_id = x + 10\n",
    "    return hundreds((rack_id*y + serial_number)*rack_id) - 5\n",
    "\n",
    "assert power_level(8, 3, 5) == 4\n",
    "assert power_level(71, 101, 153) == 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 390 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(243, 64)"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def power_levels(serial_number, S):\n",
    "    'Calculate power levels for square side `S` using supplied `serial_number`'\n",
    "    return {p: power_level(serial_number, *p) \n",
    "            for p in its.product(range(1, S+1), repeat=2)}\n",
    "    \n",
    "def max_power_cell(serial_number, s, S):\n",
    "    '''Maximise the power for a square side `s`\n",
    "    \n",
    "    Returns the cell at the top-left of the `s` square\n",
    "    - serial_number\n",
    "    - s, the side legth\n",
    "    - S, side length of the whole grid\n",
    "    '''\n",
    "    levels = power_levels(serial_number, S)\n",
    "    def total_power(x, y):\n",
    "        sq = its.product(range(x, x+s), range(y, y+s))\n",
    "        return sum(levels[p] for p in sq)\n",
    "\n",
    "    return max(\n",
    "        (p for p in its.product(range(1,1+S-s), repeat=2)),\n",
    "        key=lambda p: total_power(*p))\n",
    "\n",
    "s, S = 3, 300\n",
    "serial_number = 5468\n",
    "assert max_power_cell(18, s, S) == (33, 45)\n",
    "%time max_power_cell(5468, s, S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " -4 -3 -3 -3\n",
      " -2 -2 -1 -1\n",
      " -1  0  0  1\n",
      "  0  1  2  3\n"
     ]
    }
   ],
   "source": [
    "def draw_cells(cells):\n",
    "    'Draw the square grid of `cells`'\n",
    "    S = int(math.sqrt(len(cells)))\n",
    "    R = range(1, S+1)\n",
    "    print(ncat(cat(f'{cells[(x,y)]:3}' for x in R) for y in R))\n",
    "\n",
    "draw_cells(power_levels(6, 4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the second part of the question, we want to maximise the power in a square region over all possible square side lengths `s`. We start by accumulating the power over the grid. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " -4 -3 -3 -3\n",
      " -2 -2 -1 -1\n",
      " -1  0  0  1\n",
      "  0  1  2  3\n",
      "\n",
      " -4 -7-10-13\n",
      " -6-11-15-19\n",
      " -7-12-16-19\n",
      " -7-11-13-13\n"
     ]
    }
   ],
   "source": [
    "def cumulative_power(serial_number, S):\n",
    "    cells = power_levels(serial_number, S)\n",
    "    R = range(1, S+1)\n",
    "    # Accumulate rows top-to-bottom\n",
    "    for y in R[1:]:\n",
    "        cells.update({(x,y): cells[x,y]+cells[x,y-1] for x in R})\n",
    "\n",
    "    # Accumulate columns left-to-right\n",
    "    for x in R[1:]:\n",
    "        cells.update({(x,y): cells[x,y]+cells[x-1,y] for y in R})\n",
    "    \n",
    "    return collections.Counter(cells)\n",
    "\n",
    "draw_cells(power_levels(6,4))\n",
    "print()\n",
    "draw_cells(cumulative_power(6, 4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the cumulative power grid we can read out the total power for a rectangular region."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "def region_power(accu, t, l, b, r):\n",
    "    '''Return the total power for a rectangular region\n",
    "    \n",
    "    accu - the cumulative powers over the grid\n",
    "    tl - top-left corner\n",
    "    br - bottom-right corner (included)\n",
    "    '''\n",
    "    return accu[(r,b)] - accu[(r,t-1)] - accu[(l-1,b)] + accu[(l-1,t-1)]\n",
    "\n",
    "accu = cumulative_power(6, 4)\n",
    "assert region_power(accu, 1, 1, 1, 1) == -4\n",
    "assert region_power(accu, 1, 1, 3, 2) == -12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5468 300\n",
      "Wall time: 16.1 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(90, 101, 15)"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def highest_powered_square(serial_number, S):\n",
    "    R = range(S+1)\n",
    "    accu = cumulative_power(serial_number, S)\n",
    "    def square_power(lts):\n",
    "        left, top, side = lts\n",
    "        return region_power(accu, top, left, top+side-1, left+side-1)\n",
    "    return max(\n",
    "        ((left, top, side)\n",
    "        for side in range(1, S+1)\n",
    "        for top, left in its.product(range(1, S-side+2), repeat=2)),\n",
    "        key=square_power)\n",
    "\n",
    "# Check the supplied example answers\n",
    "assert highest_powered_square(18, 300) == (90, 269, 16)\n",
    "assert highest_powered_square(42, 300) == (232, 251, 12)\n",
    "\n",
    "print(serial_number, S)\n",
    "%time highest_powered_square(serial_number, S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 12](https://adventofcode.com/2018/day/12) Subterranean Sustainability\n",
    "This looks like a one dimensional [game of life](http://wordaligned.org/life)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#..#.#..##......###...###\n",
      "#...#....#.....#..#..#..#\n",
      "##..##...##....#..#..#..##\n",
      "#.#...#..#.#....#..#..#...#\n",
      "#.#..#...#.#...#..#..##..##\n"
     ]
    }
   ],
   "source": [
    "def parse_input(data):\n",
    "    'Read initial state and rules'\n",
    "    rules = {}\n",
    "    for line in data.splitlines():\n",
    "        if 'initial state' in line:\n",
    "            state = line.split()[2]\n",
    "        elif '=>' in line:\n",
    "            src, _, dst = line.split()\n",
    "            rules[src] = dst\n",
    "    return state, rules\n",
    "\n",
    "def trim(state, pos0):\n",
    "    begin, end = state.find('#'), state.rfind('#')\n",
    "    return state[begin:end+1], pos0-begin\n",
    "\n",
    "def grow_plants(state, rules):\n",
    "    pos0 = 0\n",
    "    while True:\n",
    "        state, pos0 = trim(state, pos0)\n",
    "        yield state, pos0\n",
    "        # Pad the state with enough blanks to apply the rules\n",
    "        padded = '....' + state + '....'\n",
    "        state = cat(rules.get(padded[p:p+5], '.') for p,c in enumerate(padded[2:-2]))\n",
    "        pos0 += 2\n",
    "\n",
    "example_setup = '''\\\n",
    "initial state: #..#.#..##......###...###\n",
    "\n",
    "...## => #\n",
    "..#.. => #\n",
    ".#... => #\n",
    ".#.#. => #\n",
    ".#.## => #\n",
    ".##.. => #\n",
    ".#### => #\n",
    "#.#.# => #\n",
    "#.### => #\n",
    "##.#. => #\n",
    "##.## => #\n",
    "###.. => #\n",
    "###.# => #\n",
    "####. => #'''\n",
    "\n",
    "# Let's check the output against the example shown\n",
    "state, rules = parse_input(example_setup)\n",
    "print('\\n'.join(s for s, _ in take(grow_plants(state, rules), 5)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2040"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sum_of_plant_positions(setup, time):\n",
    "    plants = grow_plants(*parse_input(setup))\n",
    "    state, pos0 = next(its.islice(plants, time, None))\n",
    "    return sum(i - pos0 for i, c in enumerate(state) if c == '#')\n",
    "\n",
    "assert sum_of_plant_positions(example_setup, 20) == 325\n",
    "sum_of_plant_positions(day(12), 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part two, we're asked for the value returned by `sum_of_plant_positions()` when `time=50_000_000_000`. This is way too big to run directly. Let's see if the pattern repeats."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "192 -96 191 -95\n"
     ]
    }
   ],
   "source": [
    "def repeat(setup):\n",
    "    '''Grow plants from initial setup until a state repeats\n",
    "    \n",
    "    Returns (state, time of repeat, pos0 at repeat, time first seen, pos0 first seen)\n",
    "    '''\n",
    "    seen = {}\n",
    "    for t, (state, pos0) in enumerate(grow_plants(*parse_input(setup))):\n",
    "        if state in seen:\n",
    "            return (state, t, pos0, *seen[state])\n",
    "        seen[state] = t, pos0\n",
    "\n",
    "state, t_repeat, pos0_repeat, t_first_seen, pos0_first_seen = repeat(day(12))\n",
    "print(t_repeat, pos0_repeat, t_first_seen, pos0_first_seen)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This tells us the state at time `192` is the same as the state at time `191`, shifted one to the left. Now we can figure out the state at `time=50_000_000_000`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1700000000011"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "T = 50_000_000_000\n",
    "pos0 = -96 - T + 192\n",
    "sum(i - pos0 for i, c in enumerate(state) if c == '#')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 13](https://adventofcode.com/2018/day/13) Mine Cart Madness\n",
    "Carts are moving round a grid, according to simple rules. The challenge for part one is to locate the first collision. This can be done by reading in the initial set up and then applying the rules to simulate the carts' movements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Complex numbers can be used to represent both position and direction.\n",
    "\n",
    "# Directions to step\n",
    "N, E, S, W = -1j, 1, 1j, -1\n",
    "# Ways to turn through 90 degrees\n",
    "# Note: multiplying a direction by a turn effects that turn\n",
    "LEFT, AHEAD, RIGHT = -1j, 1, 1j \n",
    "\n",
    "class Cart:\n",
    "    'A cart on a grid'\n",
    "\n",
    "    def __init__(self, pos, dir_):\n",
    "        'Initialise, given position and direction'\n",
    "        self.pos = pos\n",
    "        self.dir = dir_\n",
    "        self.turn = its.cycle([LEFT,AHEAD,RIGHT])\n",
    "\n",
    "    def step(self, track):\n",
    "        'Step along the track, returning new position'\n",
    "        self.pos += self.dir\n",
    "        # Recalculate direction\n",
    "        at = track[self.pos]\n",
    "        if   at == '+' : self.dir = next(self.turn) * self.dir\n",
    "        elif at == '/' : self.dir = {N:E, S:W, W:S, E:N}[self.dir]\n",
    "        elif at == '\\\\': self.dir = {N:W, S:E, E:S, W:N}[self.dir]\n",
    "        return self.pos\n",
    "\n",
    "    def __lt__(self, o):\n",
    "        # We need to advance the carts in order\n",
    "        return (self.pos.imag, self.pos.real) < (o.pos.imag, o.pos.real)\n",
    "    \n",
    "    def __str__(self):\n",
    "        return {N:'^', S:'v', E:'>', W:'<'}[self.dir] "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to read in the initial setup."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "/->-\\        \n",
      "|   |  /----\\\n",
      "| /-+--+-\\  |\n",
      "| | |  | v  |\n",
      "\\-+-/  \\-+--/\n",
      "  \\------/   \n"
     ]
    }
   ],
   "source": [
    "def read_setup(data):\n",
    "    'Read the setup from `data`, returning carts and track.'\n",
    "    cart_to_track = {'^':'|','v':'|','>':'-','<':'-'}\n",
    "    cart_or_track = set('^v><+|-/\\\\')\n",
    "    cart_to_dir = {'^':N, 'v':S, '>':E, '<':W}\n",
    "\n",
    "    all_ = {complex(x,y): c\n",
    "            for y, row in enumerate(data.splitlines())\n",
    "            for x, c in enumerate(row)}\n",
    "\n",
    "    carts = {Cart(p, cart_to_dir[c]) for p,c in all_.items()\n",
    "             if c in cart_to_track}\n",
    "\n",
    "    track = {p: cart_to_track.get(c, c)\n",
    "             for p,c in all_.items() if c in cart_or_track}\n",
    "\n",
    "    return carts, track\n",
    "\n",
    "\n",
    "def draw(carts, track):\n",
    "    width = int(max(p.real for p in track))\n",
    "    height = int(max(p.imag for p in track))\n",
    "    pic = {**track, **{cart.pos: str(cart) for cart in carts}}\n",
    "    draw_grid({p: pic.get(complex(*p), ' ') \n",
    "               for p in its.product(range(width+1), range(height+1))})\n",
    "\n",
    "example_13 = read_setup(\n",
    "r'''/->-\\        \n",
    "|   |  /----\\\n",
    "| /-+--+-\\  |\n",
    "| | |  | v  |\n",
    "\\-+-/  \\-+--/\n",
    "  \\------/   \n",
    "''')\n",
    "\n",
    "draw(*example_13)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part one, we want to know where the first crash occurs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(136, 36)"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def first_crash(carts, track):\n",
    "    while True:\n",
    "        for cart in sorted(carts):\n",
    "            pos = cart.step(track)\n",
    "            if ilen(c for c in carts if c.pos == pos) > 1:\n",
    "                return int(pos.real), int(pos.imag)\n",
    "\n",
    "assert first_crash(*example_13) == (7, 3)\n",
    "first_crash(*read_setup(day(13)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two asks for the position of the final cart after the others have crashed out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(53, 111)\n"
     ]
    }
   ],
   "source": [
    "def last_cart_pos(carts, track):\n",
    "    crashed = set()\n",
    "    while len(carts) > 1:\n",
    "        for cart in sorted(carts):\n",
    "            pos = cart.step(track)\n",
    "            at_pos = {c for c in carts-crashed if c.pos==pos}\n",
    "            if len(at_pos) > 1:\n",
    "                crashed |= at_pos\n",
    "        carts -= crashed\n",
    "    assert len(carts) == 1\n",
    "    pos = carts.pop().pos\n",
    "    return int(pos.real), int(pos.imag)\n",
    "\n",
    "example_13_part2 = read_setup(\n",
    "r'''/>-<\\  \n",
    "|   |  \n",
    "| /<+-\\\n",
    "| | | v\n",
    "\\>+</ |\n",
    "  |   ^\n",
    "  \\<->/  \n",
    "''')\n",
    "\n",
    "assert last_cart_pos(*example_13_part2) == (6, 4)\n",
    "print(last_cart_pos(*read_setup(day(13))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 14](https://adventofcode.com/2018/day/14) Chocolate Charts\n",
    "A pair of elves are inventing recipes, which they do by combining numbers from a list of existing recipes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[3, 7, 1, 0, 1, 0, 1, 2, 4],\n",
       " [3, 7, 1, 0, 1, 0, 1, 2, 4],\n",
       " [3, 7, 1, 0, 1, 0, 1, 2, 4],\n",
       " [3, 7, 1, 0, 1, 0, 1, 2, 4],\n",
       " [3, 7, 1, 0, 1, 0, 1, 2, 4]]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def digits(N):\n",
    "    '''Return a list of the digits in +ve int N\n",
    "    \n",
    "    >>> digits(123)\n",
    "    [1, 2, 3]\n",
    "    '''\n",
    "    return [int(d) for d in str(N)]\n",
    "\n",
    "def generate_recipes(recipes, elf1, elf2):\n",
    "    '''Generate the list of recipes\n",
    "    \n",
    "    - recipes: initial list of recipes\n",
    "    - elf1, elf2: position of santa's helpers\n",
    "    '''\n",
    "    digits_ = [digits(n) for n in range(19)]\n",
    "    while True:\n",
    "        yield recipes\n",
    "        recipes += digits_[recipes[elf1] + recipes[elf2]]\n",
    "        elf1 = (elf1 + recipes[elf1] + 1) % len(recipes)\n",
    "        elf2 = (elf2 + recipes[elf2] + 1) % len(recipes)\n",
    "\n",
    "# Check generate_recipes() matches the supplied example\n",
    "take(generate_recipes([3, 7], 0, 1), 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "input14 = 540391"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're asked for the 10 recipes which follow the first N, where N is the puzzle input -- in my case, `540391`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1474315445\n"
     ]
    }
   ],
   "source": [
    "gen = generate_recipes([3, 7], 0, 1)\n",
    "recipes = next(r for r in gen if len(r) >= input14 + 10)\n",
    "print(cat(map(str, recipes[input14:input14+10])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two asks when we see the recipe sequence formed from the digits of N, the puzzle input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "def day14_part2(input_n):\n",
    "    gen = generate_recipes([3, 7], 0, 1)\n",
    "    seq = digits(input_n)\n",
    "    L = len(seq)\n",
    "    for recipes in gen:\n",
    "        if recipes[-L:] == seq: \n",
    "            return len(recipes) - L\n",
    "        if recipes[-L-1:-1] == seq: \n",
    "            return len(recipes) - L - 1\n",
    "\n",
    "assert day14_part2(51589) == 9\n",
    "assert day14_part2(59414) == 2018"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 20.7 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "20278122"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time day14_part2(input14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 15](https://adventofcode.com/2018/day/15) Beverage Bandits\n",
    "Elves and Goblins do battle in a cave. Each round, the combatants operate in reading order -- top to bottom, left to right -- moving and attacking. They move towards the closest accessible target, again using reading order to break ties. If a target is in range, or becomes in range, it is attacked."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "################################\n",
      "#####G.####...........##########\n",
      "######G#.##.#.G......###########\n",
      "######...##G#.........###...####\n",
      "########.##...G.......###...####\n",
      "########..##.....G....#.#......#\n",
      "######...G##G..................#\n",
      "#######..#########G............#\n",
      "#######...#########..G.........#\n",
      "#######..G.#######..........####\n",
      "######......G..###..EE......####\n",
      "######..#.G............E#...####\n",
      "#######.#.....#####........#####\n",
      "#######G.....#######...#########\n",
      "#######.....#########.##########\n",
      "#######.....#########.##########\n",
      "#######G....#########.##########\n",
      "######...EG.#########.##########\n",
      "######..G...#########.##########\n",
      "#######......#######..##########\n",
      "########.E....#####...##########\n",
      "#...###...G.........E.##########\n",
      "#....#......G....#..############\n",
      "#.........G...#......###########\n",
      "#...#.........#......###########\n",
      "##.......#######.....###########\n",
      "#.......########......##########\n",
      "##...E.E########...E...#########\n",
      "#####....###########.E.#########\n",
      "######..#############..#########\n",
      "#######...######################\n",
      "################################\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(day(15))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The input cave system 1) isn't so big and 2) is fully enclosed (by the `#` rocks). The difficulty with the puzzle will be implementing the sophisticated logic for the battle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Bandits:\n",
    "    ROCK, OPEN, ELF, GOBLIN = '#.EG'\n",
    "    def __init__(self, map_data, hit_points=200, elf_power=3, goblin_power=3):\n",
    "        ''' Initialise the map and units\n",
    "\n",
    "        - hit_points: initial # hit points for each unit \n",
    "        - power: the power of each unit\n",
    "        '''\n",
    "        self.power = {self.ELF: elf_power, self.GOBLIN: goblin_power}\n",
    "        rows = map_data.splitlines()\n",
    "        self.map = {(y, x): c \n",
    "                    for y, row in enumerate(rows)\n",
    "                    for x, c in enumerate(row)}\n",
    "        self.hit_points = {\n",
    "            p: hit_points for p in filter(self.elf_or_goblin, self.map)}\n",
    "        self.W = range(len(rows[0]))\n",
    "        self.H = range(len(rows))\n",
    "        self.casualties = collections.Counter()\n",
    "\n",
    "    def __str__(self):\n",
    "        rows = []\n",
    "        for y in self.H:\n",
    "            sqs = cat(self.map[(y, x)] for x in self.W)\n",
    "            pts = ' '.join(str(self.hit_points.get((y, x), '')) for x in self.W)\n",
    "            rows.append(f'{sqs}\\t{pts}')\n",
    "        return ncat(rows)\n",
    "\n",
    "    def elf_or_goblin(self, p):\n",
    "        'Return True if position `p` contains an Elf or a Goblin'\n",
    "        return self.map[p] in {self.ELF, self.GOBLIN}\n",
    "\n",
    "    def opposition(self, p):\n",
    "        'Elves attack goblins and vice-versa'\n",
    "        return self.ELF if self.map[p]==self.GOBLIN else self.GOBLIN\n",
    "\n",
    "    def advance_on_target(self, p):\n",
    "        ''' Advance on the target chosen by the unit at `p`\n",
    "        \n",
    "        Returns the new position of `p` if a target is chosen, None otherwise\n",
    "        '''\n",
    "        # We're looking for the first step on the shortest path\n",
    "        # to an opponent of p.\n",
    "        # Use a BFS to find such paths\n",
    "        oppo = self.opposition(p)\n",
    "        \n",
    "        fringe = {p}\n",
    "        visited = {p}\n",
    "        first_step = {}\n",
    "        stop = self.ROCK + self.map[p] # Don't visit walls or allies\n",
    "        BR = 1e6, 1e6 # Greater than any point in the map\n",
    "        \n",
    "        while fringe:\n",
    "            steps = [(f, n) \n",
    "                for f in fringe for n in neighbours4(*f)\n",
    "                if n not in visited and self.map[n] not in stop]\n",
    "            for f, n in steps:\n",
    "                # Use min to put first steps of shortest paths in reading order \n",
    "                first_step[n] = min(first_step.get(f, n), first_step.get(n, BR))\n",
    "            fringe = {n for _, n in steps}\n",
    "            opponents = sorted(n for n in fringe if self.map[n]==oppo)\n",
    "            if opponents:\n",
    "                return first_step[opponents[0]]\n",
    "            visited |= fringe\n",
    "    \n",
    "    def attack(self, p):\n",
    "        \"Unit at `p` attacks.\"\n",
    "        # Select the target in range with the fewest hit points, if any.\n",
    "        # Break ties using reading order\n",
    "        oppo = self.opposition(p)\n",
    "        target = min(\n",
    "            (n for n in neighbours4(*p) if self.map[n]==oppo),\n",
    "            default=None, key=lambda n: (self.hit_points[n], n))\n",
    "        if target:\n",
    "            self.hit_points[target] -= self.power[self.map[p]]\n",
    "            if self.hit_points[target] <= 0:\n",
    "                self.casualties[oppo] += 1\n",
    "                del self.hit_points[target]\n",
    "                self.map[target] = '.'\n",
    "    \n",
    "    def move(self, p, q):\n",
    "        \"Move a unit (elf or goblin) from `p` to `q`\"\n",
    "        self.map[q] = self.map[p]\n",
    "        self.map[p] = self.OPEN\n",
    "        self.hit_points[q] = self.hit_points[p]\n",
    "        del self.hit_points[p]\n",
    "    \n",
    "    def next_round(self):\n",
    "        'Plays the next round, returning `True` if combat should continue'\n",
    "        # Note: the map (a dict) was created in reading order\n",
    "        # and is therefore traversed in reading order\n",
    "        units = [p for p in self.map if self.elf_or_goblin(p)]\n",
    "        for p in units:\n",
    "            if self.elf_or_goblin(p):\n",
    "                oppo = self.opposition(p)\n",
    "                if oppo not in self.map.values():\n",
    "                    # Combat ends when a player finds no target\n",
    "                    return False\n",
    "                elif any(self.map[n]==oppo for n in neighbours4(*p)): \n",
    "                    self.attack(p)\n",
    "                else:\n",
    "                    step = self.advance_on_target(p)\n",
    "                    if step:\n",
    "                        self.move(p, step)\n",
    "                        self.attack(step)\n",
    "        return True\n",
    "\n",
    "    \n",
    "    def play(self, verbose=False, max_rounds=-1):\n",
    "        ''' Engage in combat\n",
    "        \n",
    "        - verbose - if True, print out map and hit points after each round\n",
    "        - max_rounds - how many rounds to play (-1 => play to finish)\n",
    "        \n",
    "        Returns the \"outcome\" - the number of full rounds multiplied by\n",
    "        the hit points of remaining units\n",
    "        '''\n",
    "        def render(): \n",
    "            if verbose: print(self)\n",
    "            return True\n",
    "        full_rounds = 0\n",
    "        stop = its.count(max_rounds, -1)\n",
    "        while next(stop) and render() and self.next_round():\n",
    "            full_rounds += 1\n",
    "            if verbose: print()\n",
    "        render()\n",
    "        return self.casualties, full_rounds * sum(self.hit_points.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#######\t      \n",
      "#.G...#\t  200    \n",
      "#...EG#\t    200 200 \n",
      "#.#.#G#\t     200 \n",
      "#..G#E#\t   200  200 \n",
      "#.....#\t      \n",
      "#######\t      \n",
      "\n",
      "#######\t      \n",
      "#..G..#\t   200   \n",
      "#...EG#\t    197 197 \n",
      "#.#G#G#\t   200  197 \n",
      "#...#E#\t     197 \n",
      "#.....#\t      \n",
      "#######\t      \n",
      "\n",
      "#######\t      \n",
      "#...G.#\t    200  \n",
      "#..GEG#\t   200 188 194 \n",
      "#.#.#G#\t     194 \n",
      "#...#E#\t     194 \n",
      "#.....#\t      \n",
      "#######\t      \n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(Counter(), 2340)"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "example_15='''\\\n",
    "#######\n",
    "#.G...#\n",
    "#...EG#\n",
    "#.#.#G#\n",
    "#..G#E#\n",
    "#.....#\n",
    "#######\n",
    "'''\n",
    "\n",
    "Bandits(example_15).play(verbose=True, max_rounds=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That matches the worked example. Now see where we are after 28 rounds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#######\t      \n",
      "#G....#\t 200     \n",
      "#.G...#\t  131    \n",
      "#.#.#G#\t     116 \n",
      "#...#E#\t     113 \n",
      "#....G#\t     200 \n",
      "#######\t      \n"
     ]
    }
   ],
   "source": [
    "bandits = Bandits(example_15)\n",
    "bandits.play(max_rounds=28)\n",
    "print(bandits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yes, that's also right. Run to completion and check the outcome."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#######\t      \n",
      "#G....#\t 200     \n",
      "#.G...#\t  131    \n",
      "#.#.#G#\t     116 \n",
      "#...#E#\t     113 \n",
      "#....G#\t     200 \n",
      "#######\t      \n"
     ]
    }
   ],
   "source": [
    "assert Bandits(example_15).play()[1] == 27730\n",
    "print(bandits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Check another example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "example_15b = '''\\\n",
    "#########\n",
    "#G......#\n",
    "#.E.#...#\n",
    "#..##..G#\n",
    "#...##..#\n",
    "#...#...#\n",
    "#.G...G.#\n",
    "#.....G.#\n",
    "#########'''\n",
    "assert Bandits(example_15b).play()[1] == 18740"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Counter({'E': 10, 'G': 4}), 217890)"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Bandits(day(15)).play()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two allows us to increase the elves' attack power until it's large enough for them to win without any casualties.\n",
    "I had to edit my `Bandits` class, which had parameterised `attack_power` to offer `elf_attack_power` and `goblin_attack_power` as independent parameters. Additionally, I modified `Bandits.play()` to provide the number of casualties on both sides."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "counts, outcome = Bandits(example_15, elf_power=15).play()\n",
    "assert not counts['E']\n",
    "assert outcome == 4988\n",
    "assert 'E' in Bandits(example_15, elf_power=14).play()[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 3.8 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "43645"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Now we can find the smallest elf_power which gives a victory\n",
    "# We could use a binary search here - but counting up from\n",
    "# 3 is quick enough\n",
    "\n",
    "results = (Bandits(day(15), elf_power=p).play() for p in its.count(3))\n",
    "%time next(outcome for counts, outcome in results if not counts['E'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 16](https://adventofcode.com/2018/day/16) Chronal Classification\n",
    "We are given a description of various computer instructions and have to figure out which of them might produce results given a sample showing the register values before and after. I split the input into two sections: part one requires the first only, which is a list of samples, the last of which reads:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before: [3, 2, 0, 3]\n",
      "11 2 0 2\n",
      "After:  [3, 2, 1, 3]\n"
     ]
    }
   ],
   "source": [
    "! tail -n 3 input/16_part_one"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((3, 2, 0, 3), (11, 2, 0, 2), (3, 2, 1, 3))"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def load_part_one(data):\n",
    "    'Load up (before, instruction, after) triples'\n",
    "    xs = array(data)\n",
    "    return take(chunked((x for x in xs if x), 3))\n",
    "\n",
    "samples = load_part_one(open('input/16_part_one').read())\n",
    "samples[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have 16 possible operations on a processor with 4 registers. The operations can be \"register\" or \"immediate\", applying to the value in the register specified in the instruction or to the value itself respectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "def addr(regs, A, B, C): regs[C] = regs[A] +  regs[B]\n",
    "def addi(regs, A, B, C): regs[C] = regs[A] +       B\n",
    "def mulr(regs, A, B, C): regs[C] = regs[A] *  regs[B]\n",
    "def muli(regs, A, B, C): regs[C] = regs[A] *       B\n",
    "def banr(regs, A, B, C): regs[C] = regs[A] &  regs[B]\n",
    "def bani(regs, A, B, C): regs[C] = regs[A] &       B\n",
    "def borr(regs, A, B, C): regs[C] = regs[A] |  regs[B]\n",
    "def bori(regs, A, B, C): regs[C] = regs[A] |       B\n",
    "def setr(regs, A, B, C): regs[C] = regs[A]\n",
    "def seti(regs, A, B, C): regs[C] =      A\n",
    "def gtir(regs, A, B, C): regs[C] =      A  >  regs[B]\n",
    "def gtri(regs, A, B, C): regs[C] = regs[A] >       B\n",
    "def gtrr(regs, A, B, C): regs[C] = regs[A] > regs[B]\n",
    "def eqir(regs, A, B, C): regs[C] =      A  == regs[B]\n",
    "def eqri(regs, A, B, C): regs[C] = regs[A] ==      B\n",
    "def eqrr(regs, A, B, C): regs[C] = regs[A] == regs[B]\n",
    "\n",
    "all_ops = [\n",
    "    addr, addi, mulr, muli, banr, bani, borr, bori, setr, seti,\n",
    "    gtir, gtri, gtrr, eqir, eqri, eqrr\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we've implemented the operators, part one asks how many samples in the puzzle input behave like three or more opcodes?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "580"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def valid_for_sample(op, sample):\n",
    "    'Return `True` iff the op is valid for the sample'\n",
    "    before, instruction, after = sample\n",
    "    regs, after = list(before), list(after)\n",
    "    code, A, B, C = instruction\n",
    "    op(regs, A, B, C)\n",
    "    return regs == after\n",
    "\n",
    "def possible_ops(all_ops, sample):\n",
    "    'Return the subset of `all_ops` which are valid for the sample'\n",
    "    return {op for op in all_ops if valid_for_sample(op, sample)}\n",
    "\n",
    "# Try out the example\n",
    "assert len(possible_ops(all_ops, ((3, 2, 1, 1), (9, 2, 1, 2), (3, 2, 2, 1)))) == 3\n",
    "\n",
    "# Now get the answer for part one\n",
    "ilen(_ for sample in samples if len(possible_ops(all_ops, sample)) >= 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part two, we learn the samples are self-consistent, and we can deduce which opcode corresponds to which operator. We need to figure out the mapping `opcode => operation` where `op_code` is the opcode value and `operation` is the function -- one of `all_ops`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "def map_code2op(all_ops, samples):\n",
    "    'Return the {code => op} mapping consistent with samples'\n",
    "    code2op = {n:set(all_ops) for n in range(16)}\n",
    "    for sample in samples:\n",
    "        code = sample[1][0]\n",
    "        code2op[code] &= possible_ops(all_ops, sample)\n",
    "    while any(len(ops) > 1 for ops in code2op.values()):\n",
    "        known_codes = {code for code, ops in code2op.items() if len(ops)==1}\n",
    "        known_ops = {op for code in known_codes for op in code2op[code]}\n",
    "        for code in set(code2op) - known_codes:\n",
    "            code2op[code] -= known_ops\n",
    "    assert all(len(ops)==1 for ops in code2op.values())\n",
    "    return {code: ops.pop() for code, ops in code2op.items()}\n",
    "\n",
    "code2op = map_code2op(all_ops, samples)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we're asked to run the program given as the second part of the input, and find the final value of register `0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "537"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def run_prog(code2op, prog):\n",
    "    regs = [0, 0, 0, 0]\n",
    "    for code, A, B, C in prog:\n",
    "        code2op[code](regs, A, B, C)\n",
    "    return regs\n",
    "\n",
    "test_prog = array(open('input/16_part_two').read())\n",
    "regs = run_prog(code2op, test_prog)\n",
    "regs[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 17](https://adventofcode.com/2018/day/17) Reservoir Research\n",
    "Water sinks into the ground. It stops when it hits clay. The worked example suggests two modes: \n",
    "- fill, when the water is contained by horizontal and vertical bounds\n",
    "- spill, when the water flows horizontally and down"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "............#.\n",
      ".#..#.......#.\n",
      ".#..#..#......\n",
      ".#..#..#......\n",
      ".#.....#......\n",
      ".#.....#......\n",
      ".#######......\n",
      "..............\n",
      "..............\n",
      "....#.....#...\n",
      "....#.....#...\n",
      "....#.....#...\n",
      "....#######...\n",
      "!!!!!!!!!!!!!!\n"
     ]
    }
   ],
   "source": [
    "example_17 = '''\\\n",
    "x=495, y=2..7\n",
    "y=7, x=495..501\n",
    "x=501, y=3..7\n",
    "x=498, y=2..4\n",
    "x=506, y=1..2\n",
    "x=498, y=10..13\n",
    "x=504, y=10..13\n",
    "y=13, x=498..504'''\n",
    "\n",
    "def read_ground(data):\n",
    "    'Reads in the ground, as specified by the example data above'\n",
    "    ground = collections.defaultdict(lambda: '.')\n",
    "    fill = ground.update\n",
    "\n",
    "    for row in data.splitlines():\n",
    "        v, lo, hi = ints(row)\n",
    "        if row.startswith('x'): \n",
    "            fill(((v,y), '#') for y in range(lo, hi+1))\n",
    "        elif row.startswith('y'):\n",
    "            fill(((x,v), '#') for x in range(lo, hi+1))\n",
    "    \n",
    "    # Add \"!\" at the base level so we know when we're in pure sand\n",
    "    x, X = min(map(first, ground)), max(map(first, ground))\n",
    "    Y = max(map(second, ground))\n",
    "    fill(((x, Y+1), '!') for x in range(x-1, X+2))\n",
    "\n",
    "    return ground\n",
    "\n",
    "example_ground = read_ground(example_17)\n",
    "draw_grid(example_ground, '.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's try and implement the fill and spill flow."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "            # \n",
      " #  #       # \n",
      " #  #  #      \n",
      " #  #  #      \n",
      " #     #      \n",
      " #     #      \n",
      " #######      \n",
      "              \n",
      "              \n",
      "    #     #   \n",
      "    #     #   \n",
      "    #     #   \n",
      "    #######   \n",
      "!!!!!!!!!!!!!!\n",
      "\n",
      "      |       \n",
      "      |     # \n",
      " #  #||||   # \n",
      " #  #~~#|     \n",
      " #  #~~#|     \n",
      " #~~~~~#|     \n",
      " #~~~~~#|     \n",
      " #######|     \n",
      "        |     \n",
      "   |||||||||  \n",
      "   |#~~~~~#|  \n",
      "   |#~~~~~#|  \n",
      "   |#~~~~~#|  \n",
      "   |#######|  \n",
      "!!!!!!!!!!!!!!\n"
     ]
    }
   ],
   "source": [
    "def step_L(p): return (left(p, d) for d in its.count())\n",
    "def step_R(p): return (right(p, d) for d in its.count())\n",
    "def step_D(p): return (down(p, d) for d in its.count())\n",
    "def layer(L, R): return ((x, L[1]) for x in range(L[0], R[0]))\n",
    "def column(T, B): return ((T[0], y) for y in range(T[1], B[1]))\n",
    "\n",
    "def left (p, d=1): return p[0]-d, p[1]\n",
    "def right(p, d=1): return p[0]+d, p[1]\n",
    "def down (p, d=1): return p[0]  , p[1]+d\n",
    "def up   (p, d=1): return p[0]  , p[1]-d\n",
    "\n",
    "def water_flow(ground, source):\n",
    "    ' Model water sinking into `ground`, starting from `source` '\n",
    "    def stop(p):\n",
    "        'Should we stop spreading horizontally at `p`?'\n",
    "        # Yes, if we've hit clay or if there's sand or water beneath\n",
    "        return ground[p] == '#' or ground[down(p)] in '.|'\n",
    "\n",
    "    fill = ground.update\n",
    "    flow_q = {source}\n",
    "    \n",
    "    while flow_q:\n",
    "        source = flow_q.pop()\n",
    "        # Vertical \"Spill\": go down until we hit clay/water/baseline\n",
    "        D = next(d for d in step_D(source) if ground[d] in '#~!')\n",
    "        fill((d, '|') for d in column(source, D))\n",
    "\n",
    "        if ground[D] == '!': continue # Bottomed out\n",
    "\n",
    "        # Horizontal \"Fill\": spread across left and right\n",
    "        D = up(D)\n",
    "        L = next(p for p in step_L(D) if stop(p))\n",
    "        R = next(p for p in step_R(D) if stop(p))\n",
    "\n",
    "        if (ground[L], ground[R]) == ('#', '#'):    \n",
    "            fill((p, '~') for p in layer(right(L), R)) # Fill this level\n",
    "            flow_q.add(up(D))\n",
    "        elif ground[L] == '#':                         # Spill right\n",
    "            fill((p, '|') for p in layer(right(L), right(R)))\n",
    "            flow_q.add(R)\n",
    "        elif ground[R] == '#':                         # Spill Left\n",
    "            fill((p, '|') for p in layer(L, R))\n",
    "            flow_q.add(L)\n",
    "        else:\n",
    "            fill((p, '|') for p in layer(L, right(R))) # Spill both sides\n",
    "            flow_q |= {L, R}\n",
    "\n",
    "    return ground\n",
    "\n",
    "water_source = 500, 0\n",
    "example_ground = read_ground(example_17)\n",
    "draw_grid(example_ground)\n",
    "print()\n",
    "ground = water_flow(example_ground, water_source)\n",
    "draw_grid(ground)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That looks OK. Let's check the result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(35707, 29293)"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def count_wet_tiles(ground_data, water_source):\n",
    "    ground = read_ground(ground_data)\n",
    "    y_range = range(min(map(second, ground)), max(map(second, ground))+1)\n",
    "    ground = water_flow(ground, water_source)\n",
    "    tiles = collections.Counter(v for (_, y), v in ground.items() if y in y_range)\n",
    "    return tiles['|'] + tiles['~'], tiles['~']\n",
    "\n",
    "assert count_wet_tiles(example_17, water_source) == (57, 29)\n",
    "count_wet_tiles(day(17), water_source)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two asks how many cells have standing water in (marked as `~` on the diagram). I adapted `count_wet_tiles` to return that information. For fun and education, let's try and plot the results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.image.AxesImage at 0x261997b39b0>"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeoAAAdhCAYAAADcytwbAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAOwwAADsMBx2+oZAAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzs3duS27iSBVDoxPz/L2Me3LJVKl14AcAEcq0Ix3j62GWJIrGRCZC61VoLABDT/65+AQDAe4IaAAIT1AAQmKAGgMAENQAEJqgBIDBBDQCBCWoACExQA0BgghoAAhPUABCYoAaAwAQ1AAT2f1e/gB5ut5uvBINoainldvWLgOvVWnddCSpqAAhMUANAYIIaAAIT1AAQmKAGmqm1/vi/wHmCGoDLmdy9J6iBTXYPpPXpV3n6PQw262RgyfuogQBePM6g1lJuF95MXWstt5ubuZmLihqYwqzVEJwlqAEgMEENAIEJaoCOerfsLQmsT1DDF+4Njq3W+vcXrMiub2B6t9tNUC/AZ/iaoAbgcm6be0/rG2hKVQRtqahZhodZjPA5hB1+aE9FzVCqLYB9BDUwPRNAViaoYSKrB9KRW+Fut9vfX7Aia9SwwbvgyLYuvvg8oZvVJ1j0Jajhi0xB/Emz43Ais1oG3rtJVuvJl/OHswQ1LORoyMzQGYj++qAXa9QAEJiKGhZjPRTWIqhhIdrD9DbDMsnd/bXO9Jpf0foGQtERuI5jH5OKGghj5qoHelFRA0BgKmqgmVpruZUNVfHRDquCm4QENdDWrf06Z61l2wQAFqT1DQCBCWoAlrXCTnatbwCWtMpdBCpqAAhMUAMQ1gqt67O0voG0hMA5sz+acxaCGgb6FgwGvXEc69dMXuIR1DDYu4AwQHI1k5eYBDUMJpCBPQQ1DJShYjEPycXEsz9BzXAu7HV1nYg4bcLJMPGMQFAzlAsbYB/3UQNAYCpqOEkrH+hJUMMJWvnHPT8sw8Mz4DWtbwAITEUNdLWrUv62inD/3xXeJCKogThun5O61lJuUppktL4B+OvV5kgbJq8lqLmcQQDgPUHNboIVYBxBfQFBB8BWgvoNYZqDzxmITlDDB4IcuJrbs+jqMeg8dQpgP0FNd7fbTWXKS84L+E5Q053BmFePHNNggW2sUQc3MuR6/Fu32+3vr6teA7COjGOEippp9Pp2pZku/Fm/YWqiQ0wws57zLQlqUos4AKw2MDV/L0KfZLS+ASAwQQ1ASrMse2l9N/TqQ1+phQnATyOWqgR1Y48f2CyztSNWfm8AkQhqdtMloJut878980SnK5MT1EAotdQmD0OptZSblGYBgroxLWEAWhLUDWkJt2GyA/CPoCYUkx2An9xHDYT32GTRcCEbFfUHWrAAXE1Qv6EFC7GYN48TrUiJ9npGE9RAeObN40QrUqK9nitYo+aw7LNcgBEEdQAC7yfHA+AfQd2QgAGgNUENxSSLz5wfXElQwwkGcO6cC/Ri1zcQjsyDfwQ1EErT23GCBH6t1W1GHKb1DRCIFjrPBDUABKb1PYGZZtjPLT4tPyCyGcZXQR2ckAPoY5bxVesbAAIT1AAQmNY3/CfSWlWk1wKP7DsZT1BDibVWFem1wFECvR1BDUmdGUi3/N1aa7mVAz+/dTNhz8/rmCu6JBwlqIF+bnOEU63l2KRiI5XlekZ2DGwmA4BOWnRSBDXN1Vr//mJO98/OZwjX0/qmKS0+4GqrbWRTUQPAF1d2lwQ18JK2N8Sg9Q38slLbkJxGTDRHTWYFNaeouoBoRkw0R05mBXVjmYJL1QU5ZRrnIhDUDQkuZmPAZS/j3HiCGpIaMeCaB/y22q1D9CeogS6mC6Mvk4re3QcBzjuCGuALAcqV3EcNAIEJagAITFADQGCCGhLxrVgwH0ENhGdiQWZ2fQNTOXwb05as//ZnbP7mAoIaSKOWWg5lfC3l1jCldQjYQ1ADDOSebPayRg0XeVVVqbSAZ4IaAAIT1EBIugvwh6AGLiGIYRtBfYKBBoDeBHVHghyAswQ1AATmPmq40BVdF50emIughotc8eCLmR+20WqCYZ7CbAQ1EF6rCcapnyPguYg1apYTobUb4TXAI+fkvAQ1HPQ48K0yCL57H6u8P3yWMxLUABCYoAaAwGwmAy6jDQvfCWrgEj1uFau1/v25j7+HmWl9A0Bgghrgwb0dry1PFIJ6UQYZ+E8t/x5WUjf8Ymotx74o46g1ajaZfb1vzwU38/vktVpq2fyx1je/f/7/nSabfRs/Zh9fehPUpLFlIIgygyaI2+/zodZSblKagQQ1aQhhYEaCmhS01cBkdVaCGiABk9V5CWqWpHI4zrGDWAQ1y1E5HOfYQTzuowZYhG7ImlTUJ0W+MCK/NuA89x8f8zg2znD8BPUJkT/gyK8NojPJbS/aMb3dbuFe0zuCGgJSKV3HYW/PuXyONWoIZJYZPsxupmtNUANfzTSojebYzOd2u/39NQNBzfQMlP84FmvwOfLIGjUpjFjzNbjG5uNhVoIaGpilhZbBqwlT888nUOibIK5PUAPLyDZhyvZ+s7JGDQCBCWoACExQA0BgghoAArOZDJjLkU3OW/+OvVlLWG0nvKAGplNLbfpM7lpLuUnpJay4E15Qs4TVZtAAd4Ka6a04gwa4s5kMAAJTUUMw2vjHvDtsGi5xZfje9RbvUVBzmQwX6V6OxznPxy/qpOfxdWX4zGe+1iO8dq1vdos6+MFMrh78mYeKGljGTJPImV4r1xLUHGKQIZqZClTVNHsIanYzyACMY40aIDgdrNxU1AAnRQrSCLuUX4l0jGYjqGExBsSxIoZiNCsfoxG32glqWMjKA+Iz8xGiuN1uXSfIgpoworbsiKfLeSL4Oah3F0tQsxRhD4w0YrwR1IRifRXgJ0FNGCphgN/cRw0AgQlqutDCZrT7OefcYzWCmmkZkIEMrFEDc6hvfr/nR7grgAkJamAatdT335KlwcKitL4BIDAVNQB8cPV+GEENAG9E2NMgqOnm6lkowArSBbVdn2M4xgBt2Ez2RBUI83L9sqJ0FTWwpp9NHIHNOlTUABCYihqYiu422aQMautYMCebFMkoXVC70IEZKTDGiHhnULqgBphNtOCIrnXYXh3eNpOxhCuqDRUOnLPyNdTyvQlqptLi5F95cAD6umL8ENQAEJigBpZyr3h0TliFzWRAbPXN76GTaJM8QQ2EV0stmzfdxhpjmUzEHfZa30A60Som+ERQA0BggpowVDkAvwlqdhGmAGMJagAITFADQGCCGliOJRpW4j5qpmMQ5pOft8E6V5ifoGYqER9GANCToAamoJFCVoIaCE8nhUhGL78JagDY6IpJo13fABCYihpY254u5Zk/qztPJ4IaWN6ur8nc+7NrKTcpfZjbLb8T1InUWn+srzz//wAjrTj+9BhXBTW7rTADXuE9AHM4G96Cml1WmAGv8B6APOz6DkzVB4CKOohR68XCH2AugjoRLV+A/loXRIIaABrpURBZowaAwAQ1AAQmqAEgMGvUQApueGBWgpqwojziNMrr4Ljun59JAB1pfXO5I7cyuB8cyEJQ89HeQBSgAG0JagAITFADdPDcXdJt4ihBDQCB2fUNcFR98/ujP84dBrwgqIHrbA23syF44O/Xsi00//y5Nv8mvCKogb8+VXS9qr23QXc1QXs5HYY/rFEDsLyZN/MJamhgzyAw84ABjCeoASAwQZ2Mag5gLjaTBXJliH7bRATANQR1EFF3NkZ9XQBZCGqATnSjaEFQA3TwuhkluNnPZjIANtMlGE9FDXCS7NrPU8e2E9QAJwgbehPUhKCdBvCaoOZyRysS4b4OHyW8J6gTWiHgtBvX4bOEzwR1MgZFvllhIgcrEdTAXyZyEI/7qAEgMEENAIFpfUMj1nahPdeVoIYmrO3+VGstt7LxmGwdhx3idFxXfwhqoI9bm0qo1rI99GFB1qgBIDBBDQCBCeoGRm12sKliPj4zvnGO8I2ghgkYzNnD+bIWQQ1c4p4lMgU+s+u7ETNYAHoQ1A241w+OMb+F77S+gUvcbv9+8du9S6dbh6DmLwMCQDxa33xVa9XeZzfzvvNMns8ZNXb1/ncENdBc80ErYV6ZHHOn9Q0AgamoAdhFS34sQQ1wsZmCT0t+PEENXOp5I062zYuZ3ivHWKPu7OxMeaaZNgDtCWqgi1OTzPr0qzz9HhLR+gbiuf1O5FpLuRVtYvIR1AAsa4XlQ0HN8rJtTgL+WOW6t0ZNKBFmvxFeA8CdoOYwgQbQn6AGgMAENQChZe/e2UxGCtkv9BX12CRo42E+M3zmgnqHGT5QfvOZATNLFdSCliuo5r9zjOC9VEENo5kYfg/g9IcIvhDU/KCyAYhFUPOX6o/Wes/7TCzJQFBzioGSd7pM/B5ONxPLtkbv4bFnaDtBzWEuMoD+BDUAU/vU2VuhoBDUkIwHhbCiV+ffKktzgnqAVieLwRAgH0H9n3sItg7DK4JVoDOFo/PXaEXSt9fjUuQkQQ1cppa67ANPai3lJqVpQFADXz0u3+jWUMq2zt3I7t4q69GvCGqai9R6t3GqnfvSEESz+vXo+6gfGIRi8/kAGamo/7P6jAwy+zTHc+nPIfNEXVADKax8n+3qshdS6YLahck3Nk7BNsbTMVIFtUGXrWycWo/Psy3j6Tipgho4buagy5gpWe9OWJGgZqjVH56/Kp/N3LaG9syTsZUJaoazqQfiMRmLS1BDQpEmRoFeCoQkqCGZSJVTpNfShUkIDXgyGQAEJqjhhUitYSA3rW94snw7lmW4BSsHQc1wqlVo71Vo773W7j/DBCAWQc1QV1z8JgZkJGjXIahZmsEKmF2KzWQqKoBttoyXxtSxVNTFhoweXMgwn6uWpoy/nwnqycwQgC66xPaenvFP5/P2vkeXD08E9UQEIDOopab8tqqzai3lJqV5IcUaNQDMSlADQGBpWt8zrO2Sm001HGFsW1+KoDb40ZuQ5QrOuRy0vgEgMEENnKL1Cn2laH3DCLMEljY9Lcxyvq9AUEMDgu+7Wku4+6sjvqYZON/HEtTAX49VksEYYhDUi9PmZK/79xH3oFsK+wnqBQlnzugV0k5JOMaub+Cv2+329xfzGbnBa/XNZO/e3xXvW1ADQGBa3wynNb++xYstGEpQ85Iw5SjnzQkmOLyg9Q0AgQlqAAhMUHPIlp2Pq+8KBRjBGjXAQkyQ1yOoARZhI9+aBDWHmbkzq953Nbz7+e6m4AhBzSEGG3oQZPCboIaEdEPa2T25+Hbo7/+7+Qr/EdS8ZTBfk4r1YrfP11WtpdykNA8ENS8ZzAFiENQA8EKUrqKgfvBqrcnmFoB8Io37nky2qFprmNkgjPR43rsGWIGKekGRZoIz0kUBIlFRw4VUfH3oKLESFTWwFN0QVqOiBoDABDUABKb1DdCBNXJaEdScZpc0/AxllwMtaX0zFVUKzOnstZv52ldRA5yUOEMYQFA/yTxrA/brsuxjGOKBoH5gnRWAaKxRA0BgghoAAhPUABCYoAaAwAR1YHagA2DXd2Oe0rXNu0mIY8dyjs63v/29hS6Vx3Ez8hh61WsT1Fzm+YTXQWBVtdRmjxWttZTbSindSeTA30tQ88NKJzdzMmGDnwT1omYIXAMyz6Kfs3AFQc0lDMjAIxP39wQ1AJcycf/M7VkAEJiKugMtHOCbT8PEqgWmsfEYQd1Y1hbOahfgau+HmF6NF6uee1nHxhYENaetdgGu9n6AuVmjBoDABDUABKb1DXCRVdejaUtQA1zAVgi20voGgMBU1AAD6HJzlKAG6Kz5LX9CPxWtbwAITFADQGCCGoAf3DYWi6AGSEwoxyeoASAwu74BWNIq3QJBfbFaq29rAn7aki9nMijBkLPSuCqoGxK6QCu11OaPGa21lFuGlF6MoF7YKm0fgMwE9aJU9v3onAAj2fXNEnQPgFUJagAITFBDYDoFgDXqxgysRGeNHeYiqBsy+AHQmtY3KX3rfOiMAFEIagAITOubtFTNwAwENSnZTwDMQlADBKXpQymCGiCkbl0f4T8dm8kAIDAVNcuwOQxYkaCekCdL/eZ4AKvS+p6EahEgJ0ENAIFpfQMkp2MXm6AG6O1IDm74O7Wc369if0d8ghqgsz+B2uUHk4A1agAITFADQGBa3xCcjT6Qm6CGwGz0AbS+ASAwQQ2kZ3mByAQ1sCThyyoENQAEJqgBIDBB3diedtve1lytVTsPIBm3Z03CbToAOamoASAwFTXAAFatOEpQA3Rm6YoztL5Jx4Y8mM/9us14/aqoO8h4IvVUa1WRAGkJ6sYECkAfWYsgrW+AgZ7DJmv47HW73f7+ykZFDdBDffN72ElQX8CaK+RQSy2/LnWhzU5a35PRJoM8XO+UIqgBIDRBDQCBCWoACExQA0Bgdn0Dy7IZ6zx3qVxPUANLEi5jCfR+BPVFzPQB2EJQX8CsE3IzUWcPQQ0w0Ot5uuDmPbu+ASAwFTVAR7rcnCWoF2HHJcTjmqQFre+kbGYBmIOgBoDAtL5JzZLBBnubL5o1/0Q9Fltfl0sjBEENHaw2AailvrmtiBXVWspNSoeh9Q0AgamoF2KDGMB6BPUiVmqzAvCP1jcABKaiJj1LBkBkgpop9ApTSwZAdIKa8IQpkJk1ajbRHga4hoo6odUexgH0ZaJ+LUENbGKszsmk/nqCGvjKYJ2QiVkY1qgBIDBBDQCBCWoACExQA0BgNpNBFmc2B9lYlNORz92+w+YENSRSSy02cNNDraXcpHQXWt8AEJiKOilPGgKYg6BOyMMrAOah9Q0AgQlqgGS2rnxZIYtBUANAYNaoARJSLc9DUE/Gd0kDZxlC9vk27vYel7W+O3MbFABnqKghGXNHmIughkQsm9CVSWAXWt8AEJigBoDABDUABGaNegA7vwE4SlB3ZvMOAGdofQNAYIIa6MayD5yn9Q2Te358Yc/HGXqELbXWcisfzoEjczOn1EeCGlb0brC8/3cDI2fc2nRKai2fQz+QK7tDghpW9GYgnWlghCiu7iJZo4ZJWO+FnAQ1AAQmqAEgMEENAIEJagAITFADQGCCGgACcx81l+r9pKssT9Jy6xYjOd3GEtQ0N1s4zvV6f4+Q07x0ltD8WhH6X2l9B3OkMpqlmrr6dV797wMcIagBIDCtb5iIpgDkI6hhEs3WBk+GvSUEGEtQA5vNs+lun7k2FJKNNWpgKip6slFRB2QgAuBOUAeTsf1mYgLwnqDmUhknJgB7WKMGgMBU1MB0LJeQiaAGpmK5hGwENczuSHH55e/U4r5i1rDCPfKCGhbwJ1ib/kCY0grB/MxmMgAITEVNKjYhAbMR1KSxWjsMyEFQ04XKFaANQU1zKldoY8WNUexnMxnAInSy1qSiBghM+CKogUs9tne1en9yLChFUMMyFF6wJkENC1B58YlOxdxsJgMuV2u1FhuAzyAmFfUOZqXQnmsKPktfUZtBAhCZihqApaxWgAlqAJax4lJK+tY3AEQmqDtZrfUCwDW0vgOxqzy5M3O7LX/XqQVTEtQQSC21tJ6r1VrKTUrDtLS+AS70bZnMMhqCGgAC0/qGST0WWrY2wLpU1DAxmw9hfYIaJmb9Etan9Q2TUkxDDoK6I9UOAGcJ6k6sHQLQgjVqAAhMRQ1wMctkfCKoIRhjdi6WyfhGUFNK8YUgUXT7DIQ/TMsaNado2QH0paIGSMCkel6CGmBxlrXmpvUNAIEJagAITOsbejmyJNhzGdESJVHtOTcTdvEFNXRUS/XlGdBAraXcMqZ00foGgNBU1MVtCwDElT6oe9y20PopX54aBpCX1jcABCaoYRJZV2iyvm+4E9QAEFj6NWqYieoS8hHUMAn7CSEnQc1fblMDiEdQU0rx7To9mf8AZwhq6MgECBpKOum16xsAAlNRd2K9F4AWBHUH2p0AtKL1DQCBCWoAhnu3PGjZ8Detbzhi61iy8c/V4hvS4K9P1839f0t0uQhqOOhPuDb7YcDd7f0FUWspt0wpXbS+AehIK/s8FTU09jgu6WYDZ6mooQPrzUArghoAAhPU0IF1OaAVa9TQmK430JKgDqxW99YC69J52kZQdyRoAUp59aAAQ+N2ghpOUBAAvQlqOEi3BLYxoT1HUAPQTZcJbbLgd3sWAAQmqAEgsGWDeoZt/7XWv79mMtvrhZW5Hte3bFC/EvGEHrEhKeL7BuIxVsSUKqgBrvAqAIUiW9n1DXd7x809f96dXPDa0fnK1r+3wLUnqOFBLbXpE5NqLeW2wkgBHbW+7kpZ69rT+gaAwAQ1pZSf62XWzgDiENQXE4oAfGKN+kLRnhVt0gBsNfrbAWv9941bj7/PQFBTSok3aYjmcQ7jUJGRr+29jtY3bGSQgmvVmvObuFTUSWhrn+cYElWGczPzPFlQJ6ASPM8hJCrX9/q0vgEgMBU1PEnQRQQmsnRQZ1i3oa0ubUSnIcV4xHHLBrV1GyAK49F35jHvLRvUAMyh20RmkfAX1J1pdwFwhqDuSLsLgLMENex1pEmS6EvugbYENRzQ+ovuV/qSe6AtDzwBgMAENQAEJqgBIDBBzWajbjVzSxvQ06sxJvK4I6gBIDC7vgFYS33z+zM/stbLno0hqAFYzsdbKON2uV/S+mYqkdeRmJfzisgENVMwkObm8yczrW9gCsKarAT1AFduQoAVuH6MI5lpfX9gBg/MxJi1JhU104g2CAV7OZDWkW5DtPHkE0HNFKK1/Lq8nnnGDRiuZev//Y+JeREKagA2makKXYmgBuCraF2tTAQ1AEtapQEgqHe6r5O4VQIgrpXGZ7dnAUBggnpRNn2ccz9+jiNwNUGdjOA5oD79Kk+/B+jIGvUBwm5SWz62V3/m9vs/1lrKrayzBgbEJah3WmmDQkYfv6P25x9s8+/Vui/Q9/y7TkVIQVBDby8q8jOiVPPufGC0rN1MQQ0JCFVml/n8tZkMAAJTUQMwl6MbQ98JXqwLaoBJZF2jfWXzxtBPPyPIfo9vBPUXLgwggsxrtNkJ6g9mvzBMMgDmJ6gXNfskA4A/BDW7ZKrSM71XIC5BzWaZqvREb5XJbL0n3r3zP7+PeuZD4T5qAJa1wmRFRU06OtqQxwpLWIKaVJrOrjde/wuMEzClBYrpUoqghq66td2EP6QhqAGYUpZulaAGmrLbmBGanWMThL2gBr5uuIkavCYFZCCogVLK+zBeYdcszExQA6UUgQxRCWpA+xgC82QyAAhMUANAYIIaAAKzRg1J2CwGcxLUkIDNYoS3dx757c8vdMoL6gaeH7rgIQwwN9fwbyOOSS319Bdp1FrKbaWULtaoAU7JvqSQ/f2PIKgBIDBBvRAzW4D1COrABC8AghoAAksT1KpTAGa07O1Zbq8AVqXwyGXZoCYfkzMycI7nI6gZTqDCnFTy1xDUAHxlcn0dQQ1AGIr23wQ1ACE0q9oXC/s0t2cBwIwENQAEpvUNNGd3MJeob36/5+99ctF+OkEdnAGP2dgdzJVafKf1r5958XdcC+pGegSqAQ8AQd2AQAWgF5vJACAwQQ3AEPclwmh7b+4vJ9jL+ktQAyyqRSB2C9Va/u22ri/+G39ZowZgvNvvRL56d3VUKmoADovWxl6RinqAT1/rmPUrH13cROccJQpBzXAZJybMxTmaT+R5maAGILXo8zJr1AAQmIoagKVEbmMfIagBWEa3/QUXhr/WNwAEtnRQ11r//gLg521nxsY5LNv6dnsFACtYuqIGIBZV/H7LVtRAfFmfzLeebeHroz5GRQ00oVI65vm4OY48U1EDcIq5RV+CGuAFX6azTfPjIPR/0foGgMBU1AAXG70ubR18LoKa3Ua2/bQYWd3o89v1NB+tbwAITFADQGCCGgACs0YNA93X3K29M4qNY/MT1ACLMhlcg6DmEipLSGZPYX+mCdCzgbD1Zzce0gQ10Iw2K5/UUpf+Yo5aS7m1TukiqIFGdEagD7u+ASAwQQ0AgQlqAAjMGvUgNtn85pgAfCeoB7DJ5jfHBGAbrW8ACExQw2Ba/sAeWt8cImyO0fIH9hLU7CZsAMYR1ABv6By155DuJ6gBXtA5ai/FMe0wEbGZDAACE9QAEJigBoDABDUABCao2cwOWIDxBHUDMwbYjK8ZICNBHUDm0Mz83gG2ENQ0J3wB2vHAEwAOq7WWW9n4IJMzc/gEz0p5R1ADcM6tXxet1rJ9IrAorW8ACExQw5Nva+zW4IGRtL4TEzhAb++GmQzfz9GKoE4qxbfYACE8jzeKhH0EdSNOPGA1tVaT+gAEdQNOZGAlrQNaIXOOoAagG3XMeXZ9A/CLKjgOFTW8YJAis71tb5dLX4IanthzANsNuV6STwS0vgEgMEENAIEJagAIzBo1vLJ1TezKtbPk63YkM9P5/ua11nLs/nRBDW/8uaiufhXAMg5ONrS+ASAwQQ0AgQlqAAhMUANAYIIaAAIT1AAQmKAGgMAENQAE5oEndOFrIgHaENQ052siAdrR+gaAwAQ1AASm9Q0fWGoHriao4Q1r7UAEWt8AEJigBoDABDUABCaoASAwQQ0AHbR6QqOgBiCdmR5z7PYsctlzbW78s7VUt3KRVq3O/94ENen8CdamP5AJCJTfrjwmW/9tn5vWNxDETK1IGElQA0BgghoAArNGDZCYJYf4BDX85914lXwfCwvLvknriMfNbaM2uglqePB80ak2gKtZowaAwFTU8EAFzSP38BKBoIb/GI8pRTjz3egJvaAGeDJDZ8WE4hpXHHNBDZRSDPx3joFzIRpBTUoTFExLEwSwnaD+oNdgYpC6lmMPMcywxBCBoC6CE2A0Y+52qe6jNnsDYDYqauAvk9k2znTpdPh4li6oDUTwmnCYj/Esh1RBbSACVrHCeHZ192CWiU6qoAZgLr3CfKaJTqrNZAAwG0HNcu7trFnaWi20fK+ZjttIz8fVcWYrre8vXEz0cPXa3Fmzv36YiaD+wEAUw6lQeDXPuv83Hy8wAUHN2m6/k7rWUm5SOqTVO1irvz/6ENRACKt3sFZ/f/QjqOEiqitgC0ENF1BdAVsJaoAOdExoRVBzmFt04DXXBS0JaroT6PNRDa7PdTkPQc2SBM1xBm+OOBr8rtXvBDWT2H4xyxmYg0nhNp71DQCBqaggUX6yAAAgAElEQVSZgu4YkJWgJrwu7THBD0xC6xsAAhPU/3m189BuRACuJqgBAlMwIKgBkhD6cxLUABCYoIYdVCTAaIIaBhDwwFGCGgAC88ATTlEpAjPa+iUiEb5lTFBz2NUn7+mni334+7Vcf3FCbybacxDUTO1PoHb5wbA0E9F5WKMGgMAENQAEJqgBIDBr1LCTDTjASIIadrABBxhN6xsAAhPUABBYyqC2xggwp4zjd5qgzvjhAszIeP1TmqAGgBnZ9c30TL6BI2ap3AU1U3O7FHDETGNHqqCeZfYEAHdpgnqm2RMA3NlMBo3o2AA9pKmooYdaq24N3ZkE5iaoWca30BSqzMg5i6B+YNYKQDSC+j+zzlpTVon1ze+P/riTx9AED+hJUPPXTKFfSy2/XuoFeTnL8QLmZdc3AEtZrcslqAHgoBGTAkENAIEJagAITFADQGB2fbOU1TaRwIpmusMkAkG9AOH0x7br3rGCKAT2NoJ6ck5ygLUJ6mDMMAGu9a5LedXYLKgbE7Tj6PjDNsal/Z6P15VLjIKaKRl0yETQ5iaoAdht9clDpE26gnqw+8m9+kkO5LDiWBbt/XjgCQAEpqK+QKSWCkBExsl/BPVg0Voq0NvI1uiKbdiMWnyGKwW9oCYc6/jAGauNG4Ka2N5Niu//fa3rEeAXQd3BSi2Xy91eH8taS7k9pLTqG7hbbTwQ1I2tdHL0cNUFtNqFe7f1fa36/vdwDNgj0vni9iwgFR0vZiOoASAwQQ0AgVmjBpjUYxs/ynpqFCstcQhqaCDSxhNyuT9zgH9Wuxa1vgnJwPOa48IqnMvbqai5wOcLdLHJMPBktYq3NxU1AIeoisdQUTOca5urCJZ2VMXjCOoAWm5Eir6pqelrM+ayQ+TrAj7R+gaAwAQ1AASm9c0ysq4/Zn3f/OHzX5+gZglZ1x+zvm/+8PnnoPUNAIGpqAEmoMWdl6AO6tNFuXq76/EWs+i3m8EIroHcBHVgry7OlLPqT2/5/r8Zx4BFCerAUobyK7f3x6HWUm5SOjznMhwnqIPK0urS2l6fzxfOsesbAAJTUQehNQjAK4I6AK1BAN7R+gaAwAQ1ACntWXK8cnlS65uQrNkD/CGoCeBnKFuyB/hH6xsAAhPUABCYoAaAwKxRczn7xgDeE9RcqsnDXgQ9i/NM/NwENTTiljJmYwLQXo9jKqihAYMd8EqL4LaZDAACE9QAEJigBoDABDUABCaoASAwQQ0AgQnqYO734ronF4BS3EdNMLXWcisH7jk8M69xCzQQmKAmntuYbkKt5dikAJjW8wNIZuheCuqAZjhxAM7o/fjSLT9/licKCupgZjlxALbyTPFzBDXTeNdocP0DKxPUTOV5Vm6ZAFid27MAIDBBDQCBaX0zFa1uIBtB3ZCdjX05tEBGWt8Hqezgta3XhmsIthHUABCY1jcANNS6WySoAeguy1JHj31KgppwklzPsMvMQWeT7TmCmlCGX9Anxj67/BnFeZaboIaNBPNcfF7M3IV4JKiBEAQrLa10Lrk9CwACU1EDzbVsOT5W2qpuXhl1Xlx1/glqoClBOieToLi0voHUVtlw1JvjdB1BzdLug4tBZm611mGfoXOFaLS+gdC0Y8lORc3UdlU/9cWv8vR7YDddiL5U1ORxez2Y1FrKrajaIKrsG91U1AAQmKAGaOSxBawdTCuCGgACE9QAEJjNZACUUuZu18/82r8R1EAYKw+20c28q3rm176FoGZ5Bv85rD7YwlGCmgW8D2JjP4xhQtyPoD7BiQmgG9KboD7IiRmH+RKRmMDTmqBmas0mTMZWGjCBpwdBDTuoloDRBDVspFoCruDJZAAQmKAGgMAENQAEJqjhi/sGMhvJgCvYTEZu9c3vAYIQ1KRXS/38qFEBDlxI65vLrNZKXu39ADEIasITgEBmWt9AeiaDRCaogdQ8cY7otL4BIDBBDQCBCWrYwBomcBVr1PDFzyVMgQ2MpaIGIBQdrJ9U1FzKBblPrdUuZTioxfVzxTUoqLlMpMAxX3htz6BkEsGqrj63BTXpCZdjrh68IAtBDZPbG5gClhlYFvtHUAMQionkT3Z9A0BgghpgIVrG69H6hgUYnBnJPoexBDVMzoDJaq6aCESdgGh9A9DUTB2eGV6rihomM8PAArQjqGEiEdtyxGMytxZBzVqOjE8H/k4tMdeyRhMI8UQ5L50b7QhqlvMnRLv/I+lFCQTisRGsLZvJgJdURESS+XwU1EDqQRCi0/oGgC+unMwKagD44Oq1b0GdQKtNFrNv1jgyIZ747QKLENSksvd7mwGuJqhJRfgCz6KPC4KaNLSxgWczLOe5PQsAAktXUc++IYptgney0vl23bku4b10Qd3LCgPN4zrNzO9l5tcO8ExQ88Ptdgu/sYI+fO4Qk6AGdCEgMJvJACCwlBW1Fh/AfLKO3emCWosPYD6Zx26tbwAITFAzhXvLK2vrC8hLUAMsbuQE12S6vXRr1MSz+2Ex38aB+/+ed0kLWIig5ocpZsO3z6+x1lJuO1J6hafKAesS1PwlrNoQ/EBLghoggSm6ZbwkqIEhBMV1dHjmJqiTMEiyRa+2vaCA45YOamuFfzgG3LkmYD7uo25ExQqsxrgWg6AGoDuhf5ygBoDABDUABCaomYbW2RpefY4+W3hv6V3fzOTzQG2jMpDV8kFtps4Rr84btzUBV1g6qA2s84g4n3o8f0z4gKssHdTMocuESq4CAbR4yJDNZJNS4QHvGB/aiXAsBXUHET5Yzqu1/v119uf05HyjJedTPFrf8IL9DUAUgroTs1JgBcay6wnqDlRjwAqMZTFYowaAwFTUULT3gLgENelp7wGRaX0DQGAqaqZRay23sqP63dPNVlQDQQlq5nJru5Zca9kX/gCDaX0DQGAqamA4u+xhO0ENDGWXPeyj9Q0Agamo6abF97ACcWW5xq9eqhHUvJXlIiQO51xeUT/7CK9JUEMyV1cHV4kaBPCNoIZEBFUe0SZkj6/HebiPoAZYTNQgvN1u4SYQM7DrG4AhhPQxKupFrboe5zqHOa04Ho0iqANZNVxb6XZshD8QmKCGAbT8gKMENXSmSwKxtexm9uiM2kwGAIEJanjhsVU9om2tNQ68o/UNi7AZkSuYZPYnqMmrvvn9nh+RLByzvd9V9PrcnAtjCGpSq6WWl2ONImE3Ib6dY8Ue1qgBIDBBDQCBaX3zkY0iANcS1LxlDQ3geoIa3tBNACIQ1PDC72aC0AauYTMZAEtapSsmqAG4xCpB2pugBoDABDUABGYzGenpvgGRCWpSc694PNYt4SdBDYRh4gS/CepgVBMAPBLUgagmcjNJA14R1BCASRrwjtuzACAwQc1y7i1krWRgBYL6wd6BXRBMoH74VZ5+DxCQNerkaq1rr4/ePqdwraXcysLvH9gkcuElqCeyfKju5HgALUQfR7S+ASAwQQ0AgWl9B6e9SzSR1/JgRYJ6MMHLzJy77ZjwsJWgXtx9YmCCAHG4FtnDGjUABKaiBuAylgC+E9QAXMISwDZa3wmYsQLMS0W9uKwzVpMTYBWCmsn9DuSkcxM6Gn3XhLs0eKT1DQCBqaiZmg43sDpBzbSatQb/C3vtRiAirW84waY1oDdBDQCBCWoACExQA0BgghoAArPrGx7YHPaaHfFwHUEN/xFE/awQ9CZxXEVQT8Zg8cGZQ3Pk786dO+ww+ySDuQnqiRgsvquldn/Wd62l3KQ0MIjNZAynKwCwnYr6iRC5xgprmOThfGUkQf3AhQdczSSAZ1rfABCYivoC2uvx1Fp+bEJ7/v+JSfVJBoJ6MIMKXEu4MxutbwAITFADQGBa31wi4jp9wJcEIKgZL+L6YMCXBFBK0foGgNBU1MDUIi6jQEuCGtgkYiBGXEaB1gQ1ywmYJ9MTiHAdQc1ShgWKyQAwSOrNZFtbeRFbfgDkkDqo2c+khaicm6xKUDOMgZRXnBfwmaAmhXsYCAVgNoIaABprWRTY9c386pvfH/1xvgaRDXRn5jPrtS2oaeZx4Bp9MdRSPz+v25j6w6wDVhSO3bxmnGAJapq63W5TXggc0yrwnTOMMOsES1ADl5p18Iyi5WTJZxGTzWQAEJigBoDABDVNRV5rjPzaAN6xRk0zkde3fr40gQ3MQ1CfNMsGjFleJ+PoMMAcBHVD0cKw1+sxwM8v0nkKfCao2SXyAG/+AKxIULOEyBMIgDPs+gaAwAQ1AAQmqAEgMEHNS2d2dtsVDtCOoAaAwAQ1AATm9iziOdI5v6LbvvPfrCXWA3GAOQhqQvoTale/isYs3QMHaH130npDlQ1awBH3scMYMq/0FbWTFzgr2nP+WUvqoHZh5fJpTuZU4BNBzJVSBzX5vBpsdVVYnXN8boK6ARcBEJVOwPwE9UlnLoJ7O01bbRyTKmA2gpo0zIVYlQno2gQ1MAWdp9cck/W5j/pivWfCtVazbbpwXsEYKuoL9Z4Jm2kDzE9FDQCBqagJS2c1Pu1v6E9QE5K2fXzZPiOTEq4iqDtyYcMask1KiEVQd+LCBqAFm8kAIDBBDQCBCWoACMwa9Q7fHmG42iMOm2yGO/ojPvy9WtY6ztDKamMQfwhqXmp5sf8J1mY/7nj4A4eYAOzT+nhpfQPARlfcdiuoASAwrW+AhXjQ0noENcAirCOvSeubMB4LAUUBwB+CGgAC0/omFJU0wE+CmjAsrwEzGL1hT1ADwEZXbNgT1AyhpQ1wjKCmO7eMABxn1zcABCaoASAwQQ0AgVmj3slzdAEYSVDvYFNUHr5/F+aQ4VrV+oYNdFKAq8YBQQ0AO40MbUHNUJ9OblUrMKue45c1avqob34PwC6Cmm5qqb+/aENoA+yi9U14WuJAZoIaAAIT1AAQmKAGgMAENQAEJqgBIDBBDQCBuY+a4dxuBbCdoGao719yI8SBfVaf/AvqE3p9vVqGr20DaCHDWGmNGmCH1as34lFRn+Si/Wzmw+Oz5ShdMVoS1Ce4ED+b+fjM/NqBtWh9A0BgghoAAhPUQGiPewXsGyAjQQ0AgQlqAAhMUANAYIIaFmU9F9YgqGEyAhhy8cATlnf2KVGeMsUzkyVGEtRsVmstt7IjsPaMZXKQSZi0cTdqwiao2efW9sSstewL/8P/jgoI7lp3iTJ2nUa+X0HN8rINIMBabCYDgMAENRBerTX18kXm947WNxBclqWLjOu8bKOiBoDAVNQA/+ld1UaqmrXT5yGoAZKJMllgG61vAAhMRc0uumUAYwlqNuvWLhP+QENn9gJE2kdwJ6gBHthkRTSCGuA/0SopKMVmMgAITVADkMJ9WWO25Q1BDQCBWaMGeGP07uHZKj3GENQAAdjIxjuCGiY0uvKKeG8pZCGoaetofuz4e7XkDo1V3vvM4f88UZr1fTAHQU1zf4K06z8Al7uHs3VlerPrGwACE9RAE68qS9UmnCeoASAwQQ0XUnEC3whqeEGAAlHY9Q1wgMkcowhqoJks4eW+aUYS1PBGltBpRXhBH4IaXhA6QBQ2kwFAYCpqYBNLAXANQU0XxvS1WAqA6whqmjOoA7RjjRpgsFbLCJYj9pvxmKmoAUhh1m6fihoAAlNRA7CcGVvc7whqAJYya4v7Ha1vhnqe5a406wXoIUVFXWtdboYFzM0kla2WDWrhPFh98/ujP87nx8Kc2+yxbFDzx8jAq6WWr/+UIoLJqHy5mqCehAozr6OfvXPmPMePCGwmA4DABDUABCaoASAwQQ0AgQlqAAjMru+JrHKbyCrvA2AEQT2JVW4Tef02BDfAO1rfABCYipqmdLVhbvcH5XhgThyCmmZc1ADtaX0DQGBLV9R2FwMwu2WDWhsWiO7MOrA15Dy0vuFCuj7AN4IaNhCowFUENQA/mJjGsuwaNQ3svVb3/HlLaxCSde94BDUf1VLfPPbz4M+rpdykNMBmghomoBUJ/2Tb8S6oIbhZBqTRg2e2wZrPVj4fbCYDgMAENQAEpvXNIZ+WTBftPgFcQlBz2Kv1IJueANrS+gaAwFTUQDM6KtCeoOYwgzKPVr01pjfXEd8Iag6ZfUxe+Z5L5uEcZAtr1CxDZQKsSEXNVzPln7AGViOo+ahLa65TlvZuI5oEAFcQ1LCBtURYy0z7VKxRA8vQ9eCMqOePoAZO6zHARR00YTStb2C3mdqGrCnTRE5Qs9nj4GygBq6SbewR1PxW3/wegOEENS/VUn8/fUxoAwxnMxldZFo/AuhJUAMMsnUCa6LLI0H9hdtOAH4yho1ljRpgoOgh546OeAQ1wCACkCO0vgEgMEE9mee2WfQ2GszGNUU0gprlGXiJxjnJHtao2SXCAGOzSwwRzgXIQFCz2e9sNFBnZaLECmaZbApqANKZabJpjRoAAlNR89YkXSGApQnqCY1YV5mpLQSwMkEd0KddzQIU+ptlkxE5COrA3IYE47nmiMZmMghOdQefrX6NqKih5OleZHmfnDM6+JyXnwlqpnT1DNrAwqqc1/EI6kz2ZFvvHDzy8/8bPwwkQCaCOpla6otHgcZWaym3MtmLBmhEUMMErm71Z2WJgwgEdVAGZu4yB0WL60DYMjtBHZBB5RomR7G4DuAPQQ1FKABxCWpOe1WIyj2ANgQ1TTxWpFrIAO0I6g0EDwBXEdRfWLukt5G7ku2AhvkIaprQdQDoQ1BzmgINOMtk/z1BDSxPCMRmOeYzQZ2QMYtMhACzE9TJTDtomVwASf3v6hcAALwnqAHozj6B4wQ1AC8J1xgENQAEZjMZAG+pqq8nqB94vGI+PnN4z7URg6AeTDDMZdTnpWoB3hHUjHc0k779vUnnPyZuwCeCmkvUUps9I7zWUm5BUlrHBGjNrm/YSHsauIKgBoDABDWhPBatClgAa9SgpQ2EJqhJzcYvIDqtbwAITFADQGBa34RjyRjgH0FNKJaMgRW0fPiR1jcAfPDtzpDed46oqLmMFvd3rR9JGuERpxFeA+vIcD4Jai7R/MIS+qdlGPBY0+rPQhDUAEwrw+RSUD9ZfWYGwFwE9YMMMzNgHMsJtGDXN5CGjhkzUlEDX70LONUi9CeogU2eQ1l1ylmWBrbR+gZSOzPhMFn5zPFpQ0UNbGLQhWsI6pVsGUejjLVbXoeOWBirtydNQohMUC+mljr9F1vUWspNSjPI6pMQ5ieoYQeVFzCaoIaNVF7AFQQ18FeGjkGG98haBHVjLe4LdG8hV8hwzmV4j1yj5wRQUAPACb0ngB54AgCBCWoACExQA0BgghoAAhPUQFpu1WIGghpgJwHPSG7PguCEAuQmqCEwD+gABPWCFGAA6xDUi1mmAjPZACil2EwGAKEJagAITFAD8IM7DWIR1ACTEKA52UzWgYsJgFYEdWPL7LoGIARBDaQ2WwdsttfLeYI6qqPX4krX8N73suPP11J1P5juHJjt9ZZiYtGCoA7sT5hc/SoWZewopfwZRLcM/lv/HDxyzrRh1zcABCaoASAwQQ0AgQlqAJa1wmY2QQ1AOCsEbCuCGgACE9QAEJigBmA6z63xlVvlghoAAvNksuAWniQCsIGgDszj9wDeW7nd/UhQAzCdTIWMNWoACExQA0BgghoAAhPUABCYzWSjHNmcuPfv5NlbAZCGoB6ollp6bFSstZSblIZl1Fpf7mp+999Zm9Y30E2L+1yz3CsL76ioITlBCLEJ6qBqLX/b5I+/h5a0USE+rW8ACExFHZiOJACCOigdSQBK0foGgNAENQAEJqgBIDBBDQCB2UwGi/GYSVbhYTx/CGqWJbD623KMDbYc4dr9R1DDB8L+HMcOzhPUgykuANhDUA/UtbowAQBYkl3fcIL1V6A3FTVL6xWk1q6BUQQ1y8ocpCp9WIeghsVknqBAD/cO2lWdNGvUAOzSqmOj87ONijqwWmu5lR2zt2/nvEKrKYMMMELKoJ5qI9DtfBjUWvYFPl9Nc/4A00sT1L3DeVP1uydz5QAAJVFQDzGg+q21lFfzjXf/HYC5CWqAgOyB4E5QAwRjDwSP3J41wKuJsckyAFsIagAILFXre5U1n0XexmlT3WZHM60+d+cPs0gT1FdfkK3CdfZxJdPgmOm9Av2kCeorGatpQfBDToIamM4qy1iwhaAmnMdBWAXJM+cE2dj1TUgZB+P7BEW1CDxSUQdnzAbITVA31DpUm1aVAn8KqmngmaBuRKhyVsZ2P/CdNWpCUllCTj2u/dnHExU14agsgWiuDHtBDQAfXF08aH0DQGCCGgACE9QAEJg1agB267m5avZd2q0JagB26bm56uqNWxEJ6tG2ThR7TCi//MxafI0iQDSC+gJ/AvHqV/GCbhNAOIKa4aw/AWwnqBlKax1gH0ENHekeAGcJauhE9wBowQNPACAwQQ0AgQlqAAhMUMOCbGKDdQhqSEJ4w5wENQAE5vasiyhuxqnVM8yBc64cRwT1BYTGP0IU2ht9XUW+jiO/tq20vgEgMBU1AKm82lgZueoW1ADJfbsjIHKIHfX4nqLfESGoAXgbxtFDLANBDYBADkxQAyS3Smt7hR3er9j1DcClVPOfqagbqrWWW9kwm/t2Tq43IfzIRQrwnqBu7XY8dGot24J+ISu2qQBaEtTAUlZdp9xLp2odgnqQ52vGOAKxrBTwq7wP/rCZbKDb7eYCCmhr5aFCAa4gqAEgMEENAIFZox5I6xSAvQT1IJamGc3EkNXcN/yttPFvC0ENC8o0iMHqBHVjihiAfjJ2igR1Q02qmHznIMAmWTtFdn0DQGAqagAul7GlvZWgBuBSV7S0Z5oYCGoAUpltrdsaNQAEJqgBIDCtbyhzrVcBuQjqQV498i7bY/Ci8hnAZz3HqhHj4OwTcUF9tVfnz/2/yQ+gkyyFwgrvUVBf7fY7qWst5SalgTeyhCx/2EzWyOytFQBiEtQAEJigBthA14yrCGqAAwQ3o9hMBjAhE4U8BDXp2DHL7Jy/uQjqgcyA5yfkgdEEdVPvg9jYDsARghpYju4VKxHUDRkb4HqWJliNoG6k+eAg9CEclTpXENQAG6jUx7Fp8ydBDeV1pWSggHXNNBnwZDL4z+12+/uLbbSCoT9BPZn7wGiA5CznEDN6dd6ufi5rfUdT3/weOlh9gOM6lpPaEdQB1VLfPyDFuEojBk16ezzHTAqPE9SLmmmjBLAm4dyGoAaYyCyT8Ble4yxsJgNIQoU7JxU1AF9FCvlIr2UEQQ3/yXbxw1aR2tiRXssoghpKzosfmIOgBiAcHa5/BPWEnMCQ2+pjgA7XT4J6Mj/P37UvVuA3IZaPoCal1SsSYB2COig50o+KBJiJoA5IkABw58lkABCYoAaAwAQ1AAQmqIElnN3J704AohLUsCChA/tEnugJauAlYQ8xCGoACExQA0BgghoG0EYGjvJkshH2jtE7/3wt1dPMkqnVZ84fzoX1CepB/oRptx8OsIuAn4fWNwAEJqhpxjosQHuCmlKKkGV9tda/v1r/3JFmuFZneI0zEdRAGtZk15JlQiCoASAwu76BNLJUYBE41u0IaiAFbe9xHOu2BDXAYN+qTUHHI0E9kE4QW9wfROGBFGt799lqGfNMUA9iwAXgCEHNX2byMI7rja0ENaUUFX80BvFjZjlurjf2ENQQjEH8GMeNVXngyUmPM/hZZvMAzENF3dq7rL7/d5P+tEzkgCMEdWu314NxraXcpHRaV7RlTQxgDYL6A/exMivnLaxDUAMpbJl4H52c617Qk6AGOEH3gt7s+gaAwFTUAFDiLmEIagDSi7yEIagbiDoLA2B+gvqrb98bO+hlAJCSzWQAEJiK+gtd7bUduW/Wg3CIxvLb2gT1B80HY9cS0JhJ4/q0vgEgMEENAIEJagCGsJZ+jKBu6H4SOhmBmRizYrOZrJd35/39v9v/AcAGgrqX2+ukrrWUm5QGYCOt7420hgC4goqa9EzCrnH0wTFnHjjjs2ZGgprUPCwiD581s9L6BoDABDVMQMsW8hLUsCDBDusQ1I0ZIAFoyWayXT6HsL0qwCx8Xes8BDXAwnoF8rvuofBvT1DvoKsN8M9zKFv660NQb9R0luhcBmAjm8kAIDBBDQCBaX3DJKz/QU6CGiZgJy2Zfdq5nuE2M63vhp4rHhUQAGepqIHLmMzm9qoazlAh7yWod9p9Er0bh+7/3flIUgZj2EZQ93Z7ndS1lnKT0gB8IagBOMTSxRiCGoDdLF2MY9c3qagAgNkIamjMZABoSeu7MYP0NdzSAaxKUB/y7ntYB7+MhYwMWpMp+M11EZegJhVVNxl9C2HXRWyCmvDu1bb2NuwX/ZrZWslnrvgFNQCX2DqJiD7Z6E1QH5B4YneZCLNpFT1wBUG9U9OB+vrsmUKrYy5ogRm5jxoAAhPUdBWhZQ0wM0HNcMIbYDtBDQCBCWoACMyu72CedybbqdyWtjswG0FNGiY8wIwE9RXqm9/v/TGqbYDlCeqL1FJff9uWziwAD2wmA4axRwD2E9TAVIQ92QhqgIWZ2MxPUAOwS4/w3/Izs046bCYDQngchN3NAP8I6oCyzhrhdrs5/ztwTOcmqIN5XUi4yMhBoLSXuTtx9lkTUZ5VIaiBECIMiBCRzWQAEJiK+kJZunxb25nansymZWs0SpuVeAT1RbJckFvfZ5bj0cKnAd1gD9vdr5fo143WNwAEpqIGhrLEQSQznI+CGhgmcnuRfGY5H7W+ASAwQQ0AgWl9A7CsGdagvxHUXC76rRHwyQpBsKpVxhVBHchjYM0eXrO/ftjCOc4Ignqk+ub3APCGoB6slvrmG7KK8AZSs4zwmqCelNYysBLj2XtuzwKAwAQ1AAQmqAEgMEENG9noAlzBZjK6EWzf2RQIfCOog1kl3IQPQBuCOpDf2bZGaANwnDVqYJdVuj4wCxX1BYxzRGB9HOYgqAczMAKwh9Y3AAQmqAEgMK1vmJANXZCHoIbJ2OcAuWh9A0BgghoAAhPUAG/YC0AEghqY2mOYClZWJKiBUIQt/GTX94k163sAAArFSURBVAG11nIrB3fe7h2DbPAFSE1QH3XrO+uvtRyfDHCJd8/O9kxt4AxBDSxF65zVCGpgGToXrMhmMgAITFADQGBa3xvYDMRW1keB1tIFtdClF+cV0IPWNwDh6E79k66iJlZXYeRrifS+ozAYktFsY4GgppvZLoZsfDYwB0ENO/SsQFtNbFaYIKn04Z+UQW0QiGWWz2P28JtF5uPcY5K1wsQtu3RB7YSNxecBvDPLJL63dEHdivMHoB+T+H8E9QHDTiCTAYD03EcNAIEJagAITFADQGCCGgACs5kMJvDuNhU7Y2F9ghom8RzK7jGFHLS+ASAwQQ3AVzo419H67u3suf3t71uiBC424/PEZ3rNgnqAWmppfT7UWspNSgO8NVMYf6L1DQCBCWoACExQA0BgghoY4tuuYbuK4TVBDQCBCWoACMztWTCJFVrDK7wHGE1QJ2XAnMsK94Ku8B7gCoI6IQMmwDwENQDLWqF7KKghkBUGFYhile6hoIYgVhlUgLYEdWPvHgKvUIptlYf3A+sR1BudGci7BUDi8BesQBaCmmlZz2VFzmueCWqmpJpmRc5rXvEIUQAITFADIWj5wmuCGnhJcMY24vNZ5Rzo/T56/3xBDQCB2UwGwCarVNizEdQR7bkWvv1Zm0iBBuxIv46gDqqWWs5cF7WWcpPSS/KwF8jFGjUsTrsS5qaiBpiUSVgOghpgQpY/8hDUwCnvqjpBwuxendtXnNeCejK1lnK7/fu/EMHz4DVzS9ZmPR49ngtXndc2kwHLmXmiAM8E9YRmGoMMmADnaH1PJltHThsSyE5Q76A65J1eEwoTFUBQb3TFYGlewDsmjTBGhGtNUAfVZGJw/flFBypsGCPKtWYzGQAEpqIGTovQHnwW8TXBEYIaOCVKe/BRxNcER2l9A0BgKmoAljfzUoigPmrPZ37k/Njzd3T5AN6afSlEUJ9QS730SWG1lnKT0gBLs0YNTGPm9iUcpaKGRoRIPys8SnXre1jhvdKWoIYGVh1YTT7geoIaeGnVyQfMxho1P6iggJmtOIYJag5b8YIAYso83ghqAAhMUANAYIIaAAIT1AAQmKAGppB5MxG5uY/6JGPHdwZYznJPdzuefDYfQX1CiJM9eAaGOEbwhfDazzEbR+sbWILODasS1AAQmKAGgMAEdVCPbTwtvb72Hl+fBzCSzWQvPG+SCLFp4lM23P+3Ri9REAHEIahncXsfnrWWcmuU0pdPSAD4IWXr+1DFWJ9+laffj3gNAKSjot7qRUXbspIFgFdSVtQAxKbr+I+gBqALYduG1jcUAwoQl6AmPTvdGcWE8Jysx09QAwwQaUI4MvBa/VuRjt9ogjqwrLNHoJ+RgZc5XFsS1G+MCcn3/4bzG4BSUge1kITV6EKxosRBzSpePYs9xPPZGcrnzarcRw0QmC4BghogmK3hLMRzSNv6jnB+R3gNQC6WheaTMqibnqQHw7b5hSL0AZak9c3/t3dvu23jABRF5f//aM5DJo1ru7Ekk9QhuRZQoBik6aCWtXmTAxCt9xJ/2paCUANAMKGGQaSN8oE+hBoaElfgU0seJhvG0Xv8q68/8j0GPggqiEAPV5yaF+o79y9AyiMMZSvNP9K0lG27DVzphNcJaOvqwfiVTRDq3+y9Lr6/Ti8Aqlt9MC7Uv7nt/XSgsWektHX1TAAY25KhTlnWZn6uM84ywOPbkqEGSGaAxz2PZwFAMKEGYGnp2wxCPbFSfn4BsF9SvIV6cva6AMbmMNmDpFEU9HbkiQhPT2Rwz5rfwqF+vrjdc6ilVcTEkXuuhTUsHOo1GG0DvJd8r1w21MGvSTUG2wDvHdnuucKSoW6yXLRA+AFWdeU2w5KhHs0Ks3/oxT4/oxHqcN1uKAYDUJUBAbV4jhoAggk1AASz9A38JfkxFViRUAN/2FOFPJa+ASCYUANAMKEGgGD2qK+y97zOgXM9ZfPcJsBshPpCX2Gt+g0BmIylbwAIJtQADO3Ms/8jfV6ApW9gOSPdpEGogaU4cMloLH0DQDChBoBgQs1h9vcA+hFqIog/wGtCDQDBnPq+2MwTyVKeP9L01X+blVUCoAahvtAqwVqR1xaoxdI3AAQzo6Ypy7+0dmY7ZaUtGMYn1DTjRghrMhCqS6jfKKVst23nBXd08vj99a5noCMhHYtQ73Frs3xbyrZ/EADAkoSaU+w9z8csCzIJNYe5mfOK0EMbHs8CgGBCDQDBhBoAggk1AAQTagAI5tQ3LMxJbWYx8yOjQr3DxK8/4YSUVmYK2+zvEaF+o/kFMM97BRjE7GGbjT1qAAhmRg3hZlqiBI4TaghmiRKw9N3Q40zIzAiAo4QaAIIJdQWHZsrl4df28HsAuGOPurfbc5FL2bbbZi8SoKZZPofAjBqASzm/8zuhBoBgQs1pTrUDtCfUABDMYTIALmdF7t+EGoBLzXAyuyWhbswoEdrzPmNmQl3N843CIJHRjBg8szFmJ9TAtm2CB6mc+gaAYEINAMEsfVcy4NYeAAMQ6gqq7O0JPQAvCDUfGfGUMMBIhJrTap8SnuVH0sG/uMY5w2EyIpmpww/vh7UJNQAEE2oACCbUABDMYbJe9mwxXb0NdeLvL5vDMZzz7mCVg1fwRag7+ora1f8XlVUeXDg0A/A3oSaG2RPAM3vUABBMqAEgmFADQDB71AAdOTDJUUIN0IkDk5xh6RsAggk1AAQTaiLYt4NxeL/2JdQsyY0Gsl35Hk27PzhMBsBhaTH7RPrnygs1AIckR21GQt3ZRINQgGkkrxAIdUdGoQB50u/NDpMBQDChhsElL9kBnxNqaExIWdG/rnvvh+PsURPDGxjgmVATIf0wB20YnMF7Qv2Jo/eYN19ftuyH7qEm1/r8DMTqEOoPfcW12jcDmIKBWD0OkwFAMKEmnuUzYGVCTSRxZgY1r2PviXUJNQAEc5isk8fBsHMWAOxhRt3R7XZzEhKAQ8yoO7LHdIx/LwCh7sZE+hgrDwBfhBqgIStDfEqoARqxMkQNQl2BATMArQj1h4yYAfoo5fgPLjrzZ9J4PAsAggk1AAQTagAIJtQAEEyoASCYUAM05ANP+JRQA+wguFxFqAEgmA88gQ7MxoCzhPrT++eOP1+28T8Zh/O89sAnhHr7DmnTvwAATrFHDQDBhBoAggn1L46c/3FWCD7n0B08s0cNDKv3jzA0kOAKQg2wg9P7XMXSNwAEE2oACGbp+w1bUj967wcCINS/WqFJ4guQzdI3AAQTagAIZun7f/aiAUgk1JvnI4Gx1T5r4uxKFkvfABBMqAEgmKVvAIax4uetCzVLXvjAeFbdNxfqxa164QOMYs5QH50gnp1QahwQwsrYvOYM9bZtZSvNPgK0lG27qTQQwsrY3Jz6BoBgQg1ALEv6Qv3k/ppwfQDML30wINQAEEyoASDYtKe+gTGlL0PS3+rXhFADMTxmxCPXhFC/tPjgDYAgQv3A4A2AJA6TAUAwoQaAYFMvfdtrBmB0t9WPvQNAMkvfABBMqAEgmFADQDChBoBgQg0AwYQaAIIJNQAEE2oACCbUABBMqAEgmFADQDChBoBgQg0AwYQaAIIJNQAEE2oACCbUABBMqAEgmFADQDChBoBgQg0AwYQaAIIJNQAEE2oACCbUABBMqAEgmFADQDChBoBgQg0AwYQaAIIJNQAEE2oACPYfpuoCU0DfNtQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 425x1842 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "ground = read_ground(day(17))\n",
    "ground = water_flow(ground, water_source)\n",
    "dpi = 96\n",
    "rx = range(min(map(first,ground)), max(map(first,ground))+1)\n",
    "ry = range(min(map(second,ground)), max(map(second,ground)))\n",
    "def colour(v):\n",
    "    return {'.': [0,0,0], '#': [255,255,255], '~': [0,0,255], '|': [0,255,0]}[v]\n",
    "z = np.array([[colour(ground[(x,y)]) for x in rx] for y in ry])\n",
    "fig = plt.figure(frameon=False, figsize=(len(rx)/dpi, len(ry)/dpi), dpi=dpi)\n",
    "ax = plt.Axes(fig, [0., 0., 1., 1.])\n",
    "ax.set_axis_off()\n",
    "fig.add_axes(ax)\n",
    "ax.imshow(z)\n",
    "plt.imshow(z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 18](https://adventofcode.com/2018/day/18) Settlers of The North Pole\n",
    "Another game of life style automaton, this time in 2D. The rules for evolution of the area are as follows. Note that the area has a boundary: it does not expand or wrap."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "clear, trees, yard = '.|#'\n",
    "\n",
    "def read_setup(data):\n",
    "    return {(x, y): c \n",
    "            for y, row in enumerate(data.splitlines())\n",
    "            for x, c in enumerate(row)}\n",
    "\n",
    "def evolve_cell(state, p):\n",
    "    adj = collections.Counter(state.get(n, '!') for n in neighbours8(*p))\n",
    "    cell = state[p] \n",
    "    return {\n",
    "        clear: trees if adj[trees] > 2 else cell,\n",
    "        trees: yard if adj[yard] > 2 else cell,\n",
    "        yard: yard if min(adj[yard], adj[trees]) > 0 else clear\n",
    "    }[cell]\n",
    "\n",
    "def evolve_area(state):\n",
    "    while True:\n",
    "        yield state\n",
    "        state = {p: evolve_cell(state, p) for p in state}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's check the worked example ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".#.#...|#.\n",
      ".....#|##|\n",
      ".|..|...#.\n",
      "..|#.....#\n",
      "#.#|||#|#|\n",
      "...#.||...\n",
      ".|....|...\n",
      "||...#|.#|\n",
      "|.||||..|.\n",
      "...#.|..|.\n",
      "\n",
      ".......##.\n",
      "......|###\n",
      ".|..|...#.\n",
      "..|#||...#\n",
      "..##||.|#|\n",
      "...#||||..\n",
      "||...|||..\n",
      "|||||.||.|\n",
      "||||||||||\n",
      "....||..|.\n",
      "\n",
      ".......#..\n",
      "......|#..\n",
      ".|.|||....\n",
      "..##|||..#\n",
      "..###|||#|\n",
      "...#|||||.\n",
      "|||||||||.\n",
      "||||||||||\n",
      "||||||||||\n",
      ".|||||||||\n"
     ]
    }
   ],
   "source": [
    "example_data = r'''\\\n",
    ".#.#...|#.\n",
    ".....#|##|\n",
    ".|..|...#.\n",
    "..|#.....#\n",
    "#.#|||#|#|\n",
    "...#.||...\n",
    ".|....|...\n",
    "||...#|.#|\n",
    "|.||||..|.\n",
    "...#.|..|.\n",
    "'''\n",
    "\n",
    "areas = evolve_area(read_setup(example_data))\n",
    "print(render_grid(next(areas)),\n",
    "      render_grid(next(areas)),\n",
    "      render_grid(next(areas)), sep='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That looks fine. Now let's check the resource value -- the number of wooded acres multiplied by the number of lumberyards -- after 10 minutes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "604884"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def area_value(area):\n",
    "    counts = collections.Counter(area.values())\n",
    "    return counts[trees] * counts[yard]\n",
    "    \n",
    "def resource_value(data, t):\n",
    "    areas = evolve_area(read_setup(data))\n",
    "    area = next(its.islice(areas, t, None))\n",
    "    return area_value(area)\n",
    "\n",
    "assert resource_value(example_data, 10) == 1147\n",
    "resource_value(day(18), 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part two, we're asked for the resource value after `1_000_000_000` minutes. Look for a repeating pattern in the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "190820"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def repeated_pattern(data, T):\n",
    "    '''Evolve the supplied data for up to T minutes, looking for repeats\n",
    "    \n",
    "    Returns the repeat, time + time first seen\n",
    "    Or the final area, 0, 0 if no repeats found\n",
    "    '''\n",
    "    seen = {}\n",
    "    areas = evolve_area(read_setup(data))\n",
    "    for t, area in its.islice(enumerate(areas), T+1):\n",
    "        area_hash = render_grid(area)\n",
    "        if area_hash in seen:\n",
    "            return area, seen[area_hash], t\n",
    "        seen[area_hash] = t\n",
    "    return area, 0, 0\n",
    "\n",
    "def resource_value(data, T):\n",
    "    area, tlo, thi = repeated_pattern(data, T)\n",
    "    if thi > tlo:\n",
    "        t_left = (T - tlo) % (thi - tlo)\n",
    "        area = next(its.islice(evolve_area(area), t_left, None))\n",
    "    return area_value(area)\n",
    "\n",
    "assert resource_value(example_data, 10) == 1147\n",
    "resource_value(day(18), 1_000_000_000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 19](https://adventofcode.com/2018/day/19) Go With The Flow\n",
    "Again, we're being asked to model a processor. In fact the processor uses the same rules as Day 16."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 5, 0, 0, 0, 0]\n",
      "[1, 5, 6, 0, 0, 0]\n",
      "[3, 5, 6, 0, 0, 0]\n",
      "[5, 5, 6, 0, 0, 0]\n",
      "[6, 5, 6, 0, 0, 9]\n"
     ]
    }
   ],
   "source": [
    "def load_program(data, instructions):\n",
    "    ip, *ops = data.splitlines()\n",
    "    ip = int(ip.split()[1])\n",
    "    return ip, [(instructions[op.split()[0]], ints(op)) for op in ops]\n",
    "\n",
    "def run_program(regs, ip, ops):\n",
    "    while regs[ip] in range(len(ops)):\n",
    "        op, args = ops[regs[ip]]\n",
    "        op(regs, *args)\n",
    "        yield regs[:]\n",
    "        regs[ip] += 1\n",
    "\n",
    "example_program = r'''\\\n",
    "ip 0\n",
    "seti 5 0 1\n",
    "seti 6 0 2\n",
    "addi 0 1 0\n",
    "addr 1 2 3\n",
    "setr 1 0 0\n",
    "seti 8 0 4\n",
    "seti 9 0 5'''\n",
    "\n",
    "ops = {op.__name__: op for op in all_ops}\n",
    "prog = load_program(example_program, ops)\n",
    "print(*take(run_program([0, 0, 0, 0, 0, 0], *prog)), sep='\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 5, 6, 0, 0, 9]"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "last(run_program([0, 0, 0, 0, 0, 0], *prog))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 8.85 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1568, 892, 256, 893, True, 893]"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time last(run_program([0, 0, 0, 0, 0, 0], *load_program(day(19), ops)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had a strong suspicion that this technique wasn't going to get me answer to the second part of the question -- so I set it running whilst also trying to figure out what the [instructions](input/19) were actually doing. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#ip 2\n",
      "addi 2 16 2\n",
      "seti 1 8 5\n",
      "seti 1 0 3\n",
      "mulr 5 3 4\n",
      "eqrr 4 1 4\n",
      "addr 4 2 2\n",
      "addi 2 1 2\n",
      "addr 5 0 0\n",
      "addi 3 1 3\n",
      "gtrr 3 1 4\n",
      "addr 2 4 2\n",
      "seti 2 1 2\n",
      "addi 5 1 5\n",
      "gtrr 5 1 4\n",
      "addr 4 2 2\n",
      "seti 1 1 2\n",
      "mulr 2 2 2\n",
      "addi 1 2 1\n",
      "mulr 1 1 1\n",
      "mulr 2 1 1\n",
      "muli 1 11 1\n",
      "addi 4 2 4\n",
      "mulr 4 2 4\n",
      "addi 4 12 4\n",
      "addr 1 4 1\n",
      "addr 2 0 2\n",
      "seti 0 9 2\n",
      "setr 2 3 4\n",
      "mulr 4 2 4\n",
      "addr 2 4 4\n",
      "mulr 2 4 4\n",
      "muli 4 14 4\n",
      "mulr 4 2 4\n",
      "addr 1 4 1\n",
      "seti 0 1 0\n",
      "seti 0 4 2\n"
     ]
    }
   ],
   "source": [
    "! cat input/19"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "C = C + 16       # 0\n",
      "F = 1            # 1\n",
      "D = 1            # 2\n",
      "E = F * D        # 3\n",
      "E = E == B       # 4\n",
      "C = E + C        # 5\n",
      "C = C + 1        # 6\n",
      "A = F + A        # 7\n",
      "D = D + 1        # 8\n",
      "E = D > B        # 9\n",
      "C = C + E        # 10\n",
      "C = 2            # 11\n",
      "F = F + 1        # 12\n",
      "E = F > B        # 13\n",
      "C = E + C        # 14\n",
      "C = 1            # 15\n",
      "C = C * C        # 16\n",
      "B = B + 2        # 17\n",
      "B = B * B        # 18\n",
      "B = C * B        # 19\n",
      "B = B * 11       # 20\n",
      "E = E + 2        # 21\n",
      "E = E * C        # 22\n",
      "E = E + 12       # 23\n",
      "B = B + E        # 24\n",
      "C = C + A        # 25\n",
      "C = 0            # 26\n",
      "E = C            # 27\n",
      "E = E * C        # 28\n",
      "E = C + E        # 29\n",
      "E = C * E        # 30\n",
      "E = E * 14       # 31\n",
      "E = E * C        # 32\n",
      "B = B + E        # 33\n",
      "A = 0            # 34\n",
      "C = 0            # 35\n"
     ]
    }
   ],
   "source": [
    "def rewrite(instructions):\n",
    "    vars = 'ABCDEF'\n",
    "    def put(s, i):\n",
    "        print('{:<16} # {}'.format(s, i))\n",
    "\n",
    "    for i, (op, (a, b, c)) in enumerate(instructions):\n",
    "        syms = {\n",
    "            addr:'+', addi:'+', mulr:'*', muli:'*', \n",
    "            banr:'&', bani:'&', borr:'|', bori:'|',\n",
    "            gtir:'>', gtri:'>', gtrr:'>', eqir:'==', eqri:'==', eqrr:'=='\n",
    "        }\n",
    "        name = op.__name__\n",
    "        \n",
    "        if name == 'seti':\n",
    "            put(f'{vars[c]} = {a}', i)\n",
    "        elif name == 'setr':\n",
    "            put(f'{vars[c]} = {vars[a]}', i)\n",
    "        else:\n",
    "            if   name.endswith('rr'): lhs, rhs = vars[a], vars[b]\n",
    "            elif name.endswith('ir'): lhs, rhs =      a , vars[b]\n",
    "            elif name.endswith('i' ): lhs, rhs = vars[a], b\n",
    "            elif name.endswith('r' ): lhs, rhs = vars[a], vars[b]\n",
    "            put(f'{vars[c]} = {lhs} {syms[op]} {rhs}', i)\n",
    "\n",
    "rewrite(load_program(day(19), ops)[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, C is the instruction pointer. Running the program for ~100 iterations and checking the registers, it became clear that B had become fixed at `10551292` and the eventual exit point would be line 16, `C = C * C`.\n",
    "\n",
    "I refactored the inner block as:\n",
    "\n",
    "    for F in range(1, B+1):\n",
    "        for D in range(1, B+1):\n",
    "            if F*D == B:\n",
    "                A += F\n",
    "\n",
    "That is, A (register 0, which part two asks for) is the sum of factors of B. We can figure this out by processing numbers up to the square root of B."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19030032"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "B = 10_551_292\n",
    "sum(F + B//F for F in range(1, int(math.sqrt(B))) if B % F == 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 20](https://adventofcode.com/2018/day/20) A Regular Map\n",
    "A branching path through a grid of rooms is specified by a regular expression. For part one, we are asked to find the shortest path to the furthest room.\n",
    "\n",
    "We can step through the regex one character at a time, exploring the map at the same time. I sketched this procedure out a few times on a simple regex containing 1) nested groups and 2) empty options, noting down what state needed saving.\n",
    "\n",
    "![Procedure sketch](images/day20.jpg)\n",
    "\n",
    "My coded solution maintains a \"frontier\" -- the rooms we are visiting right now -- and a stack corresponding to the groups in the regex. For each group we have two things:\n",
    "1. the start positions for the group. That is, the frontier when the group started. We go back to these start positions for each branch in the group.\n",
    "2. the ends of each branch visited during group traversal. When the group ends, these become the new frontier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Use Complex numbers for 2-D position and direction\n",
    "step_vals = {'N': -1j, 'E': 1, 'S': 1j, 'W':-1}\n",
    "\n",
    "def advance(frontier, c, doors):\n",
    "    \"Advance `frontier` by a compass direction `c`, noting `doors` used\"\n",
    "    s = step_vals[c]\n",
    "    for f in frontier:\n",
    "        doors[f].add(f + s)\n",
    "        doors[f + s].add(f)\n",
    "    return {f + s for f in frontier}\n",
    "\n",
    "def visit_rooms(map_re):\n",
    "    \"Process the map regex, returning the doors we discovered\"\n",
    "    doors = collections.defaultdict(set)\n",
    "    frontier = {0}\n",
    "\n",
    "    group_stack = []\n",
    "    push = group_stack.append\n",
    "    pop = group_stack.pop\n",
    "    start = lambda: group_stack[-1][0]\n",
    "    branches = lambda: group_stack[-1][1]\n",
    "    \n",
    "    for c in map_re:\n",
    "        if c in '^(':\n",
    "            push((frontier, set()))\n",
    "        elif c in 'NEWS':\n",
    "            frontier = advance(frontier, c, doors)\n",
    "        elif c == '|':\n",
    "            branches().update(frontier)\n",
    "            frontier = set(start())\n",
    "        elif c == ')':\n",
    "            branches().update(frontier)\n",
    "            _, frontier = pop()\n",
    "        else:\n",
    "            assert c == '$'\n",
    "            return doors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A breadth first search generates the rooms at distances 0, 1, 2, ... from the origin. The distance to the final room(s) visited in this way gives us the answer to part one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3725"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def shortest_paths_to_rooms(map_re):\n",
    "    doors = visit_rooms(map_re)\n",
    "    frontier = {0}\n",
    "    visited = {0}\n",
    "    d = 0\n",
    "    # A breadth first traversal gives us the distances to each room\n",
    "    while frontier:\n",
    "        yield frontier, d\n",
    "        frontier = set.union(*[doors[f] for f in frontier]) - visited\n",
    "        d += 1\n",
    "        visited |= frontier\n",
    "\n",
    "\n",
    "assert last(shortest_paths_to_rooms('^ENWWW(NEEE|SSE(EE|N))$'))[1] == 10\n",
    "assert last(shortest_paths_to_rooms('^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$'))[1] == 18\n",
    "\n",
    "last(shortest_paths_to_rooms(day(20)))[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two asks how many rooms are more than 1000 steps away."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8541"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(len(f) for f, d in shortest_paths_to_rooms(day(20)) if d >= 1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 21](https://adventofcode.com/2018/day/21) Chronal Conversion\n",
    "We're asked to run the same machine and instruction set as we did in days 16 and 19. This time we're asked for the smallest value for `register 0` which stops the program entering an infinite loop.\n",
    "\n",
    "The puzzle description hints:\n",
    "> the activation system begins with a few instructions which verify that **bitwise AND** (via bani) does a numeric operation and not an operation as if the inputs were interpreted as strings. If the test fails, it enters an infinite loop re-running the test instead of allowing the program to execute normally. If the test passes, the program continues, and assumes that all other **bitwise operations** (banr, bori, and borr) also interpret their inputs as **numbers**.\n",
    "\n",
    "I am not sure exactly what that means or how it helps. Certainly my implementation does treat the bitwise operations as numeric: what does it even mean for a bitwise operation to treat inputs as strings?\n",
    "\n",
    "Well, let's start by looking at the [program](input/21)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#ip 2\n",
      "seti 123 0 4\n",
      "bani 4 456 4\n",
      "eqri 4 72 4\n",
      "addr 4 2 2\n",
      "seti 0 0 2\n",
      "seti 0 7 4\n",
      "bori 4 65536 3\n",
      "seti 10283511 1 4\n",
      "bani 3 255 1\n",
      "addr 4 1 4\n",
      "bani 4 16777215 4\n",
      "muli 4 65899 4\n",
      "bani 4 16777215 4\n",
      "gtir 256 3 1\n",
      "addr 1 2 2\n",
      "addi 2 1 2\n",
      "seti 27 8 2\n",
      "seti 0 1 1\n",
      "addi 1 1 5\n",
      "muli 5 256 5\n",
      "gtrr 5 3 5\n",
      "addr 5 2 2\n",
      "addi 2 1 2\n",
      "seti 25 3 2\n",
      "addi 1 1 1\n",
      "seti 17 0 2\n",
      "setr 1 4 3\n",
      "seti 7 6 2\n",
      "eqrr 4 0 1\n",
      "addr 1 2 2\n",
      "seti 5 2 2\n"
     ]
    }
   ],
   "source": [
    "! cat input/21"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "E = 123          # 0\n",
      "E = E & 456      # 1\n",
      "E = E == 72      # 2\n",
      "C = E + C        # 3\n",
      "C = 0            # 4\n",
      "E = 0            # 5\n",
      "D = E | 65536    # 6\n",
      "E = 10283511     # 7\n",
      "B = D & 255      # 8\n",
      "E = E + B        # 9\n",
      "E = E & 16777215 # 10\n",
      "E = E * 65899    # 11\n",
      "E = E & 16777215 # 12\n",
      "B = 256 > D      # 13\n",
      "C = B + C        # 14\n",
      "C = C + 1        # 15\n",
      "C = 27           # 16\n",
      "B = 0            # 17\n",
      "F = B + 1        # 18\n",
      "F = F * 256      # 19\n",
      "F = F > D        # 20\n",
      "C = F + C        # 21\n",
      "C = C + 1        # 22\n",
      "C = 25           # 23\n",
      "B = B + 1        # 24\n",
      "C = 17           # 25\n",
      "D = B            # 26\n",
      "C = 7            # 27\n",
      "B = E == A       # 28\n",
      "C = B + C        # 29\n",
      "C = 5            # 30\n"
     ]
    }
   ],
   "source": [
    "rewrite(load_program(day(21), ops)[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: the instruction pointer is 2, i.e. C. \n",
    "\n",
    "The program will exit following line 29, iff line 28 sets `B` to `1`, i.e. iff `E == A`.\n",
    "\n",
    "Let's take a look at what's happening after 10_000 cycles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1163, 17, 13443200, 16217789, False]\n",
      "[0, 1163, 18, 13443200, 16217789, 1164]\n",
      "[0, 1163, 19, 13443200, 16217789, 297984]\n",
      "[0, 1163, 20, 13443200, 16217789, False]\n",
      "[0, 1163, 21, 13443200, 16217789, False]\n",
      "[0, 1163, 23, 13443200, 16217789, False]\n",
      "[0, 1164, 24, 13443200, 16217789, False]\n",
      "[0, 1164, 17, 13443200, 16217789, False]\n",
      "[0, 1164, 18, 13443200, 16217789, 1165]\n",
      "[0, 1164, 19, 13443200, 16217789, 298240]\n",
      "[0, 1164, 20, 13443200, 16217789, False]\n",
      "[0, 1164, 21, 13443200, 16217789, False]\n",
      "[0, 1164, 23, 13443200, 16217789, False]\n",
      "[0, 1165, 24, 13443200, 16217789, False]\n",
      "[0, 1165, 17, 13443200, 16217789, False]\n",
      "[0, 1165, 18, 13443200, 16217789, 1166]\n",
      "[0, 1165, 19, 13443200, 16217789, 298496]\n",
      "[0, 1165, 20, 13443200, 16217789, False]\n",
      "[0, 1165, 21, 13443200, 16217789, False]\n",
      "[0, 1165, 23, 13443200, 16217789, False]\n"
     ]
    }
   ],
   "source": [
    "prog = load_program(day(21), ops)\n",
    "N = 10_000\n",
    "regvals = its.islice(run_program([0,0,0,0,0,0], *prog), N, N + 20)\n",
    "print(*list(regvals), sep='\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 19910, 24, 15986692, 8046313, False]\n",
      "[0, 19910, 17, 15986692, 8046313, False]\n",
      "[0, 19910, 18, 15986692, 8046313, 19911]\n",
      "[0, 19910, 19, 15986692, 8046313, 5097216]\n",
      "[0, 19910, 20, 15986692, 8046313, False]\n",
      "[0, 19910, 21, 15986692, 8046313, False]\n",
      "[0, 19910, 23, 15986692, 8046313, False]\n",
      "[0, 19911, 24, 15986692, 8046313, False]\n",
      "[0, 19911, 17, 15986692, 8046313, False]\n",
      "[0, 19911, 18, 15986692, 8046313, 19912]\n",
      "[0, 19911, 19, 15986692, 8046313, 5097472]\n",
      "[0, 19911, 20, 15986692, 8046313, False]\n",
      "[0, 19911, 21, 15986692, 8046313, False]\n",
      "[0, 19911, 23, 15986692, 8046313, False]\n",
      "[0, 19912, 24, 15986692, 8046313, False]\n",
      "[0, 19912, 17, 15986692, 8046313, False]\n",
      "[0, 19912, 18, 15986692, 8046313, 19913]\n",
      "[0, 19912, 19, 15986692, 8046313, 5097728]\n",
      "[0, 19912, 20, 15986692, 8046313, False]\n",
      "[0, 19912, 21, 15986692, 8046313, False]\n"
     ]
    }
   ],
   "source": [
    "# How about after 1_000_000 cycles?\n",
    "N = 1_000_000\n",
    "regvals = its.islice(run_program([0,0,0,0,0,0], *prog), N, N + 20)\n",
    "print(*list(regvals), sep='\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, it appears the inner loop is instructions 17, 18, 19, 20, 21, 23, 24. We''ll only exit this loop when `F > D` is `True`.\n",
    "\n",
    "Other things to notice:\n",
    "- `A` looks stuck on its initial value\n",
    "- `B` increments with each run of the inner loop body\n",
    "- `D` and `E` hold large values which change less frequently\n",
    "- `F` is used for numbers and boolean test values\n",
    "\n",
    "At this point I started rewriting the program from this inner loop outwards. The inner loop refactors as `B = D // 256`, and we have the next level loop as:\n",
    "```\n",
    "E = 10283511     # 7\n",
    "B = D & 255      # 8\n",
    "E = E + B        # 9\n",
    "E = E & 16777215 # 10\n",
    "E = E * 65899    # 11\n",
    "E = E & 16777215 # 12\n",
    "B = 256 > D      # 13\n",
    "C = B + C        # 14\n",
    "C = C + 1        # 15\n",
    "C = 27           # 16\n",
    "D //= 256\n",
    "C = 7            # 27\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I refactored the program as:\n",
    "```\n",
    "E = 0            # 5\n",
    "\n",
    "while True:\n",
    "    D = E | 65536    # 6\n",
    "    E = 10283511     # 7\n",
    "    while True:\n",
    "        E += D & 255\n",
    "        E &= 16777215\n",
    "        E *= 65899\n",
    "        E &= 16777215\n",
    "        if D < 256: break\n",
    "        D //= 256\n",
    "\n",
    "    if E == A: break\n",
    "```\n",
    "It's now possible to find the value of `A` which causes the program to exit soonest. We set `A` to be the value `E` takes first time the inner loop is exited."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13443200"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def generate_E_values():\n",
    "    E = 0\n",
    "    while True:\n",
    "        D = E | 65536    # 6\n",
    "        E = 10283511     # 7\n",
    "        while True:\n",
    "            E += D & 255\n",
    "            E &= 16777215\n",
    "            E *= 65899\n",
    "            E &= 16777215\n",
    "            if D < 256: break\n",
    "            D //= 256\n",
    "        yield E\n",
    "\n",
    "next(generate_E_values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part two, we're asked for the lowest value of `A` that causes the program to halt after executing the most instructions. This will be the value of `E` produced immediately before we see a repeated value of `E`. (Note that `E <= 16777215` so there must be repeats.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7717135"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "seen = set()\n",
    "for prev_E, this_E in pairwise(generate_E_values()):\n",
    "    if this_E in seen:\n",
    "        break\n",
    "    seen.add(this_E)\n",
    "\n",
    "prev_E"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 22](https://adventofcode.com/2018/day/22) Mode Maze\n",
    "Recursive calculations to figure out erosion levels in a cave system. We can use a cache to save time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10603"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@functools.lru_cache(None)\n",
    "def erosion_level(x, y, depth, target):\n",
    "    return (geological_index(x, y, depth, target) + depth) % 20183\n",
    "\n",
    "@functools.lru_cache(None)\n",
    "def geological_index(x, y, depth, target):\n",
    "    if (x, y) == target: return 0\n",
    "    if y == 0: return x * 16807\n",
    "    if x == 0: return y * 48271\n",
    "    return erosion_level(x-1, y, depth, target) * erosion_level(x, y-1, depth, target)\n",
    "\n",
    "def region_type(x, y, depth, target):\n",
    "    return erosion_level(x, y, depth, target) % 3\n",
    "\n",
    "def risk_level(depth, target):\n",
    "    return sum(region_type(x, y, depth, target)\n",
    "               for x, y in its.product(range(target[0]+1), \n",
    "                                       range(target[1]+1)))\n",
    "               \n",
    "assert risk_level(510, (10, 10)) == 114\n",
    "\n",
    "depth, target = 6084, (14, 709)\n",
    "\n",
    "risk_level(depth, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two asks us for the quickest route from the start point of `(0, 0)` to the target. We have tools to traverse the cave system, and rules for swapping these tools."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "952"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ROCKY, WET, NARROW = 0, 1, 2\n",
    "TOOLS = TORCH, ROPE, NEITHER = 0, 1, 2\n",
    "T_STEP, T_CHANGE = 1, 7\n",
    "\n",
    "CaveState = collections.namedtuple('CaveState', 'x y tool')\n",
    "\n",
    "def usable(tool, region):\n",
    "    'Return True iff the tool is usable in the region'\n",
    "    return tool in {ROCKY: (ROPE, TORCH),\n",
    "                    WET: (ROPE, NEITHER),\n",
    "                    NARROW: (TORCH, NEITHER)}[region]\n",
    "\n",
    "def cave_moves(cave_state, depth, target):\n",
    "    ''' Generate the moves from the supplied state \n",
    "\n",
    "    Yields (new_state, step_cost) pairs\n",
    "    '''\n",
    "    x, y, tool = cave_state\n",
    "\n",
    "    yield from (\n",
    "        (CaveState(nx, ny, tool), T_STEP)\n",
    "        for nx, ny in neighbours4(x, y)\n",
    "        if nx >= 0 and ny >= 0 and usable(tool, region_type(nx, ny, depth, target)))\n",
    "\n",
    "    yield from(\n",
    "        (CaveState(x, y, new_tool), T_CHANGE)\n",
    "        for new_tool in set(TOOLS) - {tool}\n",
    "        if usable(new_tool, region_type(x, y, depth, target)))\n",
    "        \n",
    "def heuristic(cave_state, target):\n",
    "    'Return an A-star heuristic for moving from the state to the target'\n",
    "    x, y, tool = cave_state\n",
    "    swap_to_torch = 0 if tool == TORCH else T_CHANGE\n",
    "    return manhattan_distance((x, y), target) + swap_to_torch\n",
    "\n",
    "def rescue_time(start, target, depth):\n",
    "    return a_star(CaveState(*start, TORCH),\n",
    "                  lambda s: heuristic(s, target),\n",
    "                  lambda s: map(first, cave_moves(s, depth, target)),\n",
    "                  lambda s: map(second, cave_moves(s, depth, target)))[0]\n",
    "\n",
    "assert rescue_time((0, 0), (10, 10), 510) == 45\n",
    "\n",
    "rescue_time((0, 0), target, depth)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 23](https://adventofcode.com/2018/day/23) Experimental Emergency Teleportation\n",
    "Nanobots in 3-space. In part one, each has a position and radius. We are asked to find how many are in range of the one with the largest radius, using a city-block distance metric."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "219"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "example_23 = '''\\\n",
    "pos=<0,0,0>, r=4\n",
    "pos=<1,0,0>, r=1\n",
    "pos=<4,0,0>, r=3\n",
    "pos=<0,2,0>, r=1\n",
    "pos=<0,5,0>, r=3\n",
    "pos=<0,0,3>, r=1\n",
    "pos=<1,1,1>, r=1\n",
    "pos=<1,1,2>, r=1\n",
    "pos=<1,3,1>, r=1'''\n",
    "\n",
    "def in_range_of_strongest(nanobot_data):\n",
    "    nanobots = array(nanobot_data)\n",
    "    *strongest, strength = max(nanobots, key=lambda nb: nb[3])\n",
    "    return ilen(nb for nb in nanobots \n",
    "                if manhattan_distance(nb[:3], strongest) <= strength)\n",
    "\n",
    "assert in_range_of_strongest(example_23) == 7\n",
    "in_range_of_strongest(day(23))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part two asks us for the point in range of the greatest number of nanobots. If there's more than one such point, return the one closest to the origin.\n",
    "\n",
    "We can do this by finding the maximal clique of the graph formed from the nanobots, where an edge links N1 and N2 if N1 is in range of N2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "83779034.0"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def nanobot_neighbours(nanobot_data):\n",
    "    ''' Return the graph connecting nanobots\n",
    "    \n",
    "    For a nanobot N, G[N] is the set of nanobots in range of N.\n",
    "    '''\n",
    "    nanobots = array(nanobot_data)\n",
    "    G = collections.defaultdict(set)\n",
    "    for p, q in its.permutations(nanobots, 2):\n",
    "        r = p[3] + q[3]\n",
    "        if manhattan_distance(p[:3], q[:3]) <= r:\n",
    "            G[p].add(q)\n",
    "    return dict(G)\n",
    "\n",
    "def maximal_cliques(G):\n",
    "    ''' Generate maximal cliques of a graph, G\n",
    "    \n",
    "    https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm\n",
    "    '''\n",
    "    def max_cliques(R, P, X):\n",
    "        # R, P, X are disjoint sets of vertices\n",
    "        # We're looking for maximal cliques which contain R\n",
    "        # with some of P and none of X\n",
    "        if not P and not X:\n",
    "            yield R\n",
    "        else:\n",
    "            pivot = next(iter(P | X))\n",
    "            for v in P - G[pivot]:\n",
    "                N = set(G[v])\n",
    "                yield from max_cliques(R | {v}, P & N, X & N)\n",
    "                P.remove(v)\n",
    "                X.add(v)\n",
    "    yield from max_cliques(set(), set(G), set())\n",
    "\n",
    "example_23 = '''\\\n",
    "pos=<10,12,12>, r=2\n",
    "pos=<12,14,12>, r=2\n",
    "pos=<16,12,12>, r=4\n",
    "pos=<14,14,14>, r=6\n",
    "pos=<50,50,50>, r=200\n",
    "pos=<10,10,10>, r=5'''\n",
    "\n",
    "G = nanobot_neighbours(day(23))\n",
    "origin = 0, 0, 0\n",
    "clique = max(maximal_cliques(G), key=len)\n",
    "max(manhattan_distance(n[:3], origin) - n[3] for n in clique)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Although this answer turns out to be correct the reasoning is flawed. The assumption made is that if a group of nanobots pairwise connect, then there must be a point connected to every point in the group. That assumption need not hold.\n",
    "\n",
    "Here's an alternative way to find the answer using the Z3 SMT solver.\n",
    "\n",
    "See [Reddit solutions](https://www.reddit.com/r/adventofcode/comments/a8s17l/2018_day_23_solutions/) for details. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import z3\n",
    "\n",
    "def Abs(v):\n",
    "    return z3.If(v > 0, v, -v)\n",
    "\n",
    "def Dist(pos, bot):\n",
    "    return sum(Abs(p-b) for p, b in zip(pos, bot))\n",
    "\n",
    "def most_in_range(nanobot_data):\n",
    "    optimizer = z3.Optimize()\n",
    "    pos = z3.IntVector('pos', 3)\n",
    "    optimizer.maximize(sum(\n",
    "        z3.If(Dist(pos, bot) <= r, 1, 0) \n",
    "        for *bot, r in array(nanobot_data)))\n",
    "    dist_to_origin = optimizer.minimize(Dist(pos, origin))\n",
    "    optimizer.check()\n",
    "    return optimizer.lower(dist_to_origin)\n",
    "\n",
    "assert most_in_range(example_23) == 36\n",
    "%time most_in_range(day(23))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 24](https://adventofcode.com/2018/day/24) Immune System Simulator 20XX\n",
    "Oh, this looks similar to day 15 -- which I haven't done yet. It's a battle between the immune system and the infection following complicated rules. Let's start by reading the game parameters from the input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input_24s = '''\\\n",
    "6111 units each with 1395 hit points (weak to bludgeoning; immune to radiation, fire) with an attack that does 1 slashing damage at initiative 14\n",
    "231 units each with 3038 hit points (immune to radiation) with an attack that does 128 cold damage at initiative 15\n",
    "3562 units each with 22067 hit points with an attack that does 9 fire damage at initiative 18\n",
    "'''\n",
    "\n",
    "@dataclasses.dataclass\n",
    "class Group:\n",
    "    units: int\n",
    "    hit_points: int\n",
    "    damage_: int\n",
    "    initiative: int\n",
    "    attack_: str\n",
    "    weak_to: frozenset\n",
    "    immune_to: frozenset\n",
    "    name: str\n",
    "    selects: object=None\n",
    "    selected_by: object=None\n",
    "    \n",
    "    @property\n",
    "    def effective_power(self): return self.units * self.damage_\n",
    "\n",
    "    def damage(self, defender):\n",
    "        'Return the damage inflicted on `defender`'\n",
    "        d = self.effective_power\n",
    "        return (\n",
    "            0   if self.attack_ in defender.immune_to else\n",
    "            2*d if self.attack_ in defender.weak_to else d)\n",
    "    \n",
    "    def defend(self, strike_damage):\n",
    "        'Defend against a strike'\n",
    "        pts_left = max(self.units * self.hit_points - strike_damage, 0)\n",
    "        units_before = self.units\n",
    "        self.units = (pts_left + self.hit_points - 1)//self.hit_points\n",
    "        return units_before - self.units\n",
    "        \n",
    "    def attack(self):\n",
    "        'Attack selected target, if any, returning # units destroyed'\n",
    "        d = self.selects\n",
    "        return d.defend(self.damage(d)) if d else 0\n",
    "    \n",
    "    def select(self, target):\n",
    "        'Select `target` to attack'\n",
    "        self.selects = target\n",
    "        target.selected_by = self\n",
    "    \n",
    "    def deselect(self):\n",
    "        'Reset any selections'\n",
    "        self.selects = self.selected_by = None\n",
    "    \n",
    "    def boost(self, b):\n",
    "        self.damage_ += b\n",
    "    \n",
    "    def __str__(self):\n",
    "        return self.name\n",
    "\n",
    "def group(s, name):\n",
    "    units, hit_points, damage, initiative = ints(s)\n",
    "    attack    = re.search('(\\w+) damage', s).group(1)\n",
    "    weak_to   = re.findall(  'weak to ([^;)]*)', s) or ['']\n",
    "    immune_to = re.findall('immune to ([^;)]*)', s) or ['']\n",
    "    weak_to   = frozenset(weak_to[0].split(', '))\n",
    "    immune_to = frozenset(immune_to[0].split(', '))\n",
    "    return Group(*ints(s), attack, weak_to, immune_to, name)\n",
    " \n",
    "for i, s in enumerate(input_24s.splitlines(), 1): \n",
    "    print(repr(group(s, f'Group {i}')))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That looks fine -- here's a function to read in both armies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def read_armies(data):\n",
    "    armies = [], []\n",
    "    names = 'Immune', 'Infect'\n",
    "    for s in data.splitlines():\n",
    "        if   s.startswith('Immune'): i = 0\n",
    "        elif s.startswith('Infect'): i = 1\n",
    "        elif s.strip(): \n",
    "            armies[i].append(group(s, f'{names[i]}-{len(armies[i])+1}'))\n",
    "    return armies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need to get to grips with the battle rules. There are two phases:\n",
    "- target selection\n",
    "- attacking"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def attack_key(attacker):\n",
    "    'Key function for group selection ordering'\n",
    "    return -attacker.effective_power, -attacker.initiative\n",
    "\n",
    "def defend_key(attacker):\n",
    "    def key(d):\n",
    "        return -attacker.damage(d), -d.effective_power, -d.initiative\n",
    "    return key\n",
    "\n",
    "def select_targets(attackers, defenders):\n",
    "    for a in sorted(attackers, key=attack_key):\n",
    "        for d in sorted(defenders, key=defend_key(a)):\n",
    "            if a.damage(d) > 0 and d.selected_by is None:\n",
    "                a.select(d)\n",
    "                break\n",
    "\n",
    "def selection(armies):\n",
    "    for group in flatten(armies): # Clear any existing selections\n",
    "        group.deselect()\n",
    "    select_targets(armies[0], armies[1])\n",
    "    select_targets(armies[1], armies[0])\n",
    "\n",
    "def remove_dead_units(armies):\n",
    "    return ([a for a in armies[0] if a.units],\n",
    "            [a for a in armies[1] if a.units])\n",
    "\n",
    "def display(armies):\n",
    "    for army in armies:\n",
    "        print(ncat(f'{g} has {g.units} units, '\n",
    "                   f'selects {g.selects} selected_by {g.selected_by}'\n",
    "                   for i, g in enumerate(army, 1)))\n",
    "    print()\n",
    "\n",
    "def battle(armies, verbose=False):\n",
    "    units_destroyed = 1 # Any truthy value, just to enter the loop\n",
    "    while all(armies) and units_destroyed:\n",
    "        selection(armies)\n",
    "        if verbose: display(armies)\n",
    "        units_destroyed = sum(\n",
    "            group.attack()\n",
    "            for group in sorted(armies[0] + armies[1], \n",
    "                                key=lambda g: -g.initiative))\n",
    "        armies = remove_dead_units(armies)\n",
    "    return armies\n",
    "\n",
    "def remaining_units(data, verbose=False):\n",
    "    armies = battle(read_armies(data), verbose)\n",
    "    return sum(a.units for a in flatten(armies))\n",
    "\n",
    "example24 ='''\\\n",
    "Immune System:\n",
    "17 units each with 5390 hit points (weak to radiation, bludgeoning) with an attack that does 4507 fire damage at initiative 2\n",
    "989 units each with 1274 hit points (immune to fire; weak to bludgeoning, slashing) with an attack that does 25 slashing damage at initiative 3\n",
    "\n",
    "Infection:\n",
    "801 units each with 4706 hit points (weak to radiation) with an attack that does 116 bludgeoning damage at initiative 1\n",
    "4485 units each with 2961 hit points (immune to radiation; weak to fire, cold) with an attack that does 12 slashing damage at initiative 4\n",
    "'''\n",
    "\n",
    "assert remaining_units(example24, verbose=True) == 5216"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "remaining_units(day(24))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the second part, we have the option of _boosting_ the immune system's army. Boosting by an amount `B` results in the attack damage being increased by `B`. We are asked to find the smallest boost which results in the immune system winning.\n",
    "\n",
    "To do this, I went back to the `Group` class and added a `boost` method.\n",
    "Then I checked the worked example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def boost(army, b):\n",
    "    for group in army:\n",
    "        group.boost(b)\n",
    "\n",
    "armies = read_armies(example24)\n",
    "boost(armies[0], 1570)\n",
    "immune, infect = battle(armies)\n",
    "assert sum(g.units for g in immune) == 51"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def final_immune_winning_units(army_description, boost_=0):\n",
    "    armies = read_armies(army_description)\n",
    "    boost(armies[0], boost_)\n",
    "    armies = battle(armies)\n",
    "    return (sum(g.units for g in armies[0]) \n",
    "            if armies[0] and not armies[1]\n",
    "            else 0)\n",
    "\n",
    "desc = day(24)\n",
    "\n",
    "# Note: We could use a binary search here - but I can wait 10 seconds!\n",
    "units = (final_immune_winning_units(desc, b) for b in its.count())\n",
    "%time next(its.dropwhile(lambda u: u==0, units)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Day 25](https://adventofcode.com/2018/day/25) Four-Dimensional Adventure\n",
    "We have points in 4-space, and we're using a Manhattan distance metric. For part one, we have to figure out the number of constellations formed by a set of points: this is the number of connected components of the graph whose nodes are the points, with an edge `PQ` iff `|PQ|` is 3 or less."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def graph(pts, D=3):\n",
    "    '''Form the graph from the `pts` data\n",
    "    \n",
    "    D - add an edge between two points P, Q iff |PQ| <= D\n",
    "    '''\n",
    "    pts = array(pts)\n",
    "    g = {p: set() for p in pts}\n",
    "    for p, q in its.permutations(pts, 2):\n",
    "        if manhattan_distance(p, q) <= D:\n",
    "            g[p].add(q)\n",
    "    return g\n",
    "\n",
    "example_25 = '''\\\n",
    "0,0,0,0\n",
    " 3,0,0,0\n",
    " 0,3,0,0\n",
    " 0,0,3,0\n",
    " 0,0,0,3\n",
    " 0,0,0,6\n",
    " 9,0,0,0\n",
    "12,0,0,0'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def component(g, v):\n",
    "    cpt = {v}\n",
    "    fringe = g[v]\n",
    "    while fringe:\n",
    "        cpt |= fringe\n",
    "        fringe = {w for f in fringe for w in g[f]} - cpt\n",
    "    return cpt\n",
    "    \n",
    "def connected_components(g):\n",
    "    'Generate the connected components of a graph `g`'\n",
    "    vs = set(g)\n",
    "    while vs:\n",
    "        cpt = component(g, vs.pop())\n",
    "        yield cpt\n",
    "        vs -= cpt\n",
    "\n",
    "assert ilen(connected_components(graph(example_25))) == 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "example_25_b = '''\\\n",
    "1,-1,-1,-2\n",
    "-2,-2,0,1\n",
    "0,2,1,3\n",
    "-2,3,-2,1\n",
    "0,2,3,-2\n",
    "-1,-1,1,-2\n",
    "0,-2,-1,0\n",
    "-2,2,3,-1\n",
    "1,2,2,0\n",
    "-1,-2,0,-2'''\n",
    "\n",
    "assert ilen(connected_components(graph(example_25_b))) == 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ilen(connected_components(graph(day(25))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Completed](./completed.png)"
   ]
  },
  {
   "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}