ipynb/Advent 2017.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# December 2017: Advent of Code Solutions\n",
    "\n",
    "Peter Norvig\n",
    "\n",
    "I'm doing the [Advent of Code](https://adventofcode.com) puzzles, just like [last year](https://github.com/norvig/pytudes/blob/master/ipynb/Advent%20of%20Code.ipynb). My terms of engagement are:\n",
    "\n",
    "* You'll need to follow the links in the section headers (e.g. **[Day 1](https://adventofcode.com/2017/day/1)**) to understand what each puzzle is asking; I won't repeat the puzzle description.\n",
    "* What you see is mostly the algorithm I came up with first, although sometimes I go back and refactor for clarity.\n",
    "* I'll clean up the code a bit: adding docstrings, making variable names longer and more descriptive, adding `assert` statements.\n",
    "* I will discuss any errors I made along the way; usually I won't show the erroneous code, just a description of what I did wrong.\n",
    "* The way Advent of Code works is that you read the puzzle descriotion for Part One, but only when you correctly solve it do you get to see Part Two. This is typical in software development: you deploy some code, and then some new requirements arise. So it makes sense to program by creating small functions and data types that form a *vocabulary* for the domain at hand, and can be recombined to solve new problems in the domain.\n",
    "* Each day's code should run in a few seconds; certainly less than a minute. (As it turns out, the total run time for all my solutions was just under a minute.)\n",
    "* There is a contest to see who can solve each day's puzzle fastest; I do not expect to be competitive.\n",
    "\n",
    "\n",
    "\n",
    "# Day 0: Imports and Utility Functions\n",
    "\n",
    "I might need these:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Python 3.x Utility Functions\n",
    "\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "import os\n",
    "import urllib.request\n",
    "\n",
    "import re\n",
    "import numpy as np\n",
    "import math\n",
    "import random\n",
    "import time\n",
    "\n",
    "from collections import Counter, defaultdict, namedtuple, deque, abc, OrderedDict\n",
    "from functools   import lru_cache\n",
    "from statistics  import mean, median, mode, stdev, variance\n",
    "from itertools   import (permutations, combinations, chain, cycle, product, islice, \n",
    "                         takewhile, zip_longest, count as count_from)\n",
    "from heapq       import heappop, heappush\n",
    "from numba       import jit\n",
    "\n",
    "letters  = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "cache = lru_cache(None)\n",
    "\n",
    "cat = ''.join\n",
    "\n",
    "Ø   = frozenset() # Empty set\n",
    "inf = float('inf')\n",
    "BIG = 10 ** 999\n",
    "\n",
    "################ Functions for Input, Parsing\n",
    "\n",
    "def Input(day, year=2017):\n",
    "    \"Open this day's input file.\"\n",
    "    directory = 'advent{}/'.format(year)\n",
    "    filename = directory+'input{}.txt'.format(day)\n",
    "    try:\n",
    "        return open(filename)\n",
    "    except FileNotFoundError:\n",
    "        if not os.path.exists(directory):\n",
    "            os.makedirs(directory)\n",
    "\n",
    "        urllib.request.urlretrieve(\"https://raw.githubusercontent.com/norvig/pytudes/master/data/\" + filename, filename)\n",
    "        return Input(day)\n",
    "\n",
    "def Inputstr(day, year=2017): \n",
    "    \"The contents of this day's input file as a str.\"\n",
    "    return Input(day, year).read().rstrip('\\n')\n",
    "    \n",
    "def Array(lines):\n",
    "    \"Parse an iterable of str lines into a 2-D array. If `lines` is a str, splitlines.\"\n",
    "    if isinstance(lines, str): lines = lines.splitlines()\n",
    "    return mapt(Vector, lines)\n",
    "\n",
    "def Vector(line):\n",
    "    \"Parse a str into a tuple of atoms (numbers or str tokens).\"\n",
    "    return mapt(Atom, line.replace(',', ' ').split())\n",
    "\n",
    "def Integers(text): \n",
    "    \"Return a tuple of all integers in a string.\"\n",
    "    return mapt(int, re.findall(r'-?\\b\\d+\\b', text))\n",
    "\n",
    "def Atom(token):\n",
    "    \"Parse a str token into a number, or leave it as a str.\"\n",
    "    try:\n",
    "        return int(token)\n",
    "    except ValueError:\n",
    "        try:\n",
    "            return float(token)\n",
    "        except ValueError:\n",
    "            return token\n",
    "        \n",
    "def error(err=RuntimeError, *args): raise err(*args)\n",
    "\n",
    "################ Functions on Iterables\n",
    "\n",
    "def first(iterable, default=None): \n",
    "    \"The first item in an iterable, or default if it is empty.\"\n",
    "    return next(iter(iterable), default)\n",
    "\n",
    "def first_true(iterable, pred=None, default=None):\n",
    "    \"\"\"Returns the first true value in the iterable.\n",
    "    If no true value is found, returns *default*\n",
    "    If *pred* is not None, returns the first item\n",
    "    for which pred(item) is true.\"\"\"\n",
    "    # first_true([a,b,c], default=x) --> a or b or c or x\n",
    "    # first_true([a,b], fn, x) --> a if fn(a) else b if fn(b) else x\n",
    "    return next(filter(pred, iterable), default)\n",
    "\n",
    "def nth(iterable, n, default=None):\n",
    "    \"Returns the nth item of iterable, or a default value\"\n",
    "    return next(islice(iterable, n, None), default)\n",
    "\n",
    "def upto(iterable, maxval):\n",
    "    \"From a monotonically increasing iterable, generate all the values <= maxval.\"\n",
    "    # Why <= maxval rather than < maxval? In part because that's how Ruby's upto does it.\n",
    "    return takewhile(lambda x: x <= maxval, iterable)\n",
    "\n",
    "identity = lambda x: x\n",
    "\n",
    "def groupby(iterable, key=identity):\n",
    "    \"Return a dict of {key(item): [items...]} grouping all items in iterable by keys.\"\n",
    "    groups = defaultdict(list)\n",
    "    for item in iterable:\n",
    "        groups[key(item)].append(item)\n",
    "    return groups\n",
    "\n",
    "def grouper(iterable, n, fillvalue=None):\n",
    "    \"\"\"Collect data into fixed-length chunks:\n",
    "    grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx\"\"\"\n",
    "    args = [iter(iterable)] * n\n",
    "    return zip_longest(*args, fillvalue=fillvalue)\n",
    "\n",
    "def overlapping(iterable, n):\n",
    "    \"\"\"Generate all (overlapping) n-element subsequences of iterable.\n",
    "    overlapping('ABCDEFG', 3) --> ABC BCD CDE DEF EFG\"\"\"\n",
    "    if isinstance(iterable, abc.Sequence):\n",
    "        yield from (iterable[i:i+n] for i in range(len(iterable) + 1 - n))\n",
    "    else:\n",
    "        result = deque(maxlen=n)\n",
    "        for x in iterable:\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 sequence(iterable, type=tuple):\n",
    "    \"Coerce iterable to sequence: leave alone if already a sequence, else make it `type`.\"\n",
    "    return iterable if isinstance(iterable, abc.Sequence) else type(iterable)\n",
    "\n",
    "def join(iterable, sep=''):\n",
    "    \"Join the items in iterable, converting each to a string first.\"\n",
    "    return sep.join(map(str, iterable))\n",
    "                \n",
    "def powerset(iterable):\n",
    "    \"Yield all subsets of items.\"\n",
    "    items = list(iterable)\n",
    "    for r in range(len(items)+1):\n",
    "        for c in combinations(items, r):\n",
    "            yield c\n",
    "            \n",
    "def quantify(iterable, pred=bool):\n",
    "    \"Count how many times the predicate is true.\"\n",
    "    return sum(map(pred, iterable))\n",
    "\n",
    "def length(iterable):\n",
    "    \"Same as len(list(iterable)), but without consuming memory.\"\n",
    "    return sum(1 for _ in iterable)\n",
    "\n",
    "def shuffled(iterable):\n",
    "    \"Create a new list out of iterable, and shuffle it.\"\n",
    "    new = list(iterable)\n",
    "    random.shuffle(new)\n",
    "    return new\n",
    "    \n",
    "flatten = chain.from_iterable\n",
    "\n",
    "################ Functional programming\n",
    "\n",
    "def mapt(fn, *args): \n",
    "    \"Do a map, and make the results into a tuple.\"\n",
    "    return tuple(map(fn, *args))\n",
    "\n",
    "def map2d(fn, grid):\n",
    "    \"Apply fn to every element in a 2-dimensional grid.\"\n",
    "    return tuple(mapt(fn, row) for row in grid)\n",
    "\n",
    "def repeat(n, fn, arg, *args, **kwds):\n",
    "    \"Repeat arg = fn(arg) n times, return arg.\"\n",
    "    return nth(repeatedly(fn, arg, *args, **kwds), n)\n",
    "\n",
    "def repeatedly(fn, arg, *args, **kwds):\n",
    "    \"Yield arg, fn(arg), fn(fn(arg)), ...\"\n",
    "    yield arg\n",
    "    while True:\n",
    "        arg = fn(arg, *args, **kwds)\n",
    "        yield arg\n",
    "        \n",
    "def compose(f, g): \n",
    "    \"The function that computes f(g(x)).\"\n",
    "    return lambda x: f(g(x))\n",
    "\n",
    "################ Making immutable objects\n",
    "            \n",
    "class Set(frozenset):\n",
    "    \"A frozenset, but with a prettier printer.\"\n",
    "    def __repr__(self): return '{' + join(sorted(self), ', ') + '}'\n",
    "    \n",
    "def canon(items, typ=None):\n",
    "    \"Canonicalize these order-independent items into a hashable canonical form.\"\n",
    "    typ = typ or (cat if isinstance(items, str) else tuple)\n",
    "    return typ(sorted(items))\n",
    "            \n",
    "################ Math Functions\n",
    "            \n",
    "def transpose(matrix): return tuple(zip(*matrix))\n",
    "\n",
    "def isqrt(n):\n",
    "    \"Integer square root (rounds down).\"\n",
    "    return int(n ** 0.5)\n",
    "\n",
    "def ints(start, end, step=1):\n",
    "    \"The integers from start to end, inclusive: range(start, end+1)\"\n",
    "    return range(start, end + 1, step)\n",
    "\n",
    "def floats(start, end, step=1.0):\n",
    "    \"Yield floats from start to end (inclusive), by increments of step.\"\n",
    "    m = (1.0 if step >= 0 else -1.0)\n",
    "    while start * m <= end * m:\n",
    "        yield start\n",
    "        start += step\n",
    "        \n",
    "def multiply(numbers):\n",
    "    \"Multiply all the numbers together.\"\n",
    "    result = 1\n",
    "    for n in numbers:\n",
    "        result *= n\n",
    "    return result\n",
    "\n",
    "import operator as op\n",
    "\n",
    "operations = {'>': op.gt, '>=': op.ge, '==': op.eq,\n",
    "              '<': op.lt, '<=': op.le, '!=': op.ne,\n",
    "              '+': op.add, '-': op.sub, '*': op.mul, \n",
    "              '/': op.truediv, '**': op.pow}\n",
    "\n",
    "################ 2-D points implemented using (x, y) tuples\n",
    "\n",
    "def X(point): return point[0]\n",
    "def Y(point): return point[1]\n",
    "\n",
    "origin = (0, 0)\n",
    "HEADINGS = UP, LEFT, DOWN, RIGHT = (0, -1), (-1, 0), (0, 1), (1, 0)\n",
    "\n",
    "def turn_right(heading): return HEADINGS[HEADINGS.index(heading) - 1]\n",
    "def turn_around(heading):return HEADINGS[HEADINGS.index(heading) - 2]\n",
    "def turn_left(heading):  return HEADINGS[HEADINGS.index(heading) - 3]\n",
    "\n",
    "def add(A, B): \n",
    "    \"Element-wise addition of two n-dimensional vectors.\"\n",
    "    return mapt(sum, zip(A, B))\n",
    "\n",
    "def neighbors4(point): \n",
    "    \"The four neighboring squares.\"\n",
    "    x, y = point\n",
    "    return (          (x, y-1),\n",
    "            (x-1, y),           (x+1, y), \n",
    "                      (x, y+1))\n",
    "\n",
    "def neighbors8(point): \n",
    "    \"The eight neighboring squares.\"\n",
    "    x, y = point \n",
    "    return ((x-1, y-1), (x, y-1), (x+1, y-1),\n",
    "            (x-1, y),             (x+1, y),\n",
    "            (x-1, y+1), (x, y+1), (x+1, y+1))\n",
    "\n",
    "def cityblock_distance(P, Q=origin): \n",
    "    \"Manhatten distance between two points.\"\n",
    "    return sum(abs(p - q) for p, q in zip(P, Q))\n",
    "\n",
    "def distance(P, Q=origin): \n",
    "    \"Straight-line (hypotenuse) distance between two points.\"\n",
    "    return sum((p - q) ** 2 for p, q in zip(P, Q)) ** 0.5\n",
    "\n",
    "def king_distance(P, Q=origin):\n",
    "    \"Number of chess King moves between two points.\"\n",
    "    return max(abs(p - q) for p, q in zip(P, Q))\n",
    "\n",
    "################ Debugging \n",
    "\n",
    "def trace1(f):\n",
    "    \"Print a trace of the input and output of a function on one line.\"\n",
    "    def traced_f(*args):\n",
    "        result = f(*args)\n",
    "        print('{}({}) = {}'.format(f.__name__, ', '.join(map(str, args)), result))\n",
    "        return result\n",
    "    return traced_f\n",
    "\n",
    "def grep(pattern, iterable):\n",
    "    \"Print lines from iterable that match pattern.\"\n",
    "    for line in iterable:\n",
    "        if re.search(pattern, line):\n",
    "            print(line)\n",
    "            \n",
    "class Struct:\n",
    "    \"A structure that can have any fields defined.\"\n",
    "    def __init__(self, **entries): self.__dict__.update(entries)\n",
    "    def __repr__(self): \n",
    "        fields = ['{}={}'.format(f, self.__dict__[f]) \n",
    "                  for f in sorted(self.__dict__)]\n",
    "        return 'Struct({})'.format(', '.join(fields))\n",
    "\n",
    "################ A* and Breadth-First Search (tracking states, not actions)\n",
    "\n",
    "def always(value): return (lambda *args: value)\n",
    "\n",
    "def Astar(start, moves_func, h_func, cost_func=always(1)):\n",
    "    \"Find a shortest sequence of states from start to a goal state (where h_func(s) == 0).\"\n",
    "    frontier  = [(h_func(start), start)] # A priority queue, ordered by path length, f = g + h\n",
    "    previous  = {start: None}  # start state has no previous state; other states will\n",
    "    path_cost = {start: 0}     # The cost of the best path to a state.\n",
    "    Path      = lambda s: ([] if (s is None) else Path(previous[s]) + [s])\n",
    "    while frontier:\n",
    "        (f, s) = heappop(frontier)\n",
    "        if h_func(s) == 0:\n",
    "            return Path(s)\n",
    "        for s2 in moves_func(s):\n",
    "            g = path_cost[s] + cost_func(s, s2)\n",
    "            if s2 not in path_cost or g < path_cost[s2]:\n",
    "                heappush(frontier, (g + h_func(s2), s2))\n",
    "                path_cost[s2] = g\n",
    "                previous[s2] = s\n",
    "\n",
    "def bfs(start, moves_func, goals):\n",
    "    \"Breadth-first search\"\n",
    "    goal_func = (goals if callable(goals) else lambda s: s in goals)\n",
    "    return Astar(start, moves_func, lambda s: (0 if goal_func(s) else 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'pass'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def tests():\n",
    "    \"Tests for my utility functions.\"\n",
    "    \n",
    "    # Functions for Input, Parsing\n",
    "    assert Array('''1 2 3\n",
    "                    4 5 6''') == ((1, 2, 3), \n",
    "                                  (4, 5, 6))\n",
    "    assert Vector('testing 1 2 3.') == ('testing', 1, 2, 3.0)\n",
    "    assert Integers('test1 (2, -3), #4') == (2, -3, 4)\n",
    "    assert Atom('123.4') == 123.4 and Atom('x') == 'x'\n",
    "    \n",
    "    # Functions on Iterables\n",
    "    assert first('abc') == first(['a', 'b', 'c']) == 'a'\n",
    "    assert first_true([0, None, False, {}, 42, 43]) == 42\n",
    "    assert nth('abc', 1) == nth(iter('abc'), 1) == 'b'\n",
    "    assert cat(upto('abcdef', 'd')) == 'abcd'\n",
    "    assert cat(['do', 'g']) == 'dog'\n",
    "    assert groupby([-3, -2, -1, 1, 2], abs) == {1: [-1, 1], 2: [-2, 2], 3: [-3]}\n",
    "    assert list(grouper(range(8), 3)) == [(0, 1, 2), (3, 4, 5), (6, 7, None)]\n",
    "    assert list(overlapping((0, 1, 2, 3, 4), 3)) == [(0, 1, 2), (1, 2, 3), (2, 3, 4)]\n",
    "    assert list(overlapping('abcdefg', 4)) == ['abcd', 'bcde', 'cdef', 'defg']  \n",
    "    assert list(pairwise((0, 1, 2, 3, 4))) == [(0, 1), (1, 2), (2, 3), (3, 4)]\n",
    "    assert sequence('seq') == 'seq'\n",
    "    assert sequence((i**2 for i in range(5))) == (0, 1, 4, 9, 16)\n",
    "    assert join(range(5)) == '01234'\n",
    "    assert join(range(5), ', ') == '0, 1, 2, 3, 4'\n",
    "    assert transpose(((1, 2, 3), (4, 5, 6))) == ((1, 4), (2, 5), (3, 6))\n",
    "    assert isqrt(9) == 3 == isqrt(10)\n",
    "    assert ints(1, 100) == range(1, 101)\n",
    "    assert identity('anything') == 'anything'\n",
    "    assert set(powerset({1, 2, 3})) == {\n",
    "        (), (1,), (1, 2), (1, 2, 3), (1, 3), (2,), (2, 3), (3,)}\n",
    "    assert quantify(['testing', 1, 2, 3, int, len], callable) == 2 # int and len are callable\n",
    "    assert quantify([0, False, None, '', [], (), {}, 42]) == 1  # Only 42 is truish\n",
    "    assert set(shuffled('abc')) == set('abc')\n",
    "    \n",
    "    # Functional programming\n",
    "    assert mapt(math.sqrt, [1, 9, 4]) == (1, 3, 2)\n",
    "    assert map2d(abs, ((1, -2, -3), (-4, -5, 6))) == ((1, 2, 3), (4, 5, 6))\n",
    "    assert repeat(3, isqrt, 256) == 2\n",
    "    assert compose(isqrt, abs)(-9) == 3\n",
    "            \n",
    "    # Making immutable objects\n",
    "\n",
    "    assert Set([1, 2, 3, 3]) == {1, 2, 3}\n",
    "    assert canon('abecedarian') == 'aaabcdeeinr'\n",
    "    assert canon([9, 1, 4]) == canon({1, 4, 9}) == (1, 4, 9)\n",
    "    \n",
    "    # Math\n",
    "    assert transpose([(1, 2, 3), (4, 5, 6)]) == ((1, 4), (2, 5), (3, 6))\n",
    "    assert isqrt(10) == isqrt(9) == 3\n",
    "    assert ints(1, 5) == range(1, 6)\n",
    "    assert list(floats(1, 5)) == [1., 2., 3., 4., 5.]\n",
    "    assert multiply(ints(1, 10)) == math.factorial(10) == 3628800\n",
    "    \n",
    "    # 2-D points\n",
    "    P = (3, 4)\n",
    "    assert X(P) == 3 and Y(P) == 4\n",
    "    assert cityblock_distance(P) == cityblock_distance(P, origin) == 7\n",
    "    assert distance(P) == distance(P, origin) == 5\n",
    "    assert turn_right(UP) == turn_left(DOWN) == turn_around(LEFT) == RIGHT\n",
    "    \n",
    "    # Search\n",
    "    assert Astar((4, 4), neighbors8, distance) == [(4, 4), (3, 3), (2, 2), (1, 1), (0, 0)]\n",
    "    assert bfs((4, 4), neighbors8, {origin}) == [(4, 4), (3, 3), (2, 2), (1, 1), (0, 0)]\n",
    "    forty2 = always(42)\n",
    "    assert forty2() == forty2('?') == forty2(4, 2) == 42\n",
    "\n",
    "    return 'pass'\n",
    "\n",
    "tests()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 1](https://adventofcode.com/2017/day/1): Inverse Captcha\n",
    "\n",
    "This was easier than I remember last year's puzzles being:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2014, (3, 2, 9, 4, 1, 9, 9, 4, 7, 1))"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digits = mapt(int, Inputstr(1))\n",
    "N = len(digits)\n",
    "\n",
    "N, digits[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1158"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(digits[i] \n",
    "    for i in range(N) \n",
    "    if digits[i] == digits[i - 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1132"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(digits[i] \n",
    "    for i in range(N) \n",
    "    if digits[i] == digits[i - N // 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 2](https://adventofcode.com/2017/day/2): Corruption Checksum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "rows2 = Array('''790\t99\t345\t1080\t32\t143\t1085\t984\t553\t98\t123\t97\t197\t886\t125\t947\n",
    "302\t463\t59\t58\t55\t87\t508\t54\t472\t63\t469\t419\t424\t331\t337\t72\n",
    "899\t962\t77\t1127\t62\t530\t78\t880\t129\t1014\t93\t148\t239\t288\t357\t424\n",
    "2417\t2755\t254\t3886\t5336\t3655\t5798\t3273\t5016\t178\t270\t6511\t223\t5391\t1342\t2377\n",
    "68\t3002\t3307\t166\t275\t1989\t1611\t364\t157\t144\t3771\t1267\t3188\t3149\t156\t3454\n",
    "1088\t1261\t21\t1063\t1173\t278\t1164\t207\t237\t1230\t1185\t431\t232\t660\t195\t1246\n",
    "49\t1100\t136\t1491\t647\t1486\t112\t1278\t53\t1564\t1147\t1068\t809\t1638\t138\t117\n",
    "158\t3216\t1972\t2646\t3181\t785\t2937\t365\t611\t1977\t1199\t2972\t201\t2432\t186\t160\n",
    "244\t86\t61\t38\t58\t71\t243\t52\t245\t264\t209\t265\t308\t80\t126\t129\n",
    "1317\t792\t74\t111\t1721\t252\t1082\t1881\t1349\t94\t891\t1458\t331\t1691\t89\t1724\n",
    "3798\t202\t3140\t3468\t1486\t2073\t3872\t3190\t3481\t3760\t2876\t182\t2772\t226\t3753\t188\n",
    "2272\t6876\t6759\t218\t272\t4095\t4712\t6244\t4889\t2037\t234\t223\t6858\t3499\t2358\t439\n",
    "792\t230\t886\t824\t762\t895\t99\t799\t94\t110\t747\t635\t91\t406\t89\t157\n",
    "2074\t237\t1668\t1961\t170\t2292\t2079\t1371\t1909\t221\t2039\t1022\t193\t2195\t1395\t2123\n",
    "8447\t203\t1806\t6777\t278\t2850\t1232\t6369\t398\t235\t212\t992\t7520\t7304\t7852\t520\n",
    "3928\t107\t3406\t123\t2111\t2749\t223\t125\t134\t146\t3875\t1357\t508\t1534\t4002\t4417''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "46402"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(abs(max(row) - min(row)) for row in rows2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "265"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def evendiv(row): \n",
    "    return first(a // b for a in row for b in row if a > b and a // b == a / b)\n",
    "\n",
    "sum(map(evendiv, rows2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This day was also very easy. It was nice that my pre-defined `array` function did the whole job of parsing the input. In Part One, I was slowed down by a typo: I had `\"=\"` instead of `\"-\"` in `\"max(row) - min(row)\"`. I was confused by Python's misleading error message, which said `\"SyntaxError: keyword can't be an expression\"`. Later on, Alex Martelli explained to me that the message meant that in `abs(max(row)=...)` it thought that `max(row)` was a keyword argument to `abs`, as in `abs(x=-1)`.\n",
    "\n",
    "In Part Two, note that to check that `a/b` is an exact integer, I used `a // b == a / b`, which I think is more clear  than the marginally-faster expression one would typically use here, `a % b == 0`, which requires you to think about two things: division and the modulus operator (is it `a % b` or `b % a`?)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 3](https://adventofcode.com/2017/day/3): Spiral Memory\n",
    "\n",
    "For today the data is just one number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "M = 277678"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This puzzle takes some thinking, not just fast typing. I decided to break the problem into three parts:\n",
    "- Generate a spiral (by writing a new function called `spiral`).\n",
    "- Find the Nth square on the spiral (with my function `nth`).\n",
    "- Find the distance from that square to the center (with my function `cityblock_distance`).\n",
    "\n",
    "I suspect many people will do all three of these in one function. That's probably the best way to get the answer really quickly, but I'd rather be clear than quick (and I'm anticipating that `spiral` will come in handy in Part Two), so I'll factor out each part, obeying the *single responsibility principle*. \n",
    "\n",
    "Now I need to make `spiral()` generate the coordinates of squares on an infinite spiral, in order, going out from the center square, `(0, 0)`. After the center square, the spiral goes 1 square right, then 1 square up, then 2 square left, then 2 square down, thus completing one revolution; then it does subsequent revolutions. In general if the previous revolution ended with *s* squares down, then the next revolution consists of *s*+1 squares right, *s*+1 squares up, *s*+2 squares left and *s*+2 down.  A small test confirms that this matches the example diagram in the puzzle description (although I had a bug on my first try because I only incremented `s` once per revolution, not twice):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 0),\n",
       " (0, -1),\n",
       " (-1, -1),\n",
       " (-1, 0),\n",
       " (-1, 1),\n",
       " (0, 1),\n",
       " (1, 1),\n",
       " (1, 0),\n",
       " (1, -1),\n",
       " (1, -2)]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def spiral():\n",
    "    \"Yield successive (x, y) coordinates of squares on a spiral.\"\n",
    "    x = y = s = 0   # (x, y) is the position; s is the side length.\n",
    "    yield (x, y)\n",
    "    while True:\n",
    "        for (dx, dy) in (RIGHT, UP, LEFT, DOWN):\n",
    "            if dy: s += 1 # Increment side length before RIGHT and LEFT\n",
    "            for _ in range(s):\n",
    "                x += dx; y += dy\n",
    "                yield (x, y)\n",
    "\n",
    "list(islice(spiral(), 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can find the `N`th square. As this is Python, indexes start at 0, whereas the puzzle description starts counting at 1, so I have to subtract 1. Then I can find the distance to the origin:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(263, -212)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nth(spiral(), M - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "475"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cityblock_distance(_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "I can re-use my `spiral` generator, yay! Here's a function to sum the neighboring squares (I can use my `neighbors8` function, yay!):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def spiralsums():\n",
    "    \"Yield the values of a spiral where each square has the sum of the 8 neighbors.\"\n",
    "    value = defaultdict(int)\n",
    "    for p in spiral():\n",
    "        value[p] = sum(value[q] for q in neighbors8(p)) or 1\n",
    "        yield value[p]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 4, 5, 10, 11, 23, 25, 26, 54, 57]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(islice(spiralsums(), 12))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looks good, so let's get the answer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "279138"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "first(x for x in spiralsums() if x > M)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 4](https://adventofcode.com/2017/day/4): High-Entropy Passphrases\n",
    "\n",
    "This is the first time I will have to store an input file and read it with the function `Input`. It should be straightforward, though:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "337"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def is_valid(line): return is_unique(line.split())\n",
    "\n",
    "def is_unique(items): return len(items) == len(set(items))\n",
    "\n",
    "quantify(Input(4), is_valid)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "231"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def is_valid2(line): return is_unique(mapt(canon, line.split()))\n",
    "\n",
    "quantify(Input(4), is_valid2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was easy, and I started on time, but the leaders were still three times faster than me!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 5](https://adventofcode.com/2017/day/5): A Maze of Twisty Trampolines, All Alike\n",
    "\n",
    "Let's first make sure we can read the data/program okay:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 2, 0, 0, -2, -2, -1, -4, -5, -6)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "program = mapt(int, Input(5))\n",
    "\n",
    "program[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I'll make a little interpreter, `run`, which takes a program, loads it into memory,\n",
    " and executes the instruction, maintaining a program counter, `pc`, and doing the incrementing/branching as described in the puzzle,\n",
    "until the program counter no longer points to a location in memory:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "364539"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def run(program):\n",
    "    memory = list(program)\n",
    "    pc = steps = 0\n",
    "    M = len(memory)\n",
    "    while 0 <= pc < M:\n",
    "        steps += 1\n",
    "        oldpc = pc\n",
    "        pc += memory[pc]\n",
    "        memory[oldpc] += 1\n",
    "    return steps\n",
    "        \n",
    "run(program)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "Part Two seems tricky, so I'll include an optional argument, `verbose`, and check if the printout it produces matches the example in the puzzle description:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 0 [1, 3, 0, 1, -3]\n",
      "2 1 [2, 3, 0, 1, -3]\n",
      "3 4 [2, 2, 0, 1, -3]\n",
      "4 1 [2, 2, 0, 1, -2]\n",
      "5 3 [2, 3, 0, 1, -2]\n",
      "6 4 [2, 3, 0, 2, -2]\n",
      "7 2 [2, 3, 0, 2, -1]\n",
      "8 2 [2, 3, 1, 2, -1]\n",
      "9 3 [2, 3, 2, 2, -1]\n",
      "10 5 [2, 3, 2, 3, -1]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@jit\n",
    "def run2(program, verbose=False):\n",
    "    memory = list(program)\n",
    "    pc = steps = 0\n",
    "    M = len(memory)\n",
    "    while 0 <= pc < M:\n",
    "        steps += 1\n",
    "        oldpc = pc\n",
    "        pc += memory[pc]\n",
    "        memory[oldpc] += (-1 if memory[oldpc] >= 3 else 1)\n",
    "        if verbose: print(steps, pc, memory)\n",
    "    return steps\n",
    "        \n",
    "run2([0, 3, 0, 1, -3], True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That looks right, so I can solve the puzzle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "27477714"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "run2(program)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thanks to [Clement Sreeves](https://github.com/ClementSreeves) for the suggestion of making a distinction between the `program` and the `memory`. In my first version, `run` would mutate the argument, which was OK for a short exercise, but not best practice for a reliable API. And thanks to [Max Albert](https://github.com/maxalbert) for speeding up the loop by pulling the `len(memory)` out of the loop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 6](https://adventofcode.com/2017/day/6): Memory Reallocation "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had to read the puzzle description carefully, but then it is pretty clear what to do. I'll keep a set of previously seen configurations, which will all be tuples. But in the function `spread`, I want to mutate the configuration of banks, so I will convert to a list at the start, then convert back to a tuple at the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "banks = Vector('4\t10\t4\t1\t8\t4\t9\t14\t5\t1\t14\t15\t0\t15\t3\t5')\n",
    "\n",
    "def realloc(banks):\n",
    "    \"How many cycles until we reach a configuration we've seen before?\"\n",
    "    seen = {banks}\n",
    "    for cycles in count_from(1):\n",
    "        banks = spread(banks)\n",
    "        if banks in seen:\n",
    "            return cycles\n",
    "        seen.add(banks)\n",
    "        \n",
    "def spread(banks):\n",
    "    \"Find the area with the most blocks, and spread them evenly to following areas.\"\n",
    "    banks  = list(banks)\n",
    "    maxi   = max(range(len(banks)), key=lambda i: banks[i])\n",
    "    blocks = banks[maxi]\n",
    "    banks[maxi] = 0\n",
    "    for i in range(maxi + 1, maxi + 1 + blocks):\n",
    "        banks[i % len(banks)] += 1\n",
    "    return tuple(banks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 4, 1, 2)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spread((0, 2, 7, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "realloc((0, 2, 7, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These tests look good; let's solve the problem:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12841"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "realloc(banks)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "Here I will just replace the `set` of `seen` banks with a `dict` of `{bank: cycle_number}`; everything else is the same, and the final result is the current cycle number minus the cycle number of the previously-seen tuple of banks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def realloc2(banks):\n",
    "    \"When we hit a cycle, what is the length of the cycle?\"\n",
    "    seen = {banks: 0}\n",
    "    for cycles in count_from(1):\n",
    "        banks = spread(banks)\n",
    "        if banks in seen:\n",
    "            return cycles - seen[banks]\n",
    "        seen[banks] = cycles\n",
    "\n",
    "realloc2((0, 2, 7, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8038"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "realloc2(banks)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 7](https://adventofcode.com/2017/day/7): Recursive Circus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First I'll read the data into two dicts as follows: the input line\n",
    "\n",
    "     tcmdaji (40) -> wjbdxln, amtqhf\n",
    "     \n",
    "creates the two entries:\n",
    "\n",
    "     weight['tcmdaji'] = 40\n",
    "     above['tcmdaji'] = ['wjbdxln', 'amtqhf']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def towers(lines):\n",
    "    \"Return (weight, above) dicts.\"\n",
    "    weight = {}\n",
    "    above = {}\n",
    "    for line in lines:\n",
    "        name, w, *rest = re.findall(r'\\w+', line)\n",
    "        weight[name] = int(w)\n",
    "        above[name] = set(rest)\n",
    "    return weight, above\n",
    "\n",
    "weight, above = towers(Input(7))\n",
    "\n",
    "programs = set(above)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the root progam is the one that is not above anything:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'wiapj'}"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "programs - set(flatten(above.values()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "A program is *wrong* if it is the bottom of a tower that is a different weight from all its sibling towers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def wrong(p): return tower_weight(p) not in map(tower_weight, siblings(p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we define `tower_weight`, `siblings`, and the `below` dict:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def tower_weight(p): \n",
    "    \"Total weight for the tower whose root (bottom) is p.\"\n",
    "    return weight[p] + sum(map(tower_weight, above[p]))\n",
    "\n",
    "def siblings(p): \n",
    "    \"The other programs at the same level as this one.\"\n",
    "    if p not in below:\n",
    "        return Ø # the root has no siblings\n",
    "    else:\n",
    "        return above[below[p]] - {p}\n",
    "\n",
    "below = {a: b for b in programs for a in above[b]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'eionkb', 'lsire', 'wiapj', 'ycpcv'}"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set(filter(wrong, programs))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So these four programs are wrong. Which one should we correct? The one that is wrong, and has no wrong program above it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eionkb'"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def wrongest(programs):\n",
    "    return first(p for p in programs\n",
    "                 if wrong(p) \n",
    "                 and not any(wrong(p2) for p2 in above[p]))\n",
    "\n",
    "wrongest(programs)                              "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now what should we correct it to? To the weight that makes it the same weight as the sibling towers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1072"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def correct(p):\n",
    "    \"Return the weight that would make p's tower's weight the same as its sibling towers.\"\n",
    "    delta = tower_weight(first(siblings(p))) - tower_weight(p) \n",
    "    return weight[p] + delta\n",
    "\n",
    "correct(wrongest(programs))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 8](https://adventofcode.com/2017/day/8): Memory Reallocation \n",
    "\n",
    "This one looks easy: a simple interpreter for straight-line code where each instruction has 7 tokens. It is nice that my `Array` function parses the whole program."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6828"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "program8 = Array(Input(8))\n",
    "\n",
    "def run8(program):\n",
    "    \"Run the program and return final value of registers.\"\n",
    "    registers = defaultdict(int)\n",
    "    for (r, inc, delta, _if, r2, cmp, amount) in program:\n",
    "        if operations[cmp](registers[r2], amount):\n",
    "            registers[r] += delta * (+1 if inc == 'inc' else -1)\n",
    "    return registers\n",
    "\n",
    "max(run8(program8).values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "Here I modify the interpreter to keep track of the highest value of any register at any time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7234"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def run8_2(program):\n",
    "    registers = defaultdict(int)\n",
    "    highest = 0\n",
    "    for (r, inc, delta, _if, r2, cmp, amount) in program:\n",
    "        if operations[cmp](registers[r2], amount):\n",
    "            registers[r] += delta * (+1 if inc == 'inc' else -1)\n",
    "            highest = max(highest, registers[r])\n",
    "    return highest\n",
    "\n",
    "run8_2(program8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 9](https://adventofcode.com/2017/day/9): Stream Processing\n",
    "\n",
    "For this problem I could have defined a single parser that handles all five magic characters, `'{<!>}'`, but I think it is easier to first clean up the garbage, using regular expressions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'{{{{{{{},},{{},}},{{{{}},{{{{{}}},{}},},{{{{},{,{{{}}}}},},{{{}},{{}}}'"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text1 = re.sub(r'!.', '', Inputstr(9))  # Delete canceled characters\n",
    "text2 = re.sub(r'<.*?>', '', text1)     # Delete garbage\n",
    "\n",
    "text2[:70]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I can deal with the nested braces (which can't be handled with regular expressions). The puzzle says \"*Each group is assigned a score which is one more than the score of the group that immediately contains it,*\" which is the same as saying that a group's score is its nesting level, a quantity that increases with each open-brace character, and decreases with each close-brace:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9662"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def total_score(text):\n",
    "    \"Total of group scores; each group scores one more than the group it is nested in.\"\n",
    "    total = 0\n",
    "    level = 0 # Level of nesting\n",
    "    for c in text:\n",
    "        if c == '{':\n",
    "            level += 1\n",
    "            total += level\n",
    "        elif c == '}':\n",
    "            level -= 1\n",
    "    return total\n",
    "\n",
    "total_score(text2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "At first I thought that the amount of garbage is just the difference in lengths of `text2` and `text3`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5989"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(text1) - len(text2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But this turned out to be wrong; it counts the angle brackets themselves s being deleted, whereas the puzzle is actually asking how many character between the angle brackets are deleted. So that would be:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4903"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text3 = re.sub(r'<.*?>', '<>', text1)  # Delete garbage inside brackets, but not brackets\n",
    "\n",
    "len(text1) - len(text3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 10](https://adventofcode.com/2017/day/10): Stream Processing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I have to do a bunch of reversals of substrings of `stream`. It looks complicated so I will include a `verbose` argument to `knothash` and confirm it works on the example puzzle. I break out the reversal into a separate function, `rev`. The way I handle reversal interacting with wraparound is that I first move all the items before the reversal position to the end of the list, then I do the reversal, then I move them back."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "stream = (63,144,180,149,1,255,167,84,125,65,188,0,2,254,229,24)\n",
    "\n",
    "def knothash(lengths, N=256, verbose=False):\n",
    "    \"Do a reversal for each of the numbers in `lengths`.\"\n",
    "    nums = list(range(N))\n",
    "    pos = skip = 0\n",
    "    for L in lengths:\n",
    "        nums = rev(nums, pos, L)\n",
    "        if verbose: print(nums)\n",
    "        pos = (pos + L + skip) % N\n",
    "        skip += 1\n",
    "    return nums[0] * nums[1]\n",
    "        \n",
    "def rev(nums, pos, L):\n",
    "    \"Reverse nums[pos:pos+L], handling wrap-around.\"\n",
    "    # Move first pos elements to end, reverse first L, move pos elements back\n",
    "    nums = nums[pos:] + nums[:pos]\n",
    "    nums[:L] = reversed(nums[:L])\n",
    "    nums = nums[-pos:] + nums[:-pos]\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Reverse [0, 1, 2]:\n",
    "assert rev(list(range(5)), 0, 3) == [2, 1, 0, 3, 4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Reverse [4, 0, 1], wrapping around:\n",
    "assert rev(list(range(5)), 4, 3) == [0, 4, 2, 3, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 1, 0, 3, 4]\n",
      "[4, 3, 0, 1, 2]\n",
      "[4, 3, 0, 1, 2]\n",
      "[3, 4, 2, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "# Duplicate the example output\n",
    "assert knothash((3, 4, 1, 5), N=5, verbose=True) == 12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's correct, but the first time through I got it wrong because I forgot the `\"% N\"` on the update of `pos`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4480"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knothash(stream)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "Now it gets *really* complicated: string processing, the suffix, hex string output, and dense hashing. But just take them one at a time:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'c500ffe015c83b60fad2e4b7d59dabc4'"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stream2 = '63,144,180,149,1,255,167,84,125,65,188,0,2,254,229,24'\n",
    "\n",
    "def knothash2(lengthstr, N=256, rounds=64, suffix=(17, 31, 73, 47, 23),\n",
    "              verbose=False):\n",
    "    \"Do a reversal for each length; repeat `rounds` times.\"\n",
    "    nums = list(range(N))\n",
    "    lengths = mapt(ord, lengthstr) + suffix\n",
    "    pos = skip = 0\n",
    "    for round in range(rounds):\n",
    "        for L in lengths:\n",
    "            nums = rev(nums, pos, L)\n",
    "            if verbose: print(nums)\n",
    "            pos = (pos + L + skip) % N\n",
    "            skip += 1\n",
    "    return hexstr(dense_hash(nums))\n",
    "\n",
    "def hexstr(nums): \n",
    "    \"Convert a sequence of (0 to 255) ints into a hex str.\"\n",
    "    return cat(map('{:02x}'.format, nums))\n",
    "    \n",
    "def dense_hash(nums, blocksize=16): \n",
    "    \"XOR each block of nums, return the list of them.\"\n",
    "    return [XOR(block) for block in grouper(nums, blocksize)]\n",
    "\n",
    "def XOR(nums):\n",
    "    \"Exclusive-or all the numbers together.\"\n",
    "    result = 0\n",
    "    for n in nums:\n",
    "        result ^= n\n",
    "    return result\n",
    "    \n",
    "assert XOR([65, 27, 9, 1, 4, 3, 40, 50, 91, 7, 6, 0, 2, 5, 68, 22]) == 64\n",
    "assert hexstr([255, 0, 17]) == 'ff0011'\n",
    "\n",
    "assert knothash2('') == 'a2582a3a0e66e6e86e3812dcb672a272'\n",
    "\n",
    "knothash2(stream2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had a bug: originally I used `'{:x}'` as the format instead of `'{:02x}'`; the later correctly formats `0` as `'00'`, not `'0'`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 11](https://adventofcode.com/2017/day/11): Hex Ed\n",
    "\n",
    "The first thing I did was search [`[hex coordinates]`](https://www.google.com/search?source=hp&ei=Ft4xWoOqKcy4jAOs76a4CQ&q=hex+coordinates), and the #1 result (as I expected) was Amit Patel's \"[Hexagonal Grids](https://www.redblobgames.com/grids/hexagons/)\" page. I chose his \"odd-q vertical layout\" to define the six headings as (dx, dy) deltas:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "headings6 = dict(n=(0, -1), ne=(1, 0), se=(1, 1), s=(0, 1), sw=(-1, 0), nw=(-1, -1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I can read the path, follow it, and see where it ends up. From there, we have to compute how far we are from the origin: I can use my `king_distance` function for that&mdash;the number of moves a Chess King would take."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "705"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "path = Vector(Inputstr(11))\n",
    "\n",
    "def follow(path):\n",
    "    \"Follow each step of the path; return final distance to origin.\"\n",
    "    pos = origin\n",
    "    for dir in path:\n",
    "        pos = add(pos, headings6[dir])\n",
    "    return king_distance(pos)\n",
    "\n",
    "follow(path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one seemed so easy that I didn't bother testing it on the simple examples in the puzzle; all I did was confirm that the answer for my puzzle input was correct.\n",
    "\n",
    "## Part Two\n",
    "\n",
    "This looks pretty easy; repeat Part One, but keep track of the maximum number of steps we get from the origin at any point in the path:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1469"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def follow2(path):\n",
    "    \"Follow each step of the path; return the farthest away we ever got.\"\n",
    "    pos = origin\n",
    "    maxsteps = 0\n",
    "    for dir in path:\n",
    "        pos = add(pos, headings6[dir])\n",
    "        maxsteps = max(maxsteps, king_distance(pos))\n",
    "    return maxsteps\n",
    "\n",
    "follow2(path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, no tests, just the final answer.\n",
    "\n",
    "# [Day 12](https://adventofcode.com/2017/day/12): Digital Plumber\n",
    "\n",
    "First I'll parse the data, creating a dict of `{program: direct_group_of_programs}`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def groups(lines):\n",
    "    \"Dict of {i: {directly_connected_to_i}\"\n",
    "    return {lhs: {lhs} | set(rhs)\n",
    "            for (lhs, _, *rhs) in Array(lines)}\n",
    "    \n",
    "assert groups(Input(12))[0] == {0, 659, 737}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That looks good. I recognize this as a [Union-Find](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) problem, for which there are efficient algorithms. But for this small example, I don't need efficiency, I need clarity and simplicity. So I'll write `merge` to take a dict and merge together the sets that are connected:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def merge(G):\n",
    "    \"Merge all indirectly connected groups together.\"\n",
    "    for i in G:\n",
    "        for j in list(G[i]):\n",
    "            if G[i] != G[j]:\n",
    "                G[i].update(G[j])\n",
    "                G[j] = G[i]\n",
    "    return G\n",
    "\n",
    "G = merge(groups(Input(12)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "115"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(G[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's the answer for Part One.\n",
    "\n",
    "## Part Two\n",
    "\n",
    "I did almost all the work; I just need to count the number of distinct groups. That's a set of sets, and regular `set`s are not hashable, so I use my `Set` class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "221"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len({Set(G[i]) for i in G})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 13](https://adventofcode.com/2017/day/13): Packet Scanners\n",
    "\n",
    "First thing: The puzzle says the data is *depth: range*, but `range` has a meaning in Python, so I'll use the term *width* instead.\n",
    "\n",
    "Second thing: I misread the puzzle description and mistakenly thought the scanners were going in a circular route,\n",
    "so that they'd be at the top at any time that is 0 mod *width*. That gave the wrong answer and I realized the scanners are actually going back-and-forth, so with a width of size *n*, it takes *n* - 1 steps to get to the bottom, and *n* - 1 steps to get back to the top, so the scanner will be \n",
    "at the top at times that are multiples of 2(*n* - 1). For example, with width 3, that would be times 0, 4, 8, ... "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def trip_severity(scanners): \n",
    "    \"The sum of severities for each time the packet is caught.\"\n",
    "    return sum((d * w if caught(d, w) else 0) \n",
    "               for (d, w) in scanners)\n",
    "\n",
    "def caught(depth, width):\n",
    "    \"Does the scanner at this depth/width catch the packet?\"\n",
    "    return depth % (2 * (width - 1)) == 0\n",
    "\n",
    "example = ((0, 3), (1, 2), (4, 4), (6, 4))\n",
    "assert trip_severity(example) == 24"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((0, 3), (1, 2), (2, 4), (4, 6), (6, 4))"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "scanners = mapt(Integers, Input(13))\n",
    "scanners[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1504"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trip_severity(scanners)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "A packet is safe if no scanner catches it. We now have the possibility of a delay, so I update `caught` to allow for an optional delay, and define `safe_delay`:  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def caught(depth, width, delay=0):\n",
    "    \"Does the scanner at this depth/width catch the packet with this delay?\"\n",
    "    return (depth + delay) % (2 * (width - 1)) == 0 \n",
    "\n",
    "def safe_delay(scanners):\n",
    "    \"Find the first delay such that no scanner catches the packet.\"\n",
    "    safe = lambda delay: not any(caught(d, w, delay) for (d, w) in scanners)\n",
    "    return first(filter(safe, count_from(0)))\n",
    "\n",
    "safe_delay(example)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3823370"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "safe_delay(scanners)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 14](https://adventofcode.com/2017/day/14): Disk Defragmentation\n",
    "\n",
    "I found this puzzle description confusing: are they talking about what I call `knothash`, or is it `knothash2`? I decided for the latter, which turned out to be right:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "key = 'ljoxqyyw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8316"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bits(key, i):\n",
    "    \"The bits in the hash of this key with this row number.\"\n",
    "    hash = knothash2(key + '-' + str(i))\n",
    "    return format(int(hash, base=16), '0128b')\n",
    "\n",
    "sum(bits(key, i).count('1') for i in range(128))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "So as not to worry about running off the edge of the grid, I'll surround the grid with `'0'` bits:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Grid(key, N=128+2):\n",
    "    \"Make a grid, with a border around it.\"\n",
    "    return border('0', (list(bits(key, i)) for i in range(128)))\n",
    "\n",
    "def border(fill, grid):\n",
    "    \"Surround a grid with a border of fill cells.\"\n",
    "    rows  = [[fill] + list(row) + [fill] \n",
    "             for row in grid]\n",
    "    empty =  [fill] * len(rows[0])\n",
    "    return [empty] + rows + [empty]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To find a region, start at some `(x, y)` position and [flood fill](https://en.wikipedia.org/wiki/Flood_fill) to neighbors that have the same value (a `'1'` bit)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def flood(grid, x, y, val, R):\n",
    "    \"For all cells with value val connected to grid[x][y], give them region number R.\"\n",
    "    if grid[y][x] == val:\n",
    "        grid[y][x] = R\n",
    "        for x2, y2 in neighbors4((x, y)):\n",
    "            flood(grid, x2, y2, val, R)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def flood_all(grid, val='1'):\n",
    "    \"Label all regions with consecutive ints starting at 1.\"\n",
    "    R = 0 # R is the region number\n",
    "    for y in range(1, len(grid) - 1):\n",
    "        for x in range(1, len(grid) - 1):\n",
    "            if grid[y][x] == val:\n",
    "                R += 1\n",
    "                flood(grid, x, y, val, R)\n",
    "    return R "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1074"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "flood_all(Grid(key))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 15](https://adventofcode.com/2017/day/15): Dueling Generators\n",
    "\n",
    "My personalized inputs for this puzzle are `516` and `190`; the other numbers are shared by all puzzle-solvers. I decided to make infinite generators of numbers, using `gen`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 15 s, sys: 30.7 ms, total: 15 s\n",
      "Wall time: 15.1 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "597"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@jit\n",
    "def gen(prev, factor, m=2147483647):\n",
    "    \"Generate a sequence of numbers according to the rules; stop at 0.\"\n",
    "    while prev:\n",
    "        prev = (prev * factor) % m\n",
    "        yield prev\n",
    "        \n",
    "def judge(A, B, N, mask=2**16-1): \n",
    "    \"How many of the first N numbers from A and B agree in the masked bits (default last 16)?\"\n",
    "    return quantify(a & mask == b & mask\n",
    "                    for (a, b, _) in zip(A, B, range(N)))\n",
    "\n",
    "\n",
    "def A(): return gen(516, 16807)\n",
    "def B(): return gen(190, 48271)\n",
    "\n",
    "%time judge(A(), B(), 40*10**6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice I also decided to use `@jit` (i.e. `numba.jit`) to speed things up, since this is the slowest-running day yet.\n",
    "\n",
    "## Part Two\n",
    "\n",
    "A small change: only consider numbers that match the **criteria** of being divisible by 4 or 8, respectively;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 9.71 s, sys: 7.49 ms, total: 9.72 s\n",
      "Wall time: 9.72 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "303"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def criteria(m, iterable): \n",
    "    \"Elements of iterable that are divisible by m\"\n",
    "    return (n for n in iterable if n % m == 0)\n",
    "        \n",
    "%time judge(criteria(4, A()), criteria(8, B()), 5*10**6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When I got this solution on Day 15, I was happy to end there. But looking back, after Day 25, I noticed this day's run time was the slowest of all, so I wondered if I could speed things up, using `@jit`. Unfortunately, `@jit` doesn't work with generators, so I'll have to rewrite the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 645 ms, sys: 2.26 ms, total: 648 ms\n",
      "Wall time: 646 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "597"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@jit\n",
    "def duelgen(prev1=516, factor1=16807, prev2=190, factor2=48271, \n",
    "            m=2147483647, mask=2**16-1, N=40*10**6):\n",
    "    matches = 0\n",
    "    for _ in range(N):\n",
    "        prev1 = (prev1 * factor1) % m\n",
    "        prev2 = (prev2 * factor2) % m\n",
    "        matches += (prev1 & mask == prev2 & mask)\n",
    "    return matches\n",
    "\n",
    "%time duelgen()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was an excellent speedup (and the same answer); I'll leave optimizing Part Two as an exercise for the reader."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 16](https://adventofcode.com/2017/day/16): Permutation Promenade\n",
    "\n",
    "Let's read the input and check that it looks reasonable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('x5/15',\n",
       " 's15',\n",
       " 'x1/3',\n",
       " 'pn/f',\n",
       " 'x11/2',\n",
       " 's13',\n",
       " 'x6/3',\n",
       " 'pe/a',\n",
       " 'x14/12',\n",
       " 's15')"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dance = Vector(Inputstr(16))\n",
    "dance[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10000"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(dance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll define `perform` to perform the dance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'lbdiomkhgcjanefp'"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dancers = 'abcdefghijklmnop'\n",
    "\n",
    "def perform(dance, dancers=dancers):\n",
    "    D = deque(dancers)\n",
    "    def swap(i, j): D[i], D[j] = D[j], D[i]\n",
    "    for move in dance:\n",
    "        op, arg = move[0], move[1:]\n",
    "        if   op == 's': D.rotate(int(arg))\n",
    "        elif op == 'x': swap(*Integers(arg))\n",
    "        elif op == 'p': swap(D.index(arg[0]), D.index(arg[2]))\n",
    "    return cat(D)\n",
    "            \n",
    "perform(dance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's the right answer.\n",
    "\n",
    "## Part Two\n",
    "\n",
    "My first thought was to define a dance as a permutation: a list of numbers `[11, 1, 9, ...]` which says that the net effect of the dance is that the first dancer (`a`) ends up in position, the second (`b`) stays in position 1, and so on. Applying that permutation once is a lot faster than interpreting all 10,000 moves of the dance, and it is feasible to apply the permutation a billion times. I tried that (code not shown here), but that was a mistake: it took 15 minutes to run, and it got the wrong answer. The problem is that a dance is *not* just a permutation, because a dance can reference dancer *names*, not just positions.\n",
    "\n",
    "It would take about 10,000 times 20 minutes to perform a billion repetitions of the dance, so that's out. But even though the dance is not a permutation, it might repeat after a short period. Let's check:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abcdefghijklmnop is seen in iterations (0, 56)\n"
     ]
    }
   ],
   "source": [
    "seen = {dancers: 0}\n",
    "d = dancers\n",
    "for i in range(1, 1000):\n",
    "    d = perform(dance, d)\n",
    "    if d in seen:\n",
    "        print(d, 'is seen in iterations', (seen[d], i))\n",
    "        break\n",
    "    seen[d] = i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we get back to the start position after 56 repetitions of the dance. What happens after a billion repetitions?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "48"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1000000000 % 56"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The end position after a billion repetitions is the same as after 48:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ejkflpgnamhdcboi'"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def whole(N, dance, dancers=dancers):\n",
    "    \"Repeat `perform(dance)` N times.\"\n",
    "    for i in range(N):\n",
    "        dancers = perform(dance, dancers)\n",
    "    return dancers\n",
    "    \n",
    "whole(48, dance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# [Day 17](https://adventofcode.com/2017/day/17): Spinlock\n",
    "\n",
    "This one looks pretty easy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "355"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "step = 314\n",
    "\n",
    "def spinlock(step=step, N=2017):\n",
    "    \"Make N inserts into the buffer, skipping ahead by `step` each time.\"\n",
    "    buf = [0]\n",
    "    pos = 0\n",
    "    for i in ints(1, N):\n",
    "        pos = (pos + step) % i + 1\n",
    "        buf[pos:pos] = [i]\n",
    "    return buf\n",
    "        \n",
    "buf = spinlock()\n",
    "\n",
    "buf[buf.index(2017)+1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's the right answer.\n",
    "\n",
    "## Part Two\n",
    "\n",
    "But Part Two is not so easy, if we care about the run time. Insertion into a `list` has to move all the elements after the insertion down, so insertion is O(N) and `spinlock` is O(N<sup>2</sup>). That's no problem when N = 2017, but when N is 50 million?  We're gonna need a bigger boat, where by \"boat\" I mean algorithm or data structure. My first thought is a (circular) linked list, because insertion is O(1). I can implement the three key methods: `skip` to move ahead, `insert` to add a new node after the current one, and `find` to find a piece of data (with a linear search):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    \"A Node in a singly-linked list\"\n",
    "    \n",
    "    __slots__ = ('data', 'next') # Declaring slots makes it more efficient\n",
    "    \n",
    "    def __init__(self, data, next): self.data, self.next = data, next\n",
    "                \n",
    "    def skip(self, n):\n",
    "        \"Skip ahead n nodes, and return that node.\"\n",
    "        node = self\n",
    "        for i in range(n):\n",
    "            node = node.next\n",
    "        return node\n",
    "        \n",
    "    def insert(self, value):\n",
    "        \"Insert a new node with the given value after this node.\"\n",
    "        self.next = Node(value, self.next)\n",
    "        return self.next\n",
    "    \n",
    "    def find(self, value):\n",
    "        \"Find the node with the given data value.\"\n",
    "        node = self\n",
    "        while node.data != value:\n",
    "            node = node.next\n",
    "        return node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I can rewrite `spinlock` to use this class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def spinlock2(step=step, N=2017):\n",
    "    node = Node(0, None)\n",
    "    node.next = node # Make node be a circular linked list\n",
    "    for i in ints(1, N):\n",
    "        node = node.skip(step).insert(i)\n",
    "    return node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's replicate the Part One results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "355"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spinlock2().find(2017).next.data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Good news! We get the same answer. But how fast/slow is it?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.33 s, sys: 4.04 ms, total: 1.33 s\n",
      "Wall time: 1.33 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x10daae390>"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time spinlock2(N=100000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bad news! More than a second for just 100,000 insertions, which projects to over 10 minutes for 50 million insertions. I did in fact try\n",
    "\n",
    "     spinlock2(N=50000000).find(0).next.data\n",
    "     \n",
    "and it eventually gave the right answer, but while it was running I had plenty of time to think.\n",
    "I realized that, if we go back to the original `spinlock` version, the value `0` will always be in `buf[0]`, and the value we are looking for will always be in `buf[1]`. So I can create a version of `spinlock` that only keeps track of `buf[0:2]`. That should run in a few seconds, not minutes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 5.53 s, sys: 4.42 ms, total: 5.53 s\n",
      "Wall time: 5.53 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6154117"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def spinlock3(step=step, N=2017):\n",
    "    \"Make N inserts into a simulated buffer, but ignore all except buf[0:2].\"\n",
    "    pos = 0\n",
    "    buf = [0, 0]\n",
    "    for i in ints(1, N):\n",
    "        pos = (pos + step) % i + 1\n",
    "        if pos <= 1:\n",
    "            buf[pos] = i\n",
    "    return buf\n",
    "\n",
    "%time spinlock3(N=50000000)[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The moral of the story is *keep your eyes on the prize*. I got distracted because I asked the wrong question. I asked myself \"how can I make my solution in `spinlock` faster?\" and answered myself \"insertion is O(N<sup>2</sup>) and it should be O(N).\" I knew how to do that, with a linked list, but that was the right answer to the wrong question. I should have asked myself \"how do I solve Part Two quickly,\" concentrating on solving the actual problem. Once I did that, I realized I didn't need all those insertions: not doing them at all is a better idea than doing them faster."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 18](https://adventofcode.com/2017/day/17): Duet\n",
    "\n",
    "First, read the input, and take a peak at it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(('set', 'i', 31),\n",
       " ('set', 'a', 1),\n",
       " ('mul', 'p', 17),\n",
       " ('jgz', 'p', 'p'),\n",
       " ('mul', 'a', 2),\n",
       " ('add', 'i', -1),\n",
       " ('jgz', 'i', -2),\n",
       " ('add', 'a', -1),\n",
       " ('set', 'i', 127),\n",
       " ('set', 'p', 826))"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "program18 = Array(Input(18))\n",
    "program18[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now write an interpreter for the assembly language:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7071"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def run18(program):\n",
    "    \"Interpret the assembly language program; return recovered `snd`.\"\n",
    "    regs = defaultdict(int)\n",
    "    pc = snd = 0\n",
    "    while True:\n",
    "        instr = program[pc]\n",
    "        pc += 1\n",
    "        op, x, y = instr[0], instr[1], instr[-1]\n",
    "        vy = value(regs, y)\n",
    "        if   op == 'snd': snd = regs[x]\n",
    "        elif op == 'set': regs[x] = vy\n",
    "        elif op == 'add': regs[x] += vy\n",
    "        elif op == 'mul': regs[x] *= vy\n",
    "        elif op == 'mod': regs[x] %=  vy\n",
    "        elif op == 'jgz' and regs[x] > 0: pc += vy - 1\n",
    "        elif op == 'rcv' and regs[x] != 0: return snd\n",
    "        \n",
    "def value(regs, y): return (y if isinstance(y, int) else regs[y])\n",
    "\n",
    "run18(program18)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was easy. (One tricky bit: the `pc` is incremented by 1 every time through the loop, regardless of the instruction. Therefore, the `'jgz'` jump instruction increments by \"`vy - 1`\" so that the net increment is \"`vy`\".)\n",
    "\n",
    "## Part Two\n",
    "\n",
    "In Part Two we have to run two copies of the program, and send messages between them.  I'll break up the loop in `run18` into\n",
    "two functions. First, `run18_2`, creates (in `ps`) two structures to hold the state variables necessary to run a program:\n",
    "- `id`: The id number (0 or 1) of this copy of the program.\n",
    "- `pc`: The program counter.\n",
    "- `sends`: A count of the number of `snd` instructions executed.\n",
    "- `regs`: A dict of the program registers (`a` to `z`).\n",
    "- `status`: A program has a status which can be:\n",
    "  * `'run'` when it is ready to execute an instruction, \n",
    "  * `'wait'` when it is waiting for a value to arrive in its input queue, or \n",
    "  * `'end'` when the `pc` has run off the end of the program and it has terminated.\n",
    "\n",
    "`run18_2`  repeatedly calls the second function, `step18(program, p)` to execute one instruction of `program` with the state variables in `p`. I choose randomly which of the two programs to step on each iteration.  The function exits when neither copy of the program can run, according to their status. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def run18_2(program):\n",
    "    \"Run two copies of program, with different state variables. Return final states.\"\n",
    "    Qs = [deque(), deque()]\n",
    "    ps = [Struct(id=id, pc=0, sends=0, regs=defaultdict(int, p=id), status='run')\n",
    "          for id in (0, 1)]\n",
    "    while any(p.status == 'run' for p in ps):\n",
    "        step18(program, Qs, random.choice(ps))\n",
    "    return ps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`step18` has most of the guts of thee previous `run18` function, but with a few changes:\n",
    "- State variables are accessed indirectly: `p.pc` instead of just `pc`.\n",
    "- If the `pc` is out of bounds, the program terminates; the status is set to `'end'`.\n",
    "- The `snd` instruction sends a value to the other program's queue.\n",
    "- The `rcv` instruction pops a value off the queue if there is one, otherwise the status is set to `'wait'`.\n",
    "- The \"`X`\" in \"`jgz X Y`\" might be an integer, not a register name, so use `vx = value(p.regs, x)`. I was stuck for a *long* time before I realized this. Finally I tried the strategy of *look carefully at the input*. I noticed  the instruction `\"jgz 1 3\"`, and it was a simple change to make the program work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8001"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def step18(program, Qs, p):\n",
    "    \"Execute one instruction in program, using state variables in p.\"\n",
    "    if p.pc < 0 or p.pc > len(program):\n",
    "        p.status = 'end'\n",
    "    else:\n",
    "        instr = program[p.pc]\n",
    "        op, x, y = instr[0], instr[1], instr[-1]\n",
    "        vx, vy = value(p.regs, x), value(p.regs, y)\n",
    "        if   op == 'snd': Qs[1-p.id].append(vy); p.sends += 1\n",
    "        elif op == 'set': p.regs[x] = vy\n",
    "        elif op == 'add': p.regs[x] += vy\n",
    "        elif op == 'mul': p.regs[x] *= vy\n",
    "        elif op == 'mod': p.regs[x] %= vy\n",
    "        elif op == 'jgz' and vx > 0: p.pc += vy - 1\n",
    "        elif op == 'rcv': \n",
    "            if not Qs[p.id]:\n",
    "                p.status = 'wait'\n",
    "                return # don't update pc; try again next time\n",
    "            else:\n",
    "                p.regs[x] = Qs[p.id].popleft()\n",
    "                p.status = 'run'\n",
    "        p.pc += 1\n",
    "        \n",
    "run18_2(program18)[1].sends"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 19](https://adventofcode.com/2017/day/19): A Series of Tubes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At first I was confused; I thought this was a maze-following problem where I had to make a choice of directions at every turn. Actually, the direction is always determined: keep going in the current direction as long as possible, but when we hit a `'+'` character, find the new direction to go in (there will only be one possibility). Leave breadcrumbs (the `'.'` character) so that we don't back up along a previously-followed path. As in Day 14, the grid is surrounded by a border of space characters so that we don't have to worry about `(x, y)` going off the edge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "diagram = Inputstr(19)\n",
    "\n",
    "def follow_tubes(diagram):\n",
    "    \"Follow [-+|] lines, yielding characters along the path.\"\n",
    "    grid = border(' ', diagram.splitlines())\n",
    "    x, y = grid[1].index('|'), 1\n",
    "    dx, dy = 0, 1\n",
    "    while grid[y][x] != ' ':\n",
    "        yield grid[y][x]\n",
    "        if grid[y][x] == '+':\n",
    "            dx, dy = new_direction(grid, x, y)\n",
    "        grid[y][x] = '.' # Leave a breadcrumb\n",
    "        x += dx; y += dy\n",
    "    \n",
    "def new_direction(grid, x, y):\n",
    "    \"Find a direction that continues the path.\"\n",
    "    for (dx, dy) in (UP, DOWN, RIGHT, LEFT):\n",
    "        if grid[y+dy][x+dx] not in (' ', '.'):\n",
    "            return dx, dy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'VEBTPXCHLI'"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cat(filter(str.isalpha, follow_tubes(diagram)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's the right answer.\n",
    "## Part Two\n",
    "\n",
    "This is a surprisingly easy Part Two; I already generated the characters in the path; all I have to do is count them: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18702"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length(follow_tubes(diagram))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 20](https://adventofcode.com/2017/day/20): Particle Swarm\n",
    "\n",
    "I'll create structures for particles, each will have fields for particle's number (`id`), position (`p`), velocity(`v`), and acceleration (`a`). I have `particles` as a function that creartes a collection, and not a collection in its own right, because I anticipate that I will want to mutate particles, so I'll need a fresh copy every time I want to do something with them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Struct(a=(-7, 8, -10), id=0, p=(1199, -2918, 1457), v=(-13, 115, -8)),\n",
       " Struct(a=(-6, -5, 6), id=1, p=(2551, 2418, -1471), v=(-106, -108, 39)),\n",
       " Struct(a=(-6, 2, -9), id=2, p=(-73, 1626, 1321), v=(58, -118, -8)),\n",
       " Struct(a=(3, 3, 11), id=3, p=(-3297, -894, -551), v=(183, 31, -61)),\n",
       " Struct(a=(7, -12, -1), id=4, p=(-1425, 4298, 617), v=(32, -166, -32))]"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def particles(lines=tuple(Input(20))):\n",
    "    \"Parse the input file into a list of particles.\"\n",
    "    return [Particle(id, *grouper(Integers(line), 3)) \n",
    "            for id, line in enumerate(lines)]\n",
    "\n",
    "def Particle(id, p, v, a): return Struct(id=id, p=p, v=v, a=a)   \n",
    "\n",
    "particles()[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'm not quite sure how to determine what \"in the long run\" means, so I'll just interpret it as meaning \"after 1000 updates.\" "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "243"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def update(particles):\n",
    "    \"Update velocity and position of all particles.\"\n",
    "    for r in particles:\n",
    "        r.v = add(r.v, r.a)\n",
    "        r.p = add(r.p, r.v) \n",
    "    return particles\n",
    "\n",
    "def closest(particles):\n",
    "    \"Find the particle closest to origin.\"\n",
    "    return min(particles, key=lambda r: sum(map(abs, r.p)))\n",
    "\n",
    "# Answer: the id of the particle closest to origin after 1000 updates\n",
    "closest(repeat(1000, update, particles())).id"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "I'll add the function `remove_collisions`, and now the thing we repeatedly do is the composition of `remove_collisions` and `update`. Also, instead of finding the `id` of the `closest` particle, now we just need to count the number of surviving particles:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "648"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def remove_collisions(particles):\n",
    "    \"Eliminate particles that are in the same place as another.\"\n",
    "    num_particles_at = Counter(r.p for r in particles)\n",
    "    return [r for r in particles if num_particles_at[r.p] == 1]\n",
    "    \n",
    "# Answer: number of particles remaining after collisions removed\n",
    "len(repeat(1000, compose(remove_collisions, update), particles()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I got the right answer both times, so my assumption that \"in the long run\" means \"1000 updates\" turned out to work for my input data, but I feel bad that it is not guaranteed to work for all input data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 21](https://adventofcode.com/2017/day/21): Fractal Art\n",
    "\n",
    "Today looks like a complex one, so I'll break the code up into more chunks and have more test assertions than usual. I can identify the following important data types:\n",
    "\n",
    "- `Enhancements`: a `dict` of `{grid: larger_grid}` rewrite rules.\n",
    "- `grid`: a square of 0-or-1 pixels, such as `((0, 1), (0, 1))`. The function `Pixels` translates text into this form.\n",
    "\n",
    "I define the functions `rotate` and `flip`; the puzzle descriptions says \"When searching for a rule to use, rotate and flip the pattern as necessary,\" but I'm going to be doing many searches, and only one initialization of the rule set, so it will be more efficient to do the rotating and flipping just once:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Enhancements(lines):\n",
    "    \"Create a dict of {grid: enhanced_grid}; include all rotations/flips.\"\n",
    "    enhancements = {}\n",
    "    for line in lines:\n",
    "        lhs, rhs = map(Pixels, line.split('=>'))\n",
    "        for rot in range(4):\n",
    "            enhancements[lhs] = enhancements[flip(lhs)] = rhs\n",
    "            lhs = rotate(lhs)\n",
    "    return enhancements\n",
    "\n",
    "def Pixels(text): \n",
    "    \"Translate the str '.#/.#' to the grid ((0, 1), (0, 1))\"\n",
    "    bits = {'#': 1, '.': 0}\n",
    "    return tuple(tuple(bits[p] for p in row.strip())\n",
    "                 for row in text.split('/'))\n",
    "        \n",
    "def rotate(subgrid): \n",
    "    \"Rotate a subgrid 90 degrees clockwise.\"\n",
    "    return tuple(zip(*reversed(subgrid)))\n",
    "\n",
    "def flip(subgrid): \n",
    "    \"Reverse every row of the subgrid.\"\n",
    "    return tuple(tuple(reversed(row)) for row in subgrid)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's test some assertions, and then look at all the 2x2 enhancement rulesfrom my input file; with rotations and flips there should be 2<sup>4</sup> = 16 entries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{((0, 0), (0, 0)): ((0, 0, 0), (0, 1, 0), (0, 1, 0)),\n",
       " ((0, 0), (0, 1)): ((0, 0, 0), (1, 0, 0), (1, 0, 0)),\n",
       " ((0, 0), (1, 0)): ((0, 0, 0), (1, 0, 0), (1, 0, 0)),\n",
       " ((0, 0), (1, 1)): ((1, 0, 1), (0, 1, 0), (0, 1, 0)),\n",
       " ((0, 1), (0, 0)): ((0, 0, 0), (1, 0, 0), (1, 0, 0)),\n",
       " ((0, 1), (0, 1)): ((1, 0, 1), (0, 1, 0), (0, 1, 0)),\n",
       " ((0, 1), (1, 0)): ((1, 1, 0), (1, 1, 0), (0, 0, 0)),\n",
       " ((0, 1), (1, 1)): ((0, 1, 1), (1, 1, 1), (1, 0, 0)),\n",
       " ((1, 0), (0, 0)): ((0, 0, 0), (1, 0, 0), (1, 0, 0)),\n",
       " ((1, 0), (0, 1)): ((1, 1, 0), (1, 1, 0), (0, 0, 0)),\n",
       " ((1, 0), (1, 0)): ((1, 0, 1), (0, 1, 0), (0, 1, 0)),\n",
       " ((1, 0), (1, 1)): ((0, 1, 1), (1, 1, 1), (1, 0, 0)),\n",
       " ((1, 1), (0, 0)): ((1, 0, 1), (0, 1, 0), (0, 1, 0)),\n",
       " ((1, 1), (0, 1)): ((0, 1, 1), (1, 1, 1), (1, 0, 0)),\n",
       " ((1, 1), (1, 0)): ((0, 1, 1), (1, 1, 1), (1, 0, 0)),\n",
       " ((1, 1), (1, 1)): ((0, 1, 1), (1, 0, 0), (1, 1, 0))}"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "assert Pixels('../##') == ((0, 0), (1, 1))\n",
    "assert rotate(((0, 0), (1, 1))) == ((1, 0), (1, 0))\n",
    "assert flip(((0, 0, 1), (1, 1, 0))) == ((1, 0, 0), (0, 1, 1))\n",
    "\n",
    "Enhancements('''\n",
    "../.. => .../.#./.#.\n",
    "#./.. => .../#../#..\n",
    "##/.. => #.#/.#./.#.\n",
    ".#/#. => ##./##./...\n",
    "##/#. => .##/###/#..\n",
    "##/## => .##/#../##.\n",
    "'''.strip().splitlines())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert len(_) == 2 ** 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looks good; let's create the complete `enhancements` for my data. There should be 2<sup>4</sup> + 2<sup>9</sup> = 528 entries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "enhancements = Enhancements(Input(21))\n",
    "\n",
    "assert len(enhancements) == 2 ** 4 + 2 ** 9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now on each iteration we `enhance` the grid by first dividing it into pieces with `divide_grid`, then using my utility function `map2d` to apply `enhancements` to each piece, and then call `stitch_grid` to put all the pieces back together into a bigger grid:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def enhance(grid): \n",
    "    \"Divide the drid into pieces, enhance each piece, and stitch them together.\"\n",
    "    return stitch_grid(map2d(enhancements.get, divide_grid(grid)))\n",
    "\n",
    "def divide_grid(grid):\n",
    "    \"Divide the grid into d x d pieces and enhance each piece.\"\n",
    "    N = len(grid[0])\n",
    "    d = (2 if N % 2 == 0 else 3 if N % 3 == 0 else error())\n",
    "    return [[tuple(row[c:c+d] for row in grid[r:r+d])\n",
    "             for c in range(0, N, d)]\n",
    "            for r in range(0, N, d)]\n",
    "\n",
    "def stitch_grid(pieces): \n",
    "    \"Stitch the pieces back into one big grid.\"\n",
    "    N = sum(map(len, pieces[0]))\n",
    "    return tuple(tuple(getpixel(pieces, r, c) \n",
    "                       for c in range(N))\n",
    "                 for r in range(N))\n",
    "\n",
    "def getpixel(pieces, r, c):\n",
    "    \"The pixel at location (r, c), from a matrix of d x d pieces.\"\n",
    "    # Use `//` to find the right piece, and `%` to find the pixel within the piece\n",
    "    d = len(pieces[0][0])\n",
    "    piece = pieces[r // d][c // d]\n",
    "    return piece[r % d][c % d]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Some tests\n",
    "corners = Pixels('#..#/..../..../#..#')\n",
    "pieces  = [[((1, 0), \n",
    "             (0, 0)), ((0, 1), \n",
    "                       (0, 0))], \n",
    "           [((0, 0), \n",
    "             (1, 0)), ((0, 0), \n",
    "                       (0, 1))]]\n",
    "\n",
    "assert divide_grid(corners) == pieces\n",
    "assert stitch_grid(pieces) == corners"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((0, 1, 0), (0, 0, 1), (1, 1, 1))"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# An extended test \n",
    "grid = Pixels('.#./..#/###')\n",
    "grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[((0, 1, 0), (0, 0, 1), (1, 1, 1))]]"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "divide_grid(_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((((1, 0, 1, 0), (0, 0, 1, 0), (0, 1, 0, 1), (0, 1, 0, 0)),),)"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "map2d(enhancements.get, _)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((1, 0, 1, 0), (0, 0, 1, 0), (0, 1, 0, 1), (0, 1, 0, 0))"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stitch_grid(_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[((1, 0), (0, 0)), ((1, 0), (1, 0))], [((0, 1), (0, 1)), ((0, 1), (0, 0))]]"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "divide_grid(_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((((0, 0, 0), (1, 0, 0), (1, 0, 0)), ((1, 0, 1), (0, 1, 0), (0, 1, 0))),\n",
       " (((1, 0, 1), (0, 1, 0), (0, 1, 0)), ((0, 0, 0), (1, 0, 0), (1, 0, 0))))"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "map2d(enhancements.get, _)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((0, 0, 0, 1, 0, 1),\n",
       " (1, 0, 0, 0, 1, 0),\n",
       " (1, 0, 0, 0, 1, 0),\n",
       " (1, 0, 1, 0, 0, 0),\n",
       " (0, 1, 0, 1, 0, 0),\n",
       " (0, 1, 0, 1, 0, 0))"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stitch_grid(_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(flatten(_))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That looks right; Let's try to solve the whole puzzle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "147"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(flatten(repeat(5, enhance, grid)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's correct!\n",
    "\n",
    "## Part Two\n",
    "\n",
    "Huh &mdash; It looks like I don't need to change any code for Part Two, just do `18` repetitions instead of `5`. \n",
    "\n",
    "Well, almost. Doing that gave an answer (in a few seconds); but the answer was wrong. I carefully looked over all my code, and realized there was a place  where I had swapped the order of `r` and `c`. Once I fixed that (the fix is already incorporated above), I got the right answer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 5.2 s, sys: 80.6 ms, total: 5.28 s\n",
      "Wall time: 5.28 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1936582"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time sum(flatten(repeat(18, enhance, grid)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 22](https://adventofcode.com/2017/day/22): Sporifica Virus\n",
    "\n",
    "This one looks to be of medium difficulty. One important choice: since we are dealing with \"a seemingly-infinite two-dimensional grid of compute nodes,\" and I think it will be sparse, I'll represent the grid with a `set` of the positions of infected nodes, rather than with a 2-dimensional array.  I'll define a `namedtuple` to hold the state of the network: the current position of the virus, its heading, the number of infections caused so far, and the set of infected nodes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Net = namedtuple('Net', 'current, heading, caused, infected')\n",
    "\n",
    "def parse_net(lines):\n",
    "    \"Read the initial state of the network.\"\n",
    "    lines = list(lines)\n",
    "    center = (len(lines) // 2, len(lines[0].strip()) // 2)\n",
    "    return Net(center, UP, 0,\n",
    "               {(x, y) \n",
    "                for (y, row) in enumerate(lines) \n",
    "                for (x, node) in enumerate(row)\n",
    "                if node == '#'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Net(current=(1, 1), heading=(0, -1), caused=0, infected={(0, 1), (2, 0)})"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test = '''\n",
    "..#\n",
    "#..\n",
    "...\n",
    "'''.strip().splitlines()\n",
    "    \n",
    "parse_net(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the logic for one step of the simulation, called a *burst*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def burst(net):\n",
    "    \"Simulate the virus through one step and return the new state of the network.\"\n",
    "    (current, heading, caused, infected) = net\n",
    "    heading = (turn_right if current in infected else turn_left)(heading)\n",
    "    if current in infected:\n",
    "        infected.remove(current)\n",
    "    else:\n",
    "        caused += 1\n",
    "        infected.add(current)\n",
    "    return Net(add(current, heading), heading, caused, infected)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Net(current=(1, 0), heading=(1, 0), caused=5, infected={(0, 1), (-1, 1), (-1, 0), (2, 0), (1, 1)})"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# We're supposed to get 5 infections caused in the first 7 steps:\n",
    "repeat(7, burst, parse_net(test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Net(current=(2, 0), heading=(0, -1), caused=41, infected={(5, -1), (3, 2), (-1, 0), (3, -3), (1, 0), (1, -2), (4, -2), (-1, 1), (2, -3), (5, 0), (2, 2), (0, -1), (4, 1), (1, 1)})"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# And 41 out of 70:\n",
    "repeat(70, burst, parse_net(test))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This testing revealed a problem: I had (yet again) messed up the order of (x, y). (I find it confusing that there are two traditional orders: (x, y) and (row, col), and this is yet another reminder that I have to pay extra attention to keep them straight.) After fixing that, I was\n",
    "ready to solve the problem:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5460"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "repeat(10000, burst, parse_net(Input(22))).caused"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "It looks like I can't re-use any of my code from Part One (except by copy-and-paste). I have the following concerns:\n",
    "- I want to replace the `set` of `infected` nodes with a `dict`, `status[node]`, which can be `I`, `F`, `C`, or `W` (default `C` for clean).\n",
    "- I need to run 10,000,000 steps, so I want it to be efficient.\n",
    "- I have some confidence from doing Part One successfully, so I'm comfortable stressing efficiency over simplicity.\n",
    "I'll use variables inside a function, `bursts`, that does `N` repetitions; I'll avoid creating a new `Net` object each iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bursts(N, net):\n",
    "    \"Run N steps of bursts on the network depicted by `lines`.\"\n",
    "    (current, heading, caused, infected) = net\n",
    "    status = defaultdict(lambda: 'C', {pos: 'I' for pos in infected})\n",
    "    for _ in range(N):\n",
    "        S = status[current]\n",
    "        if S == 'C':\n",
    "            heading = turn_left(heading)\n",
    "            status[current] = 'W'\n",
    "        elif S == 'W':\n",
    "            # heading unchanged\n",
    "            status[current] = 'I'\n",
    "            caused += 1\n",
    "        elif S == 'I':\n",
    "            heading = turn_right(heading)\n",
    "            status[current] = 'F'\n",
    "        elif S == 'F':\n",
    "            heading = turn_around(heading)\n",
    "            status[current] = 'C' \n",
    "        current = add(current, heading)\n",
    "    return caused"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Of the first 100 bursts of the test network, 26 will result in infection\n",
    "assert bursts(100, parse_net(test)) == 26"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had another bug here that gave me the wrong answer the first time: I had put the \"`caused += 1`\" line under the condition where the status *was* `'I'`, whereas it actually belongs under the condition where the status *becomes* `'I'`. With that fix, I get the right answer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 13.5 s, sys: 9.95 ms, total: 13.5 s\n",
      "Wall time: 13.5 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2511702"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time bursts(10000000, parse_net(Input(22)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "# [Day 23](https://adventofcode.com/2017/day/23): Coprocessor Conflagration\n",
    "\n",
    "Part One looks straightforward. I won't make the \"register X might be an integer\" mistake again:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9409"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def run23(program):\n",
    "    regs = {L: 0 for L in 'abcdefgh'}\n",
    "    pc = 0\n",
    "    mulcount = 0\n",
    "    while 0 <= pc < len(program):\n",
    "        op, X, Y = program[pc]\n",
    "        pc += 1\n",
    "        if   op == 'set': regs[X] = value(regs, Y)\n",
    "        elif op == 'sub': regs[X] -= value(regs, Y)\n",
    "        elif op == 'mul': regs[X] *= value(regs, Y); mulcount += 1\n",
    "        elif op == 'jnz' and value(regs, X): pc += value(regs, Y) - 1\n",
    "    return mulcount\n",
    "\n",
    "run23(Array(Input(23)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "The hint of \"You'll need to **optimize the program**\" reminded me of a puzzle from 2016 where I had to understand what the program was doing and make it more efficient. It wasn't obvious what Day 23's program was doing, but I began the process of re-writing it as a Python program, converting the `jnz` instructions to `if` and `while` statements. Eventually I realized that the inner loop was doing \"`b % d`\", and my  program became the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 939 ms, sys: 2.89 ms, total: 942 ms\n",
      "Wall time: 940 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "913"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@jit\n",
    "def run23_2():\n",
    "    a = 1\n",
    "    d = e = f = g = h = 0\n",
    "    b = 99\n",
    "    c = b\n",
    "    if a:\n",
    "        b *= 100\n",
    "        b -= -100000\n",
    "        c = b\n",
    "        c -= -17000\n",
    "    while True:\n",
    "        f = 1\n",
    "        d = 2\n",
    "        e = 2\n",
    "        while True:\n",
    "            if b % d == 0:\n",
    "                f = 0\n",
    "            d -= -1\n",
    "            g = d - b\n",
    "            if g == 0:\n",
    "                if f == 0:\n",
    "                    h -= -1\n",
    "                g = b - c\n",
    "                if g == 0:\n",
    "                    return h\n",
    "                b -= -17\n",
    "                break\n",
    "            \n",
    "%time run23_2()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `numba.jit` decorator really helps here, speeding up execution from 13 seconds to 1 second.\n",
    "\n",
    "# [Day 24](https://adventofcode.com/2017/day/24): Electromagnetic Moat\n",
    "\n",
    "First I will read the data and store it as a table of `{port_number: [components_with_that_port]}`. I also define two simple utility functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def component_table(pairs):\n",
    "    \"Make a table of {port: {components_with_that_port}\"\n",
    "    ctable = defaultdict(set)\n",
    "    for pair in pairs:\n",
    "        ctable[pair[0]].add(pair)\n",
    "        ctable[pair[1]].add(pair)\n",
    "    return ctable\n",
    "\n",
    "ctable = component_table(map(Integers, Input(24)))\n",
    "\n",
    "def other_port(component, port):\n",
    "    \"The other port in a two-port component.\"\n",
    "    return (component[1] if component[0] == port else component[0])\n",
    "\n",
    "def strength(chain): return sum(flatten(chain))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are dealing with an optimization problem involving paths in a graph (called *chains* in this problem), and we're looking for the chain that maximizes `strength`. I'll represent a chain as a tuple of components. I could have defined a single function that traverses the graph and also keeeps track of the maximum, but  I think it is cleaner to keep the two aspects of the problem separate. First a function to generate all possible chains:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def chains(chain=(), port=0, ctable=ctable):\n",
    "    \"Given a partial chain ending in `port`, yield all chains that extend it.\"\n",
    "    yield chain\n",
    "    for c in ctable[port]:\n",
    "        if c not in chain: \n",
    "            # Extend with components, c, that match port but are not already in chain\n",
    "            yield from chains(chain + (c,), other_port(c, port), ctable)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And then asking for the strength of the strongest chain:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.32 s, sys: 2.56 ms, total: 2.32 s\n",
      "Wall time: 2.32 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1695"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time strength(max(chains(), key=strength))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I was worried it was going to be slow, so I measured the `%time`, but it turned out not too bad.\n",
    "\n",
    "## Part Two\n",
    "\n",
    "Now we want to find the strength of the longest chain, but if there is a tie, pick the strongest one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.39 s, sys: 1.44 ms, total: 2.39 s\n",
      "Wall time: 2.39 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1673"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def length_and_strength(c): return len(c), strength(c)\n",
    "\n",
    "%time strength(max(chains(), key=length_and_strength))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I think I made the right choice in defining things the way I did. My code is simple, and gets the right answers in a few seconds. But I realize there are some inefficiencies:\n",
    "\n",
    "- Calculating the strength of a chain is O(N), but since we always form new chains by extending an old chain (for which we know the strength) with one new component, calculating the strength of the new chain could be O(1).\n",
    "- A chain is a `tuple`, so checking \"`c not in chain`\" is O(N). If the chain were a `set`, it would be O(1).\n",
    "- A new chain is created by *copying* the previous chain and appending a new component. A more efficient approach is to *mutate* the chain by adding a component, and then removing the component when it is time to consider other possibilities. This is called *backtracking*.\n",
    "\n",
    "Here is a backtracking implementation. It keeps track of a single `chain`, `port`, and `strength`. A call to `recurse(best_strength)` returns the best strength, either the one passed in, or one found by adding components to the current chain. When `recurse` returns, `chain`, `port`, and `strength` are reset to their original values, and the best strength found is returned as the value of the call to `recurse`. This is indeed faster (and gives the same answer): "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 638 ms, sys: 3.98 ms, total: 642 ms\n",
      "Wall time: 642 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1695"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def strongest_chain(ctable=ctable):\n",
    "    \"\"\"Return the strength of the strongest chain, using backtracking.\"\"\"\n",
    "    chain = set()\n",
    "    port = 0\n",
    "    strength = 0\n",
    "    def recurse(best_strength):\n",
    "        nonlocal chain, port, strength\n",
    "        for c in ctable[port] - chain:\n",
    "            # Update chain, port, strength\n",
    "            # then recurse and possibly update best_strength\n",
    "            # then backtrack and restore chain, port, strength\n",
    "            chain.add(c)\n",
    "            port = other_port(c, port)\n",
    "            strength += sum(c)\n",
    "            best_strength = max(strength, recurse(best_strength))\n",
    "            chain.remove(c)\n",
    "            port = other_port(c, port)\n",
    "            strength -= sum(c)\n",
    "        return best_strength\n",
    "    return recurse(0)\n",
    "\n",
    "%time strongest_chain()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can decide whether the saving in time is worth the complication in code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 25](https://adventofcode.com/2017/day/25): The Halting Problem\n",
    "\n",
    "I won't write a parser for my input; instead I'll translate it into a `dict` by hand:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def machine():\n",
    "    \"machine()[state][value] == (new_value, move, new_state)}\"\n",
    "    L, R = -1, +1\n",
    "    A, B, C, D, E, F = 'ABCDEF'\n",
    "    return {A: [(1, R, B), (0, L, C)],\n",
    "            B: [(1, L, A), (1, R, D)],\n",
    "            C: [(0, L, B), (0, L, E)],\n",
    "            D: [(1, R, A), (0, R, B)],\n",
    "            E: [(1, L, F), (1, L, C)],\n",
    "            F: [(1, R, D), (1, R, A)]}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now a simple interpreter for machines like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4769"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def turing(machine, state, steps):\n",
    "    \"Run the Turing machine for given number of steps, then return tape.\"\n",
    "    tape = defaultdict(int)\n",
    "    cursor = 0\n",
    "    for step in range(steps):\n",
    "        tape[cursor], move, state = machine[state][tape[cursor]]\n",
    "        cursor += move\n",
    "    return tape\n",
    "\n",
    "sum(turing(machine(), 'A', 12667664).values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is no **Part Two** today; we're done!\n",
    "\n",
    "# A Note on Reuse\n",
    "\n",
    "One interesting question: for what days did my Part Two code reuse the Part One code? How so?\n",
    "Here are my answers:\n",
    "\n",
    "\n",
    "* **Total Reuse (11 days)**: The major function defined in Part One is called again in Part Two:\n",
    "<br>Days 3 (`spiral`), 6 (`spread`, but `realloc2` is copy-edit), 9, 12, 14 (`bits`), \n",
    "15 (`A, B, gen, judge`), 16 (`perform`), 19 (`follow_tubes`), 20 (`update, particles`), 21 (`enhance`),\n",
    "24 (`chains`, `strength`)\n",
    "\n",
    "* **Generalization (1 day)**: A major function from Part One is generalized in Part Two (e.g. by adding an optional parameter):\n",
    "<br>Days 13 (`caught`)\n",
    "\n",
    "* **Copy-edit (7 days)**: The major function from Part One is copied and edited for Part Two:\n",
    "<br>Days 5 (`run2`), 8 (`run8_2`), 10 (`knothash2`), 11 (`follow2`), 17 (`spinlock2`), 18 (`run18_2`), 22 (`parse_net2`, `burst2`)\n",
    "\n",
    "* **All new (5 days)**: All the code for Part Two (except possibly reading and parsing the input) is brand new: \n",
    "<br>Days 1, 2, 4, 7, 23\n",
    "\n",
    "I think I did a reasonably good job of facilitating reuse. It seems like using generators and higher-order functions like `repeat` helps.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Verification and Run Times\n",
    "\n",
    "A little test harness and a report on all the run times that are over 5 seconds per day:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Day 15: 10.3 sec\n",
      "Day 17:  5.5 sec\n",
      "Day 21:  5.3 sec\n",
      "Day 22: 13.9 sec\n",
      "CPU times: user 56.3 s, sys: 193 ms, total: 56.5 s\n",
      "Wall time: 56.6 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "def run_tests(tests, short=5.0):\n",
    "    \"Run daily test assertions; report times > `short` seconds.\"\n",
    "    for day in sorted(tests):\n",
    "        t0 = time.time()\n",
    "        assert tests[day]()\n",
    "        dt = time.time() - t0\n",
    "        if dt > short: \n",
    "            print('Day {:2d}: {:4.1f} sec'.format(day, dt))\n",
    "    \n",
    "run_tests({\n",
    "  1: lambda: sum(digits[i] for i in range(N) if digits[i] == digits[i - 1]) == 1158 and\n",
    "             sum(digits[i] for i in range(N) if digits[i] == digits[i - N // 2]) == 1132,\n",
    "  2: lambda: sum(abs(max(row) - min(row)) for row in rows2) == 46402 and\n",
    "             sum(map(evendiv, rows2)) == 265,\n",
    "  3: lambda: cityblock_distance(nth(spiral(), M - 1)) == 475 and\n",
    "             first(x for x in spiralsums() if x > M) == 279138,\n",
    "  4: lambda: quantify(Input(4), is_valid) == 337 and\n",
    "             quantify(Input(4), is_valid2) == 231,\n",
    "  5: lambda: run(program) ==  364539 and\n",
    "             run2(program) == 27477714,\n",
    "  6: lambda: realloc(banks) == 12841 and\n",
    "             realloc2(banks) == 8038,\n",
    "  7: lambda: first(programs - set(flatten(above.values()))) == 'wiapj' and\n",
    "             correct(wrongest(programs)) == 1072,\n",
    "  8: lambda: max(run8(program8).values()) == 6828 and\n",
    "             run8_2(program8) == 7234,\n",
    "  9: lambda: total_score(text2) == 9662 and\n",
    "             len(text1) - len(text3) == 4903,\n",
    " 10: lambda: knothash(stream) == 4480 and\n",
    "             knothash2(stream2) == 'c500ffe015c83b60fad2e4b7d59dabc4',\n",
    " 11: lambda: follow(path) == 705 and\n",
    "             follow2(path) == 1469,\n",
    " 12: lambda: len(G[0]) == 115 and\n",
    "             len({Set(G[i]) for i in G}) == 221,\n",
    " 13: lambda: trip_severity(scanners) == 1504  and\n",
    "             safe_delay(scanners) == 3823370,\n",
    " 14: lambda: sum(bits(key, i).count('1') for i in range(128)) == 8316 and\n",
    "             flood_all(Grid(key)) == 1074,\n",
    " 15: lambda: duelgen() == 597 and\n",
    "             judge(criteria(4, A()), criteria(8, B()), 5*10**6) == 303,\n",
    " 16: lambda: perform(dance) == 'lbdiomkhgcjanefp' and\n",
    "             whole(48, dance) == 'ejkflpgnamhdcboi',\n",
    " 17: lambda: spinlock2().find(2017).next.data == 355 and\n",
    "             spinlock3(N=50*10**6)[1] == 6154117,\n",
    " 18: lambda: run18(program18) == 7071  and\n",
    "             run18_2(program18)[1].sends == 8001,\n",
    " 19: lambda: cat(filter(str.isalpha, follow_tubes(diagram))) == 'VEBTPXCHLI' and\n",
    "             quantify(follow_tubes(diagram)) == 18702,\n",
    " 20: lambda: closest(repeat(1000, update, particles())).id == 243 and\n",
    "             len(repeat(1000, compose(remove_collisions, update), particles())) == 648,\n",
    " 21: lambda: sum(flatten(repeat(5,  enhance, grid))) == 147 and\n",
    "             sum(flatten(repeat(18, enhance, grid))) == 1936582,\n",
    " 22: lambda: repeat(10000, burst, parse_net(Input(22))).caused == 5460 and\n",
    "             bursts(10000000, parse_net(Input(22))) == 2511702,\n",
    " 23: lambda: run23(Array(Input(23))) == 9409 and\n",
    "             run23_2() == 913,\n",
    " 24: lambda: strongest_chain() == 1695 and\n",
    "             strength(max(chains(), key=length_and_strength)) == 1673,\n",
    " 25: lambda: sum(turing(machine(), 'A', 12667664).values()) == 4769\n",
    "})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All the days together run in a but less than a minute; only 4 days take more than 5 seconds each; and only 2 take more than 10 seconds.\n",
    "\n",
    "# Development Time\n",
    "\n",
    "Here is a plot of the time it took to program solutions each day, for me, the first person to finish, and the hundredth person.  My mean time to solve is a little slower than the 100th solver, and five times slower than the first solver."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAENCAYAAAAG6bK5AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsnXdcFNfXxp9dqhRRUVEQAbErVuyKJfYu2BFFjYn62rCg\nJgIqtsQuJrYUoxL9mVhjByFgA8TeCyyoLCAi4LIgbe/7x4SFlV22zRbgfvPZT9iZufeeGWfnzC3n\nORxCCAGFQqFQqhxcXRtAoVAoFN1AHQCFQqFUUagDoFAolCoKdQAUCoVSRaEOgEKhUKoo1AFQKBRK\nFcVQUxUXFhZi+fLlSEpKgqGhIQIDA2FgYIAVK1aAy+WiSZMmCAgI0FTzFAqFQpGDxhxAREQERCIR\njh07hps3b2L79u0oKCjA4sWL4erqioCAAISGhqJ///6aMoFCoVAo5aCxISBHR0cUFRWBEAKBQABD\nQ0M8ffoUrq6uAAA3NzfcunVLU81TKBQKRQ4a6wGYm5vj3bt3GDx4MDIzM7F3717ExsZK7BcIBJpq\nnkKhUChy0JgDOHjwIHr16gUfHx+kpqbCy8sLBQUF4v1CoRDVq1fXVPMUCoVCkYPGHICVlRUMDZnq\nLS0tUVhYiJYtWyImJgadO3dGZGQkunbtWqbcnTt3NGUShUKhVGo6duyo1PEcTYnB5eTk4LvvvkNa\nWhoKCwsxbdo0tGrVCqtWrUJBQQGcnZ2xbt06cDgciXJ37txR+iQqK3w+H7a2tro2Qy+g16IEei1K\noNeiBFWenRrrAZiZmWHHjh1lth8+fFhTTVIoFApFCWggGIVCoVRRqAOgUCiUKgp1ABQKhVJFoQ6A\nQqFQqijUAVAoFEoVhToACoVCqaJQB0ChUChVFOoAKBQKpYpCHQALJCUloXnz5vDy8iqzb+XKlWje\nvDkyMzOVrvfs2bP466+/1LLtzJkzGDVqFMaMGYNJkybhyZMnAIAFCxZgzJgxGDNmDEaPHg1XV1fM\nnTtX5XZ27dqFM2fOlHtMamoq5s2bp3IbFAqFXTQWCaxP8HiJ8PM7iKQkEezsuAgM9IaTkwOrbZiY\nmIDH4yE5ORn169cHAOTm5uLu3btl5C4Ugc/n4/Llyzh16pTKNvF4PGzZsgWnT5+GtbU1IiIiMG/e\nPISHh2PXrl3i4x49eoSFCxeqlaBnwYIFco+xsbFBy5YtERwcDE9PT5XbolAo7FDpHQCPl4gBA4IQ\nF7cGgDkAIaKiAhASMp9VJ8DlcjF06FCcPXsW3377LQDgypUr6NevHw4ePCg+Ljw8HHv27EFhYSFM\nTU3h6+uLdu3alalv3759GDBggPh78+bNERUVhRo1akh8f/bsGX744YcyTmbp0qVwdHTEunXrYG1t\nDQBo3bo1Pnz4gMLCQrFQX0FBAVasWIHvv/8eNjY2ZexYuXIlTExM8OjRI6Snp2Pw4MGoVasWwsLC\nkJ6ejnXr1qFLly5YuXIlmjZtiunTp6NNmzb45ptvcOPGDaSlpcHLywvTpk0DAHh4eGDcuHGYMGGC\n2AZK5UEbL1sUFiF6RmxsLKv1eXquJkA2AUipTzbx9FzNWhvv3r0j7du3J0+ePCFDhw4Vb/f29iav\nXr0izZs3JxkZGSQhIYEMHz6cZGZmEkIIefXqFenRowfJzc0tU2fXrl3J3bt3xd+L65D1XRGWLFlC\nFi5cKLEtODiYTJ8+XWaZFStWkAkTJpCioiKSlpZGmjVrRo4cOUIIIeSPP/4gM2bMEB/322+/EUII\nadasGQkODiaEEPL48WPi4uJC8vLyxHWOHTuWREdHK2V7UlKSUsdXZvT1WsTHJxBn5yWlfm/ZxNl5\nCYmPT9BYm/p6LXSBKs/OCj0HsHo1wOGU/axeXXJMUpIIzJt/acwRHCySerw6tGzZElwuF0+fPkVK\nSgpycnLQuHFjkP8EV2/cuIEPHz7A29sbo0ePxtKlS2FoaIjExESJejIyMiAQCCTeyIkM0dZbt25h\n9OjREp8xY8bgxo0b4mNyc3OxYMECvHv3DuvWrZMo/8cff8gd++/bty+4XC5q166NatWqoVevXgCA\nhg0bIisrS2qZr776CgDQqlUrFBQUIDc3V7zP3t4ePB6v3DYpFQ8/v4OletoAYI64uDXw8zuoQ6so\n5VGh++CrV8t/eNvZcQEIIekEhPD05OLIEfZtGjlyJM6cOYNatWph5MiRACAenhGJROjWrRu2bdsm\nPj4lJaXM0AuXK90vf/78WeL/ANCtWzecPn1apj18Ph9z5sxB48aNcejQIRgbG4v3PXv2DCKRSJym\nUxalywBQaOjGxMRE4ntpB1ZUVCTzHCkVF1kvW3y+SBfmUBSg0v8KAwO94ewcAMYJAIAQzs4BCAz0\nZrWd4gfcyJEjcenSJVy8eBEjRoyQ2Ne1a1fcuHED8fHxAICIiAiMGjUKeXl5EnVZWVmhevXqSElJ\nkdgeEREBAAgLC1PIpqysLEyZMgUDBw7E1q1byzzIY2JipCblYZsvey9v375Fo0aNNN4uRbuUvGyV\nRghb20r/mKmwVOgegCI4OTkgJGQ+/Py2gM8XwdaWi8BAdieAgZK3fBsbGzRu3BiWlpbilJfF+xo3\nboy1a9di8eLFAAADAwPs2bMHpqamZeobOHAgYmJi0KFDB/G2q1ev4vDhw6hXr55C6TSPHj2K1NRU\nhIaGIiQkRGzLwYMHYWVlhcTERNjZ2al0nsocU/p7eno6MjIyaNKfSkhgoDfOnw9AZmbJggvmZWu+\nji2jyEJjGcFUhWYEY3j37h3mzp2Ls2fPAmBW/URHR8PKykrHlqnH7t27UatWLUyePFmpcjTzUwn6\nfC3OnUvEjh0HkZsrgpOT5lcB6fO10DZ6lRGMoh4NGjTAoEGD8L///Q8TJkwAh8ORORFcUUhJScHT\np0/x008/6doUioYYPtwBw4erHk9C0S7UAegxY8aMEb/dPHv2TMfWqE+9evXw888/69oMCoXyH3R2\nhkKhUKooGusBnDp1CidPngSHw0FeXh6eP3+O4OBgbNiwAVwuF02aNFFLeoBCoVAo6qGxHsCYMWNw\n+PBhHDp0CK1atcKqVavw008/YfHixThy5AhEIhFCQ0M11TyFQqFQ5KDxIaBHjx7h9evXGDduHJ48\neSIOOnJzc8OtW7c03TyFQtECsbGAh0fJdx4P6NxZd/ZQFEPjDmD//v2YP7/sOmBzc3MIBAJNN0+h\nULRARARQr17Jd3t74MkT4NMn3dlEkY9GHYBAIEBCQgI6derENFYq/F8oFCoUzFTRWLlyJX7//Xfx\nd5FIhPXr12PIkCEYNGgQjh07Jt6XmJgIT09PDBs2DOPHjxdHCGdnZ4vVMwEolU8gMjISO3bsYOVc\ndu7cKaEdlJ+fD39/fwwaNAju7u4ICgpSq/5jx47hwIED5R6Tk5ODWbNmIT8/X622KJrl2jXAza3k\nu6Eh0LYtcO+e7myiyEejy0Bv374tITXQokUL3L59G506dUJkZKRMGQI+n8+aDQFbAvA4+XGZ7a3r\nt8aapWtYa+fNmzfYsWMHnj17BhsbG/E5nDlzBi9fvsQvv/wCoVCI//u//4ONjQ2aNWuGBQsWYNy4\ncejXrx9iYmIwZ84c/P7770hJScHDhw8hEAjA5/PB4XDE4nLlkZubi40bN2LPnj1qXcO0tDT89NNP\niI6OxpAhQ8R1HTx4EAkJCThw4AAMDQ2xZcsW/Pzzzxg9erRK7bj998SQZ2vPnj2xd+9ehXIOVAWK\n7wt9QSQCIiLqwd//vYTuT/Pm1XH1ahGaNPlSHoI99O1aVDQ06gB4PB7s7e3F35cvXw4/Pz8UFBTA\n2dkZgwcPllqOzci+QX0G4c/TfyLHoeThaZZghqV9l7Lazq+//orJkyfj1q1bsLKyEtd9+/ZtTJ48\nWSy5MGrUKNy8eRMtW7ZEUlISpkyZAgAYPXo0goKCkJWVhR07diAvLw9LlizB2bNnQQjB8ePHcf/+\nfWRlZWHGjBlSE6rs378fffv2haOjIwCgX79+CAoKQqtWrSS+m5qaYsmSJWUkG6ZOnYoxY8bg5MmT\n6NWrF1q3bo1Pnz6Jz+XNmzdwd3dHw4YNxefy66+/llET3b17N968eYM3b94gLS0Nbdq0QY8ePXD6\n9GkkJSVh2bJlGDp0KHbv3o3MzEysWrUK/fr1g7u7O27duoXk5GQMGTIEy5YtAwBMmjQJffr0ga+v\nL2rVqsXGP1eFRt+iX588AaytgQ4d6klsd3MDrlwBbG01F72ub9dClyQnJytdRqMOYObMmRLfHR0d\ncfjwYU02WQaPER7YcngLokk0wAFAAJdsF7gPd2e1HT8/PwAoM7FdOkMYwGgFvXz5EikpKahbt67E\nsTY2NkhJScHGjRsxYsQI7N+/Xzxs1rBhQ/j7++PZs2eYMGECJk6cCAMDA4nyly9fxooVK+Ta6uzs\nXK6CaHHaxt27d0tsb9OmDS5cuICBAwfC0NAQ//zzD9LS0qTWcffuXZw5cwaGhoZwc3NDvXr1cOTI\nEVy9ehWbN2/G0KFDy5TJyclBcHAwUlNTMXDgQLHjNDY2RuvWrREREYExY8bIPT+KdomNBf5TCJeg\nY0dg+3bt20NRnAodCbz639XM//usLvf7Uq+lmHZ6GnIccmDEM8KyqcvA4XDklmcDkaisFC6Xy5W6\nvXifNIYPHw6AGUYrKChAdnZ2GV2g+Ph48dt5ecTFxYl7AMXyEhwOR9wDkMWsWbOwfft2TJgwATVq\n1MCQIUPw8uVLqcd2794d5uaMNHDdunXFwz2K5BCwsbGBtbU1srKyxD0nOzs7mkNAT5k2DZg0qez2\nVq2AO3e0bw9FcSq2A/jiQS3rOyFE3AvokNNB/PYvrzwb2Nra4v379+LvqampqFevHmxtbcu8PRfv\nk8aXGvzSdIEMDAzKOJbSiViK8wjI6wHIIisrC9OnT4evry8A4MKFC3BwkC70pUoOgS9VUWkOgYrD\nF//cAAAul/lQ9Jcq8c/D4XCw1GspLMMtxW//2uKrr77CiRMnUFRUhE+fPuHChQvo378/bGxs0LBh\nQ1y4cAEAcO3aNRgYGKBZs2YwNDSU2UMAZGcHc3R0xNu3byW2RUZGAgAePHiAjx8/qnUuYWFh8Pf3\nB8Cs4jp48KA454GmSU5OpjkEKBSWqdA9AGXwGOGB2HuxrI/9y2PSpEl4+/YtRo0ahYKCAkyaNEkc\nDLd9+3Z8//332LNnD0xMTLBz504AQJ06ddCiRQt4e3vj+PHj5errl2bQoEGIjIxE51IROE+ePMHw\n4cNhYWGh0PBQeXh4eODhw4cYPnw4RCIRxo8fj4EDB6pVZzHlnWN+fj6ePn2K7XRAmUJhFZoPQI9R\ndoVDdnY2Jk6ciBMnTsDExKTMKqCKyqlTp3D//n2sWcPest2KDF35UgK9FiWo8uysEkNAVQULCwss\nXrxYLLmszaEuTSEUCnHu3Dl4e3vr2hSKFB48YOIAyiMpCfgi6ylFT6AOoJLRr18/+Pj4AGBSSFb0\nt39zc3P8+uuvZZLMU3RPSgrQpw8gbwxh7FggKkorJlGUhDoACoWiEtevAz16AF+Eo5ShY0e6HFRf\noQ6AQqGoRGSkpP6PLFxdqQPQV6gDoFAoKvGlAJwsOnZkooUp+keVWQZKoVRVeLxE+PkdRFKSCHZ2\nXAQGesPJSXoAn6JkZgKvXwMdOsg/tkUL4N07Rhq6EgoAV2ioA6BQKjE8XiIGDAhCXNwaAOYAhIiK\nCkBIyHy1nEB6OjBnjvQI4C8xNATGjWMmjakD0C/oEBCFUonx8ztY6uEPAOaIi1sDP7+DatXr7Az8\n+KPixx88CDRtqlaTFA1QZRwAIQQ/rlghU0aBLb5MCCOLR48eISAgQOb+Z8+e4UdlfmFSCA8PR5cu\nXTBmzBjxR15OgfIYM2YMsrOzyz3m0KFDKukMUTRDUpIIJQ//YswldPspVZcq4wAunziB5J9/xpWT\nJzVSf1xcHKZNm4ZLly4pdPyrV6+QmpoqdR8hBN9//z2+/vprtWy6d+8eZs6ciVOnTok/ZmZmKtd3\n6tQpWFhYlHvMlClTcOjQIaSnp6vcDoU97Oy4AL5MyCKErW2V+elTyqFKzAEQQnB5yxZsEwiwePNm\nDHR3Zz1K9s8//4SHh0eZsPTY2Fj88MMPEIlE4HA4+Pbbb+Hi4oKgoCBkZ2fju+++w4YNGyTKXLx4\nEfb29uLkJ15eXvDy8hLr7hR/79atG7y8vMqcy+DBg/Htt9/i3r17MDIywqVLl2BmZoZFixaJdYhK\n06ZNG3h7eyM8PBxCoRDLli3DpUuX8PLlS9StWxf79u2DqakpmjdvjqioKISHhyMkJARcLheJiYkw\nMjLCjz/+iMaNG4PL5WLw4MHYv38/Vq5cyeYlpqhAYKA3oqICJOYAnJ0DEBhYNk83pepRsR3A6tUK\n/f9y69YY/OgROAAG3b2LKydPYpCHh/zySiArIczu3bsxffp0DB06FC9evMDx48cxYMAALFiwAJcv\nXy7z8AeAS5cuoV+/fnLbtLS0LHe4pWbNmhg1ahS++uor3LlzB3PnzsXZs2dhY2MjcVx+fj5sbGzw\nzz//4MCBA/Dz88PFixdRp04duLu74+rVqxg2bJiEo4mNjcW5c+dQt25drFu3Dr/++is2btwIgIlG\n/uabb6gD0AOcnBwQEjIffn5b8PixCDweF5cvqzcBTKk8VA4HUM53Qggud+uGbf+NfQ8qKCjpBcgr\nzwJDhw7F2rVrERYWhu7du4tlGsqDx+MppNwpEAjEPYDSiV2KewC7du0SH9uxY0e0b98eN2/elJr0\nZcCAAQCYhC1NmzZFnTp1AAANGjQQJ6QvPX/SqlUrcUazli1bIiQkRLyvYcOG4PP5yM/PL5MXgKJ9\n7OwccOBAAExNgc6dgfv3mUlcVdm1i5F3UFaD7dkzQCBgbKDoB5V+IPDyiRPit3+AyQo56NEjjc0F\nfMn48ePxzz//oGfPnrh+/TpGjhwpdyKVw+EolNiluAdw6tQpnD59Wvz3t99+C4FAgH379pWpW1Zi\nltIPalnHlO4BlNbmKe2AgJLkLTSBi34QHg6MGgVwOMD33wMbNsjX75FFQQGwahXwRe4ehYiOBnbs\nUK1dimaQ+wtNTU3F69evwePx8N133+HZs2fasIs1Ht24gZuurljdu7f4c8vVFQ+vX9dK+xMnTsTT\np08xevRorF27FgKBAJ8+fYKBgQEKCwullikvscvbt2/x+vVrue2am5sjODhY/Gb+9OlTPHr0CL2k\nJW9VEEVXUL19+xYNGjRQKAsYRfOkpADFieZGjgQsLYGEBNXquncPcHQE/pueUgqqCaR/yP2FLlmy\nBPPmzcOff/6JQYMGYcOGDQondt+/fz/CwsJQUFCAyZMno1OnTlixYgW4XC6aNGlS7jJItlim4yQi\nvr6+WLduHXbu3AkOh4N58+bB1tYW7du3x44dOzB//nwEBQVJlBk8eDBCQkLQpUsX8bYPHz5g2LBh\nMDExgZOTk9x2uVwu9uzZg8DAQOzatQuGhobYsWMHatSoUebY8ibES+9TdOL82rVrGDx4sELHUjRP\naQfA5TI9AlXXQFy7Jj0BvCLQiGA9hMhhypQppLCwkEybNo0QQsjUqVPlFSGEEBIdHU1mz55NCCFE\nKBSSoKAgMnv2bHL79m1CCCH+/v4kJCSkTLnY2FiF6q/MFBUVkdGjR5OHDx8SQph/g8uXL+vYKsUo\nLCwkI0eOJOnp6azWm5SUxGp9FRllr8WiRYRs3cpO2yNHEnLsmOrlu3Uj5N9/2bGFEHpflEaVZ6fc\nIaDCwkJs3rwZrq6uiIqKQkFBgUKO5fr162jatCnmzp2LOXPmoE+fPnj69Kl4GaKbm1uZFTMUBi6X\ni7Vr1+KXX34BULESuxw+fBje3t7iJawU3VO6B6AOIhEjAa3GKCIVhtMz5A4Bbdy4ETdu3MC4ceMQ\nGhqKH374QaGKMzIywOfzsW/fPrx9+xZz5syRmNg0NzeHQCBQ3fJKjouLC5YvXw6Aia6tKNDMXfpH\nfr7yK3akUVQEHDigXl1jxwJy1kBQtIhcB3Do0CH4+/sDYJY0+vr6KiRRUKNGDTg7O8PQ0BBOTk4w\nMTGRiHwVCoWoLmMgkM/nK2p/pUYgENBr8R/0WpSg7LUonmKSVoQQ5eYDunaVXo+iNGki2xZVoPeF\nesh0AMHBwdizZw8yMzNx5coV8XZnBRcQd+zYUTwckJqaitzcXHTt2hUxMTHo3LkzIiMj0bVrV6ll\naZJnBprwugR6LUpg81oMGQJs2QJU1Myh9L4oITk5WekyMh2Ap6cnPD09sXfvXsyePVvpivv06YPY\n2FiMHTsWhBCsXr0adnZ2WLVqFQoKCuDs7ExXilAoOqZ3b2DjRuDIEV1bQtEFcoeAIiIiVHIAALB0\n6dIy2xRdQkqhUDTP3LlAo0ZAXJx60cGUiolcB2BlZYU//vgDTk5O4sjOnj17atwwCoWieapXZxK7\n/PADsH+/rq2haBu5y0Br1qyJ58+f4+LFizh//jzOnz+vDbsoFAoLCARAVlb5xyxcCPz9NxOkJYtF\niwC20jxkZADLlrFTF0U9FFoGWpr3799rzBgKhcIuwcGMfIMUWSgxtWsD330HvHkDNGgg/ZgLF4AZ\nM9ixydIS+PlnwM+PRgTrGrkOYOfOnTh69CgKCgrw+fNnODo60l4AhVJBUDQITMp0nUQdaWlA69bs\n2GRoCLRpwzim3r3ZqZOiGnKHgMLCwhAZGYkRI0bgwoULZbTkKRSK/sJGFPC1a0DPnoyOEFtQYTj9\nQO4/aZ06dWBsbAyhUAgHBweFpSAoFIruSU5mxwGoI/8gDVdX6gD0AbkOoF69evj7779RrVo1bN26\nFZ8+fdKGXRQKhQXY6AHcvg24ubFjTzFUE0g/kDsHsHbtWiQnJ2Pw4ME4deoUtm7dqg27KBQKC5ia\nAvXrK1cmP58RfitO+hIZye7wD8BIQ+/cyW6dFOWR6QDS0tLw22+/wczMDDNnzoSZmRm8vLy0aRuF\nQlGTiAjly8yfDzRvDhRnLzUyYtcmgJkIpkIAukemX1+xYgUaNmwIIyMjbN68WZs2USgUHTJ7NqMP\nlJena0somkZmD6CgoACTJk0CQCV+KZSqRPv2QJMmiejV6yDMzUWws+MiMNAbTk4OujatQuDj74O7\niXcl8ngQQtDBoQO2r9VthsIvkekAShv/ZYJyCoVSeeHxEvH6dRCSktYAMAcgRFRUAEJC5lMnoAA9\nXHtg/7v9yHHIEW8zSzDDgk4LdGiVdGQOAeXm5iIhIQHx8fH4/PkzEhISwOPxwOPxtGkfhULRMn5+\nB0s9/AHAHHFxa+Dnd1CHVlUcPEZ4wEXgApD/NhDAJdsF7sPddWqXNGT2AExMTODn51fmbw6HU6Ey\nVFEoVZXUVGay1dpauXJJSSKUPPyLMQefz/5IwMyZwPTpTKBZZYHD4WCp11JMOz0NOQ45MEs0w7Kp\ny/QytatMB0BlmymUis3WrUCtWsCKFcqVs7PjAhBC0gkIYWvL8lpQAGZmQHR05XIAANML2HJ4C6JJ\nNFpktdDLt39AgUAwCoVSMVE1CCww0BvOzgFgnAAACOHsHIDAQG/WbCumskpCcDgcTBw5EeZh5lg5\nfaVevv0DCgSCUSiUiomqDsDJyQEhIfPh57cFfL4ItrZcBAZqZgK4Y0cmI1llxKmTE/pG9dXbt39A\nQQfw8eNHfP78Wfyd5uCkUPQfdWQgnJwccORIALsGSaFFCyApCfj0qfJJQ49qPgrN1zTHmRdnMLr5\naF2bIxW5DsDPzw+3bt1C7dq1QQgBh8PBsWPHtGEbhUJRg5QU5WUgtE1ll4YuEBXgU57+6qfJdQAv\nXrxASEiI3o5hUSiUsohETHKX2rV1bYl8LlwArKx0bQW7EELwx4M/MLXtVLSuy1IiBQ0g1wHUrVsX\nQqEQFhYWSlfu7u4uLtegQQPMnj0bK1asAJfLRZMmTRAQoPkuJoVSFeFygbt3dW2FYtSooWsL2Ce/\nKB+33t6CdztvXZtSLjIdwIQJE8DhcJCeno6BAwfC3t4eABQeAsrPzwcAiZiBOXPmYPHixXB1dUVA\nQABCQ0PRv39/dc+BQqFUYHi8xP+CzyqP7AT/bQqE/7NF320B+NziPn6cswy9XPRvratMB7Bt2zYA\njCaQUSk5wCx5Gab/4/nz58jJycHMmTNRVFQEHx8fPH36FK6urgAANzc33Lx5kzoACqUKw+MlYsCA\nIMTFVR7ZiTLnlHEAU27+gX9P2evdOcmMAzA2NkZ+fj58fX1RUFCA/Px8fP78Gf7+/gpVbGpqipkz\nZ+LXX3/F6tWrsXTpUhBCxPvNzc0hEAjUPwMKhVJh8fM7WOrhD1QG2Qk/v4OIK+wP1I1nNjyYhTcP\ndujlOcnsATx48AB//PEHeDyeWAaCy+Wip4Ihe46OjnBwcBD/XaNGDTx9+lS8XygUorqMdV98Pl/h\nE6jMCAQCei3+g16LEirTtYiPz4U02QkeL1ehc9THaxEfnwtYZAGoVmqr4uekTWQ6gP79+6N///6I\niIhAbxXWZ504cQIvX75EQEAAUlNTkZ2djR49eiAmJgadO3dGZGQkunbtKrUsjTNg4PP59Fr8B70W\nJShyLV6/BmrWVF4HSNs0alQNt26VlZ1wcqqm0L+3Pt4XjRpVw63g4RCfkyUfaP2HwuekKsnJyUqX\nkSsFYWNjAw8PD/Ts2ROjR4+WeIsvj7Fjx0IgEGDy5MlYsmQJNm3ahO+//x5BQUGYOHEiCgsLMZim\nBKJQNMLKlUBoqK6tkI82ZSe0RZlzKixCner/6uU5yV0Gun79eqxfvx7NmzfHs2fPsGbNGoVWARkZ\nGWHLli1ltlOROQpF81SEIDCgRHZi0aItuHxZhLFjNSc7oS2sbWvCe3dNnFu9BZ8/i9C6NReBgfv1\n8pzkOgBCCJo3bw4AaNGiBQwNqXwQhaLvqCMDoW2cnBxw8mQALCyA/fsZhdCKzOfCzzCyMERU1Pe6\nNkUucoeADAwMEB4eDoFAgLCwMBgbG2vDLgqFogYVyQEAgIEB0KgR8OqVri1Rn7rmdbG853KJbX8+\n+hPXEq+Sw3LxAAAgAElEQVTpyCLZyHUAGzZswKlTpzBp0iScOXMGgYGB2rCLQqGoSHY2UFQEWFrq\n2hLl6NQJeP9e11ZoBjtLO9SqVkvXZpRB7niOnZ0ddu3aBT6fj6KiItjZ2WnDLgqFoiJCITB4MFDR\n5LsOHtS1Bexw9NFRdKjfAc1qNxNv6+2on0p3MnsAN2/exIgRI+Dt7Y2TJ09i/PjxmDFjBg4cOKBN\n+ygUipLY2AAnT+raiqqLiIjE4pmEAA8fMv/XR2Q6gG3btiEoKAg+Pj4IDAzEmTNncP78eYRWhLVl\nFAqFoiM823gi7K+myMpiemFubkDKhzzMOjtLQg1BH5DpAKpVqwZHR0e0bdsWLVq0gLW1NYyNjWFq\naqpN+ygUCqVCkZcH+PgAxetlHByA5LfGcHNwA4F+OQCZcwCl9f9LL/3UNw9GoVAoiuDj74O7iXcl\nnm2EEHRw6IDta7ez0kZ8RjwOhF9B48azUe0/JQgHB+DNGw68Rnux0gabyHQAT548wcSJE0EIwevX\nr8V/x8XFadM+CoVShUhMBCwsNCNh0cO1B/a/248chxzxNrMEMyzotIC1NrgcLtLf1UD79iXbGjZk\nzksfkekAzp49q007KBQKS8TGAo0bV8xEK/7+TGrIGTPYr9tjhAe2HN6CaBINcAAQwCXbhdWk7Y41\nHGH0whEtSjkApgcA/PPiH3zI+YDp7aez1p66yJwDsLOzk/mhUCj6y5w5FTegqmlT4OVLzdTN4XCw\n1Gsp8N8ghlmiGZZNXcZ6utt79yDRA2jdmunVNKvdDB3qd2C1LXWRGwhGoVAqFhUtCrg0zZoBL15o\nrn6PER7okttFI2//ALDp+iaMmvoWHUo954cMAdasAZpaN0Xbem1ZbU9dqAOgUCoRIhETTVu3rq4t\nUQ1N9gCA/3oBU5fCMtxSI2//9tXtMWuaOWSkOtE75DqAly9fYvLkyRg+fDj279+P8PBwbdhFoVBU\nICODGW4wMdG1JarRpAkQH89IWWiCNGEaevTtgfZN2rP+9g8wMQDlST5MPTUVqdmprLerKnIdwPr1\n67Fx40bUrFkTY8eORVBQkDbsolAoKlCRh38AoFo1ZsgkI0Mz9QdGBiI0PhRjZ41l/e1fEWa2nwkL\nYwuttysLhbSdHRwcwOFwUKtWLZibf5m+jUKh6BNDhujaAvXQpIzFriG7NFb39TfX8fzDc3zd4WuZ\nx+ibJpBcB2BlZYVjx44hNzcX58+fl5nHl0Kh6J5WrQApeZgoWsDG3AYiIpK6Ly4O4HIBJyctGyUH\nheSg3717h5o1a+Lx48dYv369NuyiUCgUVknNTkVKdgoAIOpdFPbF7mO1frPPTXB8s5vUfUeOAL/9\nBtx6ewu+Ib6stqsOcnsAu3btwvjx49G4cWNt2EOhVAl4vET4+R1EUpIIdnZcBAZ662XKQGXQhtSC\nOoTxwhCfEY/v3b5HXfO6EnLNbBAby0xgS6NhQyA8nFkKOrXtVFbbVQe5DqBjx47YvHkzhEIh3N3d\nMXToUCoIR6GoAY+XiAEDghAXtwaAOQAhoqICEBJSsXPhakNqQR0muUwS/92oZiM0qtmI1frX3JuF\nfu23Aig7TO7gwMhBWJtZw9pMAzoXKiJ3CGjQoEHYt28ftm3bhmvXrqFnz54KV56eno4+ffqAx+Ph\nzZs3mDx5MqZMmYI1a9aoZTSFUpHx8ztY6uEPAOaIi1sDP7+DOrRKfTxGeMBF4AKx4KUawVbnzgG5\nuezap2m4Cf3RqZ30RTLFchD6hlwHwOfz8dNPP2HWrFkwNTVVOCFMYWEhAgICxL2FjRs3YvHixThy\n5AhEIhHNK0BRCB4vEVOmrMHYsbswZcoa8Hh6qqqlBElJIpQ8/IsxB58vfQJRGS5dYjKC6YJiqQWz\nN0xWd3WkFpYvZzcgTJAnQExSjPh+6ts3AJ3/bxgOXv+DtTZSr06AawcDqfsaNAD4fCa+Yf6F+bjx\n5gZr7aoFkYO7uzs5evQoEQgE8g6VYN26deT69evEy8uLxMXFETc3N/G+0NBQsnbtWqnlYmNjlWqn\nMpOUlKRrE3RKfHwCcXZeQoBswuRUyibOzktIfHyCrk1TC0/P1aXOiYjPzdNztULly7svrK0Jef+e\nLUuVRyQSEdsBtgQBIF3GdiEikUilekaPJuT4cfnHKfobefL+CZly1Evyfqp3gzRsM4uV+yktjZDq\n1QkpKpJ9zOTJhGRmEvLiwwuS9TlL7Ta/RJVnp8weAI/HA4/Hw+bNm9GlSxekpaWJt8nj5MmTsLa2\nRo8ePcT5A0Sikrcbc3NzCAQCFtwXpTJTWYdKAgO9UaNGAIDiV3UhnJ0DEBjorVa9+fnAp0+akVJW\nlKu8q+jVtxcswi3Uklpo1ozdHkDLOi1BzjlL3k8p3fHm4XZW7qcLb4/C9/Cf4JYzphIcDFhZMRPB\n1U30Yzm9zElgf39/AEy3jpRKAsPhcHDo0KFyKz158iQ4HA5u3LiBFy9eYPny5cgoFdonFArLjSfg\n8/kKn0BlRiAQVOlrER+fC2lDJTxeboW+LiKRMQiZiwEDAiEUAjY2BL6+42FiYqTQecm6L5KSuLC2\nroOUFN1JDeRk5WD8gPGo/bE2unboqvK/U9261XDzpgn4/Mxyj1PmN6LJ+8nJpAEcnEUV775UpJvw\n8eNH8uDBA5Kenq50F8PLy4vEx8eT2bNnk5iYGEIIIf7+/uTChQtSj6dDQCVU9SEgdYdK9BUej5BV\nq1QvL+u+iIkhpEMH1evVJ65fJ6RLF/nHKfobOfH0BJnk6Vf2fhrrQUZPW6SmtcqRkJFABh4eyHq9\nrA4BFXPx4kVMnDgRe/fuxYQJE3DmzBmVHM3y5cuxa9cuTJw4EYWFhRg8eLBK9VCqDoGB3nB2Zn+o\nRNc4OgKBgezXq086QAMPD0SaME3l8s2bAz16sGNLflE+Tj47icC109GggeT9ZJdoivXff8tOQwpi\na2mLn4b+pNU2ZSLPQ4wfP55kZ2cTQggRCATE3d1dedekBLQHUEJV7wEQQsjz5wnE2Hg1cXJaSbp0\nWV3hJ4DZQNZ9ERlJyM6dWjamFK/SX5F1EesIIYQ8THlI8grzNN6msr+RmTMTSNu2q0m7dv5k6FB2\n7qfcglwyNHioyhPebKHKs1NuIBiHwxELwFlYWMCkourMUiokaWkOaN06AFOmZODOnZp6p6WiLp8+\nMdm7OnZUv65evZiPrjA3Mke7eu0AAC42LrozpByePXPA9u0BiI4G3r1jR5uHy+HCt7uv3AlvoRAI\nCQFGj1a/TbaQOwRkb2+PTZs2ITQ0FJs2bULDhg21YReFAoAJn+/bF2jRohAPH+raGvbh8YBp03Rt\nBTvUt6yPYU2H6dqMMpx4egLJgmTk5wP37wOuroC7O3DqFJAqSEOv39Xzmr//Yoyw3+WrfBYWAlOm\nMLMPgRGB2H9nv1rtsoFcB7Bx40bY29vj5s2bsLe3R6AmBi8pFBkUO4AmTQrw6hWz1LGiIs32Zs0Y\npciKfF7S+Jj7ES57XCRWEOqKVx9foUBUgAcPgMaNAUtLJvNYzZpA3KPa2D9cvQdxTAxQv77846ys\nAENDJtfBnE5z4OniqVa7bFCuA3j+/DkMDQ0xbtw4NGrUCMbGxjAwkB7pRqGwzefPzI+rZ08mUYiD\ng2bzxWqSzEzm4fNllK6pKTMprMk0iNqAEILxf41HfhHjyWqa1sRFz4s6tophRc8VaGjVEFFRQNeu\nJduZXgAHLeq0UKv+i8L1ENqdU+jYYk2g2ma1YW6s+9wqMh3A77//Dj8/PxQWFuLHH3/EzZs38eLF\nC2zYsEGb9lGqMDwe0KcP8+YEAC4uwKNHOjVJZX79lRmfl5ZPqXVr4PFj7dvEJkWkCFPbToWxgTEA\nZu6wQfUGamXd+vQJ2LOHLQuBtm0lh9vc3ZnkM+p0UvLzgY+REzGmi6tCxxc7AH1BpgO4dOkSjh07\nBi6Xi3PnzmHTpk1YtWoVHlf0O5VSYWjRghEFK2bbNmDECN3ZoyqFhUBQELBwofT9bDgAQoBDh5ik\n8LrAkGuI4U2Hl9leJFI9ua+hIbB4sXr5gS++uojod9EAADc3oHv3kn1t2wI7dgD/vDiH6Wemq1T/\n06eAc01nNKqr2Prbhg0ZB1AkKoLtVlsUFBWo1C5byHQA5ubmMDAwwLNnz2Bvby+O3NWHMT1K1cTe\nnhm/rWicPQvY2QGdO0vf7+am/vp9gQCYOxflShFom2uJ1zD0z6EqlzczA+rUUe+Nmfz3nzQ4HOaF\n4qtGfbFrsGqpIh8/Btq3V/z4AQOYIT8DrgEezXkEQ65CWXk1hszbhcPhgMfj4dSpU+jXrx8AICEh\ngc4BUChKsmOH7Ld/gJnknjdPvTZ0HQQ2/8J83E2+K7Gta4Ou+GfSP2rVq64m0NAmQ9G1QddyjzE3\nNoeliWpvFt2GxkEwTHG561GjmA/A5AbQRWL60sh0AAsXLoSvry+SkpIwdepUxMTEYNq0afD11Z90\nZhSKvpOXx+TpdVdeEl8pdO0Avu7wNZxrOktsMzIwEs8JqErTptqbIFdluMquuh1+GKD6vKiuR1Rk\n9j/atGmDv/76S/y9Xbt2CA0NhZGRkVYMo1AqAyYm7E5kyiIlRbGliJqibb22UreLiAg5BTmwMLZQ\nqd5mzVRf+RXLj8Xj94/h3c5b7rGLLy9GU+ummO06W6k2TA1N0bx2c5Xs+/Xur7ifch9BQ4NUKs8G\nCo8YGhsb04c/RWucOAFkZ0vfR6ehyqLrHoAsdsfsxqbrm1Qu/9VXzEcVLI0tUd+iPoqKAA8PoKCc\n+dZV3Tbg247a1QTybOOJHYN3aLXNL9HtDASFIoWcHGa5XqoUVeNDh4CoKODnn7Vvlz7j7MxMkuuC\nnVE7YWxgjDmd5pTZN7/zfLXGuVu1Yj6q0Kx2MzSr3QyPHwMPHwKy3l9FIsClhSmio5nMXcow9dRU\nzHadje723eUf/AWmhrrPra5QDyAzMxMPHz7Ex48fNW0PhYKbN4F27aSvmXd0ZML5KxupqcCxY6qX\nHzYMGDOGPXuUYUqbKRjTQnrjup7kBIDoaMkAsC/hcoH+/YHjp3KUmgd4/x5Y23sj2tpIH/6Sxfnz\nJfMaRaIiiIiO1u5CAQdw4cIFTJgwQW05aIp+UjpHqr7k3C2Wf5CGiwuz9E5X690VRVlph5wcYOlS\nzdiiaazNrFHPQvb408fcj8j6nKVFi4APOR8w7wKztOrLCGBpuLsDqxN649XHVwq3MWUK8PimndIR\nvSdOAJGRzN8d9nfAy3QdhoHLkwulctC6Q9Ny0Pqac7dbN0JCQyW3lb4WDRoQEh+vZaOUQCRiErPc\nvat4maIiQszNCcnIkH9sRZMJ97nkQ04+PamRumVdi6zPWeTci3OEEEJatyZE3mMlJ4cQy+pFJC1N\nsXZFIkJq1ybk3TtlrGVYvbokIVBBUYHyFchAIwlhqBx05UUfc+5mZzPjtd3LGVJ1cYFeK4NGRDBv\n9G2VGBngcpmx7idPNGeXJohMjMS4v8aVe8y2QdtkDhFpiuom1TGs6TB8+gTExwNt2pR/fLVqwKCB\nXJw9q1j9SUlAgX0IvotRXsq1OBoYgM4DweS2XiwH7erqitjYWCoHXYlIShJBWo5UPl934yt5ecCW\nLcwPUhZt2gCvX2vPJmXZuZMJ/FI2KrdYEoKtTFjaoId9D7SorZ6Ymjzu3wdu3QLmlJ1jlouZGTMH\noMgCxomTRLgfxwcgfyb43j2gs01vbB6o3Pg/IKkHRAiBsECo8jJZdVFaDnrdunXasIuiBezsuChJ\nj1eMELa2utMTsLYGZstZir1+PbBkiXbsUZb4eOD6dcDLS/myqmoCffoEHDyofDk2MOAaoI55HbnH\nPUh5gNyCXJXaEAqBP/5QrszY42ORkZsBQ0PmuipCvyFZOG0xRKHgrHv3gI7tjFHXvK5yhoFxAG/e\nMH+HJ4Rj0olJStfBFnJ/6Rs2bICnpyf8/f3h6emJ7777Tht2UTTEmTPMhBchFTfnrj6rkQQFATNn\nSl/BJI8BAxhdIGXh8RihPF2g6KqZrbe2IjFLtQUGxcFgisZ/EEIwx3UOapjWUKqdmtVq4tGcRwqt\nXCosLH+Ysjzs7YGpU5m/+zr2VVsuQx1kDgEFBwdjz549yMzMxJUrV8TbnZ2dZRWh6DHv3gHz5zPq\nhXv3MkJYTk4OCAmZDz+/Lbh2TYQaNbg4fXo+nJwcdG1uhcXcHPhWxXii1q0Vf1stja6CwPIK89Bg\newPwF/NhZFD+GMuhMYdUbsfamrlfP3xgxOHkweFw8FUjFaPHFGTtWsB1vytafDyGxrUaK1XW2BhY\ns4b5W9fLZGU6AE9PT3h6emLv3r2YLa9PLgWRSIRVq1aBx+OBy+VizZo1MDY2xooVK8DlctGkSRME\nBASoZTxFPkVFwE8/MTfsvHnA0aNMEpJinJwccORIAE6cYIYRKlvOXW2jixFSXTkAE0MTvFn0Ru7D\nX104HEYT6MULxRyAOgjyBHgvfA/nWvJfdK9OvcrK2L0gTwBDriGqGZUz8aUh5A4BqfLwB4CwsDBw\nOBwcPXoUCxcuxLZt27Bx40YsXrwYR44cgUgkQmhoqEp1U6QjbU3/iRNM0ovr14HVqyUf/qXp3Bm4\nfZvKLKiCrmMpdCkDoehDq1BUiPMvz6vcjjKqoP93/v9w/c11lfIIRCdF4+fbioWZW5lawYCr/njk\n7POzEZEYoXY9KsHaIlQpFBUVEUIIOXXqFFmxYgVxc3MT7wsNDSVr164tU4bGAZSgzHpvWWv6X79O\nICKR/PIiESH79xNSwN6yZKXx9iaEx5O+78tr8fkzIXy+5m2Shy5iKb68FosWEbJ1q8aak4kgT0BE\nitxchBCRSETGHh9LcgtyVWrr9m1Cnj8vu13abyTuYxzJzM0k8+cTsmeP8m09eULIzp3lH6PoeWsT\njcQBqAOXy8WKFSuwbt06DB8+XGJ23dzcHAKBQJPNVylkrekPCDgIRYYZORxg1iwmC5MuyMoC/v5b\ncUXLq1dLJtJ0iT7EUnTtqvqEpDq4/88dN9/eVOhYDoeDv8b9pbL+jasr0wtQhEY1G8HK1ApRUarN\nqVhaMkOm5YnH7b+zH4suLVK+cj1D7s/95s2bKCwsBCEEgYGBWLhwIUYokZdv06ZNSE9Px9ixY5GX\nlyfeLhQKxVnGvoTP5ytcf2VGIBAofC3i43MhbU0/j5dbIa5nSIgJ2rWzQHp6utT9X16LunW5ePCg\nDvh8KYpxWoTt687nc3H0qDmWLJH9cvTltejVq7is0s2pxe/9fgcB0en9Jes38vkz8PhxPdSvnwo+\nX7lxzcTseNg0rYeTJ2ugV6+ymh4hISYY0Gs4+tftr/K5v3ljgMhIE0yZwugPpeSkwM7CTqW61EGu\nA9i+fTu2bt2KNWvW4OjRo1i0aJFCDuDMmTNITU3FN998AxMTE3C5XLRu3RoxMTHo3LkzIiMj0VWG\nQIetra3yZ1IJ4fP5Cl+LRo2q4dYtISQfRkI4OVWrENfz4UNg0CDZ//ZfXov69ZmleAYGtrCx0ZaV\nZWH7upuYAAcOAFu2WMrsuSlzX+gT6TnpiEyMZDUq+MtrseXmFhhwDNAVPmjRAnB2Vj5Jwom3J9Bh\nWANERo7BhAmS+4RCJk4lK4tZzaMq6elMbIOvbw0kC5Ix/9J8RH0dpXqFAJKTk5UuI3cIyNTUFNbW\n1jA0NESdOnUUXrY0cOBAPH36FFOmTMHXX3+NVatWwd/fH0FBQZg4cSIKCwsxePBgpQ2mSCcw0Bt1\n61a8Nf3F/PuvbAE4aXA4jCTEo0caM0khAgO9YWnJ3nW3tgYsLIC3b9mxT1N8zP2InIIcpcoUiAoQ\ny4/VkEUMczvNxdS2UxUSgJPF/C7z4TduDE6dKis6+PAh0LIlwDFQL5l7sRwEIUB9y/pqP/xVRW4P\nwMLCAl9//TUmTJiA4OBg1KpVS6GKq1Wrhh07yiY7OHz4sPJWUuTi5OSAnj3n4+3bLbCwEMHWlovA\nwIqxpj8zE3j1CujUSblybdowDqB/f83YpQiOjg4wN5+P3r23QChk57oXRwTrs+rK7/d+B4fDweJu\nixUuU8+iHtZ/tV6DVgFmRmYwMzJDQgLQrZvq9TRtCtSqxchIlK7n3j2gXXuCulvqImlxEsyMzFSq\n38qKmW/LyGDa0RVyHcDOnTvx5s0bNG7cGC9fvsS4ceULP1F0AyFAdLQDwsMD0KSJ6vXs2MFo7o8e\nzZppcrGyAp49U75L3b07E+CmS169AgwNHXD2bIBCk+2KUOwAhg5lpz5NsKS79rU4fvuN0YiaJEM5\nQURE4IADDoeDnTvVW9J86fUlHPmrO1o6S85T3rsHdGjPwb45aWoLuRVrAtWqBbwXvgchBDYW2h3P\nlDsElJGRgb1792LGjBm4f/8+nj17pg27KEry4gUjkdBYuaDEMhQVAdoOz+BwADsV5r8mTQKWLWPf\nHmUIDWV6IGwGdLZurbgqaEICEBwse7+Pvw96T+uNPt59xJ/e03rDx9+HFVuV5fH7xzjzXLWcItnZ\nTDyLLK7GX8WY/5XML6jzbxLGC0P1eh/KvJTcuwe0b8+OimdpVdBDDw7h/CvV4yRURa4D8PPzg4eH\nBwoKCuDq6or16zXbhaOoRmgooyWj7oOoOCCMohj377M/BDV4sHxBvNLtHz8ue38P1x6INYhFhFOE\n+BPLjUXPTj1Vtk+QJ0B8RrxKZYtERUrPHRRTHA0si/6N+iPYvRxvqAQ/DvgRjWo2KrO9Tx+gcQvl\nMofJYu7ckqWtS7svxYz2M9SuU1nkOoDPnz+jW7du4HA4aNSoEc0HoKeMGgUsX65+PR06MOPqyma0\nqqrs2yd7SEJVbG0VH7+WFwXsMcIDLgIXoHg4hAAu2S5wH+6usn1P0p6onOi9bb22mOSi2gWTFw3M\n4XCUzs6lLFu2APsebsWWm1vUrmvIEKCFZpW05SLXAZiYmODatWsQiUS4f/8+jNVZ+0TRGPb2UGvs\nvxhzc2YYSZ8TrugTHI7yuv9sIs8BcDgcLPVaCrM3zGSlWaIZlk1dppYIWdcGXbF/xH6Vy6tKw4ZA\nWhqzFFMawnwZO1QgpyAHhx5IF7Dz6+0H3x6+rLUFMAqmMUkxCklRs4ncWzcwMBAnT55ERkYGfvvt\nN6wplrGjVFo6dQJiYrTTVmqq/uf31WcU0QEaPmQ4Wn9qzcrbPxv88+IfXI2/qnQ5AwOgUSPpyYCy\nPmeh6e6mKCgguKlYcHK5GHGNxA/kDx+Y1Tql0YSKp2+Ir8rDY6oi1wFcu3YN27dvx/nz57Fr1y6E\nhYVpwy6KDlm3TrWEJqrw1VfAnTuql8/IYGIIqirJyfIdwMXXF2HQxAAGIQZY6LlQ7YfXvwn/QkRU\n99o1TGvAytRKpbLHjgHSFOmtTK3w1uctnjzh4OuvVTZNjJGBEXYP3Q0OhwM/PyY4D2De1NOEaeo3\n8AUcDgf/ev+r8SGsL5E5lX3u3DmEhYUhOjoaUVFMkIJIJMLLly8xVR9EWChq4+Pvg7uJdyUeCIQQ\ndHDogO1rt2u8/ffvmWWc7dvLty8vLw8mJiZl7Hv/nknAEhencXNZg83r7u4uP/fwmBZjMCxwGPzX\n+2PiqImqmCwmtyAXP974Eb0deqtcRy+HXiqXdXGRvY/L4aoVACaLbt0SsXjxQVy8KIK1fS7udziJ\n14v0OCepEsh0AL169UKdOnWQmZmJCf/FQ3O5XNjb22vNOIp8iopUH4fu4doD+9/tR45DSbfTLMEM\nCzotYNFC2UREAD17yhagU8S+xo2Zt2CBgBHx0hbx8cxEefPmypdV5LzevgV8fBiBvPKYpmBOcmND\nY2wKUG3itjTVjKrhgucFtethG76ADxtzG0RFGbAmjPcy/SVCHoZi25p4pKevwb//mgMQwvmmCLxR\niawEWa5ZA8yYwczhpWSnICM3Ay3qaG9mWOZjw8rKCl26dMG6devQoEEDNGjQALa2tihSRWSbojEu\nXWLeAlVBEytElOHff5lldbJQxD4DAyY0X9F182zx88/lL78sD0XOq04d4Nw5oJR+okq8F76XGLII\n54Xjj/tKJtjVABuvbcTDVPZWGkw6MQm8TB6rPQAREeHI8SuIj9ec2mtkJBMECQB3+Hdw7uU5VupV\nFLnvjT4+Pli8eDEWLVqEsWPHYom+ZuOuooSGMmv3VUETK0SUITy8fP0fRe1r00b7q5ZCQpi4C1Xg\ncDgYPGgwDOKZZCLSzsvUlInIVjQJiixC40OxJ3aP+Ht9y/poYq36crEwXhjSc6QrtipDlwZdUNus\nttr1FBPhHQFrTmPw+UCrVuzU2bx2c5g+bwsJoT/zVMCQCz6fnZULpRPED2s6DMt6aDeyUa4D+N//\n/odjx47h+PHjuHTpEurWrasNuygKUhyJqioeIzzEK0RaZLWQeAstTw9dXfLymGV97drJt6/4bVlW\n70TbonCpqUwEp7LaRSIiEi/z85vhhw7CDuWelzIRwbKY7DIZ/r39xd+b126O7vaqj5FcibuCjM8Z\n8g+UQz+nfrC1ZFfRNDMTWLCA6RWyhZ0dFyVCfwB6bgKanIStLTtrf4vlIHSFUmdhaWmJt/ouU1iF\nSE5mJlE7dlS9DkG+AK9rvYZluCVWTl8pfgtNSFBtfFtRTEyY4St5P9biXoBFmIXM3knv3pq19UvC\nwpg2lU2eM+vsLFyJuwIAMOAawHeaL6qFVcO4keOknlexJpAmKBQVqlRuU/9NSidBZ5vJk4GoUuKZ\nvAweMj9nwsmJ/ZzMvb+xg233GRA7gcvr4Jx/jzWV3dJyEAAQkRCBT3mfWKlbEeTewhMmTACHwwEh\nBB8/fkQ3dST2KjC6XjEjjatXmSEUdd54qptUx9vdb7F241qJt9CGDRnN8rQ0zSfiLo8Ddw7AyN4I\n07pMwyOLR2j2vhla15VM89ShA/PRFqoO/6ztuxb1LErWbHqM8MCRkCPo0aeH1ONbtwaOHJFd3+3b\nzIcQF3sAACAASURBVMNj7Fjp+x+/fwxjA2M0tW5aZl+fg32wf8R+tKzTUqlzYBOP4x74deSvqGFa\nQ6lyhobMuHnxWP/v939Hx/odMar5KNZtbNKwMX7eYYO/dm4Bn8++yu6XPYATz07ArrodqptIT5bF\nNnIdwLZt28R/m5iYoHZt9sbtKhK6XjEjjcREJpxcXcyMzbApYBPuJt9F67qtYWxgDC6XScN3+7Zu\nVSmHNBmC/KJ8DPQZiBd5L1DHTIfe6D9cXRm9HnmkCdMw4+wMnJpwCoZcQ9hVl1S843A4OB10Wmb5\nQYPKT/V4/Xr5DuBh6kMYcY2kOoB/Jv2DmtVqyj+JUkS9i4KpoSna1ZMzbqcgi7osgomB8tIyzZpJ\nagKt7buWFXuk0cexD+AIjDoyArkFuUjOToZTTfYk1tu1k5Rw2TVkF2t1K4JcB8DlcnHu3DmJdI7z\n5s3TqFH6iMcID2w5vAXRJBrgQC+iKr//Xr3y+UX54Av4cKzhCADYfHMz1vVdB+daTKRN585MRLAu\nHUCD6g0AAPxcPvo6KZExRoPMnVvyd3k9w21rtsHPzU9l5UhLy/KXtsoLApvsMlnmPmUf/gCQ9CmJ\n1UAlVeMBmjYFjh5lzQyFicuIw+p/V+Pv8XLW5ipBrVq6/X3JnQNYuHAhsrOzUbt2bfGnKqLrFTOa\nIO5jHOZfnC/+ftTjqPjhDzCTnLpUBs0rlL4GUtt6KeUhTW0zmhONnp16gsPhoLOd/CVa4bxw7Lm9\nR+5xX6KIDER5ZOdnI+qd4pmoPFp6YHBj3WfxK90DSMpOwvMPzzXaXkB4ABIzE9G6bmtWH/7SSBOm\nIYynPbUFuQ7A3NwcPj4+mDhxovhTVfnU4BPIa6IXb/9s0KJOC/wz6R+Z+zt3Zt4y2eavv5hAqvIg\nhKD9vvZI+pQksf38y/OYeXYm+0apiLQ1/U0zmip1bzjUcEBHW+Vn8stzABdeXcD9lPvllucL+Pj9\n3u9Kt8sWH3I+oO8fyvfqGjdm7p+iIuBJ+hNcfn0ZwcGamzDvZNdJ5cxfyvIx96NWHYDcvmmTJk1w\n/vx5tGjRQvy26+TkpHHD9JFhTYchb04elu9djmVLK/bbvywuvLoAV1tX1DWvCzs74O5d9urm8RLh\n53cQJ06I0K8fF7t3e8ucTONwOLjzzR1UM6omsb2PYx+4ObiVOT4zE/j9dyZ6VptwOBwsmLQAs87N\nQo5DDswSzRDwdYBS90ajmo2kas/LozwHkFuQK3elT1Prptg3Yp9CbcVnxCP6XbTKUs7SsK5mjZ2D\nd4IQotT1+n6TD9qPuYt+MzjIz2ckQmJjT2J4tw44doD9BRnDmw4HADxLewZ7K3tYGFuw3gYgOZzY\n51AfAJpfaCLXATx79kwiCxiHw8GhQ9JlUis7NhY2mD1xNhJfJlb4t/93n94h6VMSujToIrH9YepD\nONZwRF1zduM9eLxEDBgQhLg4JqrywgUhBgwIQEiI7BUVXz78AcgcgzYxAb77Dpg3DzAyYtNy+dR0\nqYlqP1VDTsMcjfQMCZGe6Gf+fEDWu5hHSw9Wbcgvykd+EbtJIjgcDtrYtFG6nLQFGcg1w+ghml2Q\nseXmFvxf5/9Dh/qaWXKmk4UmRAMUFBSQZcuWkcmTJ5Nx48aRq1evksTERDJp0iTi6elJVq9eLbNs\nbGysJkxSG5FIJP47RZBC4j7GabzNpKQkqdtfvSIkIkK9uq8nXiebb2xWrxIl8PRcTYBswjzOij/Z\nxNOz7L2Q9TmLPEx5KLHty2sR/zG+TLlmzQh59Ihdu0tz4AAhJ05I33f89HFi6WZJ/j77t0p1v/zw\nkgw6PKjM9nfvCGncWHKbrPtCVQ7cOUAiEyJZrVOTiEQi0mVsF4IAEKwGQQCIefMuEr9RNhHkCcj4\nv8ZrrP7QUEK2b5d+Xl3GKn5eqjw7Zc4BLFjAeJ2ePXuW+cjj7NmzqFmzJoKDg/HLL78gMDAQGzdu\nxOLFi3HkyBGIRCKEajvxrJqsvLoSGy5vxJQpa9Dn69mYsGoeeDzdhPD9+Sdw9qx6dfRo2ANLuy9l\nxyAFSEoSQSKkHgBgLjWk/mX6S+y/IzvhSKGoEB7HPcoEzLi4aFYSIjiYkWiQxtiRYzG331yV3/4b\n1WyEn4f9XGZ7/frMPExmpuJ17YjagbvJio/dNbVuivqW9RVvgEWuv7kOj+PK9Va+XJBh9NoMfZpr\nZkjWx98Hw2YNw5PjTzSWUzk3F7hypeS8jBOYpFtaWWiitMtQgJycHCIUCgkhhHz8+JF89dVXxM3N\nTbw/NDSUrF27VmpZfe0BPH/1kjg1m1/qLTabODsvIfHxCRprU9abXq9ehFy6pLFmyZEHR8q8gauL\nMj0AaSjy1rt2LSErVqhrqXSyswmxsCBEIJDcfi3xGknNTtVMo//RuTMh16+XfJd3LULiQsi7rHes\ntV9YVEh8r/iSIlERa3UWk5OfQz7mfFT4+NTsVJIiSJF4W67p0oX8+adm3s7/OvMXMZtuxryR//cx\n8zZTuacnjYcPCWnZkvm79Hkp8/ZPCMs9gJUrV8r8yKNatWowMzNDdnY2Fi5cCB8fH4mle+bm5hAI\nBOx4MC0RuPpP8F5shKZUARUlO5uZmFWgIyaTiIQIhPPCZe43NzaHAbckvPjJE+DDB9XbA4DAQG84\nOQWgRFdFCGfnANZC6gHNisJdu8ZEG1t8Mf93Nf4q3n16x1o72fnZZbYpKwnRv1H/MkFniiBr0ji/\nKB/2VvbgctjPfVnNqJpSMQm/3P0FofGh4HA4WOzJSITMHbsMX32lmbdkbSjmFstBMHM9TC/AMtxS\nK8vMZU4CP378GJ8/f8bIkSPRvn17pddeJycnY968eZgyZQqGDRuGzZs3i/cJhUJUry471JnP5yvV\nlqbJ+JyBuPgcSAxh1H4OGH4Gj5erMXsFAkGZuq9eNUGbNhbIykpHVpZq9aZ9SIOIiMA3kW535+qd\ngYKSfwc/vxro1SsPEybkqtYgABMTI/z553j8+ONapKZyYGND4Os7HiYmRhLneIF3AY2sGqF5LUlx\nH2nXIjY1FpZGlmhWqxkAwNGRi+HDjcHnf1bZTlmcPl0dnTuLwOdLPqBnNZ0FEHbu2SJREbr/rztC\nPEJQ3bjk92Fvb47oaAOMGMEMeUm7FuqSU5CDAScH4KrHVZgalh3ncm/grtHfZaGoUGbAXHpuOqyr\nWQMAvJ29AQDv3vEx02sMxk29gjkzu6KwkA9NmTdj2Aw8iniEHEdmldfM4TORrMD6aEII9m7ciNkr\nV8p9kBsY1MPTp6moWZOgW8du8OzkiZ0pO9EqoZXEvcA65XUPXrx4QTZv3ky8vLzIrl27SEKCYsMd\naWlpZMiQIeTWrVvibbNnzyYxMTGEEEL8/f3JhQsXpJbVxyGguefmkh7fekgOYTQ/RdD6N4WHMFRB\nWlffx4eQ9es11qRUtm8nZM4c7bT158M/yePUx2W2S7sWRx4cIaFxodowi7RtS8jNm5pvJ78wv8y2\nK1cIGTKk5HtSUhI5e5YQaT+h6aenk0epqs2EKzMUwyZB0UHE94qv1H15hXnE5WcXkp6TXmZfq1aE\nXLmi2eE3QlQflrn4119kkaUlufS3/OGiNm0IuXtXctvtpNtKDbup8uxUeA4gJiaGzJ8/n4wbN07u\nsevWrSM9evQgXl5eZMqUKcTLy4s8f/6c/H975x0WxbX+8e9SLDSjXmswgAaj6FWjIBqNNUaM0QS5\nEQu2aG5MjAZ7+6koBoySaG6iseXaMBoRsRvERMGCigXEhl4BESmiWOgszPv7Y2DZhW0zO1tw5/M8\nPDLsnHNeD4c5c97znu/r5+dHvr6+tGjRIpWdaIoTABHRgwcpVK/ebKPvARw6RJSUpLcmZWy5uoWO\nJB0hItb/7O6u/zbVIXTkC1cePSKSSquuC0sLaU7kHL1FhshTXk4k38zjx4/pm2+I1q2reW9CVgIV\nlBYI2v7yM8v1GvVWLC2u0Y/F0mLZ99JyafUiRETk7U20cWPNiUEfhB0K4xTlxTAM+Xt6EgOw/2oY\nJ5cuET1/rpuNfJ6dGs8B5OfnIyoqCkePHkVRURGGDx+ucVWxePFiLFYiVLNr1y5+yxQTwNraGXXq\nTMenn4YgK4tBs2YWCA4WThVQW7TofrWsu7gO3Vp006jD4t7SXaZI+O677D5ASQkbb2+OODoqXksZ\nKTo27agXH+2dnDsKipDK0n1mZSnfB+ITV69Qb34WnhU+Q4emVVlVOjXrxFmxU1uUaSk9K3yGcqty\n3P79NgAodQ2lpDxEUtJ2XLlSirNn61TsMenvb9FnmA+uXL+ite8/MjwcXomJkAAYnJiIkwcOYLCP\n6mgnVUmdGGKQ+iKV10FBrVA1Mxw7doymTZtG3t7e9Ouvv9KjR490mp20xdRWAInZifSq+BX98APR\n5Mnsz37+mWjqVDaWPjpVx4B8Nejjrffio4v08MVDzuU6d2bfUvgQFUVUVqb+noLSAhq6e6hSFwiR\n6r5Izk2mhacW8jPMRPnq6Fd0Of2yys8fP35MvXvXPAsixGrkwO0D9NPFn3SuR1tURdmEhoeqLJOc\nnEpt2hh2Nc4F+bd/ArReBSjjeuZ18t7rrdW9gkYBzZo1C8nJyXB2dsa9e/ewdu1azJ492+xSQm6+\nuhm3cm5h717A15f92eDBwMGDQEFpMYqk/DdGjYGnoyfeavAW53ITJ7LaK1yJjwcmTQIYDRn0rC2s\nsaD3AlhbcjvG28yumVaCa7WJDUM3wONN9enGlMlAvLvpXTx8odvZFO/23pjhaTiJc1VRNmO8VSuZ\nLlmyXXainMU4EXmqkH/7B6CwCuBKl+ZdED4yXFD75FHpAjJXuYfq/GfIf/DgARumVZm/1tWVTZJi\nmz0QvZTn8ngt2HJ1C16VvMLs92bD359fHT/9BEybplmewdrSGr3f4h7bamNtg0/bfSq7lkqBsWOB\nvXuVu06E4JfLv0ACCaZ1n6afBrRA2QTw94S/0bAed5lndfx27Tc0tmms0MdCUhn2OOHgBJmWkqbw\nRy6HCo1B4vnzyHd3R2w1iXC7c+fUuoFUoc9QUJUTQHe+mcZfQ2xsgK1bFVMAjhgBHDiAWjUBjPhj\nBFb0X1Ejo5Yqhr0zDHUs6/BuLzubXSn973/q7ystL4W1hbVOA50qwpStrSWIjWUnbCE0C3NygIYN\nFX/34zqNUxqvLyRxj+MgkUjg3tIdALuCyshg9yIYBli7tmaugEb1GwnW/vyo+ZjVcxZ6OPZAXSv9\nbvzI59rQJsa+Kk+v/CRQIFieXl2Zu3Yt8Pw5O3Aqyc4GmjXjXefJBydRxpThI1dhkweYRo+ZKIeT\nDuNZ4TO0aAEMG6b4mbc3OwEcunsYx+4d07st27YB69frVscPH/4A10auWt/f3K65Tg+VjRtZt1nj\nxurv23Z9G+afmq/+Jg147fZC4hM2M7yQkhBffgns26f4swb1GvA6aMWFzPxMPCl4Irt+/hxwc2Od\nyhYWwJQpigJxuUW5grU9c+lMHNt8DCO+GoFp86ZhyqwpgssfyMP18FNg4ES0aaPfQ4U68fgxmzS6\n8uyUVMpeazj82q8fKwuhDIe6DnrZiOeXqshMiH0UK3sDq06nTmx0jA3THI0cdEjKqyUHDwKjdVTi\ndWnI75VYWi7l7JsvKQF+/ZVNoK6Jf3f7N4rKdNtL2f7Jdlm+3U6dgMRE4BMdU8SWlQGnT7P/j0py\ni3IFfdNWxfB3FMO9GjdmTyE/elQzGX05Uw73ze6InxovSC5ZY6hScomycXFxQlTUdCxZEoKUlCK4\nuNQXNE+vzrz5JnD9etUMbW3NJjHWMLGlpwNpaWzCm+r0cOyhB0OhHy0gXTC1KCBjUhn5IpUSNWhA\nlK3DmZciaRGvcjvid9DXR7/mXE4qJfrrL15NKoVLRFRoKJEWx1U0cvEi0T//WXXNMAx12diFUp8b\nJ9pk0CCiY8eU94WQ5xF0VaU0JMY+HyIkAwYQRUaqv0daLhX0DJXoAqoFXL4MODsDTXlK9DPEoO3P\nbfGimIOkZAUjO4yUJapOTQX++1/tyllZAQMGaL4vPisexWXCSDeUlJUgMy9TtgLQlVOngA8+qLqW\nSCS48sUVOL1hmDfNG9k38J9LVUnCO3Zkz2MoQ8iNwtcx/anBuHMHuH9f+WfXrqn+DICTE7sCUMfw\nPcNx+fFlHQxURJwAVPD9ue+R/Uo7v+q269uw9+ZevdlS/UHEFQuJBe5Pv8/Lh1jPqp5MGK6sDAgI\n4G+HMlafXy2YmFrojVBsuroJ7dqxeya6EhVVs9/lRfL0TeP6jfF2o7dl16pE4S4/vgyGhI2AkQ/P\nfB3SnxqM+HjVibSvXVObC9XJiQ1eUMfuEbtrJHHSBXECUAIRwcrCCmu+s0NIiOb7e7bqCc83hful\nVCc6WrcJAIBOkRxlTBky8jLQpg2rRpqVpZst8vzu87vCQ04XPn/3cwT0C4C1NdBDR5cpEdCgAdCn\nIvvki+IXiE6N1t1IDrzp8KZC1EeXLuwG8M6dNjh/nv1ZXkkeFv9d89S9rhhalfK1YfRoYIyKMwxT\nprCHiFRQqQqqDi7KqdogTgBKkEgkmNVzNsL21sGgQZrvb/ePdrw3WLXh6FFg4EB+ZYkId5/e5azm\nKs/JBycRcCYAEgng4aH6BcfYCOsGAQ4dqpJ/TnuZhsgHkYLVz4euXdmVzV9/1UNuxeLUvq49osZF\n6UWq2WeYj05JbkS48cknwMqVmu8rLS/FkaQjgrQpTgAquHiRjf/vpIW0SmAgG52hL+rX55/n9mnh\nU3xx5Aud2v/I9SNsHsZm6NI0AZw7x64SNJFblIsNcTUzYOlKcVkx9iTuEbzeTs06IWhgkOD1aiK3\nKBcDdw5UmMBzcixUJoMXEolEglXLVolv/9oSGMgeHFFHairw3XdKP2rUiF0FaIKIsP/OfpSUlXC3\nsRriBFANhhiMDh+N3X8UYdQojZFbAFi33vQ9IdhydYv+DeRIE9smODvprGB/xB4e7Ka0MvLy2LeY\nZ88011NQWqD5Jh5YWVgh5mEMpOVSvdRvaBrWa4iQQYp+yCdPLNG8Ofsm+Hvi70ayTEQBIjZWt0ED\n9fc1bsxGdOhAXau62PHpDkEO6IkTQDUYYuDrNgYH9tWXaf9oYsQIIPvUGIzsMFK/xhmRl8UvcSn9\nEnr3Br5QsaDYvp2N/HHSIkimVYNW+Nrja0FtBNgJ4NePf0V6Wgb8/Jajf/9l8PNbrlP+5p0JOxH3\n2Dh+L4lEgndbvAuJRIKUlIcYO3Y5srKWY9685YhPSkB8VrxR7BKphkQCfP01UEfDyXl7e1arxFTg\nHDiqZ0zhHEBaGtHIkdrfX1TExuk/eSKsHbrGOOcW5tLJ/50UxJbbT27TtGPTVH5eXk709ttEZ88K\n0lwNuPSF0GqRx+8dp7s5d3mVFYq79+9R6zazTFYB01i8TucAuBL7KJZmR86WXYvnAASiVSvgjz+0\nv79ePeDDD4HDh9lTmbqSkvIQfn7LMWzYz/jsM/5vr5n5mTibdlZnewCgfZP2+OWjX1R+fvw4u/pV\npY00c+lM9J3QF/0m9kMb7zboOLKj3uQFhoz0xYP6EUDb3oBTP8BpKB6UXUT/4b4oLVVdrrLf27df\nhuHDq/p9iOsQvPMPJcczDUjP/76P5NxJMFUFTLPm3DlWM4QLw4apPtShJe3/0R7jOo3TqQ5RCkKO\nF8Uv4BXqhdjJsZx95iNGAItPL0TxPx11UolMSXmIQYN+lsndXrtWgOvXlyEqivtRd7cmbljRfwVv\nW7iwbh3g7696z8SQ8gKWZa2ADglAe7mY69s2yDo+FJcuAe8ryYVTvd/v3i3A7dv8+l0fdLz0Oc4+\nlxPxs8sEOuwzGQVMs8bDg7vQ208/KfWVrl0LWFoCM7T4s2hQrwE6N+/Mrd1qiCsAOezr2GPHpzt4\nbZgOHw4cm79YZ7+2KWud5xblIvRGqNLPliwBRqrZAlGl+66PEMMubh2A84pt4UIH+Ax3U/rwB4CB\nA5X0e9o8dN/UG6XlapYNBuKtFnVRJX4GwKIcKLYxGQVMs6ZuXVYjngutW7NP+mrUqcMeJuZCXkke\nnhc951aoAnH0yGFpYcl7qW9jA7RrbadztI1QWufXMq8h4k6ETrZUx1JiiTs5ykdn377q978kEgl8\nh/ui/sP6APQrL7By5SQ0RTPgDitlgDv10AzNsXLlJJVlHByU9Lu0CVrf/FgnSWyhCAycCKcOc4B6\nFaemXzVEm/wk01HANFdevKhS/eRKeTlkBzoq0OY0sDwzl85Eh886oOe4nrxM0OsEkJCQgHHjWB9V\nWloaxowZAz8/PyxfvlyfzfKCiAQJHSwpK9FJK75K61we7lrnEkgEly1oUK8BvhvIxjB/+SVw+za3\n8k06NYHjE0e9ywu4uDghNvpnNL7XECDA4b4dLkT/R60rp2NHZf1eCNc3DBBwrwUuLk74YFkZ+o6f\nh/feW4CxY0NMxj1l1syeDUTwfNHauhX48UeFH3GdAHq598KzfzxD0j+T+Nkg4Ka0Alu2bKGPP/6Y\nfH19iYho6tSpFBcXR0RES5cupaioKKXljBUFlPQ0iVxDutJ//6tbPTOOz6Cd8Tt5l09OTiVbW9PN\nd1qJnx/R1q3cy4UdCiP7Pva0//B+TuX4RHtUb6u0rJT+vP+n0ntrRA5ZZ1NrV3+T63ciouPxxykw\nOtDYZpgERo8CYhjNCa9VUV5e40cvXhDZ2rLVatd8lXKrSUUBOTk5Yb1cBpNbt27B3Z3V1u/Tpw9i\nY2P11TQv2jZuiy7XzqJYR2HKdV7rMK4z/515Fxcn7N8/HaNGhRjsTY+IsHrBAq3kIvJK8jA/aj5c\nXB5i1SrNcfYrolcoCOUZUl6gelvpr9JxOOmw0v9npcb82LEh6N9/GXpOnoo+gS9M5g1bPopqSdAS\nhG8I12uSFl3gMp6MgaD2SSRKfflaoSRnaW7uQ5SWLsf772t3fkUikWD84AmwvM9TKoDzlMGB9PR0\n2Qqgd+/esp/HxsbS3LlzlZYx1gqgoEB3zX0idlK/f18Ym/i+3Wy7vo0i7kRoff+JsDDyt7enP/dr\nfitnGIYCT6yklo4ztVqlpDxPoVfFrzjZrwx9vOndenKLyspVv72p+8zQhB0KI5tJNqw+f8WXzUQb\nzispQ8BlPOkKn3EhiH0MQ3T8OP+3/0qKi4kOHyYifudXkpNTqXXrWQRHD9NaAVTHQm62KygogIOD\n7pmLhKK4rBi7D2XD05O/5n4lmZmAx8B0ZLzQoAmiRzxaesCtiZtW9xIRIlevxo95efhzzRqNb0US\niQR3Q8uQkR4IVZFKSU+TZPsgzm84w76uvdK6jM2K6BW4naN6I8OQ0s+aMGQUlS5Qfj4iZ8/WejwZ\nGiJCZEiI7vbl5QE7d2qnFaMOiYTNOSqVqo0A/OYb4N//rvm1aNF2JCevALLn8WreYOcA3NzcEBcX\nBw8PD8TExKCHGr3ejIwMQ5kFAIjPiceSi5sw32s7MjJ0S00okQD1ev2KH/e3x6yPtMiIooa8vDyt\n+2JZyDLczKwpFt+xRUcsn6N60/3M0aP48OZNSAAMunEDe7duRd+hQ9W2lZxcBGWRSikpRcjIyMC6\nS+vQz7Ef3n9TRcwlD7j0hbb8+N6PQDk73havXoxbmbdgaWGJV6WvYGttC0uJpcb+MySfD/0cidGJ\nKHQuhM1DG0z+eDIyMzONbZYCMTt3YnBmJjueEhO1Gk+6wGVc1ImJwem//8aHiYmsffHxutn3ww/C\naKN//z2Qk6P278rH5znKympONhERFWWkPgCucW+bz6pFW+RdQCkpKeTn50e+vr60aNEiQdOa6Up+\nPpGDA1FurjD1ff890dSp3NpXBpflLR8XAcMw5O/pSQy73iQGYK817ECNHruEMMaLYFlcsVRll6tj\nxwZobS9X9L3ZN+vnWWQ13sqkXSzyG36mmKKR73jSBS7jgomPJ383N4Pax4WxYwPk3D/a/V3Jl+Hz\n7BS1gCrIyBCurnv3iJo31849WFpK5O5OdOpUzc84DW4eeVxPBAfTn9bW8qONTtjYaPSNTprxOVn/\nswnB+T2CU1+CU2+ydLejT/79idb2ckXfEwDDMOTpY/p5cMMOhZHd+3YmNTGRVEoUHEwndu+mP21s\nFMeTtbVe9wLUjguGIfrlF9kb1omwsJr2aTHeaxATQxQeroPVSti8mdIPHua1B1BZhs+z0+ylILLz\ns5GVn4XOLXQ7Ui2Pqytg63oFB880hc9A9QLfQUGsQqw2+XPVUZnBaXzEeBQ5F2l10Crx0SPkd+yI\nWLn9GLpxA3bh4Rjs46Oy3EcDh2Dvqz2QOl+Q/cwquS7+Nfhfuv0njIhEIsGc8XMw4eAEFDoVmmwe\nXJ9hPjhz9ozJ+f5Rpw4SY2OR7+6O2Mo+YxhQeTnszp1TO570hkQCFBUBr14BtrZIPH9e0T6wewJ2\nJ05g8MGD2vv07ezY/KhC4uSEN1u3RlRUJyxZEoKMDAYtW1ogMFB9BGBl9NqSJSEAPuberg5zll4w\n9AogOjWalp9ZLni9Y/6zln46dFrtPXFxRE2aEKWnK/9c27fey+mXqUhaJIyLIDNTYxAyn9WGrhgi\n3tvUXSyVGD32nQ8vXyqNe9eVGn3x4oXy5bQ6pFL2rb6WY9JRQKZKH6c+WNp3qeD17p7ujxnD+6n8\nvKgIGD+e1YR6803d2toWvw13n97VPo/rhQuqBUeaN9f4FlTZjiSZvc9U35a5IubB5cjy5dorWs6a\nBRwRJo1hJUSEX4OCFCN5njwBTpzgVpGVlaJCYEqKMAbWAsx+AjAWISFAx47AqFG617Vh6AZ0ad4F\ngJYHrVJTNeewjIgADh5U+bHPMB90L+pusuGIfBHz4HLA01P7t5dffmEVEwUkMjwcr3bswMmNG4Hn\nFWJorq7sHxdfcnLYhC1SFbIwPj7AvXv861fHpUuAn59+6laF4OsQHTGkCygmKYE2nzytt/qPQTKo\nwgAAEg1JREFUJB1RmUgkL09z1JGqpT7DMDTx4ET637P/6Wqiaq5eJUpIUHsLX1kHPtRKt4eeqPV9\nkZyscxXyEUf+LVoQc/SoAIbJKlf92c2brMtIHxQUsNmoeGJ2LiD54/GVX5qOx89cOhOevp5o5umM\nDz77EF/P/Qyevp56OVKfW5SrUhjOzg5o2JBfvRKJBFPenYK3GmiRQVoeLjHjXbsCnTqpvcVQb8uk\nbKlvYpCJyx8IxpYtrIgZXxgGmDABSE/nX8fTp4icMwdeFfH8g1++xEldNVzkqXT9FRezYm+FhVW/\nXzc31mWkD2xsgFatDDqWavUE0Mu9F65YXkG0S7Ts64rFFfT26K2yjOtbbRFncR1PPnqI0hHZKPN+\nijjJdbR9q63g9o3vPB7dWnYTrL6U51W+yV5v9YK1JQf9DyJgzBggiaNqYEEBu2egBIlEglXLVund\nVy5b6h84oNd2dCEyPByZGzaYtI2CMGQIMHgw//IWFkB0NODoyK2c3MOQiBC5dy8+LGSTCw0uLNTP\nqWMrK/YlqH59RO7fb7Dfb+S2bQZrq1ZPAKqOx/cb2A/b47fL7sstypVdnz+dDTrfUaEMne+Cc6ez\n9WLj3r3Axo2611POlGP8wfHIyON5GlYiAU6dAt7hmO8gNZVbfkyBoYqj++vy801SWgCoJi+wapVJ\n2qgzlf8nR0c2Z6ouVL4wEAEXL2rXdq9eQFoaACAyOhpeL16g8rVDAmBwYqLwD0wrK2DCBBCAyMBA\ng8hbEMMgcvp0g0lp1OoJoDJqwyaNTfxRGY1SxpQhM6/K3SEtl8quU1MJeP41kFTx9nzHBsiej8xM\n/XT0qdzVmL/2K7z//jKMGqVZ3U/ereUz20fm1poTMAcxE2PQ0r4lf2P4qBZ26MCGKhkahgHS0hAZ\nHl611I+PN7037KIiRRuvX6+yMSMDuFlTnqMSQy71+bQlK3PhArt6FJqsLGDNGqC8vKZ9N24A9++z\n30sk7EtIxcSTeP48Lri7I6BvXyzs0QMBffsi1t0dN86dE95GsKs7rwcP9DfRyLd14AC8oMdJrTq8\ndxz0BNeNDK6x26NHBxCQR3CsiGN39CQgTy8yBsnJqdT8fW9Co3itT/YJrvqYnU3Uv78wG1eqNCv0\nwfnzxIwcqVpaoKDAcLaogRkxgvzbt1du46lTRMHBVTdfvkz011+yS76qlIZSwJSVCQsjStVvXoQa\n9m3ZQqTFxq4hTogbSt5CaVvt2mndltlKQSiLRmEYopKSmvfKjk5b7yK8a0+wDtVbwhU+2h65hbnU\nzbubwiGr7j7d+Q84hiG6dYvn/0COwkKidu2IXuku7awUqZTom2+qfmkMQyf27VN+dD8khGjAAP3Y\nwZETO3ZoLy9w5oxM+pdhGPJ/+21eDxSuDz2GYdgHiXxbsbFE69ZV3VTtmrlwgfydnAyil8MwDPl3\n6WKQvuCKYPIRfNuytKQ///hDq/JmKQWRkvIQEX/cxBtZnXBgbyJcndxx5owTNmwA5swBpkxRvL/y\n6PT//d82nLvSCb0/u4+VK7VPuEJEWLNwIeYGB2vc/Dxz7QTg9DcA+fsI0ddKACwDwEonlzFl6NC0\nAwDgx9gf0aNfD9yJvyOTJJg3YR7/jVaJBHDTThpaLfXrA1euALbV1Qq5odB/lZEb9euz/tYePdgj\n9nXqABIJEi9ckB3dLykpQd26ddmj++npGHz4cFWlDKM0uYbe2LcP8PICHByQeP26cnkBZfIHffvK\nvo0MD4dXerrCUl9fcgmR4eHwSktTbMvDg430qqRlS4XryPh4eGVnG86+pCSDtMUVlfIRepC3UNlW\nbCwGjxwpaFvyDZgUXGYxZQkUJJLZNHRoKsXEaJ9WjQtcltLvD/iMMFLRnYOR9cjto16ye/Ym7qXd\nN3YrlBNEkuDuXaLQUO7l9IxC/02eTHTggFblVL7pMQy7GkhKEtBKDQQG6hTLrnSp7+FBTFCQVoNW\n67feMWOIuXmTswvD6G4PDm3V+jMR2vLyJdGQIexKXAVm5wLi42LRBebcuZpLaTU8eJBCddu0UHDn\nWL/TmDaf2aKxLb6qjwzD0Pfz5xNz8yaRlktHzsyaRXTlSlVbWv6xMlFRim6F0lKtm1T7h56WpvTB\nydU+tQj48FPpVvjiC63Ka/3Qi4+nE3v3cnZhGN3twaEts5kAiNg9JDWYnQvo8WMGyhIoZGQwemkv\n8swZeKWkVC1Vf/sNg6v7mORo3doZPy5Yghmnv0V5Wyks71njpzmB+KKv6jKV8FV9lMWje3job9no\n6wu8845iWz4+FfNvPmBfkQHszBlg+3b2C0Dk/fuKboXDh4VZRsuHJf7+O5CdDcycWdM+vjAMK9e6\nfTvg7KyrtaqX+ra2kEXYHz3KSi00aaJ9xSkpwPr1VVIInTsjcft2zi4Mk3B7GEtB1JTx8Kj6/vZt\nYVy7fCYifWJSKwCGIdq3j6ikRPlS1caGGGU7zQpV8Hfn8Nrs47mZxhWGYci/e3fFti5fJurXr+qm\nvDxZkmWDLfWfPSO6d09RKkCIvhBAvoATAQFEDx4o/UhlX1TmlzVRFVN9YFYrgEqKi4n69mXHuhxm\n5wLik0SZEwxDNHcu0aNHmpeqanxzfDRzGIah/5s2TfODKyWF6PZtIqpYTlckeNHXkr0S+f6QtcUw\nKh8+hl7qK7WPiOjJE7XlFNxGp0+bxsM0J0cWyVVjXBw4wEbwmClmOQEQ1RiXDMOYnxZQZUTP2LEh\n6N9/GcaODUFUlPYRPUopLgauVeTWlEiA1asBR0eFwyeVXwqHT778Ejh2TGmVfDRzVMofJCay7oFK\n4uKACxdkp1E/rFAx1NvxeFSdfK1xFB9QKSWtsf8MYV9REbuMrkzmUV4O/P23QlmZ22jfPvYId26u\n4PZxJiFBdhq7xriwsWGjpkTMC7mkO5gxA5F89ZmEmIyExFgpIWUkJBBNmcK9XEGBYg5IHd4cFdwX\nHTuy0SGVXL2qdHO3Nm3c8YHLm55a++R/L9nZRKNGyS6Zp0/J38XF5HLFViK4W+s1wGxXAHIw4eHk\n3727+W0CV0IcYvOVlnn2jI1Ft7VlxZ+2bOFuhI1N1fcxMcDmzUBoqHb2FRWx7QPAzZuI/PxzeN26\nxW6WJifjpFRatTnYtati/HYF4sZdFVrb17QpsGeP7DJy/36DxebzQUFywgTtEzEOkQwDLzWSI2oR\ndCrSAMMwtHTpUvL19aVx48ZRmhLtaz6zmE7H3PfvJ5o2jejQIc7tqqS8XEHXW6EtqZTo2rWqex89\nImrbVnbJFBbKNnL1HYNdm3idjvzzwdTtMxbmvgKQHxcmvwl88uRJWrBgARERxcfH01dffVXjHj5a\nQP7duin+QeTkEK1fX3VTtWvmyRPyd3auKqOHXKWytsrKyL9Ro6q2ioqIevWqchcxjILryBjuldrA\n63Tknw+mbp+xMPcJQH5cmLwL6OrVq3i/Ivdm586dcZPvskWOyPBweN25o7gs7tNHMaUbkcJ15JEj\n8Hr8uKpMRIT+jrlHRMCroKCqrWPHMFh+41MiUVDplHdfKMgfmIh75XWlNrm1xHEhUon8uBjGpwKh\nZyR1LF68mGJiYmTX/fv3p/Jqb99cZjE+y2LxmHvtROyLKsS+qELsiypMPgzUzs4OBQUFsmuGYWCh\ng4iX/KYYoJ2GNp8yhrRPRERExFBIiAyXvujkyZM4ffo0goODER8fjw0bNmDz5s0K91y9etVQ5oiI\niIi8VnTrxi0FrUEnACJCQEAAkiry0gYHB8PFxcVQzYuIiIiIyGHQCUBERERExHSo1VIQIiIiIiL8\nMZmTwPLuoTp16uC7775DK3mZXzNjxIgRsLOzAwA4OjoiKCjIyBYZnoSEBISEhGDXrl1IS0vDggUL\nYGFhAVdXVyxbtszY5hkU+b64c+cOvvzySzhXSFOPHj0aQ4YMMa6BBqCsrAyLFi3C48ePIZVKMXXq\nVLz99ttmOS6U9UWLFi24jwsBo5B0QptDYuZCSUkJeXt7G9sMo7Jlyxb6+OOPydfXl4iIpk6dSnFx\ncUREtHTpUoqKijKmeQalel/s27ePtm3bZlyjjEB4eDgFVehivXz5kvr162e240K+L168eEH9+vWj\nsLAwzuPCZFxA+jgkVlu5e/cuCgsLMXnyZEycOBEJCQnGNsngODk5Yf369bLrW7duwd3dHQDQp08f\nxMbGGss0g6OsL86cOQM/Pz8sXrwYhRWqp687Q4YMwbfffgsAKC8vh6WlJW7fvm2W40K+LxiGgZWV\nFW7duoXTp09zGhcmMwHk5+fDvjKTFAArKyswjH4ye5k69erVw+TJk/Hbb78hICAAc+bMMbu+GDRo\nECzlTkiTXKyCra0t8vLyjGGWUajeF507d8a8efMQGhqKVq1a4eeffzaidYajfv36sLGxQX5+Pr79\n9lvMnDnTbMdF9b7w9/dHp06dMH/+fE7jwmQmAKEPidVmnJ2dMXz4cNn3b7zxBnJycoxslXGRHwsF\nBQVwcHAwojXG5YMPPoBbRTrAQYMG4e7du0a2yHBkZmZiwoQJ8Pb2xtChQ816XFTvCz7jwmSesF27\ndkV0dDQAID4+Hm3btjWyRcYjPDwcq1atAgBkZ2ejoKAATbjkhn0NcXNzQ1xcHAAgJiaG84GX14nJ\nkycjMTERABAbG4sOHToY2SLD8PTpU0yePBlz586Ft7c3AKB9+/ZmOS6U9QWfcWEyUUCDBg3C+fPn\nMWrUKADsITFz5V//+hcWLlyIMWPGwMLCAkFBQWa7Gqpk/vz5WLJkCaRSKdq0aQMvLy9jm2Q0AgIC\nEBgYCGtrazRp0gQrVqwwtkkGYdOmTXj16hU2bNiA9evXQyKRYPHixVi5cqXZjQtlfbFw4UIEBQVx\nGhfiQTARERERM8W8XytFREREzBhxAhARERExU8QJQERERMRMEScAERERETNFnABEREREzBRxAhAR\nERExU8QJQKRWc/nyZbz33nsYP348xo0bh9GjR+PEiRM61Tlu3DiFcyilpaUYMGCATnUuXLgQ586d\n06kOERGhMZmDYCIifOnZsyd++OEHAEBhYSH8/Pzg4uKCdu3a8a7z2LFj+OCDD+Dh4QEAkEgkGkqI\niNQ+xAlA5LXCxsYGo0aNQmRkJNq2bYulS5ciKysLOTk5GDBgAGbMmIHBgwdj//79cHBwwJ49e2TK\nq/IsXrwYS5YsQUREhIIQ28KFCzF06FD07t0bZ8+exfHjxxEcHIxBgwahW7duSE1NhaenJ/Lz83Hj\nxg20bt0a33//PQBg9+7d2Lp1K8rLyxEUFIRWrVohNDQUR48ehUQiwdChQ+Hn54eFCxfi+fPnePny\nJTZv3qwgkigiIiSiC0jktaNx48Z4/vw5srKy0KVLF2zduhVhYWHYs2cPJBIJhg8fjmPHjgEADh8+\nLNNSkaddu3bw9vbWWpIkIyMDM2fORGhoKHbt2oWxY8ciLCwMV69eRX5+PgBW72r79u2YMmUKVq9e\njQcPHuD48ePYs2cPdu/ejaioKKSkpABgVzV79uwRH/4iekVcAYi8dmRkZKB58+ZwcHDAjRs3cOnS\nJdja2kIqlQJgs63NmjUL7u7uaNKkCRo1aqS0ni+++AJjxoxBTEyM0s/lVVQaNmyIZs2aAWBXIa1b\ntwYA2Nvbo6SkBABk7qSuXbtizZo1uH//PjIyMjBhwgQQEfLy8pCWlgYAcHFxEaAnRETUI64ARGo9\n8g/i/Px8hIWFwcvLCxEREWjQoAHWrFmDSZMmobi4GADQsmVL2NvbY+PGjfDx8VFZr4WFBYKDgxXS\ncdapU0cmzX379m1Ott24cQMAEBcXh7Zt28LFxQWurq7YuXMndu3aBW9vb7zzzjuytkVE9I24AhCp\n9Vy6dAnjx4+HhYUFysvLMWPGDDg7O6OsrAyzZ89GfHw8rK2t4ezsjCdPnqBp06YYOXIkvvvuO4SE\nhNSoT37D18XFBRMnTsSOHTsAAJ999hkWLVqEI0eOyHKvqkO+roSEBEyYMEGm8NqiRQv06NEDo0eP\nRmlpKTp37oymTZvq3iEiIloiqoGKmCV//vkn7t+/j+nTpxvbFBERoyGuAETMjrVr1+LSpUvYtGmT\nsU0RETEq4gpARERExEwRd5pEREREzBRxAhARERExU8QJQERERMRMEScAERERETNFnABEREREzBRx\nAhARERExU/4fVvCSb2uTD9sAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x112f152b0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def plot_times(times):\n",
    "    plt.style.use('seaborn-whitegrid')\n",
    "    X = ints(1, len(times[0]) - 2)\n",
    "    for (mark, label, *Y) in times:\n",
    "        label = '{} (μ={:.0f} min)'.format(label, mean(Y))\n",
    "        plt.plot(X, Y, mark, label=label)\n",
    "    plt.xlabel('Day Number'); \n",
    "    plt.ylabel('Minutes to Solve Both Parts')\n",
    "    plt.legend(loc='upper left')\n",
    "\n",
    "plot_times([\n",
    " ('o--', 'Me',    \n",
    "  4, 6, 20, 5, 12, 30, 33, 10, 21, 40, 13, 12, 30, 41, 13, 64, 54, 74, 50, 18, 40, 25, 50, 10, 10),\n",
    " ('v:', '100th', \n",
    "  6, 6, 23, 4,  5,  9, 25,  8, 12, 25, 12,  9, 22, 25, 10, 27, 16, 41, 18, 21, 45, 20, 54, 21, 11),\n",
    " ('^:', '1st',   \n",
    "  1, 1,  4, 1,  2,  3, 10,  3,  4,  6,  3,  2,  6,  5,  2,  5,  5, 10,  5,  7, 10,  6, 19,  6, 2)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I asked [Kevin Wang](https://github.com/kevmo314), last year's overall time leader and my colleague at Google, how he manages to go so fast. His answers:\n",
    "\n",
    "- \"My code tends to be eccentrically terse.\"\n",
    "- \"I try to minimize the amount of code I write: each line of code is just another chance for a typo.\"\n",
    "- \"I save the most time by just observing that a problem is an adaptation of a common problem\" (such as a topological sort, or union-find, or A* search, or the Chinese Remainder Theorem).\n",
    "- \"A lot of it is just finding patterns and not making mistakes.\"\n",
    "- \"For AoC it's important to just read the input/output and skip all the instructions first. Especially for the first few days, you can guess what the problem is based on the sample input/output.\""
   ]
  }
 ],
 "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.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}