ipynb/Advent-2016.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# December 2016: Advent of Code Solutions\n",
    "\n",
    "## Peter Norvig\n",
    "\n",
    "From Dec. 1 to Dec. 25, [I](http://norvig.com) will be solving the puzzles that appear each day at *[Advent of Code](http://adventofcode.com/)*. The two-part puzzles are released at midnight EST (9:00PM PST); points are awarded to the first 100 people to solve the day's puzzles. The code shown here basically represents what I did to solve the problem, but slightly cleaned up:\n",
    "- On days when I start at 9:00PM and am competing against the clock, I take shortcuts. I use shorter names, because I'm not a fast typist. I run test cases in the Jupyter Notebook, but don't make them into `assert` statements. Even then, I'm not really competitive with the fastest solvers.\n",
    "- On days when I didn't get a chance to start until after all the points are gone, what you see here is pretty much exactly what I did, or at least what I ended up with after correcting typos and other errors. \n",
    "\n",
    "To understand the problems completely, you will have to read the full description in the **\"[Day 1](http://adventofcode.com/2016/day/1):\"** link in each day's section header.\n",
    "\n",
    "# Day 0: Getting Ready\n",
    "\n",
    "On November 30th, I spent some time preparing: \n",
    "\n",
    "- I'll import my favorite modules and functions, so I don't have to do it each day.\n",
    "\n",
    "- From  looking at [last year's](http://adventofcode.com/2015) puzzles, I knew that there would be a data file on many days, so I defined the function `Input` to open the file (and for those using this notebook on a remote machine, to fetch the file from the web). My data files are at [http://norvig.com/ipython/advent2016/](http://norvig.com/ipython/advent2016/).\n",
    "\n",
    "- From working on another puzzle site, [Project Euler](https://projecteuler.net/), I had built up a collection of utility functions, shown below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Python 3.x\n",
    "import re\n",
    "import numpy as np\n",
    "import math\n",
    "import urllib.request\n",
    "\n",
    "from collections import Counter, defaultdict, namedtuple, deque\n",
    "from functools   import lru_cache\n",
    "from itertools   import permutations, combinations, chain, cycle, product, islice\n",
    "from heapq       import heappop, heappush\n",
    "\n",
    "def Input(day):\n",
    "    \"Open this day's input file.\"\n",
    "    filename = 'advent2016/input{}.txt'.format(day)\n",
    "    try:\n",
    "        return open(filename)\n",
    "    except FileNotFoundError:\n",
    "        return urllib.request.urlopen(\"http://norvig.com/ipython/\" + filename)\n",
    "\n",
    "def transpose(matrix): return zip(*matrix)\n",
    "\n",
    "def first(iterable): return next(iter(iterable))\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",
    "cat = ''.join\n",
    "\n",
    "Ø   = frozenset() # Empty set\n",
    "inf = float('inf')\n",
    "BIG = 10 ** 999\n",
    "\n",
    "def grep(pattern, lines):\n",
    "    \"Print lines that match pattern.\"\n",
    "    for line in lines:\n",
    "        if re.search(pattern, line):\n",
    "            print(line)\n",
    "\n",
    "def groupby(iterable, key=lambda it: it):\n",
    "    \"Return a dic whose keys are key(it) and whose values are all the elements of iterable with that key.\"\n",
    "    dic = defaultdict(list)\n",
    "    for it in iterable:\n",
    "        dic[key(it)].append(it)\n",
    "    return dic\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",
    "# 2-D points implemented using (x, y) tuples\n",
    "def X(point): return point[0]\n",
    "def Y(point): return point[1]\n",
    "\n",
    "def neighbors4(point): \n",
    "    \"The four neighbors (without diagonals).\"\n",
    "    x, y = point\n",
    "    return ((x+1, y), (x-1, y), (x, y+1), (x, y-1))\n",
    "\n",
    "def neighbors8(point): \n",
    "    \"The eight neighbors (with diagonals).\"\n",
    "    x, y = point \n",
    "    return ((x+1, y), (x-1, y), (x, y+1), (x, y-1),\n",
    "            (x+1, y+1), (x-1, y-1), (x+1, y-1), (x-1, y+1))\n",
    "\n",
    "def cityblock_distance(p, q=(0, 0)): \n",
    "    \"City block distance between two points.\"\n",
    "    return abs(X(p) - X(q)) + abs(Y(p) - Y(q))\n",
    "\n",
    "def euclidean_distance(p, q=(0, 0)): \n",
    "    \"Euclidean (hypotenuse) distance between two points.\"\n",
    "    return math.hypot(X(p) - X(q), Y(p) - Y(q))\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 astar_search(start, h_func, moves_func):\n",
    "    \"Find a shortest sequence of states from start to a goal state (a state s with 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",
    "    while frontier:\n",
    "        (f, s) = heappop(frontier)\n",
    "        if h_func(s) == 0:\n",
    "            return Path(previous, s)\n",
    "        for s2 in moves_func(s):\n",
    "            new_cost = path_cost[s] + 1\n",
    "            if s2 not in path_cost or new_cost < path_cost[s2]:\n",
    "                heappush(frontier, (new_cost + h_func(s2), s2))\n",
    "                path_cost[s2] = new_cost\n",
    "                previous[s2] = s\n",
    "    return dict(fail=True, front=len(frontier), prev=len(previous))\n",
    "                \n",
    "def Path(previous, s): \n",
    "    \"Return a list of states that lead to state s, according to the previous dict.\"\n",
    "    return ([] if (s is None) else Path(previous, previous[s]) + [s])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some tests/examples for these:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "assert tuple(transpose(((1, 2, 3), (4, 5, 6)))) == ((1, 4), (2, 5), (3, 6))\n",
    "assert first('abc') == first(['a', 'b', 'c']) == 'a'\n",
    "assert cat(['a', 'b', 'c']) == 'abc'\n",
    "assert (groupby(['test', 'one', 'two', 'three', 'four'], key=len) \n",
    "        == {3: ['one', 'two'], 4: ['test', 'four'], 5: ['three']})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 1](http://adventofcode.com/2016/day/1): No Time for a Taxicab\n",
    "\n",
    "Given a sequence of moves, such as `\"R2, L3\"`, which means turn 90&deg; to the right and go forward 2 blocks, then turn 90&deg; left and go 3 blocks, how many blocks do we end up away from the start? I make the following choices:\n",
    "* **Intersection Points** in the city grid will be represented as points on the complex plane. \n",
    "* **Headings and turns** can be represented by unit vectors in the complex plane: if you are heading east (along the positive real axis), then a left turn means you head north, and a right turn means you head south, and [in general](https://betterexplained.com/articles/understanding-why-complex-multiplication-works/) a left or right turn is a multiplication of your current heading by the `North` or `South` unit vectors, respectively.  \n",
    "* **Moves** of the form `\"R53\"` will be parsed into a `(turn, distance)` pair, e.g. `(South, 53)`.\n",
    "\n",
    "To solve the puzzle with the function `how_far(moves)`, I initialize the starting location as the origin and the starting heading as North, and follow the list of moves, updating the heading and location on each step, before returning the distance from the final location to the origin."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "250.0"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Point = complex             \n",
    "N, S, E, W = 1j, -1j, 1, -1 # Unit vectors for headings\n",
    "\n",
    "def distance(point): \n",
    "    \"City block distance between point and the origin.\"\n",
    "    return abs(point.real) + abs(point.imag)\n",
    "\n",
    "def how_far(moves):\n",
    "    \"After following moves, how far away from the origin do we end up?\"\n",
    "    loc, heading = 0, N # Begin at origin, heading North\n",
    "    for (turn, dist) in parse(moves):\n",
    "        heading *= turn\n",
    "        loc += heading * dist\n",
    "    return distance(loc)\n",
    "\n",
    "def parse(text):\n",
    "    \"Return a list of (turn, distance) pairs from text of form 'R2, L42, ...'\"\n",
    "    turns = dict(L=N, R=S)\n",
    "    return [(turns[RL], int(d))\n",
    "           for (RL, d) in re.findall(r'(R|L)(\\d+)', text)]\n",
    "\n",
    "assert distance(Point(3, 4)) == 7 # City block distance; Euclidean distance would be 5\n",
    "assert parse('R2, L42') == [(S, 2), (N, 42)]\n",
    "assert how_far(\"R2, L3\") == 5\n",
    "assert how_far(\"R2, R2, R2\") == 2\n",
    "assert how_far(\"R5, L5, R5, R3\") == 12\n",
    "\n",
    "how_far(Input(1).read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two** of this puzzle, I have to find the first point that is visited twice. To support that, I keep track of the set of visited points. My first submission was wrong, because I didn't consider that the first point visited twice might be in the middle of a move, not the end, so I added the \"`for i`\" loop to iterate over the path of a move, one point at a time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "151.0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def visited_twice(text):\n",
    "    \"Following moves in text, find the first location we visit twice, and return the distance to it.\"\n",
    "    loc, heading = 0, N # Begin at origin, heading North\n",
    "    visited = {loc}\n",
    "    for (turn, dist) in parse(text):\n",
    "        heading *= turn\n",
    "        for i in range(dist):\n",
    "            loc += heading\n",
    "            if loc in visited:\n",
    "                return distance(loc)\n",
    "            visited.add(loc)\n",
    "\n",
    "assert visited_twice(\"R8, R4, R4, R8\") == 4\n",
    "assert visited_twice(\"R8, R4, R4, L8\") == None\n",
    "assert visited_twice(\"R8, R0, R1\") == 7\n",
    "\n",
    "visited_twice(Input(1).read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 2](http://adventofcode.com/2016/day/2): Bathroom Security\n",
    "\n",
    "Given instructions in the form of a sequence of Up/Down/Right/Left moves, such as `'ULL'`, output the keys on the bathroom lock keypad that the instructions correspond to. Start at the 5 key. Representation choices:\n",
    "* **Keypad**: a keypad is an array of strings: `keypad[y][x]` is a key. The character `'.'` indicates a location that is `off` the keypad; by surrounding the keys with a border of `off` characters, I avoid having to write code that checks to see if we hit the edge.\n",
    "* **Key**: A key is a character other than `'.'`.\n",
    "* **Instructions**: A sequence of lines of `\"UDRL\"` characters, where each line leads to the output of one key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'97289'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Keypad = str.split\n",
    "\n",
    "keypad = Keypad(\"\"\"\n",
    ".....\n",
    ".123.\n",
    ".456.\n",
    ".789.\n",
    ".....\n",
    "\"\"\")\n",
    "\n",
    "assert keypad[2][2] == '5'\n",
    "\n",
    "off = '.'\n",
    "\n",
    "def decode(instructions, x=2, y=2):\n",
    "    \"\"\"Follow instructions, keeping track of x, y position, and\n",
    "    yielding the key at the end of each line of instructions.\"\"\"\n",
    "    for line in instructions:\n",
    "        for C in line:\n",
    "            x, y = move(C, x, y)\n",
    "        yield keypad[y][x]\n",
    "\n",
    "def move(C, x, y):\n",
    "    \"Make the move corresponding to this character (L/R/U/D)\"\n",
    "    if   C == 'L' and keypad[y][x-1] is not off: x -= 1\n",
    "    elif C == 'R' and keypad[y][x+1] is not off: x += 1\n",
    "    elif C == 'U' and keypad[y-1][x] is not off: y -= 1\n",
    "    elif C == 'D' and keypad[y+1][x] is not off: y += 1\n",
    "    return x, y\n",
    "\n",
    "assert move('U', 2, 2) == (2, 1)\n",
    "assert move('U', 2, 1) == (2, 1)\n",
    "assert cat(decode(\"ULL RRDDD LURDL UUUUD\".split())) == '1985'\n",
    "\n",
    "cat(decode(Input(2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we have to deal with a different keypad. I won't need any new functions, but I will need to redefine the global variable `keypad`, and provide `decode` with the new `x` and `y` coordinates of the `5` key:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'9A7DC'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "keypad = Keypad(\"\"\"\n",
    ".......\n",
    "...1...\n",
    "..234..\n",
    ".56789.\n",
    "..ABC..\n",
    "...D...\n",
    ".......\n",
    "\"\"\")\n",
    "\n",
    "assert keypad[3][1] == '5'\n",
    "\n",
    "cat(decode(Input(2), x=1, y=3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 3](http://adventofcode.com/2016/day/3): Squares With Three Sides\n",
    "\n",
    "From a file of numbers, three to a line, count the number that represent valid triangles; that is, numbers that satisfy the [triangle inequality](https://en.wikipedia.org/wiki/Triangle_inequality)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "983"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def is_triangle(sides):\n",
    "    \"Do these side lengths form a valid triangle?\"\n",
    "    x, y, z = sorted(sides)\n",
    "    return z < x + y\n",
    "\n",
    "def parse_ints(text): \n",
    "    \"All the integers anywhere in text.\"\n",
    "    return [int(x) for x in re.findall(r'\\d+', text)]\n",
    "\n",
    "triangles = [parse_ints(line) for line in Input(3)]\n",
    "\n",
    "sum(map(is_triangle, triangles))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, the triangles are denoted not by three sides in the same line, but by three sides in the same column. For example, given the text:\n",
    "\n",
    "    101 301 501\n",
    "    102 302 502\n",
    "    103 303 503\n",
    "    201 401 601\n",
    "    202 402 602\n",
    "    203 403 603\n",
    "    \n",
    "The triangles are:\n",
    "\n",
    "    [101, 102, 103]\n",
    "    [301, 302, 303]\n",
    "    [501, 502, 503]\n",
    "    [201, 202, 203]\n",
    "    [401, 402, 403]\n",
    "    [601, 602, 603]\n",
    "    \n",
    "The task is still to count the number of valid triangles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1836"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def invert(triangles):\n",
    "    \"Take each 3 lines and transpose them.\"\n",
    "    for i in range(0, len(triangles), 3):\n",
    "        yield from transpose(triangles[i:i+3])\n",
    "\n",
    "sum(map(is_triangle, invert(triangles)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 4](http://adventofcode.com/2016/day/4): Security Through Obscurity\n",
    "\n",
    "Given a list of room names like `\"aaaaa-bbb-z-y-x-123[abxyz]\"`, consisting of an encrypted name followed by a dash, a sector ID, and a checksum in square brackets, compute the sum of the sectors of the valid rooms. A room is valid if the checksum is the five most common characters, in order (ties listed in alphabetical order)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "185371"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def parse(line): \n",
    "    \"Return (name, sector, checksum).\"\n",
    "    return re.match(r\"(.+)-(\\d+)\\[([a-z]+)\\]\", line).groups()\n",
    "\n",
    "def sector(line):\n",
    "    \"Return the sector number if valid, or 0 if not.\"\n",
    "    name, sector, checksum = parse(line)\n",
    "    return int(sector) if valid(name, checksum) else 0\n",
    "\n",
    "def valid(name, checksum):\n",
    "    \"Determine if name is valid according to checksum.\"\n",
    "    counts = Counter(name.replace('-', '')) \n",
    "    # Note: counts.most_common(5) doesn't work because it breaks ties arbitrarily.\n",
    "    letters = sorted(counts, key=lambda L: (-counts[L], L))\n",
    "    return checksum == cat(letters[:5])\n",
    "\n",
    "assert  parse('aaaaa-bbb-z-y-x-123[abxyz]') == ('aaaaa-bbb-z-y-x', '123', 'abxyz')\n",
    "assert sector('aaaaa-bbb-z-y-x-123[abxyz]') == 123\n",
    "assert  valid('aaaaa-bbb-z-y-x', 'abxyz')\n",
    "\n",
    "sum(map(sector, Input(4)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initially I had a bug: I forgot the `name.replace('-', '')` to make sure that we don't count hyphens. \n",
    "\n",
    "In **part two**, we are asked *\"What is the sector ID of the room where North Pole objects are stored?\"* We are told that names are to be decrypted by a shift cipher, shifting each letter forward in the alphabet by the sector number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "northpole-object-storage 984\n"
     ]
    }
   ],
   "source": [
    "def decrypt(line):\n",
    "    \"Decrypt the line (shift the name by sector; discard checksum).\"\n",
    "    name, sector, _ = parse(line)\n",
    "    return shift(name, int(sector)) + ' ' + sector\n",
    "\n",
    "def shift(text, N, alphabet='abcdefghijklmnopqrstuvwxyz'):\n",
    "    \"Shift cipher: letters in text rotate forward in alphabet by N places.\"\n",
    "    N = N % len(alphabet)\n",
    "    tr = str.maketrans(alphabet, alphabet[N:] + alphabet[:N])\n",
    "    return text.translate(tr)\n",
    "\n",
    "assert shift('hal', 1) == 'ibm'\n",
    "assert shift('qzmt-zixmtkozy-ivhz', 343) == 'very-encrypted-name'\n",
    "\n",
    "grep(\"north\", map(decrypt, Input(4)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 5](http://adventofcode.com/2016/day/5): How About a Nice Game of Chess?\n",
    "\n",
    "This puzzle involves md5 hashes and byte encodings; it took me a while to look up how to do that. What I have to do, for integers starting at 0, is concatenate my door ID string with the integer, get the md5 hex hash, and if the first five digits of the hash are 0, collect the sixth digit; repeat until I have collected eight digits:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "515840 00000c6c3f533fe4f7b0cb6d851185a8 c\n",
      "844745 000006a94bb1c9322cbb56dd8564e76e c6\n",
      "2968550 000006c8c9090315b0fb38154a947c86 c66\n",
      "4034943 00000970faef6424564944d5e8a59618 c669\n",
      "5108969 000007b2e0e83dfeade14ebe09f9e6a7 c6697\n",
      "5257971 00000bc5fdee6506b09262247ceb63f0 c6697b\n",
      "5830668 0000051079ac6b44fc3a5266a1630d42 c6697b5\n",
      "5833677 00000537192966c3ee924306195faede c6697b55\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'c6697b55'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import hashlib\n",
    "\n",
    "door = \"ffykfhsq\"\n",
    "\n",
    "def find_password(door):\n",
    "    \"First 8 sixth digits of md5 hashes of door+i that begin with '00000'.\"\n",
    "    password = ''\n",
    "    for i in range(BIG):\n",
    "        x = hashlib.md5(bytes(door + str(i), 'utf-8')).hexdigest()\n",
    "        if x.startswith('00000'):\n",
    "            password += x[5]\n",
    "            print(i, x, password) # Just to see something happen\n",
    "            if len(password) == 8: \n",
    "                return password\n",
    "\n",
    "find_password(door)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, the sixth digit of the hash that starts with `'00000'` is to be treated as an index that tells where in the password to place the *seventh* digit of the hash. For example, if the sixth digit is `2` and the seventh digit is `a`, then place `a` as the second digit of the final password. Do nothing if the sixth digit is not less than 8, or if a digit has already been placed at that index location."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "844745 000006a94bb1c9322cbb56dd8564e76e ......a.\n",
      "5108969 000007b2e0e83dfeade14ebe09f9e6a7 ......ab\n",
      "5830668 0000051079ac6b44fc3a5266a1630d42 .....1ab\n",
      "6497076 0000008239d1bbf480ea541e9da1e494 8....1ab\n",
      "8962195 00000351ce68ffb449644d4bfa4cee5d 8..5.1ab\n",
      "23867827 000001c3c28bcbacf0f543a33548ef24 8c.5.1ab\n",
      "24090051 000004d57fc545f376c09f27383b2c88 8c.5d1ab\n",
      "26383109 0000023d12c49f028699d4679ba91780 8c35d1ab\n",
      "CPU times: user 30.4 s, sys: 48.7 ms, total: 30.4 s\n",
      "Wall time: 30.4 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'8c35d1ab'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def find_tougher_password(door):\n",
    "    \"For md5 hashes that begin with '00000', the seventh digit goes in the sixth-digit slot of the password.\"\n",
    "    password = [off] * 8\n",
    "    for i in range(BIG):\n",
    "        x = hashlib.md5(bytes(door + str(i), 'utf-8')).hexdigest()\n",
    "        if x.startswith('00000'):\n",
    "            index = int(x[5], 16)\n",
    "            if index < 8 and password[index] is off:\n",
    "                password[index] = x[6]\n",
    "                print(i, x, cat(password)) # Just to see something happen\n",
    "            if off not in password:\n",
    "                return cat(password)\n",
    "\n",
    "%time find_tougher_password(door)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 6](http://adventofcode.com/2016/day/6): Signals and Noise\n",
    "\n",
    "Given a file, where each line is a string of letters and every line has the same length, find the most common letter in each column. We can easily do this with the help of `Counter.most_common`. (Note I use `Input(6).read().split()` instead of just `Input(6)` so that I don't get the `'\\n'` at the end of each line.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'tsreykjj'"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counts = [Counter(col) for col in transpose(Input(6).read().split())]\n",
    "cat(c.most_common(1)[0][0] for c in counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just to make it clear, here's how we ask for the most common character (and its count) in the first column:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('t', 24)]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c = counts[0]\n",
    "c.most_common(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here is how we pick out the `'t'` character:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'t'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c.most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we ask for the *least* common character in each column. Easy-peasy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'hnfbujie'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cat(c.most_common()[-1][0] for c in counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 7](http://adventofcode.com/2016/day/7): Internet Protocol Version 7\n",
    "\n",
    "Given input lines of the form `'abcd[1234]fghi[56789]zz[0]z'`, count the number of lines that are a *TLS*, meaning they have an *ABBA* outside of square brackets, but no *ABBA* inside brackets. An *ABBA* is a 4-character subsequence where the first two letters are the same as the last two, but not all four are the same.\n",
    "\n",
    "I assume brackets are in proper pairs, and are never nested. Then if I do a `re.split` on brackets, the even-indexed pieces of the split will be outside the brackets, and the odd-indexed will be inside. For example:\n",
    "- Given the line `'abcd[1234]fghi[56789]zz'`\n",
    "- Split on brackets to get `['abcd', '1234', 'fghi', '56789', 'zz']`\n",
    "- Outsides of brackets are `'abcd, fghi, zz'` at indexes 0, 2, 4.\n",
    "- Insides of brackets are `'1234, 56789'` at indexes 1, 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "110"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def abba(text):           return any(a == d != b == c for (a, b, c, d) in subsequences(text, 4))\n",
    "def subsequences(seq, n): return [seq[i:i+n] for i in range(len(seq) + 1 - n)]\n",
    "def segment(line):        return re.split(r'\\[|\\]', line)\n",
    "def outsides(segments):   return ', '.join(segments[0::2])\n",
    "def insides(segments):    return ', '.join(segments[1::2])\n",
    "def tls(segments):        return abba(outsides(segments)) and not abba(insides(segments))\n",
    "\n",
    "sum(tls(segment(line)) for line in Input(7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are some tests:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "assert abba('abba') and not abba('aaaa') and not abba('abbc')\n",
    "assert subsequences('abcdefg', 4) == ['abcd', 'bcde', 'cdef', 'defg']\n",
    "assert segment('abcd[1234]fghi[56789]zz') == ['abcd', '1234', 'fghi', '56789', 'zz']\n",
    "assert outsides(['abcd', '1234', 'fghi', '56789', 'zz']) == 'abcd, fghi, zz'\n",
    "assert insides(['abcd', '1234', 'fghi', '56789', 'zz']) == '1234, 56789'\n",
    "assert tls(['abba', '123']) \n",
    "assert not tls(['bookkeeper', '123']) and not tls(['abba', 'xxyyx'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we are asked to count the number of *SSL* lines: an *SSL* is when there is an *ABA* outside brackets, and the corresponding *BAB* inside brackets. An *ABA* is a three-character sequence with first and third (but not all three) the same. The corresponding *BAB* has the first character of the *ABA* surrounded by two copies of the second character."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "242"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alphabet = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "def ssl(segments): \n",
    "    \"Is there an ABA outside brackets, and the corresponding BAB inside?\"\n",
    "    outs, ins = outsides(segments), insides(segments)\n",
    "    return any(a+b+a in outs and b+a+b in ins\n",
    "               for a in alphabet for b in alphabet if a != b)\n",
    "\n",
    "sum(ssl(segment(line)) for line in Input(7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 8](http://adventofcode.com/2016/day/8): Two-Factor Authentication\n",
    "\n",
    "Given an array of pixels on a screen, follow commands that can:\n",
    "- Turn on a sub-rectangle of pixels in the upper left corner: `rect 3x2`\n",
    "- Rotate a row of pixels: `rotate row y=0 by 4`\n",
    "- Rotate a column of pixels: `rotate column x=1 by 1`\n",
    "\n",
    "Then count the total number of `1` pixels in the screen.\n",
    "\n",
    "I will use `numpy` two-dimensional arrays, mostly because of the `screen[:, A]` notation for getting at a column."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "128"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def interpret(cmd, screen):\n",
    "    \"Interpret this command to mutate screen.\"\n",
    "    A, B = map(int, re.findall(r'(\\d+)', cmd)) # There should be 2 numbers on every command line\n",
    "    if cmd.startswith('rect'):\n",
    "        screen[:B, :A] = 1\n",
    "    elif cmd.startswith('rotate row'):\n",
    "        screen[A, :] = rotate(screen[A, :], B)\n",
    "    elif cmd.startswith('rotate col'):\n",
    "        screen[:, A] = rotate(screen[:, A], B)\n",
    "\n",
    "def rotate(items, n): return np.append(items[-n:], items[:-n])\n",
    "\n",
    "def Screen(): return np.zeros((6, 50), dtype=np.int)\n",
    "\n",
    "def run(commands, screen):\n",
    "    \"Do all the commands and return the final pixel array.\"\n",
    "    for cmd in commands:\n",
    "        interpret(cmd, screen)   \n",
    "    return screen\n",
    "\n",
    "screen = run(Input(8), Screen())\n",
    "np.sum(screen)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we are asked what message is on the screen. I won't try to do OCR; I'll just print the screen and look at the output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "@@@@  @@   @@  @@@   @@  @@@  @  @ @   @ @@   @@  \n",
      "@    @  @ @  @ @  @ @  @ @  @ @  @ @   @@  @ @  @ \n",
      "@@@  @  @ @  @ @  @ @    @  @ @@@@  @ @ @  @ @  @ \n",
      "@    @  @ @@@@ @@@  @ @@ @@@  @  @   @  @@@@ @  @ \n",
      "@    @  @ @  @ @ @  @  @ @    @  @   @  @  @ @  @ \n",
      "@@@@  @@  @  @ @  @  @@@ @    @  @   @  @  @  @@  \n"
     ]
    }
   ],
   "source": [
    "for row in screen:\n",
    "    print(cat(' @'[pixel] for pixel in row))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "My answer is `EOARGPHYAO`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 9](http://adventofcode.com/2016/day/9): Explosives in Cyberspace\n",
    "\n",
    "In this puzzle we are asked to decompress text of the form `'A(2x5)BCD'`, where the `'(2x5)'` means to make 5 copies of the next 2 characters, yielding `'ABCBCBCBCBCD'`. We'll go through the input text, a character at a time, and if a `re` matcher detects a `'(CxR)'` pattern, process it; otherwise just collect the character. Note that the `C` characters that are to be repeated `R` times are taken literally; even if they contain an embedded `'(1x5)'`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "138735"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matcher = re.compile(r'[(](\\d+)x(\\d+)[)]').match # e.g. matches \"(2x5)\" as ('2', '5')\n",
    "\n",
    "def decompress(s):\n",
    "    \"Decompress string s by interpreting '(2x5)' as making 5 copies of the next 2 characters.\"\n",
    "    s = re.sub(r'\\s', '', s) # \"whitespace is ignored\"\n",
    "    result = []\n",
    "    i = 0\n",
    "    while i < len(s):\n",
    "        m = matcher(s, i)\n",
    "        if m:\n",
    "            i = m.end()                # Advance to end of '(CxR)' match\n",
    "            C, R = map(int, m.groups())\n",
    "            result.append(s[i:i+C] * R) # Collect the C characters, repeated R times\n",
    "            i += C                      # Advance past the C characters           \n",
    "        else:\n",
    "            result.append(s[i])         # Collect 1 regular character\n",
    "            i += 1                      # Advance past it\n",
    "    return cat(result)\n",
    "\n",
    "len(decompress(Input(9).read()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, the copied characters *are* recursively decompressed. So, given `'(8x2)(3x3)ABC'`, the `(8x2)` directive picks out the 8 characters `'(3x3)ABC'`, which would then be decompressed to get `'ABCABCABC'` and then the `'x2'` is applied to get `'ABCABCABCABCABCABC'`. However, for this part, we are not asked to actually build up the decompressed string, just to compute its length:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11125026826"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def decompress_length(s):\n",
    "    \"\"\"Decompress string s by interpreting '(2x5)' as making 5 copies of the next 2 characters.\n",
    "    Recursively decompress these next 5 characters. Return the length of the decompressed string.\"\"\"\n",
    "    s = re.sub(r'\\s', '', s) # \"whitespace is ignored\"\n",
    "    length = 0\n",
    "    i = 0\n",
    "    while i < len(s):\n",
    "        m = matcher(s, i)\n",
    "        if m:\n",
    "            C, R = map(int, m.groups())\n",
    "            i = m.end(0)                              # Advance to end of '(CxR)'\n",
    "            length += R * decompress_length(s[i:i+C]) # Decompress C chars and add to length\n",
    "            i += C                                    # Advance past the C characters \n",
    "        else:\n",
    "            length += 1                               # Add 1 regular character to length\n",
    "            i += 1                                    # Advance past it\n",
    "    return length\n",
    "\n",
    "decompress_length(Input(9).read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are some tests:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert decompress('A(2x5)BCD') == 'ABCBCBCBCBCD'\n",
    "assert decompress('ADVENT') == 'ADVENT'\n",
    "assert decompress('(3x3)XYZ') == 'XYZXYZXYZ'\n",
    "assert decompress('(5x4)(3x2)') == '(3x2)(3x2)(3x2)(3x2)'\n",
    "assert decompress('X(8x2)(3x3)ABCY') == 'X(3x3)ABC(3x3)ABCY'\n",
    "    \n",
    "assert decompress_length('(8x2)(3x3)ABC') == 18\n",
    "assert decompress_length('(25x3)(3x3)ABC(2x3)XY(5x2)PQRSTX(18x9)(3x2)TWO(5x7)SEVEN') == 445\n",
    "assert decompress_length('(9x999)(2x999)xx') == 999 * 999 * 2 == 1996002"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 10](http://adventofcode.com/2016/day/10): Balance Bots\n",
    "\n",
    "In this puzzle, a fleet of robots exchange some chips from input bins, \n",
    "passing them among themselves, and eventually putting them in output bins. We are given instructions like this:\n",
    "\n",
    "    value 5 goes to bot 2\n",
    "    bot 2 gives low to bot 1 and high to bot 0\n",
    "    value 3 goes to bot 1\n",
    "    bot 1 gives low to output 1 and high to bot 0\n",
    "    bot 0 gives low to output 2 and high to output 0\n",
    "    value 2 goes to bot 2\n",
    "    \n",
    "At first I thought I just had to interpret these instructions sequentially, but then I realized this is actually a *data flow* problem: *whenever* a bot acquires two chips, it passes the low number chip to one destination and the high number to another. So my representation choices are:\n",
    "- Bots and bins are represented as strings: `'bot 1'` and `'output 2'`.\n",
    "- Chips are represented by ints. (Not strings, because we want 9 to be less than 10).\n",
    "- Keep track of which bot currently has which chip(s) with a dict: `has['bot 2'] = {5}`\n",
    "- Keep track of what a bot does when it gets 2 chips with a dict: `gives['bot 1'] = ('output 1', 'bot 0')`\n",
    "- Pull this information from instructions with `re.findall`. The order of instructions is not important.\n",
    "- A function, `give`, moves a chip to a recipient, and if the recipient now has two chips, that triggers two more `give` calls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "bot 113 has {17, 61}\n"
     ]
    }
   ],
   "source": [
    "def bots(instructions, goal={17, 61}):\n",
    "    \"Follow the data flow instructions, and if a bot gets the goal, print it.\"\n",
    "    def give(giver, chip, recip):\n",
    "        \"Pass the chip from giver to recipient.\"\n",
    "        has[giver].discard(chip)\n",
    "        has[recip].add(chip)\n",
    "        chips = has[recip]\n",
    "        if chips == goal:\n",
    "            print(recip, 'has', goal)\n",
    "        if len(chips) == 2:\n",
    "            give(recip, min(chips), gives[recip][0])\n",
    "            give(recip, max(chips), gives[recip][1])\n",
    "            \n",
    "    has   = defaultdict(set)       # who has what\n",
    "    gives = {giver: (dest1, dest2) # who will give what\n",
    "             for (giver, dest1, dest2) \n",
    "             in re.findall(r'(bot \\d+) gives low to (\\w+ \\d+) and high to (\\w+ \\d+)', instructions)}\n",
    "    for (chip, recip) in re.findall(r'value (\\d+) goes to (\\w+ \\d+)', instructions):\n",
    "        give('input bin', int(chip), recip)\n",
    "    return has\n",
    "\n",
    "has = bots(Input(10).read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we are asked for the product of  three output bins:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12803"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def out(i): return has['output ' + str(i)].pop()\n",
    "\n",
    "out(0) * out(1) * out(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 11](http://adventofcode.com/2016/day/11): Radioisotope Thermoelectric Generators    \n",
    "\n",
    "I *knew* my `astar_search` function would come in handy! To search for the shortest path to the goal, I need to provide an initial state of the world, a heuristic function (which estimates how many moves away from the goal a state is), and a function that says what states can be reached by moving the elevator up or down, and carrying some stuff. I will make these choices:\n",
    "* The state of the world is represented by the `State` type, which says what floor the elevator is on, and for a tuple of floors, the set of objects that are on the floor. We use frozensets so that a state will be hashable.\n",
    "* To figure out what moves can be made, consider both directions for the elevator (up or down); find all combinations of one or two items on each floor, and keep all of those moves, as long as they don't violate the constraint that we can't have a chip on the same floor as an RTG, unless the chip's own RTG is there.\n",
    "* To calculate the heuristic, add up the number of floors away each item is from the top floor and divide  by two (since a move might carry two items).\n",
    "\n",
    "Here is my input: \n",
    "\n",
    "* The first floor contains a thulium generator, a thulium-compatible microchip, a plutonium generator, and a strontium generator.\n",
    "* The second floor contains a plutonium-compatible microchip and a strontium-compatible microchip.\n",
    "* The third floor contains a promethium generator, a promethium-compatible microchip, a ruthenium generator, and a ruthenium-compatible microchip.\n",
    "* The fourth floor contains nothing relevant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "State = namedtuple('State', 'elevator, floors')\n",
    "\n",
    "def fs(*items): return frozenset(items)\n",
    "\n",
    "legal_floors = {0, 1, 2, 3}\n",
    "\n",
    "def combos(things):\n",
    "    \"All subsets of 1 or 2 things.\"\n",
    "    for s in chain(combinations(things, 1), combinations(things, 2)):\n",
    "        yield fs(*s)\n",
    "\n",
    "def moves(state):\n",
    "    \"All legal states that can be reached in one move from this state\"\n",
    "    L, floors = state\n",
    "    for L2 in {L + 1, L - 1} & legal_floors:\n",
    "        for stuff in combos(floors[L]):\n",
    "            newfloors = tuple((s | stuff if i == L2 else \n",
    "                               s - stuff if i == state.elevator else \n",
    "                               s)\n",
    "                              for (i, s) in enumerate(state.floors))\n",
    "            if legal_floor(newfloors[L]) and legal_floor(newfloors[L2]):\n",
    "                yield State(L2, newfloors)\n",
    "\n",
    "def legal_floor(floor):\n",
    "    \"Floor is legal if no RTG, or every chip has its corresponding RTG.\"\n",
    "    rtgs  = any(r.endswith('G') for r in floor)\n",
    "    chips = [c for c in floor if c.endswith('M')]\n",
    "    return not rtgs or all(generator_for(c) in floor for c in chips)\n",
    "\n",
    "def generator_for(chip): return chip[0] + 'G'\n",
    "\n",
    "def h_to_top(state):\n",
    "    \"An estimate of the number of moves needed to move everything to top.\"\n",
    "    total = sum(len(floor) * i for (i, floor) in enumerate(reversed(state.floors)))\n",
    "    return math.ceil(total / 2) # Can move two items in one move."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try it out on an easy sample problem:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[State(elevator=0, floors=(frozenset({'RG'}), frozenset(), frozenset({'RM'}), frozenset())),\n",
       " State(elevator=1, floors=(frozenset(), frozenset({'RG'}), frozenset({'RM'}), frozenset())),\n",
       " State(elevator=2, floors=(frozenset(), frozenset(), frozenset({'RG', 'RM'}), frozenset())),\n",
       " State(elevator=3, floors=(frozenset(), frozenset(), frozenset(), frozenset({'RG', 'RM'})))]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "easy  = State(0, (fs('RG'), Ø, fs('RM'), Ø))\n",
    "\n",
    "astar_search(easy, h_to_top, moves)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now to solve the real problem. The answer we need is the number of elevator moves, which is one less than the path length (because the path includes the initial state)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 11.9 s, sys: 72.3 ms, total: 12 s\n",
      "Wall time: 12 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "31"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "part1 = State(0, (fs('TG', 'TM', 'PG', 'SG'), fs('PM', 'SM'), fs('pM', 'pG', 'RM', 'RG'), Ø))\n",
    "\n",
    "%time path = astar_search(part1, h_to_top, moves)\n",
    "len(path) - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we add four more items. Now, in part one there were 10 items, each of which could be on any of the 4 floors, so that's 4<sup>10</sup> &approx; 1 million states. Adding 4 more items yields &approx; 260 million states. We won't visit every state, but the run time could be around 100 times longer. I think I'll start this running, take the dog for a walk, and come back to see if it worked."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 14min 34s, sys: 11.4 s, total: 14min 46s\n",
      "Wall time: 14min 52s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "part2 = State(0, (fs('TG', 'TM', 'PG', 'SG', 'EG', 'EM', 'DG', 'DM'), \n",
    "                  fs('PM', 'SM'), fs('pM', 'pG', 'RM', 'RG'), Ø))\n",
    "\n",
    "%time path = astar_search(part2, h_to_top, moves)\n",
    "len(path) - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It worked. And it took about 60 times longer. If I wanted to make it more efficient, I would focus on *symmetry*: when there are two symmetric moves, we only need to consider one. For example, in terms of finding the shortest path, it is the same to move, say `{'TG', 'TM'}` or `{'EG', 'EM'}` or `{'DG', 'DM'}` when they are all on the ground floor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 12](http://adventofcode.com/2016/day/12): Leonardo's Monorail\n",
    "\n",
    "This one looks pretty easy: an interpreter for an assembly language with 4 op codes and 4 registers. We start by parsing a line like `\"cpy 1 a\"` into a tuple, `('cpy', 1, 'a')`. Then to `interpret` the code, we set the program counter, `pc`, to 0, and interpret the instruction at `code[0]`, and continue until the `pc` is past the end of the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 318007, 'b': 196418, 'c': 0, 'd': 0}"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def interpret(code, regs):\n",
    "    \"Execute instructions until pc goes off the end.\"\n",
    "    def val(x): return (regs[x] if x in regs else x)\n",
    "    pc = 0\n",
    "    while pc < len(code):\n",
    "        inst = code[pc]\n",
    "        op, x, y = inst[0], inst[1], inst[-1]\n",
    "        pc += 1\n",
    "        if   op == 'cpy': regs[y] = val(x)\n",
    "        elif op == 'inc': regs[x] += 1\n",
    "        elif op == 'dec': regs[x] -= 1\n",
    "        elif op == 'jnz' and val(x): pc += y - 1\n",
    "    return regs\n",
    "\n",
    "def parse(line): \n",
    "    \"Split line into words, and convert to int where appropriate.\"\n",
    "    return tuple((x if x.isalpha() else int(x)) \n",
    "                 for x in line.split())\n",
    "\n",
    "code = [parse(line) for line in Input(12)]\n",
    "\n",
    "interpret(code, dict(a=0, b=0, c=0, d=0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I had a bug initially: in the `jnz` instruction, I had `pc += y`, to do the relative jump, but I forgot the `-1` to offset the previous `pc += 1`.\n",
    "\n",
    "In **part two** all we have to do is initialize register `c` to 1, not 0:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 9227661, 'b': 5702887, 'c': 0, 'd': 0}"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "interpret(code, dict(a=0, b=0, c=1, d=0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 13](http://adventofcode.com/2016/day/13): A Maze of Twisty Little Cubicles \n",
    "\n",
    "This is a maze-solving puzzle, where the maze is infinite in the non-negative (x, y) quarter-plane. Each space in that infinite grid is open or closed according to this computation:\n",
    "> Find `x*x + 3*x + 2*x*y + y + y*y`.\n",
    "Add the office designer's favorite number (your puzzle input).\n",
    "Find the binary representation of that sum; count the number of bits that are 1.\n",
    "If the number of bits that are 1 is even, it's an open space (denoted `'.'`).\n",
    "If the number of bits that are 1 is odd, it's a wall (denoted `'#'`).\n",
    "\n",
    "The problem is to find the length of the shortest path to the goal location, (31, 39). So I'll be using `astar_search` again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "82"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "favorite = 1362\n",
    "goal = (31, 39)\n",
    "\n",
    "def is_open(location):\n",
    "    \"Is this an open location?\"\n",
    "    x, y = location\n",
    "    num = x*x + 3*x + 2*x*y + y + y*y + favorite\n",
    "    return x >= 0 and y >= 0 and bin(num).count('1') % 2 == 0\n",
    "\n",
    "def open_neighbors(location): return filter(is_open, neighbors4(location))\n",
    "\n",
    "path = astar_search((1, 1), lambda p: cityblock_distance(p, goal), open_neighbors)\n",
    "len(path) - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we see a portion of the maze:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#..###.#...#..#....##.#...#....#....#..#.#.##...##.##.##.#####.#####.####.#.##..#..#.#.#.#\n",
      "#.#..#.##.#######.#.#.####.##.###...##.#..#.###...#.#..#.##...#..###....##...##.#.##.#.#..\n",
      "#..#.#.##.#....##...#..#.####.####...#..#..#..#.#...##......#.....######.#.#...##.##.#..##\n",
      "##..##.##.#..#...###.#.....#.....##.######....#..###########.####..##....#...#......###..#\n",
      "..#.##..########.#.#####...#..##.##.#.....##.###.#..#...##.###..#....####.#######.#.#.####\n",
      "#............###.....#####.#####....#..##..#.###....#....#......#..#.##.#....##.###.###..#\n",
      "###.##.####...#.##....#..#.#..#.##.####.##....####.###.#.##.##.###......###........#...#..\n",
      "#.#..#.##.#.#.######..#.##..#.####..#.#######..###..##..#.##.#.##########.#####..#.#.#....\n",
      ".###......#..#..#..####.###..#..#.#.##..#.......###...#....#....##...#......#####..#..##.#\n",
      ".####..###.#.##.#.#...#..#.#.##.##......#..####..#.######.#####....#...##.......#.###..#.#\n",
      "..######.###..###..##.#..###..##.#..##.####...#..##....##.#...#.###.######.######.#.##....\n",
      "#..##..#.......###.#..###......#.#####..#.#...#...#..#....#...#...###....#.##..##.######..\n",
      ".......##.##.#.....#....#.##.#.###..#.#.####..##.###########..##.#....##.....#..##..#..##.\n",
      "#####.#.#.##...###.##...##.#..#..##.##...#######.....##..#######.#########.#.....##.#.#.#.\n",
      "...##..##.#.###..#.###.#.##.#..#..##.#.....#..#####....#..##..##...#..##.#..##.#..###..##.\n",
      ".#.###.#..#...#.##...#..#.#..#.......##..#.##..##.#.##.....#.....#..#...###..#......##.#..\n",
      "##..#..#.######.#####.#..###..##.###.####...#.....#.#.##.#.##.#####...#.####..##.##.#..#.#\n",
      "....##.#.##..#...##.#.##.####..#.###....#...#..###..#..#..#.#....#.##.#..#######.#..##.#..\n",
      "##...#.......#......#.....#.###...########.#####.#..##..#..####..##.#.#...##..#..#...#..#.\n",
      "###.#######.########.##.#.###.##...##..#.#.##..#.#########.##.###.##..###.....##.##.######\n",
      ".##.#...###.##...#.##.#..#.....##....#.##......#.#..#........#..##.#......##.#.#.##.#...#.\n",
      ".##.#.....#....#..#.##.#.####.#.#.##..#.#####.##.#..#..#####......###..##..#..##.#..#...##\n",
      "...###.##.#.###.#.##.###...##..##.#.#......##.#..#.####.....##.##.#####.##..#.#..#####...#\n",
      ".#..##.#..##..##...#.....#..##.#..#..##..#.##.#.##..#.#..##..#.#....#.#######.#.#....##.##\n",
      "###....#...###.#...##.#####.#..#..##.#####..###.#.#.#####.###..#.##.##..#...###...##.##.##\n",
      ".#.##.###.#..#.##.#.###..#..##.#####..........#.##...##.###.##.#.#....#.#.....######.#....\n",
      ".####..##..#.#.##..#.....#...#.#..#####.##.##.##.#.....#.....#...#.##..###.##..#..#..#..##\n",
      "...#.#...#..##..##...###.##.##..#..##.#.##.#...#.##..#.#.##.###..#.#.#..##.#.#..#.#.###...\n",
      "#..##.##..#.###.#.####.#.##.###.#.....#....#.#.######..#.##.#.###..##.#....####..##.#####.\n",
      "##..#######..#..#.....##.....#..######.##..#..#.....#.##.#..###.##..##.##.#..#.#..#..##.#.\n"
     ]
    }
   ],
   "source": [
    "for y in range(30):\n",
    "    print(cat(('.' if is_open((x, y)) else '#') for x in range(90)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we're asked how many locations we can reach in 50 moves or less. I'll grab the `breadth_first` search function from [aima-python](https://github.com/aimacode/aima-python/blob/master/search-4e.ipynb) and modify it to find all the states within N steps:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "138"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def count_locations_within(start, N, neighbors):\n",
    "    \"Find how many locations are within N steps from start.\"\n",
    "    frontier = deque([start]) # A queue of states\n",
    "    distance = {start: 0}     # distance to start; also tracks all states seen\n",
    "    while frontier:\n",
    "        s = frontier.popleft()\n",
    "        if distance[s] < N:\n",
    "            for s2 in neighbors(s):\n",
    "                if s2 not in distance:\n",
    "                    frontier.append(s2)\n",
    "                    distance[s2] = distance[s] + 1\n",
    "    return len(distance)\n",
    "                \n",
    "count_locations_within((1, 1), 50, open_neighbors)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# [Day 14](http://adventofcode.com/2016/day/14): One-Time Pad \n",
    "\n",
    "For this problem I again have to take the md5 hash of a string with increasing integers appended. The puzzle is to find the integer that yields the 64th key, where a hash is a key if:\n",
    "- It contains three of the same character in a row, like 777. Only consider the first such triplet in a hash.\n",
    "- One of the next 1000 hashes in the stream contains that same character five times in a row, like 77777.\n",
    "\n",
    "I'll use `lru_cache` to avoid repeating the hashing of the next 1000."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25427"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "salt = 'yjdafjpo'\n",
    "\n",
    "@lru_cache(1001)\n",
    "def hashval(i): return hashlib.md5(bytes(salt + str(i), 'utf-8')).hexdigest()\n",
    "\n",
    "def is_key(i):\n",
    "    \"A key has a triple like '777', and then '77777' in one of the next thousand hashval(i).\"\n",
    "    three = re.search(r'(.)\\1\\1', hashval(i))\n",
    "    if three:\n",
    "        five = three.group(1) * 5\n",
    "        return any(five in hashval(i+delta) for delta in range(1, 1001))\n",
    "    \n",
    "def nth_key(N): return nth(filter(is_key, range(BIG)), N)\n",
    "\n",
    "nth_key(63)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we do *key stretching*, hashing an additional 2016 times. Eeverything else is the same:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 36.4 s, sys: 314 ms, total: 36.7 s\n",
      "Wall time: 37 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "22045"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@lru_cache(1001)\n",
    "def hashval(i, stretch=2016): \n",
    "    h = hashlib.md5(bytes(salt + str(i), 'utf-8')).hexdigest()\n",
    "    for i in range(stretch):\n",
    "        h = hashlib.md5(bytes(h, 'utf-8')).hexdigest()\n",
    "    return h\n",
    "\n",
    "%time nth_key(63)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This was my highest-scoring day, finishing #20 on part two."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 15](http://adventofcode.com/2016/day/15): Timing is Everything\n",
    "\n",
    "In this puzzle rotating discs with a slot in position 0 spin around. We are asked at what time will all the slots be lined up for a capsule to fall through the slots. The capsule takes one time unit to fall through each disc (not clear why it doesn't accelerate as it falls) and the discs spin one position per time unit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "376777"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def parse(inputs): \n",
    "    \"Parse an input string into (disc#, positions, pos) triples.\"\n",
    "    return [tuple(map(int, triple))\n",
    "            for triple in re.findall(r'#(\\d+).* (\\d+) positions.* (\\d+)[.]', inputs)]\n",
    "    \n",
    "discs = parse('''\n",
    "Disc #1 has 13 positions; at time=0, it is at position 1.\n",
    "Disc #2 has 19 positions; at time=0, it is at position 10.\n",
    "Disc #3 has 3 positions; at time=0, it is at position 2.\n",
    "Disc #4 has 7 positions; at time=0, it is at position 1.\n",
    "Disc #5 has 5 positions; at time=0, it is at position 3.\n",
    "Disc #6 has 17 positions; at time=0, it is at position 5.\n",
    "''')\n",
    "\n",
    "def falls(t, discs):\n",
    "    \"If we drop the capsule at time t, does it fall through all slots?\"\n",
    "    return all((pos + t + d) % positions == 0 \n",
    "               for (d, positions, pos) in discs)\n",
    "\n",
    "first(t for t in range(BIG) if falls(t, discs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "assert discs == [(1, 13, 1), (2, 19, 10), (3, 3, 2), (4, 7, 1), (5, 5, 3), (6, 17, 5)]\n",
    "assert falls(5, [(1, 5, 4), (2, 2, 1)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For **part two**, we add a 7th disc, with 11 positions, at position 0 at time 0. I coud go through all the possible times, just as in part one, but I see a way to get a 19-fold speedup: Disc #2 is the largest, with 19 positions, so we only need consider every 19 values of `t`. But what is the first one to consider? Disc @2 starts at position 10, so to get back to position 0, we have to release at `t=7`, because 10 + 2 + 7 = 19 = 0 mod 19. So we will iterate `t` over `range(7, BIG, 19)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3903937"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "discs.append((7, 11, 0))\n",
    "\n",
    "first(t for t in range(7, BIG, 19) if falls(t, discs))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 16](http://adventofcode.com/2016/day/16) Dragon Checksum\n",
    "\n",
    "Given a bit string of the form `'01...'`, expand it until it fills N bits, then report the checksum.\n",
    "\n",
    "The rules for expanding:\n",
    "- Call the data you have at this point \"a\".\n",
    "- Make a copy of \"a\"; call this copy \"b\".\n",
    "- Reverse the order of the characters in \"b\".\n",
    "- In \"b\", replace all instances of 0 with 1 and all 1s with 0.\n",
    "- The resulting data is \"a\", then a single 0, then \"b\".\n",
    "- If this gives N or more bits, take the first N; otherwise repeat the process.\n",
    "\n",
    "The rules for the checksum:\n",
    "- Assume the string is 110010110100\n",
    "- Consider each pair: 11, 00, 10, 11, 01, 00.\n",
    "- These are same, same, different, same, different, same, producing 110101.\n",
    "- The resulting string has length 6, which is even, so we repeat the process.\n",
    "- The pairs are 11 (same), 01 (different), 01 (different).\n",
    "- This produces the checksum 100, which has an odd length, so we stop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'10010110010011110'"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def expand(a, N):\n",
    "    \"Expand seed `a` until it has length N.\"\n",
    "    while len(a) < N:\n",
    "        b = flip(a[::-1])\n",
    "        a = a + '0' + b\n",
    "    return a[:N]\n",
    "\n",
    "def flip(text, table=str.maketrans('10', '01')): return text.translate(table)\n",
    "\n",
    "def checksum(a):\n",
    "    \"Compute the checksum of `a` by comparing pairs until len is odd.\"\n",
    "    while len(a) % 2 == 0:\n",
    "        a = cat(('1' if a[i] == a[i+1] else '0') \n",
    "                for i in range(0, len(a), 2))\n",
    "    return a\n",
    "    \n",
    "seed = '10010000000110000'\n",
    "\n",
    "checksum(expand(seed, 272))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we take the same seed, but expand it to fill 35Mb of space:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 6.17 s, sys: 326 ms, total: 6.49 s\n",
      "Wall time: 6.54 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'01101011101100011'"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time checksum(expand(seed, 35651584)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 17](http://adventofcode.com/2016/day/17) Two Steps Forward\n",
    "\n",
    "In this puzzle, we move through a 4x4 grid/maze, starting at position (0, 0) and trying to reach (3, 3), but the door from one position to the next is open or not depending on the hash of the path to get there (and my passcode), so doors open and lock themselves as you move around. I'll represent a state as a tuple of `(position, path)` and use `astar_search` to find the shortest path to the goal:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[((0, 0), ''),\n",
       " ((1, 0), 'R'),\n",
       " ((1, 1), 'RD'),\n",
       " ((1, 0), 'RDU'),\n",
       " ((2, 0), 'RDUR'),\n",
       " ((3, 0), 'RDURR'),\n",
       " ((3, 1), 'RDURRD'),\n",
       " ((3, 2), 'RDURRDD'),\n",
       " ((2, 2), 'RDURRDDL'),\n",
       " ((3, 2), 'RDURRDDLR'),\n",
       " ((3, 3), 'RDURRDDLRD')]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "passcode = 'awrkjxxr'\n",
    "\n",
    "openchars = 'bcdef'\n",
    "\n",
    "grid = set((x, y) for x in range(4) for y in range(4))\n",
    "\n",
    "start, goal = (0, 0), (3, 3)\n",
    "\n",
    "def to_goal(state): \n",
    "    \"City block distance between state's position and goal.\"\n",
    "    pos, path = state\n",
    "    return cityblock_distance(pos, goal)\n",
    "\n",
    "directions = [(0, 'U', (0, -1)), (1, 'D', (0, 1)), (2, 'L', (-1, 0)), (3, 'R', (1, 0))]\n",
    "\n",
    "def moves(state):\n",
    "    \"All states reachable from this state.\"\n",
    "    (x, y), path = state\n",
    "    hashx = hashlib.md5(bytes(passcode + path, 'utf-8')).hexdigest()\n",
    "    for (i, p, (dx, dy)) in directions:\n",
    "        pos2 = (x+dx, y+dy)\n",
    "        if hashx[i] in openchars and pos2 in grid:\n",
    "            yield (pos2, path+p)\n",
    "    \n",
    "astar_search((start, ''), to_goal, moves)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we're asked for the longest path to the goal. We have to stop when we reach the goal, but we can make repeated visits to positions along the way, as long as the doors are open. I'll use a depth-first search, and keep track of the longest path length:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "526"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def longest_search(state, goal, moves):\n",
    "    \"Find the longest path to goal by depth-first search.\"\n",
    "    longest = 0\n",
    "    frontier = [state]\n",
    "    while frontier:\n",
    "        state = (pos, path) = frontier.pop()\n",
    "        if pos == goal:\n",
    "            longest = max(longest, len(path))\n",
    "        else:\n",
    "            frontier.extend(moves(state))\n",
    "    return longest\n",
    "            \n",
    "longest_search((start, ''), goal, moves)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 18](http://adventofcode.com/2016/day/18)  Like a Rogue\n",
    "\n",
    "Here we have a cellular automaton, where a cell is a \"trap\" iff the 3 tiles in the row above, (one to the left above, directly above, and one to the right above) are one of the set  `{'^^.', '.^^', '^..', '..^'}`; in other words if the first of the three is different from the last of the three. Given an initial row, we're asked for the count of all the safe tiles in the first 40 rows:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1951"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "safe, trap = '.', '^'  \n",
    "initial = '.^^.^^^..^.^..^.^^.^^^^.^^.^^...^..^...^^^..^^...^..^^^^^^..^.^^^..^.^^^^.^^^.^...^^^.^^.^^^.^.^^.^.'\n",
    "\n",
    "def rows(n, row=initial):\n",
    "    \"The first n rows of tiles (given the initial row).\"\n",
    "    result = [row]\n",
    "    for i in range(n-1):\n",
    "        previous = safe + result[-1] + safe\n",
    "        result.append(cat((trap if previous[i-1] != previous[i+1] else safe)\n",
    "                          for i in range(1, len(previous) - 1)))\n",
    "    return result\n",
    "\n",
    "cat(rows(40)).count(safe)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here I reproduce the simple example from the puzzle page:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['.^^.^.^^^^',\n",
       " '^^^...^..^',\n",
       " '^.^^.^.^^.',\n",
       " '..^^...^^^',\n",
       " '.^^^^.^^.^',\n",
       " '^^..^.^^..',\n",
       " '^^^^..^^^.',\n",
       " '^..^^^^.^^',\n",
       " '.^^^..^.^^',\n",
       " '^^.^^^..^^']"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rows(10, '.^^.^.^^^^')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we just have to run longer (but only a few seconds):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 7.92 s, sys: 90.6 ms, total: 8.01 s\n",
      "Wall time: 8.08 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "20002936"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time cat(rows(400000)).count(safe)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 19](http://adventofcode.com/2016/day/19) An Elephant Named Joseph\n",
    "\n",
    "Elves numbered 1 to *N* sit in a circle. Each Elf brings a present. Then, starting with the first Elf, they take turns stealing all the presents from the Elf to their left. An Elf with no presents is removed from the circle and does not take turns. So, if *N* = 5, then:\n",
    "\n",
    "    Elf 1 takes Elf 2's present.\n",
    "    Elf 2 has no presents and is skipped.\n",
    "    Elf 3 takes Elf 4's present.\n",
    "    Elf 4 has no presents and is also skipped.\n",
    "    Elf 5 takes Elf 1's two presents.\n",
    "    Neither Elf 1 nor Elf 2 have any presents, so both are skipped.\n",
    "    Elf 3 takes Elf 5's three presents, ending the game.\n",
    "    \n",
    "Who ends up with all the presents for general case of *N*?\n",
    "First, I note that I only need to keep track of the Elf number of the remaining elves,\n",
    "I don't need to count how many presents each one has. I see two representation choices:\n",
    "- Represent the circle of elves as a list of elf numbers, and everytime an Elf's presents are taken, delete the elf from the list. But this is O(*N*<sup>2</sup>), where *N* = 3 million, so this will be slow.\n",
    "- Represent the elves by a range, and instead of deleting elf-by-elf, instead limit the range round-by-round.\n",
    "If there is an even number of elves, then the elf in position 0 takes from position 1; position 2 takes from position 3, and so on, leaving only the even positions, which we denote `elves[0::2]`. If there is an odd number of elves, then it is the same, except that the last elf takes from the one in position 0, leaving `elves[2::2]`. Here's the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1842613"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def Elves(N=3018458): return range(1, N+1) \n",
    "\n",
    "def winner(elves): return (elves[0] if (len(elves) == 1) else winner(one_round(elves)))\n",
    "\n",
    "def one_round(elves): return (elves[0::2] if (len(elves) % 2 == 0) else elves[2::2])\n",
    "\n",
    "assert winner(Elves(5)) == 3\n",
    "\n",
    "winner(Elves())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a cool thing about representing the elves with a range: the total storage is O(1), not O(*N*).\n",
    "We never need to make a list of 3 million elements.\n",
    "Here we see a trace of the calls to `one_round`:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "one_round(range(1, 3018459)) = range(1, 3018459, 2)\n",
      "one_round(range(1, 3018459, 2)) = range(5, 3018459, 4)\n",
      "one_round(range(5, 3018459, 4)) = range(5, 3018461, 8)\n",
      "one_round(range(5, 3018461, 8)) = range(21, 3018461, 16)\n",
      "one_round(range(21, 3018461, 16)) = range(53, 3018469, 32)\n",
      "one_round(range(53, 3018469, 32)) = range(53, 3018485, 64)\n",
      "one_round(range(53, 3018485, 64)) = range(181, 3018485, 128)\n",
      "one_round(range(181, 3018485, 128)) = range(437, 3018549, 256)\n",
      "one_round(range(437, 3018549, 256)) = range(437, 3018677, 512)\n",
      "one_round(range(437, 3018677, 512)) = range(1461, 3018677, 1024)\n",
      "one_round(range(1461, 3018677, 1024)) = range(3509, 3019189, 2048)\n",
      "one_round(range(3509, 3019189, 2048)) = range(7605, 3020213, 4096)\n",
      "one_round(range(7605, 3020213, 4096)) = range(7605, 3022261, 8192)\n",
      "one_round(range(7605, 3022261, 8192)) = range(7605, 3022261, 16384)\n",
      "one_round(range(7605, 3022261, 16384)) = range(7605, 3022261, 32768)\n",
      "one_round(range(7605, 3022261, 32768)) = range(7605, 3022261, 65536)\n",
      "one_round(range(7605, 3022261, 65536)) = range(7605, 3022261, 131072)\n",
      "one_round(range(7605, 3022261, 131072)) = range(269749, 3022261, 262144)\n",
      "one_round(range(269749, 3022261, 262144)) = range(794037, 3153333, 524288)\n",
      "one_round(range(794037, 3153333, 524288)) = range(1842613, 3415477, 1048576)\n",
      "one_round(range(1842613, 3415477, 1048576)) = range(1842613, 3939765, 2097152)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1842613"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "one_round = trace1(one_round)\n",
    "winner(Elves())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two** the rules have changed, and each elf now takes from the elf *across* the circle. If there is an even number of elves, take from the elf directly across. Fo example, with 12 elves in a circle (like a clock face), Elf 1 takes from Elf 7. With an odd number of elves, directly across the circle falls between two elves, so choose the one that is earlier in the circle. For example, with 11 elves, Elf 2 takes from the Elf at position 7. Now who ends up with the presents?\n",
    "\n",
    "This is tougher. I can't think of a simple `range` expression to describe who gets eliminated in a round. But I can represent the circle as a list and write a loop to eliminate elves one at a time. Again, if I did that with a `del` statement for each elf, it would be O(*N*<sup>2</sup>). But if instead I do one round at a time, replacing each eliminated elf with `None` in the list, and then filtering out the `None` values, then each round is only O(*N*), and sine there will be log(*N*) rounds, the whole thing is only O(*N* log(*N*)). That should be reasonably fast.\n",
    "\n",
    "It is still tricky to know which elf to eliminate. If there are *N* elves, then the elf at position *i* should elminate the one at position *i* + *N* // 2. But we have to skip over the already-eliminated spaces; we can do that by keeping track of the number of eliminated elves in the variable `eliminated`. We also need to keep track of the current value of `N`, since it will change. And, since I don't want to deal with the headaches of wrapping around the circletconn, I will only deal with the first third of the elves: the first third all eliminate elves in the other two-thirds; if we went more than 1/3 of the way through, we would have to worry about wrapping around. (I had a bug here: at first I just iterated through `N // 3`. But when `N` is 2, that does no iteration at all, which is wrong; with two elves, the first should eliminate the other. It turns out it is safe to iterate through `ceil(N /3)` on each round.)\n",
    "\n",
    "I will change the `Elves` function to return a `list`, not a `range`. The function `winner` stays the same. The `one_round` function is where the work goes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.26 s, sys: 74.7 ms, total: 1.33 s\n",
      "Wall time: 1.34 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1424135"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def Elves(N=3018458): return list(range(1, N+1))\n",
    "\n",
    "def one_round(elves):\n",
    "    \"The first third of elves eliminate ones across the circle from them; who is left?\"\n",
    "    N = len(elves)\n",
    "    eliminated = 0\n",
    "    for i in range(int(math.ceil(N / 3))):\n",
    "        across = i + eliminated + (N // 2) \n",
    "        elves[across] = None\n",
    "        N -= 1\n",
    "        eliminated += 1\n",
    "    return list(filter(None, elves[i+1:] + elves[:i+1]))\n",
    "\n",
    "assert winner(Elves(5)) == 2\n",
    "\n",
    "assert one_round(Elves(5)) == [4, 1, 2]\n",
    "\n",
    "%time winner(Elves())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I was worried that this solution might take over a minute to run, but it turns out to only take about a second."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 20](http://adventofcode.com/2016/day/20) Firewall Rules\n",
    "\n",
    "We are given a list of blocked IP addresses, in the form `\"2365712272-2390766206\"`, indicating the low and high numbers that are blocked by the firewall. I will parse the numbers into `(low, high)` pairs, and sort them by the low number first (and peek at the first 5 to see if I got it right): "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 97802],\n",
       " [5682, 591077],\n",
       " [591078, 868213],\n",
       " [868214, 1216244],\n",
       " [1216245, 1730562]]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pairs = sorted(map(parse_ints, Input(20)))\n",
    "\n",
    "pairs[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are asked what is the lowest non-negative integer that is not blocked.  I will generate all the unblocked numbers, and just ask for the first one. (Why do it that way? Because it feels like `unblocked` is the fundamental issue of the problem, and we already have a function to compute `first`; there's no need for a `first_unblocked` function that conflates two ideas.) To find unblocked numbers, start a counter, `i` at zero, and increment it past the high value of each range, after yielding any numbers from `i` to the low value of the range:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4793564"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def unblocked(pairs):\n",
    "    \"Find the lowest unblocked integer, given the sorted pairs of blocked numbers.\"\n",
    "    i = 0\n",
    "    for (low, high) in pairs:\n",
    "        yield from range(i, low)\n",
    "        i = max(i, high + 1)\n",
    "            \n",
    "first(unblocked(pairs))   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two** we are asked how many numbers are unblocked:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "146"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(list(unblocked(pairs)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# [Day 21](http://adventofcode.com/2016/day/21) Scrambled Letters and Hash \n",
    "\n",
    "In this puzzle we are asked to take a password string, scramble it according to a list of instructions, and output the result, which will be a permutation of the original password. This is tedious because there are seven different instructions, but each one is pretty straightforward. I make the following choices:\n",
    "- I'll transform `password` (a `str`) into `pw` (a `list`), because lists are mutable and easier to manipulate. At the end I'll turn it back into a `str`.\n",
    "- I'll define functions `rot` and `swap` because they get used multiple times by different instructions.\n",
    "- I use the variables `A, B` to denote the first two integers anywhere in a line. If there is only one integer (or none), then `B` (and `A`) get as a default value `0`. I  accept ill-formed instructions, such as `\"move 1 to 4\"` instead of requiring `\"move position 1 to position 4\"`. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'gcedfahb'"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def scramble(password, instructions=list(Input(21)), verbose=False):\n",
    "    \"Scramble the password according to the instructions.\"\n",
    "    pw = list(password) \n",
    "    def rot(N):     pw[:]        = pw[-N:] + pw[:-N]\n",
    "    def swap(A, B): pw[A], pw[B] = pw[B], pw[A]  \n",
    "    for line in instructions:\n",
    "        words = line.split()\n",
    "        A, B, = parse_ints(line + ' 0 0')[:2]\n",
    "        cmd = line.startswith\n",
    "        if   cmd('swap position'): swap(A, B)\n",
    "        elif cmd('swap letter'):   swap(pw.index(words[2]), pw.index(words[5]))\n",
    "        elif cmd('rotate right'):  rot(A)\n",
    "        elif cmd('rotate left'):   rot(-A)\n",
    "        elif cmd('reverse'):       pw[A:B+1] = pw[A:B+1][::-1]\n",
    "        elif cmd('move'):          pw[A:A+1], pw[B:B] = [], pw[A:A+1]\n",
    "        elif cmd('rotate based'):\n",
    "            i = pw.index(words[6])\n",
    "            rot((i + 1 + (i >= 4)) % len(pw))\n",
    "        if verbose: \n",
    "            print(line + ': ' + cat(pw))\n",
    "    return cat(pw)\n",
    "\n",
    "scramble('abcdefgh')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When I ran the first version of this code the answer I got was incorrect, and I couldn't see where I went wrong, so I implemented the test case from the problem description and inspected the results line by line."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "swap position 4 with position 0: ebcda\n",
      "swap letter d with letter b: edcba\n",
      "reverse positions 0 through 4: abcde\n",
      "rotate left 1 step: bcdea\n",
      "move position 1 to position 4: bdeac\n",
      "move position 3 to position 0: abdec\n",
      "rotate based on position of letter b: ecabd\n",
      "rotate based on position of letter d: decab\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'decab'"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test = '''swap position 4 with position 0\n",
    "swap letter d with letter b\n",
    "reverse positions 0 through 4\n",
    "rotate left 1 step\n",
    "move position 1 to position 4\n",
    "move position 3 to position 0\n",
    "rotate based on position of letter b\n",
    "rotate based on position of letter d'''.splitlines()\n",
    "\n",
    "scramble('abcde', test, verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was enough to show me that I had two bugs (which are fixed above): \n",
    "- For `\"reverse\"`, I thought `\"positions 0 through 4\"` meant `[0:4]`, when actually it means `[0:5]`.\n",
    "- For `\"rotate based\"`, in the case where the rotation is longer than the password, I need to take the modulo of the password length.\n",
    "\n",
    "For **part two**, the task is to find the password that, when scrambled, yields `'fbgdceah'`. I think the puzzle designer was trying to tempt solvers into implementing an `unscramble` function, which would be another 20 or 30 lines of code. Fortunately, I was too lazy to go down that path. I realized there are only 40 thousand permutations of an 8-character password, so we can just brute force them all (which would be infeasible with a 20-character password):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'hegbdcfa'}"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{cat(p) for p in permutations('fbgdceah') \n",
    " if scramble(p) == 'fbgdceah'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# [Day 22](http://adventofcode.com/2016/day/22) Grid Computing\n",
    "\n",
    "We are given a description of files across a grid computing cluster, like this:\n",
    "\n",
    "    root@ebhq-gridcenter# df -h\n",
    "    Filesystem              Size  Used  Avail  Use%\n",
    "    /dev/grid/node-x0-y0     92T   70T    22T   76%\n",
    "    /dev/grid/node-x0-y1     86T   65T    21T   75%\n",
    "\n",
    "For part one, we are asked how many pairs of nodes can viably make a transfer of data. The pair (A, B) is viable if\n",
    "- Node A is not empty (its Used is not zero).\n",
    "- Nodes A and B are not the same node.\n",
    "- The data on node A (its Used) would fit on node B (its Avail).\n",
    "\n",
    "I'll represent a node as a `namedtuple` of six integers; the rest is easy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "903"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Node = namedtuple('Node', 'x, y, size, used, avail, pct')\n",
    "\n",
    "nodes = [Node(*parse_ints(line)) for line in Input(22) if line.startswith('/dev')]\n",
    "\n",
    "def viable(A, B): return A != B and 0 < A.used <= B.avail\n",
    "\n",
    "sum(viable(A, B) for A in nodes for B in nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That worked, but let's make sure the nodes look reasonable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Node(x=0, y=0, size=92, used=70, avail=22, pct=76),\n",
       " Node(x=0, y=1, size=86, used=65, avail=21, pct=75),\n",
       " Node(x=0, y=2, size=88, used=73, avail=15, pct=82),\n",
       " Node(x=0, y=3, size=91, used=67, avail=24, pct=73),\n",
       " Node(x=0, y=4, size=87, used=70, avail=17, pct=80)]"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nodes[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we are asked to move data from the node in the upper right (the one with maximum `x` value and  `y=0`) to the upper left (x=0, y=0). At first I worried about all sorts of complications: could we split the data into two or more pieces, copying different pieces into different nodes, and then recombining them? I spent many minutes thinking about these complications. Eventually, after a more careful reading of the rules, I decided such moves were not allowed, and the answer had to just involve moving the empty square around. So to proceed, we need to find the initial position of the empty node, and the maximum x value, so we know where the data is: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Node(x=35, y=21, size=91, used=0, avail=91, pct=0), 37)"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "empty = first(node for node in nodes if node.used == 0)\n",
    "maxx  = max(node.x for node in nodes)\n",
    "\n",
    "empty, maxx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I will also define the `grid` as a dict of `{(x, y): node}` entries (which will enable me to find neighbors of a node):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "grid = {(node.x, node.y): node \n",
    "        for node in nodes}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An `astar_search` seems appropriate.  Each state of the search keeps track of the position of the data we are trying to get, and the position of the currently empty node. The heuristic is the city block distance of the data to the origin:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "215"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "State = namedtuple('State', 'datapos, emptypos')\n",
    "\n",
    "def distance(state): return cityblock_distance(state.datapos)\n",
    "\n",
    "def moves(state):\n",
    "    \"Try moving any neighbor we can into the empty position.\"\n",
    "    for pos in neighbors4(state.emptypos):\n",
    "        if pos in grid:\n",
    "            # Try to move contents of `node` at pos into `empty` at emptypos\n",
    "            node, empty = grid[pos], grid[state.emptypos]\n",
    "            if node.used <= empty.size:\n",
    "                newdatapos = (state.emptypos if pos == state.datapos else state.datapos)\n",
    "                yield State(newdatapos, pos)\n",
    "                        \n",
    "path = astar_search(State((maxx, 0), (empty.x, empty.y)), distance, moves)\n",
    "len(path) - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# [Day 23](http://adventofcode.com/2016/day/23) Safe Cracking\n",
    "\n",
    "This day's puzzle is just like Day 12, except there is one more instruction, `tgl`. I made four mistakes in the process of coding this up:\n",
    "- At first I didn't read the part that says register `'a'` should initially be 7.\n",
    "- I wasn't sure exactly what constitutes an invalid instruction; it took me a few tries to get that right:\n",
    "the only thing that is invalid is a `cpy` that does not copy into a register.\n",
    "- I forgot to subtract one from the `pc` (again!) in the `tgl` instruction.\n",
    "- I forgot that I had `parse` return instructions as immutable tuples; I had to change that to mutable lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def interpret(code, regs):\n",
    "    \"Execute instructions until pc goes off the end.\"\n",
    "    def val(x): return (regs[x] if x in regs else x)\n",
    "    pc = 0\n",
    "    while 0 <= pc < len(code):\n",
    "        inst = code[pc]\n",
    "        op, x, y = inst[0], inst[1], inst[-1]\n",
    "        pc += 1\n",
    "        if   op == 'cpy' and y in regs: regs[y] = val(x)\n",
    "        elif op == 'inc':               regs[x] += 1                  \n",
    "        elif op == 'dec':               regs[x] -= 1                  \n",
    "        elif op == 'jnz' and val(x):    pc += val(y) - 1   \n",
    "        elif op == 'tgl':               toggle(code, pc - 1 + val(x))\n",
    "    return regs\n",
    "\n",
    "def toggle(code, i):\n",
    "    \"Toggle the instruction at location i.\"\n",
    "    if 0 <= i < len(code): \n",
    "        inst = code[i]\n",
    "        inst[0] = ('dec' if inst[0] == 'inc' else \n",
    "                   'inc' if len(inst) == 2 else\n",
    "                   'cpy' if inst[0] == 'jnz' else \n",
    "                   'jnz')\n",
    "\n",
    "def parse(line): \n",
    "    \"Split line into words, and convert to int where appropriate.\"\n",
    "    return [(x if x.isalpha() else int(x)) \n",
    "            for x in line.split()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 11340, 'b': 1, 'c': 0, 'd': 0}"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text = '''\n",
    "cpy a b\n",
    "dec b\n",
    "cpy a d\n",
    "cpy 0 a\n",
    "cpy b c\n",
    "inc a\n",
    "dec c\n",
    "jnz c -2\n",
    "dec d\n",
    "jnz d -5\n",
    "dec b\n",
    "cpy b c\n",
    "cpy c d\n",
    "dec d\n",
    "inc c\n",
    "jnz d -2\n",
    "tgl c\n",
    "cpy -16 c\n",
    "jnz 1 c\n",
    "cpy 84 c\n",
    "jnz 75 d\n",
    "inc a\n",
    "inc d\n",
    "jnz d -2\n",
    "inc c\n",
    "jnz c -5\n",
    "'''.strip()\n",
    "\n",
    "code = [parse(line) for line in text.splitlines()]\n",
    "\n",
    "regs = dict(a=7, b=0, c=0, d=0)\n",
    "\n",
    "interpret(code, regs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two**, we are told to run the same computation, but with register `a` set to 12. We are also warned that this will take a long time, and we might consider implementing a multiply instruction, but I was too lazy to make sense of the assembly code, and just let my interpreter run to completion, even if it takes a while."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 25min 21s, sys: 5.37 s, total: 25min 27s\n",
      "Wall time: 25min 31s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'a': 479007900, 'b': 1, 'c': 0, 'd': 0}"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "code = [parse(line) for line in text.splitlines()]\n",
    "\n",
    "regs = dict(a=12, b=0, c=0, d=0)\n",
    "\n",
    "%time interpret(code, regs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Well, it completed, and gave me the right answer. But I feel like the intent of *Advent of Code* is like *Project Euler*: all code should run in about a minute or less. So I don't think this counts as a \"real\" solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 24](http://adventofcode.com/2016/day/24) Air Duct Spelunking \n",
    "\n",
    "This is another maze-solving problem; it should be easy for my `astar_search`. First the maze:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "maze = tuple(Input(24))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The tricky part is that we have to visit all the digits in the maze, starting at `0`, and not necessarily going in order. How many digits are there?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'\\n', '#', '.', '0', '1', '2', '3', '4', '5', '6', '7'}"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set(cat(maze))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OK, there are 8 digits. What is the start square (the square that currently holds a `'0'`)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(33, 11)"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zero = first((x, y) for y, row in enumerate(maze) for x, c in enumerate(row) if c == '0')\n",
    "zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I'm ready to go. The state of the search will include the x, y position, and also the digits visited so far, which I can represent as a sorted string (a `frozenset` would also work):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "448"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def h(state):\n",
    "    \"Heuristic: the number of digits not yet visited.\"\n",
    "    _, visited = state\n",
    "    return 8 - len(visited) # Note: 8 == len('01234567')\n",
    "    \n",
    "def moves(state):\n",
    "    \"Move to any neighboring square that is not a wall. Track the digits visited.\"\n",
    "    pos, visited = state\n",
    "    for x1, y1 in neighbors4(pos):\n",
    "        c = maze[y1][x1]\n",
    "        if c != '#':\n",
    "            visited1 = (visited if c in visited or c == '.' else cat(sorted(visited + c)))\n",
    "            yield (x1, y1), visited1\n",
    "\n",
    "path = astar_search((zero, '0'), h, moves)\n",
    "len(path) - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **part two** we need to get the robot back to the start square. I'll do that by creating a new heuristic function that still requires us to collect all the digits, and also measures the distance back to the start (`zero`) square."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "672"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def h2(state):\n",
    "    \"Heuristic: the number of digits not yet visited, plus the distance back to start.\"\n",
    "    pos, visited = state\n",
    "    return 8 - len(visited) + cityblock_distance(pos, zero)\n",
    "\n",
    "path2 = astar_search((zero, '0'), h2, moves)\n",
    "len(path2) - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Day 25](http://adventofcode.com/2016/day/25)   Clock Signal\n",
    "\n",
    "This is another assembly language interpreter puzzle. This time there is one more instruction, `out`, which transmits a signal. We are asked to find the lowest positive integer value for register `a` that causes the program to output an infinite series of `0, 1, 0, 1, 0, 1, ...` signals. Dealing with infinity is difficult, so I'll approximate that by asking: what is the lowest value for register `a` that causes the program to output at least 100 elements in the `0, 1, 0, 1, 0, 1, ...` series, within the first million instructions executed?\n",
    "\n",
    "To do that, I'll change `interpret` to be a generator that yields signals, and change it to take an argument saying the number of steps to execute before halting:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def interpret(code, regs, steps=BIG):\n",
    "    \"Execute instructions until pc goes off the end, or until we execute the given number of steps.\"\n",
    "    def val(x): return (regs[x] if x in regs else x)\n",
    "    pc = 0\n",
    "    for _ in range(steps):\n",
    "        if not (0 <= pc < len(code)):\n",
    "            return\n",
    "        inst = code[pc]\n",
    "        op, x, y = inst[0], inst[1], inst[-1]\n",
    "        pc += 1\n",
    "        if   op == 'cpy' and y in regs: regs[y] = val(x)\n",
    "        elif op == 'inc':               regs[x] += 1                  \n",
    "        elif op == 'dec':               regs[x] -= 1                  \n",
    "        elif op == 'jnz' and val(x):    pc += val(y) - 1   \n",
    "        elif op == 'tgl':               toggle(code, pc - 1 + val(x))\n",
    "        elif op == 'out':               yield val(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is my program, and the function `repeats`, which returns True if the code repeats with a given value of the register `a`. Then all we need to do is iterate through integer values for register `a` until we find one that repeats:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "198"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text = '''\n",
    "cpy a d\n",
    "cpy 4 c\n",
    "cpy 633 b\n",
    "inc d\n",
    "dec b\n",
    "jnz b -2\n",
    "dec c\n",
    "jnz c -5\n",
    "cpy d a\n",
    "jnz 0 0\n",
    "cpy a b\n",
    "cpy 0 a\n",
    "cpy 2 c\n",
    "jnz b 2\n",
    "jnz 1 6\n",
    "dec b\n",
    "dec c\n",
    "jnz c -4\n",
    "inc a\n",
    "jnz 1 -7\n",
    "cpy 2 b\n",
    "jnz c 2\n",
    "jnz 1 4\n",
    "dec b\n",
    "dec c\n",
    "jnz 1 -4\n",
    "jnz 0 0\n",
    "out b\n",
    "jnz a -19\n",
    "jnz 1 -21\n",
    "'''.strip()\n",
    "\n",
    "code = [parse(line) for line in text.splitlines()]\n",
    "\n",
    "def repeats(a, code, steps=10**6, minsignals=100):\n",
    "    \"Does this value for register a cause code to repeat `out` signals of 0, 1, 0, 1, ...?\"\n",
    "    signals = interpret(code, dict(a=a, b=0, c=0, d=0), steps)\n",
    "    expecteds = cycle((0, 1))\n",
    "    for (i, (signal, expected)) in enumerate(zip(signals, expecteds)):\n",
    "        if signal != expected:\n",
    "            return False\n",
    "    # We'll say \"yes\" if the code outputs at least a minimum number of 0, 1, ... signals, and nothing else.\n",
    "    return i >= minsignals\n",
    "    \n",
    "first(a for a in range(1, BIG) if repeats(a, code))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's all folks! Thank you [Eric Wastl](http://was.tl/), that was fun!"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}