{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Advent of Code 2018\n",
"\n",
"Peter Norvig
December 2018
\n",
"\n",
"Here are my solutions to [Advent of Code 2018](https://adventofcode.com/2018), following up on my solutions for [2017](Advent%202017.ipynb) and [2016](Advent%20of%20Code.ipynb). In order to understand each day's two-part puzzle, you'll need to click on the header links below (e.g. **[Day 1: Chronal Calibration](https://adventofcode.com/2018/day/1)**) and read the description. This year I didn't find time to race in real time when the puzzles are released; instead I'm doing batch processing, doing a couple of puzzles every few days. You can see I'm currently behind.\n",
"\n",
"\n",
"# Imports and Utility Functions"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"#### IMPORTS\n",
"\n",
"%matplotlib inline\n",
"import matplotlib.pyplot as plt\n",
"import re\n",
"from collections import Counter, defaultdict, namedtuple, deque\n",
"from itertools import chain, cycle, product, islice, count as count_from\n",
"from functools import lru_cache, total_ordering\n",
"from dataclasses import dataclass\n",
"\n",
"#### CONSTANTS\n",
"\n",
"infinity = float('inf')\n",
"bignum = 10 ** 100\n",
"\n",
"#### FILE INPUT AND PARSING\n",
"\n",
"def Input(day, line_parser=str.strip, file_template='data/advent2018/input{}.txt'):\n",
" \"For this day's input file, return a tuple of each line parsed by `line_parser`.\"\n",
" return mapt(line_parser, open(file_template.format(day)))\n",
"\n",
"def integers(text): \n",
" \"A tuple of all integers in a string (ignore other characters).\"\n",
" return mapt(int, re.findall(r'-?\\d+', text))\n",
"\n",
"#### UTILITY FUNCTIONS\n",
"\n",
"def mapt(fn, *args): \n",
" \"Do a map, and make the results into a tuple.\"\n",
" return tuple(map(fn, *args))\n",
"\n",
"def first(iterable, default=None):\n",
" \"Return first item in iterable, or default.\"\n",
" return next(iter(iterable), default)\n",
"\n",
"def nth(iterable, n): return next(islice(iter(iterable), n, n+1))\n",
"\n",
"cat = ''.join\n",
"\n",
"def rangei(start, end, step=1):\n",
" \"\"\"Inclusive, range from start to end: rangei(a, b) = range(a, b+1).\"\"\"\n",
" return range(start, end + 1, step) \n",
"\n",
"def quantify(iterable, pred=bool):\n",
" \"Count how many items in iterable have pred(item) true.\"\n",
" return sum(map(pred, iterable))\n",
"\n",
"def multimap(items):\n",
" \"Given (key, val) pairs, return {key: [val, ....], ...}.\"\n",
" result = defaultdict(list)\n",
" for (key, val) in items:\n",
" result[key].append(val)\n",
" return result"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 1: Chronal Calibration](https://adventofcode.com/2018/day/1)\n",
"\n",
"Part 1 was just a wordy way of saying \"add up the input numbers.\" Part 2 requires cycling through the numbers multiple times, finding the partial sum (frequency) that first appears twice (that is, was seen before)."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"466"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input1 = Input(1, int)\n",
"\n",
"sum(input1)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 466, 'Day 1.1'"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"750"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Part 2\n",
"\n",
"def partial_sums(nums):\n",
" \"The sums of each prefix of nums.\"\n",
" total = 0\n",
" for n in nums:\n",
" total += n\n",
" yield total\n",
" \n",
"def seen_before(items):\n",
" \"The first item that appears twice.\"\n",
" seen = set()\n",
" for item in items:\n",
" if item in seen:\n",
" return item\n",
" seen.add(item)\n",
" \n",
"seen_before(partial_sums(cycle(input1)))"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 750, 'Day 1.2'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 2: Inventory Management System](https://adventofcode.com/2018/day/7)\n",
"\n",
"How many ids have a letter that appears exactly 2 times? 3 times?"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"8118"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input2 = Input(2)\n",
"\n",
"def numwith(ids, n): return quantify(ids, lambda s: n in Counter(s).values())\n",
"\n",
"numwith(input2, 2) * numwith(input2, 3)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 8118, 'Day 2.1'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, what letters are in common among the ids that differ in exactly one position?"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'jbbenqtlaxhivmwyscjukztdp'"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Part 2\n",
"\n",
"def diff(A, B): return sum(a != b for a, b in zip(A, B))\n",
"\n",
"def common(A, B): return cat(a for a,b in zip(A, B) if a == b)\n",
"\n",
"common(*[i for i in input2 if any(diff(i, x) == 1 for x in input2)])"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 'jbbenqtlaxhivmwyscjukztdp', 'Day 2.2'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 3: No Matter How You Slice It](https://adventofcode.com/2018/day/7)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"103806"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input3 = Input(3, integers)\n",
"\n",
"def claimed(claims):\n",
" \"For each square inch position (x, y), how many claims claimed it?\"\n",
" C = Counter()\n",
" for (id, x, y, w, h) in claims:\n",
" C += Counter(product(range(x, x+w), range(y, y+h)))\n",
" return C\n",
"\n",
"def value_ge(dic, threshold):\n",
" \"How many items in dic have a value >= threshold?\"\n",
" return quantify(dic[x] >= threshold for x in dic)\n",
"\n",
"value_ge(claimed(input3), 2)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 103806, 'Day 3.1'"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"625"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Part 2\n",
"\n",
"def claimed2(claims):\n",
" \"Which claim has only positions that are claimed by nobody else?\"\n",
" C = claimed(claims)\n",
" for (id, x, y, w, h) in claims:\n",
" if all(C[pos] == 1 for pos in product(range(x, x+w), range(y, y+h))):\n",
" return id\n",
"\n",
"claimed2(input3)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 625, 'Day 3.2'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 4: Repose Record ](https://adventofcode.com/2018/day/7)\n",
"\n",
"Find the guard that has the most minutes asleep, and the minute of the day that the guard spends asleep the most.\n",
"\n",
"First make sure we can parse the log correctly:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(('1518-11-01', 0, 'Guard', '10'),\n",
" ('1518-11-01', 5, 'falls', 'asleep'),\n",
" ('1518-11-01', 25, 'wakes', 'up'),\n",
" ('1518-11-01', 30, 'falls', 'asleep'),\n",
" ('1518-11-01', 55, 'wakes', 'up'),\n",
" ('1518-11-01', 58, 'Guard', '99'),\n",
" ('1518-11-02', 40, 'falls', 'asleep'),\n",
" ('1518-11-02', 50, 'wakes', 'up'),\n",
" ('1518-11-03', 5, 'Guard', '10'),\n",
" ('1518-11-03', 24, 'falls', 'asleep'),\n",
" ('1518-11-03', 29, 'wakes', 'up'),\n",
" ('1518-11-04', 2, 'Guard', '99'),\n",
" ('1518-11-04', 36, 'falls', 'asleep'),\n",
" ('1518-11-04', 46, 'wakes', 'up'),\n",
" ('1518-11-05', 3, 'Guard', '99'),\n",
" ('1518-11-05', 45, 'falls', 'asleep'),\n",
" ('1518-11-05', 55, 'wakes', 'up'))"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"example4 = '''[1518-11-01 00:00] Guard #10 begins shift\n",
"[1518-11-01 00:05] falls asleep\n",
"[1518-11-01 00:25] wakes up\n",
"[1518-11-01 00:30] falls asleep\n",
"[1518-11-01 00:55] wakes up\n",
"[1518-11-01 23:58] Guard #99 begins shift\n",
"[1518-11-02 00:40] falls asleep\n",
"[1518-11-02 00:50] wakes up\n",
"[1518-11-03 00:05] Guard #10 begins shift\n",
"[1518-11-03 00:24] falls asleep\n",
"[1518-11-03 00:29] wakes up\n",
"[1518-11-04 00:02] Guard #99 begins shift\n",
"[1518-11-04 00:36] falls asleep\n",
"[1518-11-04 00:46] wakes up\n",
"[1518-11-05 00:03] Guard #99 begins shift\n",
"[1518-11-05 00:45] falls asleep\n",
"[1518-11-05 00:55] wakes up'''.splitlines()\n",
"\n",
"def parse_record(text):\n",
" \"Return date, minutes, opcode action, and argument.\"\n",
" text = re.sub('[][#:]', ' ', text)\n",
" day, hour, mins, opcode, arg, *rest = text.split()\n",
" return day, int(mins), opcode, arg\n",
"\n",
"mapt(parse_record, example4)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"defaultdict(list,\n",
" {'1518-11-02': [40, 41, 42, 43, 44, 45, 46, 47, 48, 49],\n",
" '1518-11-04': [36, 37, 38, 39, 40, 41, 42, 43, 44, 45],\n",
" '1518-11-05': [45, 46, 47, 48, 49, 50, 51, 52, 53, 54]})"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def timecard(log):\n",
" \"Return {guard: {day: [asleep_range, ...]}}.\"\n",
" records = sorted(map(parse_record, log))\n",
" sleep = defaultdict(lambda: defaultdict(list)) # sleep[guard][day] = [minute, ...]\n",
" for day, mins, opcode, arg in records:\n",
" if opcode == 'Guard':\n",
" guard = int(arg)\n",
" elif opcode == 'falls':\n",
" falls = mins\n",
" elif opcode == 'wakes':\n",
" wakes = mins\n",
" sleep[guard][day].extend(range(falls, wakes))\n",
" else:\n",
" error()\n",
" return sleep\n",
" \n",
"timecard(example4)[99] # Guard 99's sleep record"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"143415"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def sleepiest_guard(sleep):\n",
" \"Which guard sleeps the most minutes?\"\n",
" return max(sleep, key=lambda guard: sum(map(len, sleep[guard].values())))\n",
"\n",
"def sleepiest_minute(guard, sleep):\n",
" \"In which minute is this guard asleep the most?\"\n",
" def times_asleep(m): return sum(m in mins for mins in sleep[guard].values())\n",
" return max(range(60), key=times_asleep)\n",
"\n",
"def repose(lines):\n",
" \"The ID of the sleepiest guard times that guard's sleepiest minute.\"\n",
" sleep = timecard(lines)\n",
" guard = sleepiest_guard(sleep)\n",
" minute = sleepiest_minute(guard, sleep)\n",
" return guard * minute\n",
"\n",
"repose(Input(4))"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 143415, 'Day 4.1'"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"49944"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Part 2\n",
"\n",
"def repose2(lines):\n",
" \"\"\"Of all guards, which guard is most frequently asleep on the same minute?\n",
" What is the ID of the guard you chose multiplied by the minute you chose?\"\"\"\n",
" sleep = timecard(lines)\n",
" c = Counter((guard, minute) for guard in sleep\n",
" for minute in chain(*sleep[guard].values()))\n",
" [((guard, minute), _)] = c.most_common(1)\n",
" return guard * minute\n",
"\n",
"repose2(Input(4))"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 49944, 'Day 4.2'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 5: Alchemical Reduction](https://adventofcode.com/2018/day/5)\n",
"\n",
"How many units remain after fully reacting the polymer you scanned? Reacting means removing `Cc` and `cC`, etc."
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'dabCBAcaDA'"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input5 = cat(Input(5))\n",
"\n",
"alphabet = 'abcdefghijklmnopqrstuvwxyz'\n",
"ALPHABET = alphabet.upper()\n",
"\n",
"OR = '|'.join\n",
"reaction = OR(OR([c + C, C + c]) for c, C in zip(alphabet, ALPHABET))\n",
"\n",
"def reduction(text):\n",
" \"Remove all cC or Cc pairs, and repeat.\"\n",
" while True:\n",
" text, n = re.subn(reaction, '', text)\n",
" if n == 0:\n",
" return text\n",
" \n",
"reduction('dabAcCaCBAcCcaDA')"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10180"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(reduction(input5))"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 10180, 'Day 5.1'"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5668"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Part 2\n",
"\n",
"def shortest(items): return min(items, key=len)\n",
"\n",
"def reduction2(text):\n",
" \"\"\"What is the length of the shortest polymer you can produce by removing \n",
" all units of exactly one type and fully reacting the result?\"\"\"\n",
" return shortest(reduction(re.sub(c, '', text, flags=re.I))\n",
" for c in alphabet)\n",
"\n",
"len(reduction2(input5))"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 5668, 'Day 5.2'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 6: Chronal Coordinates](https://adventofcode.com/2018/day/6)\n",
"\n",
"Given a set of pointson a grid (all positive integer (x, y) coordinates), each point defines an *area* of grid points that are closer to it than any other point in the set (i.e. the Voronoi diagram). What is the size of the largest area (measured in number of grid points) that isn't infinite? To answer, use a `Counter` over grid points in the bounding box that covers all the input points. \n",
"\n",
"Originally, I thought that if a point on the perimeter of the box was closest to point `p`, then `p` has an infinite area. That's true for `p` that are in the corners, but need not be true for all `p` (consider a set of 5 points, 4 in the corners of a box, and one near the center; the center point will have a diamond-shaped area, and unless it is at the exact center, it will \"leak\" outside one of the edges). So I expand the bounding box by a margin. I make a guess at the necessary margin size, so my answer might not always be correct, but hey, it worked for the input I was given."
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Counter({(3, 4): 9, (5, 5): 17})"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input6 = Input(6, integers)\n",
"\n",
"def closest_to(point, points):\n",
" \"Which of `points` is closest to `point`? Return None if tie.\"\n",
" p1, p2 = sorted(points, key=lambda p: distance(p, point))[:2]\n",
" return p1 if distance(p1, point) < distance(p2, point) else None\n",
"\n",
"def X(point): return point[0]\n",
"def Y(point): return point[1]\n",
"def distance(p, q): return abs(X(p) - X(q)) + abs(Y(p) - Y(q))\n",
"def maxval(dic): return max(dic.values())\n",
"\n",
"def closest_counts(points, margin=100):\n",
" \"What is the size of the largest area of closest points that isn't infinite?\"\n",
" assert len(points) > 1\n",
" xside = range(-margin, max(map(X, points)) + margin)\n",
" yside = range(-margin, max(map(Y, points)) + margin)\n",
" box = product(xside, yside)\n",
" # counts[point] = number of grid points in box that are closest to point\n",
" counts = Counter(closest_to(p, points) for p in box)\n",
" # Now delete the counts that are suspected to be infinite:\n",
" for p in perimeter(xside, yside):\n",
" c = closest_to(p, points)\n",
" if c in counts:\n",
" del counts[c]\n",
" return counts\n",
"\n",
"def perimeter(xside, yside):\n",
" \"The perimeter of a box with these sides.\"\n",
" return chain(((xside[0], y) for y in yside),\n",
" ((xside[-1], y) for y in yside),\n",
" ((x, yside[0]) for x in xside),\n",
" ((x, yside[-1]) for x in xside))\n",
" \n",
"closest_counts([(1, 1), (1, 6), (8, 3), (3, 4), (5, 5), (8, 9)]) "
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3010"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"maxval(closest_counts(input6))"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 3010, 'Day 6.1'"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [],
"source": [
"# Part 2\n",
"\n",
"def total_distance(point, points):\n",
" \"Total distance of this point to all the `points`.\"\n",
" return sum(distance(point, c) for c in points)\n",
"\n",
"def neighborhood(points, dist=10000):\n",
" \"\"\"What is the size of the region containing all locations which have a \n",
" total distance to all given points of less than `dist`?\"\"\"\n",
" maxx = max(x for x,y in points)\n",
" maxy = max(y for x,y in points)\n",
" box = product(range(maxx + 1), range(maxy + 1))\n",
" return quantify(box, lambda p: total_distance(p, points) < dist)"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"48034"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"neighborhood(Input(6, integers))"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 48034, 'Day 6.2'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 7: The Sum of Its Parts](https://adventofcode.com/2018/day/7)\n",
"\n",
"Given instructions like `Step B must be finished before step A can begin`, in what order should the steps be completed? When several steps are possible, do the alphabetically first (`min`) first.\n"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['B', 'A']"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def parse_instruction(line): return re.findall(' ([A-Z]) ', line)\n",
"\n",
"parse_instruction('Step B must be finished before step A can begin.')"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'ABGKCMVWYDEHFOPQUILSTNZRJX'"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input7 = Input(7, parse_instruction)\n",
"\n",
"def order(pairs):\n",
" \"Yield steps in order, respecting (before, after) pairs; break ties lexically.\"\n",
" steps = {step for pair in pairs for step in pair} # Steps remaining to be done\n",
" prereqs = multimap((A, B) for [B, A] in pairs) # prereqs[A] = [B, ...]\n",
" def ready(step): return all(pre not in steps for pre in prereqs[step])\n",
" while steps:\n",
" step = min(filter(ready, steps)) \n",
" steps.remove(step)\n",
" yield step\n",
" \n",
"cat(order(input7))"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 'ABGKCMVWYDEHFOPQUILSTNZRJX', 'Day 7.1'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In part 2 I need to schedule each step; I'll keep track of `endtime[step]` as a time step (initially infinitely far in the future). I'll also keep track of the number of available workers, decrementing the count when I assign a step to a worker, and incrementing the count when a step is completed."
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [],
"source": [
"# Part 2\n",
"\n",
"def schedule(pairs, workers=5):\n",
" \"Return a {step:endtime} map for best schedule, given a number of `workers`.\"\n",
" steps = {step for pair in pairs for step in pair} # Steps remaining to be done\n",
" prereqs = multimap((A, B) for (B, A) in pairs) # prereqs[A] = [B, ...]\n",
" endtime = {step: infinity for step in steps} # endtime[step] = time it will be completed\n",
" for t in count_from(0): \n",
" # Assign available steps to free workers\n",
" def ready(step): return all(endtime[p] < t for p in prereqs[step])\n",
" available = filter(ready, steps)\n",
" for step in sorted(available)[:workers]:\n",
" endtime[step] = t + 60 + ord(step) - ord('A')\n",
" steps.remove(step)\n",
" workers -= 1\n",
" # Discover if any workers become free this time step\n",
" workers += quantify(endtime[step] == t for step in endtime)\n",
" # Return answer once all steps have been scheduled\n",
" if not steps:\n",
" return endtime"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'U': 354,\n",
" 'I': 423,\n",
" 'M': 133,\n",
" 'X': 897,\n",
" 'K': 132,\n",
" 'W': 144,\n",
" 'J': 813,\n",
" 'T': 503,\n",
" 'D': 259,\n",
" 'B': 61,\n",
" 'P': 408,\n",
" 'L': 426,\n",
" 'E': 198,\n",
" 'O': 273,\n",
" 'A': 60,\n",
" 'F': 332,\n",
" 'Y': 84,\n",
" 'C': 195,\n",
" 'V': 215,\n",
" 'Z': 665,\n",
" 'S': 505,\n",
" 'G': 66,\n",
" 'H': 266,\n",
" 'N': 579,\n",
" 'Q': 350,\n",
" 'R': 743}"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"schedule(input7)"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"898"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"maxval(schedule(input7)) + 1"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 898, 'Day 7.2'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 8: Memory Maneuver](https://adventofcode.com/2018/day/8)\n",
"\n",
"I'll handle the list of numbers as a `deque` (so I can efficiently pop from the left), and I'll create a `Tree` data structure with `metadata` and `kids` (children) fields."
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [],
"source": [
"input8 = integers(cat(Input(8)))\n",
" \n",
"Tree = namedtuple('Tree', 'kids, metadata')\n",
"\n",
"def tree(nums):\n",
" \"\"\"A node consists of the numbers: [k, n, (k child nodes)..., (n metadata values)...].\"\"\"\n",
" k, n = nums.popleft(), nums.popleft()\n",
" return Tree([tree(nums) for _ in range(k)], \n",
" [nums.popleft() for _ in range(n)])\n",
"\n",
"example8 = tree(deque((2, 3, 0, 3, 10, 11, 12, 1, 1, 0, 1, 99, 2, 1, 1, 2)))\n",
"tree8 = tree(deque(input8))"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"138"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def sum_metadata(tree):\n",
" \"What is the sum of all metadata entries in a tree?\"\n",
" return sum(tree.metadata) + sum(map(sum_metadata, tree.kids))\n",
"\n",
"sum_metadata(example8)"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"48443"
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sum_metadata(tree8)"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 48443, 'Day 8.1'"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [],
"source": [
"def value(tree):\n",
" \"\"\"What is the value of the root node? \n",
" Value of tree with no kids is sum of metadata; \n",
" Otherwise metadata are 1-based indexes into kids; sum up their values.\"\"\"\n",
" if not tree.kids:\n",
" return sum(tree.metadata)\n",
" else:\n",
" return sum(value(tree.kids[i - 1]) \n",
" for i in tree.metadata \n",
" if i <= len(tree.kids)) "
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"66"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"value(example8)"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"30063"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"value(tree8)"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 30063, 'Day 8.2'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 9: Marble Mania](https://adventofcode.com/2018/day/9)\n",
"\n",
"I'll represent the circle as a `deque` (so I can `rotate`). I had a couple of off-by-one errors, due in part to the problem being 1-based not 0-based, so I put in the `verbose` option; in my verbose output (unlike the problem description), the circle always starts with the position after the \"current\" position, and the newly-inserted marble is always last."
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1 [0, 1]\n",
"2 [1, 0, 2]\n",
"3 [0, 2, 1, 3]\n",
"4 [2, 1, 3, 0, 4]\n",
"5 [1, 3, 0, 4, 2, 5]\n",
"6 [3, 0, 4, 2, 5, 1, 6]\n",
"7 [0, 4, 2, 5, 1, 6, 3, 7]\n",
"8 [4, 2, 5, 1, 6, 3, 7, 0, 8]\n",
"9 [2, 5, 1, 6, 3, 7, 0, 8, 4, 9]\n",
"1 [5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 10]\n",
"2 [1, 6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11]\n",
"3 [6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12]\n",
"4 [3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13]\n",
"5 [7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14]\n",
"6 [0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15]\n",
"7 [8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16]\n",
"8 [4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17]\n",
"9 [9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18]\n",
"1 [2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 9, 19]\n",
"2 [10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 9, 19, 2, 20]\n",
"3 [5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 9, 19, 2, 20, 10, 21]\n",
"4 [11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 9, 19, 2, 20, 10, 21, 5, 22]\n",
"5 [2, 20, 10, 21, 5, 22, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 19]\n",
"6 [20, 10, 21, 5, 22, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 19, 2, 24]\n",
"7 [10, 21, 5, 22, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 19, 2, 24, 20, 25]\n"
]
},
{
"data": {
"text/plain": [
"Counter({5: 32})"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"players, marbles = integers('448 players; last marble is worth 71628 points')\n",
"\n",
"def play(players, marbles, verbose=False):\n",
" \"Add `marbles` to `circle`, rotating according to rules and scoring every 23 marbles.\"\n",
" circle = deque([0])\n",
" scores = Counter()\n",
" for m in rangei(1, marbles):\n",
" player = (m - 1) % players + 1\n",
" if m % 23:\n",
" circle.rotate(-1)\n",
" circle.append(m)\n",
" else:\n",
" circle.rotate(+7)\n",
" scores[player] += circle.pop() + m\n",
" circle.rotate(-1)\n",
" if verbose: print(player, list(circle))\n",
" return scores\n",
"\n",
"play(9, 25, True)"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"394486"
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"maxval(play(players, marbles))"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 394486, 'Day 9.1'"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3276488008"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"maxval(play(players, marbles * 100))"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 3276488008, 'Day 9.2'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 10: The Stars Align](https://adventofcode.com/2018/day/10)\n",
"\n",
"\n",
"The basic idea of moving objects into a new configuration is easy: increment their position by their velocity to get a set of points. The hard part is figuring out when they spell a message. My assumption is that the lights are initially spread far afield; over time they will come together into a central location; then they will overshoot and go off in the other direction. My even bigger (but still resonable) assumption is that the message is spelled when the area of the bounding box of the points is a minimum. When that happens, I'll just print the configuration, and read what is there. (I won't write code to do OCR.)"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [],
"source": [
"Light = namedtuple('Light', 'x, y, dx, dy')\n",
"\n",
"input10 = Input(10, lambda line: Light(*integers(line)))\n",
"\n",
"def configuration(t, lights=input10):\n",
" \"The positions of the lights at time t.\"\n",
" return {(L.x + t * L.dx, L.y + t * L.dy) for L in lights}\n",
" \n",
"def bounds(points):\n",
" \"Return xmin, xmax, ymin, ymax of the bounding box.\"\n",
" return (min(map(X, points)), max(map(X, points)),\n",
" min(map(Y, points)), max(map(Y, points)))\n",
"\n",
"def extent(points):\n",
" \"Area of bounding box.\"\n",
" xmin, xmax, ymin, ymax = bounds(points)\n",
" return (xmax - xmin) * (ymax - ymin)\n",
"\n",
"def localmin(sequence, key):\n",
" \"Iterate through sequence, when key(item) starts going up, return previous item.\"\n",
" prevscore = infinity\n",
" for item in sequence:\n",
" score = key(item)\n",
" if prevscore < score:\n",
" return prev\n",
" prev, prevscore = item, score\n",
" \n",
"def lightshow(points, chars='.#'):\n",
" \"Print out the locations of the points.\"\n",
" xmin, xmax, ymin, ymax = bounds(points)\n",
" for y in rangei(ymin, ymax):\n",
" print(cat(chars[(x, y) in points] for x in rangei(xmin, xmax)))"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"#####...#....#.....###..#....#.....###....##....######..#....#\n",
"#....#..#....#......#...#....#......#....#..#...#.......#....#\n",
"#....#...#..#.......#....#..#.......#...#....#..#........#..#.\n",
"#....#...#..#.......#....#..#.......#...#....#..#........#..#.\n",
"#####.....##........#.....##........#...#....#..#####.....##..\n",
"#....#....##........#.....##........#...######..#.........##..\n",
"#....#...#..#.......#....#..#.......#...#....#..#........#..#.\n",
"#....#...#..#...#...#....#..#...#...#...#....#..#........#..#.\n",
"#....#..#....#..#...#...#....#..#...#...#....#..#.......#....#\n",
"#####...#....#...###....#....#...###....#....#..######..#....#\n"
]
}
],
"source": [
"configurations = map(configuration, count_from(0))\n",
"lights = localmin(configurations, key=extent)\n",
"lightshow(lights)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That should be \"`BXJXJAEX`\".\n",
"\n",
"In Part 2 I need to get the time `t` at which we generate the configuration `lights`:"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10605"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Part 2\n",
"\n",
"next(t for t in count_from(1) if configuration(t) == lights)"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 10605"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 11: Chronal Charge](https://adventofcode.com/2018/day/11)"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(30, (243, 27), 3)"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"serial = input11 = 6303\n",
"\n",
"def power_level(point):\n",
" \"Follow the rules for power level.\"\n",
" id = X(point) + 10\n",
" level = (id * Y(point) + serial) * id\n",
" return (level // 100) % 10 - 5\n",
"\n",
"def total_power(topleft, width=3):\n",
" \"Total power in the square with given topleft corner and width.\"\n",
" x, y = topleft\n",
" square = product(range(x, x + width), range(y, y + width))\n",
" return sum(map(power_level, square))\n",
"\n",
"def maxpower(bounds=300, width=3):\n",
" \"Return (power, topleft, width) of square within `bounds` of maximum power.\"\n",
" toplefts = product(rangei(1, bounds - width), repeat=2)\n",
" return max((total_power(topleft, width), topleft, width)\n",
" for topleft in toplefts)\n",
"\n",
"maxpower()"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [],
"source": [
"assert _[1] == (243, 27), 'Day 11.1'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To enumerate all the squares of any width is O(n4); too much when *n* = 300. So I'll refactor `total_power` to cache results in a summed-area table (a standard approach from computer graphics)."
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [],
"source": [
"# Part 2\n",
"\n",
"def summed_area(side, key):\n",
" \"A summed-area table.\"\n",
" I = defaultdict(int)\n",
" for x, y in product(side, side):\n",
" I[x, y] = key((x, y)) + I[x, y - 1] + I[x - 1, y] - I[x - 1, y - 1]\n",
" return I\n",
"\n",
"def total_power(topleft, width=3, I=summed_area(rangei(1, 300), power_level)):\n",
" \"Total power in square with given topleft corner and width (from `I`).\"\n",
" x, y = topleft\n",
" xmin, ymin, xmax, ymax = x - 1, y - 1, x + width - 1, y + width - 1\n",
" return I[xmin, ymin] + I[xmax, ymax] - I[xmax, ymin] - I[xmin, ymax]\n",
"\n",
"# Make sure we get the same answer for the Part 1 problem\n",
"assert maxpower() == (30, (243, 27), 3)"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(88, (284, 172), 12)"
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max(maxpower(width=w) for w in range(300))"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [],
"source": [
"assert _[1] + _[2:] == (284, 172, 12), 'Day 11.2'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 12: Subterranean Sustainability](https://adventofcode.com/2018/day/12)\n",
"\n",
"One-dimensional cellular automata. Fun! AT first I thought I would represent a row of plants as a string, but I realized I'd also need to track the start position of the string, so I decided it was easier to represent a row of plants as a set of index numbers of pots that are live. I'll make `grow()` yield all future generations:"
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1447"
]
},
"execution_count": 60,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def Plants(row):\n",
" \"Convert '#..#.#' => {0, 3, 5}\"\n",
" return {i for i, c in enumerate(row) if c == '#'}\n",
"\n",
"input12 = Input(12, str.split)\n",
"plants = Plants(input12[0][-1])\n",
"rules = {rule[0]: rule[-1] for rule in input12 if '=>' in rule}\n",
"\n",
"def grow(plants=plants, rules=rules):\n",
" \"Grow plants using rules, yielding each generation (including 0th).\"\n",
" while True:\n",
" yield plants\n",
" extent = rangei(min(plants) - 3, max(plants) + 3)\n",
" plants = {i for i in extent if lives(plants, i, rules)}\n",
"\n",
"def lives(plants, i, rules):\n",
" \"Does pot i live in next generation, according to rules?\"\n",
" neighborhood = cat('.#'[j in plants] for j in rangei(i - 2, i + 2))\n",
" return rules[neighborhood] == '#'\n",
"\n",
"sum(nth(grow(), 20))"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 1447, 'Day 12.1' "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Cool, my answer is leet-er than `1337`. But Part 2, asks for 50 billion generations. Maybe the pattern reaches a fixed point, or cycles, like the blinker in Conway's Life game. Let's plot the number of plants, and their sums, over the first couple hundred generations and see if there is a pattern:"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzt3XmU22d97/H3V7tGmn3GzsQziWPHzgaJQ5w0ThqWJEBI2NrSlp7eFi5wU3rhlECXQHvPLb23Pb3QUjhdLjQ0QGjhEsqapiwJgQAhqxOcOMZZ7LGT8RLbs3gWjUbrc//4LfpJI2k0m0bSfF/n+FjzG0nzjDz+6Jnvs4kxBqWUUs3Pt9YNUEoptTI00JVSqkVooCulVIvQQFdKqRahga6UUi1CA10ppVqEBrpSSrUIDXSllGoRGuhKKdUiAvX8Yn19fWbz5s31/JJKKdX0Hn/88VFjTP9C96troG/evJndu3fX80sqpVTTE5EXarmfllyUUqpFaKArpVSL0EBXSqkWoYGulFItQgNdKaVahAa6Ukq1CA10pZRqEU0R6PftP8H/vf/AWjdDKaUaWlME+k+fH+Uz9x9c62YopVRDa4pAj4X9JNI59EBrpZSqrEkCPUAub0hl82vdFKWUalhNEejxsLXlzEwqu8YtUUqpxtUUgR4LWYGe0EBXSqmKmiPQtYeulFILaopAd0ouiVRujVuilFKNqykCPRb2A1pyUUqpapoi0HVQVCmlFtYUgR4L66CoUkotpKkCXXvoSilVWXMEesipoeugqFJKVdIUgR7w+4gEfSTS2kNXSqlKmiLQAeLhoJZclFKqiiYKdL8OiiqlVBWBWu4kIoeBaSAHZI0xO0WkB7gT2AwcBn7DGDOxOs20BkY10JVSqrLF9NBfY4zZYYzZaX/8YeA+Y8w24D7741UTCweYntNAV0qpSpZTcnkLcId9+w7grctvTmXxcEAHRZVSqopaA90A94jI4yJys31tozHmOID994ZyDxSRm0Vkt4jsPnXq1JIbapVcdNqiUkpVUlMNHbjaGHNMRDYA94rIM7V+AWPMbcBtADt37lzykUPxsF9nuSilVBU19dCNMcfsv08C3wSuAE6IyACA/ffJ1WokWHui66CoUkpVtmCgi0hMRNqd28DrgKeBu4B32Hd7B/Dt1WokWCWX2XSOfF7PFVVKqXJqKblsBL4pIs79v2yM+Z6IPAZ8VUTeDbwI/PrqNdOzJ3o6S3skuJpfSimlmtKCgW6MGQYuKXN9DLhuNRpVTsxzyIUGulJKzdc0K0WdQy50YFQppcprmkCP657oSilVVdMEuh5yoZRS1TVNoOsxdEopVV3TBbou/1dKqfKaJtALx9Dp8n+llCqnaQK9zT6GLqk9dKWUKqtpAj3ot5qayelKUaWUKqeJAl0AyOTya9wSpZRqTE0T6CJC0C8a6EopVUHTBDpYZRctuSilVHlNF+jp7NJ66A8Pj/HoofEVbpFSSjWOpgv0pZZcPnHPs3zy3udWuEVKKdU4mirQQ8uooSczOdJaf1dKtbBaj6BrCMHA0mvo6Wwen7Wnu1JKtaTmCnS/b8m9bA10pVSra6pAD/iEzBIHRdPZPH6fBrpSqnU1Vw09sPRB0VQ2r1MelVItrakCfTnz0NPZvC5KUkq1tCYLdFlyDT2V00BXSrW2Jgv0pZVcjDGks/klL0pSSqlmUHOgi4hfRH4uInfbH39BRA6JyB77z47Va6YltMRAd3r1WkNXSrWyxcxy+QCwH+jwXPtjY8zXVrZJlQX9PjLZxYey0zPXkotSqpXV1EMXkUHgJuBfVrc51QWXOMvFCfRs3pDPay9dKdWaai25fAr4E6A0Tf9KRJ4SkU+KSLjcA0XkZhHZLSK7T506tZy2LnlQ1PuYTF576Uqp1rRgoIvIG4GTxpjHSz71EeB84HKgB7i13OONMbcZY3YaY3b29/cvq7FLraGnMp5A1zq6UqpF1dJDvxp4s4gcBr4CXCsi/2aMOW4sKeDzwBWr2E5g6fPQi3roOtNFKdWiFgx0Y8xHjDGDxpjNwNuBHxpj/ouIDACIiABvBZ5e1ZbiDIouvYYOOjCqlGpdy9nL5Usi0g8IsAd478o0qbJgYGk19FQ2597WLXSVUq1qUYFujLkfuN++fe0qtKcqbw39zsde5JfO6WVzXwyAk9Nz3LXnGO/+5XMQe1fF+/afoDMaLC65aA1dKdWimm6laN5YZZNbv76XO3ePuJ/75hNH+cv/3M+RiaR77ePfe5bP/PigllyUUutCUwV6wG/1vKfnsgBMJTPu50YmZgEYS6Tda3PZHIlUrijQdfm/UqpVNVWgh/xWc6fnrCCf9Ab6uNUzH5tJudfS2TyzmRwp7aErpdaBpgr0oBvodg/d/hvgiNNDnyn00NPZPMl0tqTkojV0pVRraspAd0otTg/dGOPWzkcThR56KptnNl18OHRWe+hKqRbVZIFu1dCdnvm0HeinplNuWaW0hz6XKamha6ArpVpUUwV6KFBcQ5+y/x7xzGwZtwdFjTGkc1YP3TsPXUsuSqlW1VSB7pZc7B76ZDJjl1us+nl7OMCoPSjq9MSTmVzJXi7aQ1dKtaamDHSnh57JGeYyeUbGrUB/+WCnW3JxSjDGwHSqMHiqga6UalVNFujF89DBKrscmUjSFw+zqSvKmD0o6q2bTySK6+pKKdWKmirQQyWzXMAqu4xMzDLYHaU3HmY8kXbPEHWc9txfa+hKqVbVVIEeDBTPQwcr3EfGkwz1tNEXD5HJGabmiueeT85m8Fmd+6YpuZycmuOff3wQY/QNSClVm+YKdKeGnir0uCdmMxw7nWSoO0pvPARYq0VTRT30NLGwtQ9ZswT6f+49zl9/9xmOTc6tdVOUUk2iyQLdnoeeLPTQnzsxTTZvGOxuozdmnYI3lkgXl1xmM8TtQG+WeejOoqmEZ0BXKaWqaapAL93LBWDfsUkAhnqi9MQKPfR0rjD3/PRsptBDzzZHCcN505rRQFdK1aipAt27l0vYrqfvOzYFwFB3G33xQg89VbI6NBr04/dJ05RcnEVT2kNXStWquQI94CwsytAeCdAW8vPC2CwiMNAV8fTQiwMdrFWmQX/zBLqWXJRSi9VcgW5PVcnkDOGAn45IEIAzOiKEA35CAR8dkYBVcikJ9HDAR9DvI53L8+CBUb6/76W6t38xnKmZM6ncAvdUSinLcs4UrTun5AIQDfnxi/DS1BxD3W3u9a62EKeTmXmBHrIDPZPL85mfDPPSZJLXX3RG3dq+WM72BjOe8QKllKqmuQI9UAj0SNBHNOgHYLA76l5vC/lJpnPzSy5+u+SSNczMZYpmyjQip4eeSGsPXSlVm5pLLiLiF5Gfi8jd9sfniMgjIvK8iNwpIqHVa6bFmbYIEPGUXAZ7Cj30SNBPsmTLXCjuoSdSOXfQsVEVSi6N/cajlGoci6mhfwDY7/n4Y8AnjTHbgAng3SvZsHKCvuKSS2fUCvShkh76bDpH2t4y12/X3cMBPyG7hj6TyjKbzjXsAGkub9wNxXRQVClVq5oCXUQGgZuAf7E/FuBa4Gv2Xe4A3roaDfTy+YSAJ6A77EAf9NTQ3UC3w9oJ/aIeenr+IdONxDvPXnvoSqla1dpD/xTwJ4DTpe0FThtjnLQ5Amxa4baV5QyMRoLWjBawFhU5oqEAyXTW3QO9q80K9HDARzAgZHLG7fV6zyRtJN76vreH/p29x3nw4OhaNEkp1QQWDHQReSNw0hjzuPdymbuWXYIpIjeLyG4R2X3q1KklNrPAqaNHg36uOreP11+0kYFOT8klWOihi0B7xBPofh+JVNbdcXGyQXvo3vp+wjNt8W/veZbPPXBoLZqklGoCtcxyuRp4s4jcCESADqwee5eIBOxe+iBwrNyDjTG3AbcB7Ny5c9nr7p1j6CJBP1du6eXKLb1Fn4/as1zS2TzhgI82eyaMU3I5PVsIy0YtuThvNOGAr6jkMpXMzpu9o5RSjgV76MaYjxhjBo0xm4G3Az80xvw28CPgbfbd3gF8e9Va6eEtuZTTFrJmuaSyeUJ+H20hO9D9PkJ+HxOzhcMuGnWmi/NGc2ZXtKjkMjU3f369Uko5lrNS9FbgQyJyAKumfvvKNKk6J9CdOeil2kJ+snmrTh4K+ImGvD10KeqhN3rJZaAz4gb6nD0VU3voSqlKFrWwyBhzP3C/fXsYuGLlm1SdU0MPVwj0aMj6lk4nM1bJxQ5079J/R6MuLnLeaAY6ozx91NpN0um1aw9dKVVJU60UBW/JpXIPHaxTiqxAt77FUMBftNIUGq/kcmg0wXf2Hmc2ncUnsKEjTCKdwxjjtrVZ9nNXStVfU23OBYVB0WolF4CJ2TShgM8N/lDA5+6n7mi0kstde47xN99/lideOE1HNEg8HCCXN6Syebet2kNXSlXSdIG+0KCoE+CnkxlC80ouhdmW4YCv4Wa5OL3wRw+P0xkN0m7Ps59JZd3yUCqre7sopcprukB3VorWUnIpmuVi19AdZ3ZFG25hkdMLz+UNHZEgMbtclEhlCyUX7aErpSpoukCvteSSzuUJB30ls1wK3+5AZ6ThSi7e3xg6ogH32LyZVFZLLkqpBTVdoDuhHK5QcokGC+O83h562O9z3wzCAR/dsRDTjRbonkHaTruGDtZqUSfsddqiUqqSJgz02kouYPXKnYAPBws19Hg4QGc02HCzXCaTWS4c6ACwSi5h63uxSi5WeSibN+TzzXHQtVKqvpow0GsruYA1VfHSs7p45fZ+zt3Q7j42Fg7QEQkymcxgTOOE41Qyw/kD7fzmziFefd4Gt4c+ncoy6VkQpVMXlVLlNN089NAC89CjnkAPB3xs7IjwxXdZ65+KAj0aIJMzzGXyRY9ZS1NzGToiQT765osAOHY6CRQPioJVdqn0/Sul1q+m7aFX3svFU0MvWUhUKLkUDsdolLJLPm+YSWXdPd4Bd1B0fqDr1EWl1HzNF+iBwva55fh94gZ56UKi0pILNM7ioum5LMYUDuQA3JKLd5YL6EwXpVR5zRfoC5RcgKLFROUeGw8H3J5woywucnrgzqEdYL05RYN+q4eezLrH6WmgK6XKadoaemlYe7UF/ZwmM+8+IU+glyu5PHponDseOuwe1XHeGe38wXXbip7j6OkkX3n0RT54/XZ8vnLnfNTGGMM//vAAb7rkTDb3xdweuLfkAtZvEzP2oda9sRAnp1M6KKqUKqvpeujXbOvnt64YwjrWtLyIZzGRl1OuiYUD9MZCAJycSrmf/9IjL3DvvhM8e2Kah4bH+NQPnpv33Pfse4l/+OEBhkcTy/o+puayfOLe5/jPvcetj+1A7ywJ9E1dEQ6cnGYqmaEvHgZwj9dTSimvpgv0X97Wx1//6sVV79NWKdA9NfSBzgh+n3BkIul+/shEksvO7uYHH3oV//WqzeQNZEt6w87+5EcmZpf1fTgDm4XzTZ2SS3GgX7mll8dfmCBvoL/dCnTtoSulymm6QK9Fm7OYKFBcZy/U0P0E/D4GOiOMeIJ5ZHzWPXDaeTMoXZk5Y5/xOeJ5I1gKp5ftBrq9+VZHtLgKduXWXpx1RG6gaw1dKVVGSwZ6tEIPPeTpoQMMdbcxMm4F+lwmx8npFIPdbUWPLQ1Pt4c+vrweutPLdt4gJiuUXC7f3ONuSOYEuk5bVEqV05KB7j1H1Ms7ywVgsDvqllyO2ot4nB6607svLW8USi7L66E7bxTekotPcHdYdMTDAS4e7ARwa+jaQ1dKldOSgV6ph+4sLHJCc6injZPTKeYyObenPrRAD33GDuCRiVlOTs3xl3f/gkyNNe183vA333+G45PJQqCnnZJLhvZIsOzMmV1bewFvD10DXSk1X0sGeqV56Oef0cF152/gkqEuoNAbPzKRdGvipSWX0vKGE8Aj47N8dfcI//LAIffcz4UcPZ3kn350kPv2n3RD2XmDmExm5pVbHL/6ikGuO38DF5zRDmgPXSlVXosGunOOaPG319kW5PZ3Xu72dJ3e+JGJWY5MzBIK+Nhgf84p11QaFJ2YzXDv/pNA7QOkTvkmnc27oTwz55RcsvMGRB1b++Pc/s7L3cDXHrpSqpwFA11EIiLyqIg8KSL7ROQv7OtfEJFDIrLH/rNj9Ztbm2iwfMmllNMbH5lIcmQ8yWBX1C15OPutlxsUdQYpnxw5DdQ+hdGZ2TKXzZHOlUxbTGbmTVksVakMpJRSUNtK0RRwrTFmRkSCwAMi8l37c39sjPna6jVvaSqVXEptaA8TCvg4Mj7LyMQsm7qj7ufCFXroiVSWrf1xnj0x7V4bGV9cDz2V8fTQPSWXczfEqz6+0kCtUkpBDT10Y5mxPwzafxpnE/EyCoFefYtZn08Y7LJmuhyZSDLU0+Z+ruKg6FyW8wesWrZPYEtfrOYeuvNcqWzefaNIpHMYY9ytc6vRHrpSqpqaaugi4heRPcBJ4F5jzCP2p/5KRJ4SkU+KSHjVWrlI0Qo19HIGe9p48OAo44m0W1MHT2/YE57GGBLpLEPdbbSF/LxsUycXnNlR8xTGQqDn3EDP5Q2pbJ6pZOUausPvE/w+cQdqZ9NZPnrXvobZAlgptbZqCnRjTM4YswMYBK4QkZcBHwHOBy4HeoBbyz1WRG4Wkd0isvvUqVMr1Ozqrtjcww0XncFZnh53JW++5Ew2dkS4eLCTa7b1udfd3rCnvJHM5Mgba2HS7+7azLuuPoeh7jaOTiRrOhbOCeKUZ1AUYCyRJpnJ0dUWWvA5Qn6f+9hHhsf5woOHeejg2IKPU0q1vkXttmiMOS0i9wM3GGP+1r6cEpHPA39U4TG3AbcB7Ny5sy6lmrN62/jM71xW033fdtkgb7tscN71ctMWnXp3POzn91+9FYB/e/gF0rk8J6bnGOiMznseL7eHnskX1eZfGLM2+nI2DKsmHCwEurNtwXgiveDjlFKtr5ZZLv0i0mXfjgLXA8+IyIB9TYC3Ak+vZkPrrVy9OmFPWXS2DgDcunstZRd3UDSbK3reF8esYO6NL1y1Cvl97puBsxhqbCZV7SFKqXWilh76AHCHiPix3gC+aoy5W0R+KCL9gAB7gPeuYjvrLlw20K0eelGg2zNjRsZnuXxzT9XndKctZopLLi+OO4FeQ8klUOihO28iozPaQ1dK1RDoxpingEvLXL92VVrUIMrttlgouRRetjO7nEBfuIee8vbQc4VSzgt2oPfFauihB3zu8zgllzEtuSilaNGVoiuh3ErRRJlAjwT9bOwIF23D65XK5viL/9jH6EyqeNpiplzJpYYaesBfqKHbbyLjCS25KKWa8Ai6enECPV2mh+4tuQBs39hecT+Xp45M8vmfHWbHUFdRoHtnzxweSxAJ+tz581XbFbBq6FNzGXfL3TEtuSil0B56RT6fWFMEc/MHReMlgX7lll6eeWm67OCkd791d9pixhoUdbYomJ7L0hsLVz1WzxH2+0hncxyxe+ddbUGtoSulAA30qkIBX1FppDAoWtyTdra3fXh4fN5zOGUR70CoszlXd1thZWgt5RanTels3i3xXDLYxXgiVdM8eKVUa9NAryIU8BUNXroll5JDKF6+qZNYyM9Dw6PznsPZFmAuU5iqaPXW80RCfiL2JmC1zEEHa/ZNOpd3e/47hrrIGzid1NWiSq13GuhVeFdlgtVDbwv55x1CEfT7uOKcHh4ss2JzxA30wmIiZy+XcMDvlm9qmYMOhd8ajkwkiYcDbOmPATowqpTSQK/KuyoTrMMtSgdEHbu29jJ8KsE7P/8oX9094l53Si5JTw/dGRQNBXzu8y2q5JLLc2RilsHuKP32G4HW0ZVSGuhVeFdlgnW4RemAqOPGlw9w+eZu9h6Z5FP3Pocxhmwuz0tTc4BdcilaKZoj7Pe55ZtaSy7Obw0j40kGu9vcnr3OdFFKaaBX4V2VCTAzl5k3IOoY7G7j3997Fbdcv41jk3O8OD7L8ck5cvZgpXe5fyZnSGbyhIO+QsmlhkVFYP3WkMpaPfShnqjbsx/TkotS657OQ6/CKW84EqncvAHRUru2Wjs2PnhwjLM9uz0m07mijb6m5zL0xULu6Uc1l1z8fiZm0xhjvYl0t4UQ0R66UkoDvapwybTFmVSWgc5I1cds7Y/R3x7moYNjOGOnbSF/0aAoWHPPQwEffvtOfYsYFDX2DMWh7ih+n9DdFtIeulJKSy7VhAJ+d98UqD4o6hARrtray0PDY4yMJ/EJbO6NWeeIegJ9KpkhFPCUXBYxKOpwdnrsjYW0h66U0kCvxhmAfProJO/6wmMcn5wjHln4l5pdW3o5NZ3iK4+NMNAZJR4OkEzniso31rTFQqD3LGIeumPQ3umxN66BrpTSkktV4YC1zP4H+0/ww2dOsmOoi+sv2LDg466/cCNXPXmMRDrH6y7cyCOHxplMZsiUnAUaCvh47YUbyRmz4Pmn3jaBteS/3T6DtDceZv/xqUV+d0qpVqOBXkXY2QgrmSUeDvCt911d0+P64mG+/N+udD9+cmQ3JzM5snlTNHMm5PfzS1t6+aUtvTW3ySm5eM8/7Y2F9NQipZSWXKpxwncymaGjhlJLJdGQ3136732ecHDxL7+zC+RQT+G4u95YmNOzGTK5fKWHKaXWAQ30Kpxpi1NzGTqiwYUfUEEk4Cdp77bYESk8jxPOi+G8CQx6e+j2gOqE9tKVWtc00KsI+a1pi1PJZQZ60OfuttjueR7vjJXa22TV2p2j7wD67EDX5f9KrW8a6FWEg1YP3Sq5LCPQK5VclhLo9mMGe7w9dHv5v85FV2pd00CvIuT3k8sbTs9m6FxmycXZYbF9mYF+6VldvOmSM7ns7G73mjPlUQdGlVrfdJZLFU5veCyRoiO69JcqYp9MlM2b4hr6EgK9Lx7mH36r+Mxu53BpLbkotb4tmCgiEhGRR0XkSRHZJyJ/YV8/R0QeEZHnReROEaltZUwTcXrQmZxZVskl6pnN4u2hLyXQy+mIBgj4pOwReEqp9aOWREkB1xpjLgF2ADeIyJXAx4BPGmO2ARPAu1evmWvDG7jLKrkEC4uGime51LaYaCEioqtFlVILB7qxzNgfBu0/BrgW+Jp9/Q7gravSwjXkDfTlzXIpBPdya+iV9MTCjGkNXal1raZEERG/iOwBTgL3AgeB08aYrH2XI8Cm1Wni2vEG7nIWFnkDvS0UcLfMXamSC1hTF3WWi1LrW02JYozJGWN2AIPAFcAF5e5W7rEicrOI7BaR3adOnVp6S9dAeMVKLoXnCQV87vOuZKDrjotKqUUlijHmNHA/cCXQJSJOt3UQOFbhMbcZY3YaY3b29/cvp611t1Ill6inhx4K+AjbH69kyaU3HtZBUaXWuVpmufSLSJd9OwpcD+wHfgS8zb7bO4Bvr1Yj14p30HKlaugh/yr10OMhEukcc5ncwndWSrWkWhJlAPiRiDwFPAbca4y5G7gV+JCIHAB6gdtXr5lrYzVmuYSDPvfjFe2hx5yzRbXsotR6teBInzHmKeDSMteHserpLcsJXJ9ALLT0KYbRSj30FZq2CIVDpsdmUmzqii5wb6VUK9KVolU4PfSOaBARWfLzVBoUXcr2uZU4Oy7e+vW9dEYDBP0+/vxNF7KlL87/uvsX/OblQ1ww0LFiX08p1Xg00KtwAn055RbAHQQFCAf87ulES9k+t5LzzmjntRduZDKZIZszPDw8yo+fG6UjEuQLDx6mqy2oga5Ui9NAr8IJ3OUs+4dys1xWflC0LRTgs7+7E4B83rD9f3yXsZmUu7+LTmlUqvXpbotVOMG7nI25AIJ+wV5LRDjgc3voKzko6uXzCd32sXTODoy6E6NSrU8DvYqwPWi53JKLiLgzW5weuk8gsIIll1K9sRCjM2l39eiozlFXquVpoFfhDoous+QChbJL2B4UXclySzl98TBjCU/JRXvoSrU8DfQqvLNclquohx7wr+iAaDnO7ovO6tHFriIdT6T50Ff3kEhlF76zUqohaKBX4fcJv//qrdz48oFlP5czdTHk9/Gmiwf4vVdtXfZzVtNTUkM/ncyQzeVrfvyjh8b5xhNHefro5Go1USm1wnSWywJuveH8FXmeSNDv1s2vOrePq87tW5HnraQvHmYmleXo6SQAxsDEbIb+9nBNj3d65om09tCVahbaQ6+TSLAw/7wenK0Anjsx7V5bzPa6TpDPpHRvGKWahQZ6nUSD/lUfCPXqjVs98RNTKQY6I8Di5qLPOD10raEr1TQ00OskElz9mS1ePbHCEa/bNrYDi5vpktBAV6rpaKDXSTi4+jNbvPrihUDfviEOLG6mS8IutUzPFQf6XCbHB+/cwzG7Nq+Uahwa6HXytlcM8p5rzqnb13NKLgBbN8TxycqUXPYfn+KbPz/KAwdGV6ahSqkVo7Nc6uQ152+o69eLhfyEAz5S2Tz98bB9iPRieujlZ7mM6d4wSjUs7aG3KBFxZ7r0xEPWIdJL6KGXznJx3hT0uDulGo8Gegtzyi59sbC1cnQFBkWd59CtBJRqPBroLcw59KI3HqI3trhDpJ1B0ZnSQNe9YZRqWBroLaw3FiYS9NEW8tMbD3FkIsnbPv0gP6swoHlkYpZbvvJz5jK5okHRqbkM7//yE4zOpMruDfPj507xiXueBawtA/733b9Y5e9MKVWOBnoL+7XLNvEH121DRLjp5QNcdW4fz7w0zZcfebHs/R94fpRv7TnG8ydmigJ9z4unufup4/zswGih5OKpx9+15xi3/WQYYwzf2Xuc2x84RCqrK0yVqjcN9BZ21dY+/vurzwVg5+YevviuK3jdRRt5aHiMfN7Mu78T1qMzKbd2PpPKuQOhRyaSnpJLCmOMezuVzZNI59zn0AM1lKq/BQNdRIZE5Ecisl9E9onIB+zrHxWRoyKyx/5z4+o3Vy3Xri29jCfSPHdyet7nnEMwjk0mydqBn0hl3RAfGZ91wz2TM0zboV+YyugtyWigK1VvtfTQs8AfGmMuAK4E3iciF9qf+6QxZof95zur1kq1YnZt7QXgwQNj8z7nhPCLY7MAdLcFSWZynJy2QnpkYpaxmfS8vWGcEB+dSbvX9IQkpepvwUA3xhw3xjxh354G9gObVrthanUMdrdxVk8bDw2XCXTCdZq7AAAOpUlEQVS79/2CHegbO6zgdgL+F8emyOYN2529YWassstowtNDL1NjV0rVx6Jq6CKyGbgUeMS+9H4ReUpEPici3SvcNrVKdm3p5RG7jv78iWk+9NU9ZHJ5N4RfGLcC/Ay7J+58PDGbAeC8M6xAH51JM5PKks5aB2ecmkkxbr8p1FJD/+xPhvnmz4/U3O4fPXuSj3/vmZrvr9R6U3Ogi0gc+DpwizFmCvg0sBXYARwHPlHhcTeLyG4R2X3q1KkVaLJarvPOaGdqLstkMsOPnzvFN544yqHRhNu7fnEsAcDG9kjRx45tzmZfiVRRcB88mcAZax2tYZuBf334Bb72eO2B/h9PHuPzPztc8/2VWm9qCnQRCWKF+ZeMMd8AMMacMMbkjDF54LPAFeUea4y5zRiz0xizs7+/f6XarZah0z4jdWouw1TS6nW/ODbrhnMibU053NgRdj8u2r3RLrmMz6TdQ6ih5DCNGkou44n0okoz44k0yUzO/Y1AKVWsllkuAtwO7DfG/J3nuvegzV8Bnl755qnV4Bx6PZnMMGVvj7v36CS5kqmMG+waOsCOoS739kBnhPZIgLFEumiBUXGgV++hO4uXFrPi1An/qblMzY9Raj2ppYd+NfA7wLUlUxQ/LiJ7ReQp4DXAB1ezoWrldESsTTanklm3h75n5DSAO4MFCoOiAC/fVAj07liIvnjYWjlqB/JAZ8SdDTPQGVkwqL3z1cvNiS/7GPtNwmmzUqrYgtvnGmMeAKTMp3SaYpPqbCuUXCbtcHzyiBXo2ze2c3xyDiiUXAAGuiJs7Agzl8kT9PvojVm7Nzohu83zuO0b2zlwcqZqG5zH5fKGyWSGbs8JS+V4Z9NMzekpSkqVoytF16GOiB3oyYxbvjhdMoMFYEN7oYfeFw8x1N1WtOHXWCLF6Eya9nCATV3WfUXg3A3xopWk5Xhr57WUXRLpQu18MpnhoYNj/Pm3tcqnlJcG+jpUVENPFvd2nRks4YDPHTwFa6Ov91yzhfe+aisAW/vjDJ9KMDI+S0885J5h2t0Wor/d6snPpivv5+JdeFTLLpDe+0wlM3x/30vc8dALZHI6QKqUQwN9HYqF/Ph9UlRycZxrB3o8HCAS9OGzi209sRA3vOwMfmPnEGCtOM3mDQ8cGKU3Zm3PC9i3rXCvNoPF2yuvpYfunU0zNZdx3xC0nq5UgQb6OiQidEQC1qDoXIZNXVHAWurvDITGwgFEhFjYGmbpjRfXuHee3UPQL6SyeXrj4aJSTJ99sEa1ueje+euL7aFPJjPu47WerlSBBvo61RENMp5IM5vOcdGZHYB1wpFTOonbQd4eDtAW8tMWKh4/j4b87lTGPk+Ie8O9Wg99dCbFGfabx2gNc9G9vfipZGHDMO2hK1Wggb5OdUaDHJmwlvRfdGYnYJVLIkE/7eGAG+ixcGBe79yxa2uf/bhCiPfFQu7Rd+NVeuhjM2k2dITpbgvWtE2Ac5/2SICpuYy770xpyUip9UwDfZ3qiAQZmUgCMNQTpT1SCO6eeIhY2A9Ygd4TC5d9jl1brJ0be2KFQdGeWNitoX/y3ue5+Yu7ixYsfex7z/DtPUcZS6Ssens8zFgixafvP8hNf/9T3vbpBzl6Oune/1s/P8rHv/cMozMp2sMB+tvDnJ5Ne0ouGuhKORach65aU2e00DPujAb549efx5Y+a0D0/a851w3o91xzDlJ2GQLs3NzNe375HF574Ub642He/5pzueniASJBP+991VYePTTGPb84wb5jk1w82MXUXIZ//vFBXrapk7GZNOef0cFsOsep6RSf/ekwsbCffcem+O7e47znmi0AfPanwzz70jSv2t5PTzxERyTIC2Oz7p4xpbN0lFrPNNDXqY5owHM7yHUXbHQ//nV7JgvAGy8+s+JzBP0+/scbL3Q//qPXn+fe/vAbzufk9BxX/NV9PHhwjIsHu3js0Dh5A08fncQnQm8sxGw6yw/2nySdzfOnN17CP/7weR4eHuM912zh9GyaXxyfwhj46YFRXnZmB/FIkMcPj7tfR0suShVoyWWdchYXld5eSRvaI5y7Ic5DB629152/8wayeUNv3Jru6CwY2rW1l11be3lkeJxsLs/Dw+M4a5PS9myazmjQ3TwMtOSilJcG+jrV4Vk05F1AtNKu2trLY4fHyeTyPDQ8xmVndxMOWD923sHUs3vb2NQVZdfWPqZTWfYdm+Lh4TGiQT+XnlWYTePsQ+PQWS5KFWigr1PeQPeWX1bari29zKZz/OS5U/zi+BSv2t7PZWdbZ6H0xgszYpwB1iu39ADw0PAYDx4cZefmbl65zdp2uTcWLm53JKAlF6U8NNDXKaenG/AJ0aB/1b7OlXZQ/+G/P4kxVo/9Kvtc095YmD578NU563RDe4RtG+J8+v6DPHdihl2e+/fEQu5vEyJwdm9MFxYp5aGDouuUE4yd0SDWlverozsW4oPXb+fpY5P0t4fZMdTFUE8bY4k05w+0c1ZPG++8ajPXewZlb7l+O9/ac5RQwMdbd2yivz3M771yC6+9cCM/fX4UgJ62EF1tQS25KOWhgb5OOaWLjlWsnzs+cP22oo83dkT48zddBEBnm4+Pvvmios/fdPEAN108UHTtIzdeABTKQ71xq7d+dCKJUsqiJZd1ypnZUjrI2Oic3yx6YiE6okGd5aKUhwb6OtVZxx76SnLeiHrjYToiQaaS2ar7riu1nmigr1NO6aLpAt1ub589QJrO5ZnL6J7oSoHW0NetcMBPJOhbtUVFq6VQcgm7b0rf3/cS//yT4ZrPJlVqLfzlr7yMyzf3rOrX0EBfxz58w/lcMtS18B0bSHdbkFuu38abLhlg37EpAG5/4BAvjiW4xp6vrlQjWs3pwQ4N9HXsnVefs9ZNWDQR4ZbrtwO4u0XuPTrJTS8f4J9++xVr2TSl1tyCNXQRGRKRH4nIfhHZJyIfsK/3iMi9IvK8/Xf36jdXqQLvlgXOwiSl1rNaBkWzwB8aYy4ArgTeJyIXAh8G7jPGbAPusz9Wqm68Uy410JWqIdCNMceNMU/Yt6eB/cAm4C3AHfbd7gDeulqNVKocZ8bLhvYwW/pia9wapdbeoqYtishm4FLgEWCjMeY4WKEPbFjpxilVjTND56qtvau6fYFSzaLmQVERiQNfB24xxkzV+h9IRG4GbgY466yzltJGpcoKBXzcesP5vHJ731o3RamGUFMPXUSCWGH+JWPMN+zLJ0RkwP78AHCy3GONMbcZY3YaY3b29+u0MrWyfv/VW91DrpVa72qZ5SLA7cB+Y8zfeT51F/AO+/Y7gG+vfPOUUkrVqpaSy9XA7wB7RWSPfe1Pgf8DfFVE3g28CPz66jRRKaVULRYMdGPMA1Dh2He4bmWbo5RSaql0cy6llGoRGuhKKdUiNNCVUqpFaKArpVSL0EBXSqkWIfU8vktETgEvLPHhfcDoCjZnpTRqu6Bx26btWpxGbRc0bttarV1nG2MWXJlZ10BfDhHZbYzZudbtKNWo7YLGbZu2a3EatV3QuG1br+3SkotSSrUIDXSllGoRzRTot611Aypo1HZB47ZN27U4jdouaNy2rct2NU0NXSmlVHXN1ENXSilVRVMEuojcICLPisgBEVmzs0urHJj9URE5KiJ77D83rkHbDovIXvvr77avrelB3iJynuc12SMiUyJyy1q9XiLyORE5KSJPe66VfY3E8vf2z9xTIvKKOrfrb0TkGftrf1NEuuzrm0Uk6XntPlPndlX8txORj9iv17Mi8vo6t+tOT5sOOzvD1vn1qpQP9fsZM8Y09B/ADxwEtgAh4EngwjVqywDwCvt2O/AccCHwUeCP1vh1Ogz0lVz7OPBh+/aHgY+t8b/jS8DZa/V6Aa8EXgE8vdBrBNwIfBdrp9ErgUfq3K7XAQH79sc87drsvd8avF5l/+3s/wdPAmHgHPv/rL9e7Sr5/CeA/7kGr1elfKjbz1gz9NCvAA4YY4aNMWngK1gHVNedqXxgdqNqpIO8rwMOGmOWurBs2YwxPwHGSy5Xeo3eAnzRWB4GupwTuurRLmPMPcaYrP3hw8DganztxbarircAXzHGpIwxh4ADWP9369ou+0Ce3wD+32p87Wqq5EPdfsaaIdA3ASOej4/QACEqxQdmA7zf/rXpc/UubdgMcI+IPC7WOa7QWAd5v53i/2Rr/Xo5Kr1GjfRz9y6snpzjHBH5uYj8WESuWYP2lPu3a5TX6xrghDHmec+1ur9eJflQt5+xZgj0codrrOnUHCk5MBv4NLAV2AEcx/qVr96uNsa8AngD8D4ReeUatKEsEQkBbwb+3b7UCK/XQhri505E/gzIAl+yLx0HzjLGXAp8CPiyiHTUsUmV/u0a4vUCfovijkPdX68y+VDxrmWuLes1a4ZAPwIMeT4eBI6tUVvKHphtjDlhjMkZY/LAZ1mlXzWrMcYcs/8+CXzTbkNNB3nXwRuAJ4wxJ+w2rvnr5VHpNVrznzsReQfwRuC3jV10tUsaY/btx7Fq1dvr1aYq/3aN8HoFgF8F7nSu1fv1KpcP1PFnrBkC/TFgm4icY/f03o51QHXd2fW5eQdml9S9fgV4uvSxq9yumIi0O7exBtSepnEO8i7qNa3161Wi0mt0F/C79kyEK4FJ59fmehCRG4BbgTcbY2Y91/tFxG/f3gJsA4br2K5K/3Z3AW8XkbCInGO369F6tct2PfCMMeaIc6Ger1elfKCeP2P1GP1dgdHjG7FGjA8Cf7aG7fhlrF+JngL22H9uBP4V2GtfvwsYqHO7tmDNMHgS2Oe8RkAvcB/wvP13zxq8Zm3AGNDpubYmrxfWm8pxIIPVO3p3pdcI69fhf7J/5vYCO+vcrgNY9VXn5+wz9n1/zf43fhJ4AnhTndtV8d8O+DP79XoWeEM922Vf/wLw3pL71vP1qpQPdfsZ05WiSinVIpqh5KKUUqoGGuhKKdUiNNCVUqpFaKArpVSL0EBXSqkWoYGulFItQgNdKaVahAa6Ukq1iP8PfMIVbsx29xcAAAAASUVORK5CYII=\n",
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"# Part 2\n",
"\n",
"gens = list(islice(grow(), 200))\n",
"plt.plot(mapt(len, gens), label='x');"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAD8CAYAAAB+UHOxAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzt3Xd8W9X5+PHPY3nPeGY5ibNDEiDDGSQUKFAIdIRCaQMF0hIIofAt0BYKpYO29Fc6aWmZAZowA6SMtIVSCrRlhcTOIpM4y3aGd7xkS5Z0fn/oSpET79iWLD3v10uvSEf3So+ulfvonHuGGGNQSikVeaKCHYBSSqng0ASglFIRShOAUkpFKE0ASikVoTQBKKVUhNIEoJRSEUoTgFJKRShNAEopFaE0ASilVISKDnYAHcnKyjJ5eXnBDkMppQaUwsLCSmNMdmfbhXQCyMvLo6CgINhhKKXUgCIiB7qynTYBKaVUhNIEoJRSEUoTgFJKRShNAEopFaE0ASilVITSBKCUUhFKE4BSSkUoTQBKKRVi/r29jJcKSvr8fTQBKKVUiDDGsPx/e7n+6QKeX1eM29O3a7aH9EhgpZSKFC1uDz9+bSvPryvh4lOH8LvLp2GLkj59T00ASikVZLX2Fm58tpAP91Rx82fH8Z3PTSCqj0/+oAlAKaWCal9lI0tWrKekxs7vLj+dy2bm9tt7awJQSqkgWbu3imXPFCLAs9fNZfbojH59f00ASikVBC8WlHD3K58wMiORJ78xi1GZSf0eQ5d7AYmITUQ2isjfrccrRGSfiGyybtOschGRB0SkSES2iMiMgNdYLCK7rdvi3v84SikV2jwew31v7OSO1VuYOyaTl781Pygnf+heDeAWYAeQGlB2uzFm9XHbXQSMt25zgIeBOSKSAfwEyAcMUCgia4wxNT0NXimlBhK708VtL2zizW1lfH3OSO750hRibMHrjd+ldxaRXODzwONd2Hwh8JTxWgsMEpGhwIXAW8aYauuk/xawoIdxK6XUgHKktpmvPvoRb20v4ydfnMy9l0wN6skfut4E9AfgDsBzXPkvrGae+0UkziobDgQOYSu1ytorV0qpsLb1YC0LH3yffRWNPL44n2/OH41I33fz7EynCUBEvgCUG2MKj3vqLmASMAvIAL7v26WNlzEdlB//fktFpEBECioqKjoLTymlQtqb245w+SMfER0VxV+/NY9zJw0Odkh+XakBzAe+JCL7gVXAuSLyjDHmsNXM4wD+Asy2ti8FRgTsnwsc6qC8FWPMY8aYfGNMfnZ2p2saK6VUSDLG8Mh/97DsmUImDknhlZvmMWlIauc79qNOE4Ax5i5jTK4xJg9YBLxjjLnKatdHvPWYS4Ct1i5rgGus3kBzgVpjzGHgTeACEUkXkXTgAqtMKaXCitPl4Y7VW7jvjZ18/tShrFo6l5yU+GCHdYKTGQfwrIhk423a2QQss8pfBy4GigA78E0AY0y1iPwcWG9t9zNjTPVJvL9SSoWcmkYny54p5ON91Xz7vPHcet74fpnWoSfEmL6dbe5k5Ofnm4KCgmCHoZRSXbKnooElK9Zz6Ggzv/7KaVwyPTj9XESk0BiT39l2OhJYKaV6wYdFlSx7ppAYWxTPL53DzFH9O61DT2gCUEqpk7RqXTE/fHUro7OSePIbsxiRkRjskLpEE4BSSvWQ22O4740dLH9vH2dPyOZPV04nNT4m2GF1mSYApZTqgUaHi1tWbeLfO8pYfMYofvSFyUQHeWRvd2kCUEqpbjp0tIklKwvYdaSOn35pCovn5QU7pB7RBKCUUt2wueQo1z1VQLPTzZPfmMU5E3OCHVKPaQJQSqkuev2Tw9z2wiayU+J49ro5TBicEuyQToomAKWU6oQxhof+s4ffvLmLmaPSefTqmWQlx3W+Y4jTBKCUUh1wuNzc9ddPeHnjQS6ZNoz7LjuN+BhbsMPqFZoAlFKqHdWNTm54uoD1+2v4zucm8H/njguJaZx7iyYApZRqQ1F5PdeuKKCsrpk/XTGdL54+LNgh9TpNAEopdZz3dlfwrWc3EBdtY9XSuUwfmR7skPqEJgCllArw9NoD3LNmG+Nzknl8cT656QNjWoee0ASglFJ4p3W49x/b+csH+zl3Ug4PXDGd5LjwPkWG96dTSqkuqG9u4dvPb+TdXRUsOXM0P7j4FGwhOod/b9IEoJSKaKU1dpasKKCoooF7L5nKVXNHBTukfqMJQCkVsTYU17D0qQIcLg8rvzmbM8dnBTukfqUJQCkVkdZsPsT3XtrMkNR4Vi2dxbic5GCH1O80ASilIooxhj++vZs//Hs3s/MyeOTqmWQkxQY7rKDQBKCUihjNLW7uWL2FNZsPcdmMXP7fpVOJiw6PaR16QhOAUioiVNQ7uOHpAjYUH+X2CyfyrXPGhtW0Dj2hCUApFfZ2Hann2hXrqWp08NDXZ3DxqUODHVJI6PL6ZSJiE5GNIvJ36/FoEflYRHaLyAsiEmuVx1mPi6zn8wJe4y6rfJeIXNjbH0YppY737q5yLnv4Q5xuDy8sPUNP/gG6s4DlLcCOgMe/Au43xowHaoAlVvkSoMYYMw6439oOEZkMLAKmAAuAh0QkchvflFJ9bsUH+1iyYj0jMxJ57ab5nD5iULBDCildSgAikgt8HnjceizAucBqa5OVwCXW/YXWY6znz7O2XwisMsY4jDH7gCJgdm98CKWUCuRye/jxa1u552/bOXfSYF5adgbDBiUEO6yQ09VrAH8A7gB8659lAkeNMS7rcSkw3Lo/HCgBMMa4RKTW2n44sDbgNQP3UUqpXlHX3MLNz23kf59WsPSsMXx/waSImNahJzpNACLyBaDcGFMoIuf4itvY1HTyXEf7BL7fUmApwMiRIzsLTyml/Eqq7Vy7Yj37Khu579JTWTRbzyEd6UoNYD7wJRG5GIgHUvHWCAaJSLRVC8gFDlnblwIjgFIRiQbSgOqAcp/AffyMMY8BjwHk5+efkCCUUqothQeqWfpUIS1uD09dO5t54yJrWoee6PQagDHmLmNMrjEmD+9F3HeMMV8H3gW+Ym22GHjNur/Geoz1/DvGGGOVL7J6CY0GxgPreu2TKKUi1qsbD3LFYx+TEh/NqzfN15N/F53MOIDvA6tE5F5gI/CEVf4E8LSIFOH95b8IwBizTUReBLYDLuAmY4z7JN5fKRXhPB7DH/79KQ+8U8Sc0Rk8ctVM0iN0WoeeEO+P89CUn59vCgoKgh2GUioENbe4+e5Lm/nHlsN8NT+Xey85ldjo7vRsD18iUmiMye9sOx0JrJQacMrrm7n+qUK2lB7lrosmsfSsMRE/rUNPaAJQSg0oOw7XsWTFemrsLTxy1UwunDIk2CENWJoAlFIDxjs7y/i/5zaSHB/NS8vOYOrwtGCHNKBpAlBKhTxjDE9+sJ9f/GM7k4el8vg1sxiSFh/ssAY8TQBKqZDW4vbwkzXbeO7jYhZMGcLvv3Y6ibF66uoNehSVUiGrtqmFm57dwPtFldx4zlhuv2AiUTqtQ6/RBKCUCkkHqhq5dsV6iqvt/OYrp3F5/ojOd1LdoglAKRVyPt5bxbJnCjHAM0vmMGdMZrBDCkuaAJRSIWV1YSl3vbyFERmJPLl4FnlZScEOKWxpAlBKhQSPx/Dbf+3iof/sYf64TB66ciZpiTHBDiusaQJQSgVdk9PNbS9s4p/bjnDF7JH8bOEUYmw6rUNf0wSglAqqsrpmrltZwNZDtfzw86ew5MzROq1DP9EEoJQKmq0Ha7luZQF1zS0svzqf8ycPDnZIEUUTgFIqKP617Qi3rNpEemIMq5fNY/Kw1GCHFHE0ASil+pUxhuXv7eWXb+zktOFpLL8mn5xUndYhGDQBKKX6jdPl4UevbuWFghI+f+pQfvfV04mPsQU7rIilCUAp1S+O2p0se6aQtXur+b9zx3Hb+RN0Wocg0wSglOpzeysaWLKygIM1Tfz+q6dz6YzcYIek0ASglOpjH+6p5MZnNmCLEp69fg6z8jKCHZKyaAJQSvWZF9YXc/crW8nLSuLJxbMYmZkY7JBUAE0ASqle5/YYfv3PnTz6v718ZnwWf75yBmkJOq1DqNEEoJTqVY0OF7e+sIm3tpdx1dyR3PPFKUTrtA4hqdO/iojEi8g6EdksIttE5KdW+QoR2Scim6zbNKtcROQBESkSkS0iMiPgtRaLyG7rtrjvPpZSKhgO1zZx+SMf8faOMu754mR+vnCqnvxDWFdqAA7gXGNMg4jEAO+LyBvWc7cbY1Yft/1FwHjrNgd4GJgjIhnAT4B8wACFIrLGGFPTGx9EKRVcW0qPct3KAuxON08snsVnJ+UEOyTViU5Ts/FqsB7GWDfTwS4Lgaes/dYCg0RkKHAh8JYxpto66b8FLDi58JVSoeCNTw7z1Uc/IsYWxeobz9CT/wDRpbqZiNhEZBNQjvck/rH11C+sZp77RSTOKhsOlATsXmqVtVeulBqgjDE8+G4RNz67gVOGpvLqTfOZNETn9BkoupQAjDFuY8w0IBeYLSJTgbuAScAsIAP4vrV5W0P7TAflrYjIUhEpEJGCioqKroSnlAoCp8vD7au38Js3d/HF04fx/PVzyU6J63xHFTK6dXXGGHMU+A+wwBhz2GrmcQB/AWZbm5UCgas35wKHOig//j0eM8bkG2Pys7OzuxOeUqqfVDc6ueqJj1ldWMqt54/ngUXTdE6fAagrvYCyRWSQdT8BOB/YabXrI96VGy4Btlq7rAGusXoDzQVqjTGHgTeBC0QkXUTSgQusMqXUAFJU3sCXH/qATSVH+eOiadx6/gRdwGWA6kovoKHAShGx4U0YLxpj/i4i74hINt6mnU3AMmv714GLgSLADnwTwBhTLSI/B9Zb2/3MGFPdex9FKdXXPiiq5MZnComNjuL56+cyc1R6sENSJ0GM6ahDT3Dl5+ebgoKCYIehlAKe+7iYH722lXHZyTy+OJ8RGTqtQ6gSkUJjTH5n2+lIYKVUh9wew/97fQdPvL+PcyZm86crppMSr9M6hANNAEqpdjU4XNzy/Ebe3lnON+bl8cPPn6Ije8OIJgClVJsOHm1iyYr17C5v4OcLp3D1GXnBDkn1Mk0ASqkTbCrxTuvgaHHz5DdmcfYE7ZIdjjQBKKVa+fuWQ3z3xc3kpMbx/PVzGD84JdghqT6iCUApBXindfjzO0X87q1PyR+VzqNXzyQzWUf2hjNNAEopHC43d/71E17ZeJAvTx/OfZedSly0juwNd5oAlIpwVQ0Obni6kIIDNXzvggnc9NlxOrI3QmgCUCqC7S6r59qV6ymvc/DglTP4/GlDgx2S6keaAJSKUP/9tIKbn91AXIyNF244g2kjBgU7JNXPNAEoFYGe/mg/9/xtO+NzknniG7MYPigh2CGpINAEoFQEcbk93PuPHaz4cD/nTcrhj1dMJzlOTwORSv/ySkWI+uYW/u/5jfxnVwVLzhzNDy4+BVuUXuyNZJoAlIoAJdV2lqxcz56KRn7x5al8fc6oYIekQoAmAKXCXOGBGpY+VYDT7WHlN2dz5visYIekQoQmAKXC2GubDnL76i0MTYvnicWzGJeTHOyQVAjRBKBUGDLG8Id/7+aPb+9mdl4Gj1w9k4yk2GCHpUKMJgClwkxzi5vbV2/hb5sPcdmMXP7fpVN1WgfVJk0ASoWRinoHS58uYGPxUe5YMJEbzx6r0zqodmkCUCpM7DxSx5IVBVQ1OnjkqhksmKrTOqiOaQJQKgy8u7Ocm5/bQFJcNC/dMI9Tc9OCHZIaADQBKDWAGWNY8eF+fv737ZwyNJXHF+czNE2ndVBd0+nqziISLyLrRGSziGwTkZ9a5aNF5GMR2S0iL4hIrFUeZz0usp7PC3itu6zyXSJyYV99KKUiQYvbw49e28pP/7ad804ZzIs3nKEnf9UtnSYAwAGca4w5HZgGLBCRucCvgPuNMeOBGmCJtf0SoMYYMw6439oOEZkMLAKmAAuAh0REuyYo1QO1TS1cu2I9z6wt5oazx/DoVTNJ0jl9VDd1mgCMV4P1MMa6GeBcYLVVvhK4xLq/0HqM9fx54u2GsBBYZYxxGGP2AUXA7F75FEpFkOIqO5c9/CEf7aniV5edyl0XnUKUzumjeqArNQBExCYim4By4C1gD3DUGOOyNikFhlv3hwMlANbztUBmYHkb+wS+11IRKRCRgoqKiu5/IqXC2Pr91Sx88H0q6h08vWQOX5s1MtghqQGsSwnAGOM2xkwDcvH+aj+lrc2sf9v6KWI6KD/+vR4zxuQbY/Kzs7O7Ep5SEeGvhaV8ffnHDEqM5dWb5nPG2Mxgh6QGuG41GhpjjorIf4C5wCARibZ+5ecCh6zNSoERQKmIRANpQHVAuU/gPkqpdng8ht+/9Sl/freIM8Zk8vBVMxiUqNM6qJPXlV5A2SIyyLqfAJwP7ADeBb5ibbYYeM26v8Z6jPX8O8YYY5UvsnoJjQbGA+t664MoFY6anG5ufn4Df363iK/lj2DltbP15K96TVdqAEOBlVaPnSjgRWPM30VkO7BKRO4FNgJPWNs/ATwtIkV4f/kvAjDGbBORF4HtgAu4yRjj7t2Po1T4KK9r5vqnCthysJa7Lz6F6z4zWqd1UL1KvD/OQ1N+fr4pKCgIdhhK9bvth+q4buV6auwt/HHRNC6YMiTYIakBREQKjTH5nW2nHYeVCjH/3l7Gt1dtJDU+hpeWncHU4Tqtg+obmgCUChHGGJ54fx+/eH0Hpw5PY/k1+QxOjQ92WCqMaQJQKgS0uD38+LVtPL+umIumDuH3X51GQqwOlFd9SxOAUkFWa2/hxmcL+XBPFTd9dizf/dxEHdmr+oUmAKWCaH9lI9euWE9JjZ3fXn46X5mZG+yQVATRBKBUkKzdW8WyZwoBeGbJHOaM0ZG9qn9pAlAqCF4sKOHuVz5hREYiTy6eRV5WUrBDUhFIE4BS/cjjMfz6zV088t89zB+XyUNXziQtMSbYYakIpQlAqX5id7q47YVNvLmtjCvnjOSnX5pCjK1L8zEq1Sc0ASjVD47UNnPdU+vZdqiOH31hMtfOz9NpHVTQaQJQqo9tPVjLkpXraWh28fg1+Zx3yuBgh6QUoAlAqT715rYj3LpqE+mJMay+cR6nDE0NdkhK+WkCUKoPGGN49H97+dU/d3Ja7iCWXzOTnBSd1kGFFk0ASvUyp8vD3a98wkuFpXz+tKH87vLTiY/RaR1U6NEEEEY+LasnMymWzOS4YIcSsWoanSx7ppCP91Xz7XPHcev5E3RaBxWytA9amDDGcOXytdz/70+DHUrE2lPRwJcf+oCNxUf5w9em8Z0LdE4fFdq0BhAmKhucVDY4OVjTFOxQItKHRZUse6aQGFsUz10/h/y8jGCHpFSnNAGEiaLyBgDK6x1BjiTyrFpXzA9f3crorCSe/MYsRmQkBjskpbpEE0CYKKrQBNDf3B7DfW/sYPl7+zhrQjZ/vnI6qfE6rYMaOPQaQJjYY9UAqhocuD3edZ6bW9y8WFBCKK/7PFA1Olzc8HQhy9/bxzVnjOLJxfl68lcDjiaAMLHHqgF4DFQ1emsBf99ymDtWb2HrwbpghhZ2Dh1t4iuPfMQ7O8v46Zem8LOFU4nWOX3UANTpt1ZERojIuyKyQ0S2icgtVvk9InJQRDZZt4sD9rlLRIpEZJeIXBhQvsAqKxKRO/vmI0WmPeUNJMd5W/TK67wJYNcR74m/slGbhXrL5pKjLHzwA0qq7Tz5jVksnpcX7JCU6rGuXANwAd81xmwQkRSgUETesp673xjz28CNRWQysAiYAgwD/i0iE6ynHwQ+B5QC60VkjTFme298kEjW6HBxqLaZ8ybl8PbOciqs6wA7j9QD3r7p6uS9/slhbnthE9kpcTyzZA4Th6QEOySlTkqnNQBjzGFjzAbrfj2wAxjewS4LgVXGGIcxZh9QBMy2bkXGmL3GGCewytpWnaS9FY0AnDHWu6KULwF8WuZNANWaAE6KMYYH3y3iW89uYMqwVF69ab6e/FVY6FbDpYjkAdOBj62im0Vki4g8KSLpVtlwoCRgt1KrrL1ydZJ2l3tP9HOtJQXL65s5andSZjUFHbW3BC22gc7hcvPdFzfzmzd3sXDaMJ67fi5ZOtJahYkuJwARSQb+CtxqjKkDHgbGAtOAw8DvfJu2sbvpoPz491kqIgUiUlBRUdHV8CLaiwUl5KTEMXFICqnx0ZTXO9hlNf8AVNsjswbQ4HAx7Wf/4p9bj/Ro/+pGJ1c9/jEvbzzIbedP4A9fm6Zz+qiw0qUEICIxeE/+zxpjXgYwxpQZY9zGGA+wHG8TD3h/2Y8I2D0XONRBeSvGmMeMMfnGmPzs7Ozufp6Is3ZvFWv3VrPs7LHE2KLISY2nvM7hb/5JjY+O2GsAeysaOGpvYWNxDcYY7vzrFgoPVHdp36Lyei558AM2l9bywBXTueX88bqAiwo7XekFJMATwA5jzO8DyocGbPZlYKt1fw2wSETiRGQ0MB5YB6wHxovIaBGJxXuheE3vfIzI9cDbu8lOiePKOSMByEmJo6LBwc4j9aTERzNpSGrEXgM4UGUHoLjazpG6ZlatL+EfWzqvDby3u4IvP/QhdqeLVUvn8qXTh/V1qEoFRVd6Ac0HrgY+EZFNVtkPgCtEZBreZpz9wA0AxphtIvIisB1vD6KbjDFuABG5GXgTsAFPGmO29eJn8TPGUNvUQrQtyt81Mhy1uD18tLeKZWeP9TdN5KTEUVhcg9tjmDQkhYykWPZWNvj3Katrxu0xDBuUEKyw+01xtTcBlNTY2WddKC+ubuxwn6fXHuCeNdsYn5PM44vzyU3XaR1U+Or07GiMeZ+22+9f72CfXwC/aKP89Y726y1H6po545fvcO8lU7lq7qgevYbd6eKBt4u49fzxIdvuW1HvwBgYEXCSyk6Jo6S6iZLqJu5YMJGS6iaqDxy7CHzbC5twuQ0vLjsjGCH3q2JfDaDKzt5KXwKwt7mt22O49x/b+csH+/nsxGweuGI6KTqyV4W5sBy+mJMSjy1KOFLb3K39jtQ2c9NzG7A7XazbV80j/93DhgM1fRTlyTtS5/18Q9KO9UrxrTo1bcQgln5mDBlJMdTYnRhjcHsMm0qOcqCTX8Hhwvc565pdbC45CngTwPFTYzQ4XFy3cj1/+WA/35yfx/Jr8vXkryJCWCYAW5QwOCWOQ7Xdmxp53f5q/rHlMJ+WNWB3ugFodrn7IsReUWYluMGpx5YanDFqEONykvnD16YRbYsiPTEWt8dQ1+xiX6X3c5XXO2hxe4IVdr8prrKTEu+t5P5vt7dHWXOLh4qGYyOjS2vsfOXhD/nf7kp+fslUfvLFKTqtg4oYYftNH5IWz+Gj3asBNFsnfbvDRaPDBUCTM3RPlP4aQEACmDkqg39/52zyspIAyEiKBbyjgT85WAuAMeE/a6jD5eZwXTPzrMFxZXUOUqzrQSVWM9DG4houefBDDtY08ZdvzOLqHjYXKjVQhW0CGDoowX+C7KqmFm8CaHS6/febW0K4BlDnIMYm/pN8W9Kt56rtTraU1vrLj3SzdhQq6pq7NqitpLoJY+DMcVn+svnW/eJqO//YcpivPbaWhNgoXv7WPM6aoF2OVeQJ2wQwLC2eQ0ebujUVsu+kb3e6aHQMgCagumZyUuI77J+ekXisBrD1YC2DEr1t24e7eX0kFHy8t4oZP3uLA1XtX8NocLj4zgubWLPZO8Rk8rA0/2f+zIQsRGBzSS23vbCJqcNSefVb8xk/WKd1UJEpbBPAkLQEHC5Pt6ZB8LX7Nzhc2J2+JqDgJoB/bj3Cb9/c1eZzR2qbGZIW3+ZzPr7aQWWDg22H6jh3Yg5At5vHQsHWQ3W4PKZVTeZ4r248yMsbD/LA27sBGJWZyEhrha5JQ1IYmhrP8+uKcbo9/PLS08jUaR1UBAvbBDDMOjF250Kwr7nH7nD7awAOV3CvAfxz62GeW1fc5nNldc2t2v/b4msCWrevBrvTzbxxWSTG2gZkDaC0xtt271v+si2r1hczMiORpFgbSbE2MpNi/d1kR2clMyIjEYfLw+m5aTqhm4p4YZsAfL+Mu/NL1/drv9HZugZQ0+jk0oc+6LDpoa/YnW4arAvSgYwxHKlrbtUDqC1JsTZibVGs2XyQGJswb2wmQ9PiOVIXOtcAth2q9R/vjpRaC977lr90ewz3v/Upf7J+7W89WMvWg3Vc95nRPL54Fj/6wmREhNmjMzhlaCrpiTH+2sDl+SPafhOlIkjYDpP1jXQ93I0Lwb4mILvTTaPz2EXgoooGNhQfZWPxUUZlJvV+sJ3E5HR5aHF7iAnonljvcGF3uluNAWiLiJCeFENZnYNvzs9j2KAEhqYlhEwNoMnp5ssPfsgt54/nps+O63BbX++dPeUNtLg9fPv5jbxhTfQ2MjORVzceJD4mioXThpOWEOOfHnvxvDz/wi1Th6fxr+1lfFGnd1AqfBNAVnIc0VHC4aPdbwJqdLiwW7+6m11uf2KoCcKsmo3WL2O7w01a4rEE0NYYgPakJ8bS6HBzs3WCHZIWz/u7K/sg2ra53B48BmKjT6xwltbYcbo9rWYvbYsxhoNWDWBvRSN/33KIN7Ye4fYLJ/LmtiPcsso7S8lPvjiZtIT2B3FdPXcUl84YrgO9lCKME4AtShicGt+tX7pNAQmg0XlsHIAvGQRjVk2741izVEKsjUaHi/Sk2DbHALTnlvPGE22L8l/wHJYWT3l9My63p18GPd3zt218WtbAizd4p5/wLbByyfTh/mad/Z00r9U1uah3uJg4OIVdZfUs/98+slPiuPHssVw0dQh3rN7CdZ8ZzYKpQzt8nago0ZO/UpawTQAAQ9PiOdyNi8C+duhGp7vVSGDf/WDMq++vAThdPPrfUp5ae4CP7zrPP81FV2oAF53a+qQ4JC0Bj4GKBgdD0/p+UrgNB45SVN7gTzjF1XZ++69PcXmMv5fSvopGjDHtdmktsS4AnzMxm11l9Ww/XMfX54wkKkoYk53M6hvn9fnnUCrchO1FYPAOButeDcDb48c7DsBqAnK6/YmhprH/V9Y61jXVTUmNnYp6Bweq7f7P1ZUEcLyhvgvkvXwd4J2dZXxY1LppyRjDvsrktxBFAAAX9klEQVRGnG6P/9e+b0K2ovIGf1m9w0VVBzUsXw+gsyceG7C1YOqQXo1fqUgT1glgcEoc5XVdn/LANxVEo8Pt7xHUqgbQT01AD7y9m++84G3TtvuvAbiob/be33aoli2ltYzOSiIhtvszlY6wesLs6aA7ZU/c98ZOfvfWp/7HxhjK6hz+pjVf982S6ib/Y9+JHWB/5YnNQG6PYW/FsUQxeWgqOSlxpMZH+5fAVEr1TFg3AaXEx9DU4j6hB0177C1WE5DDFdALyOO/318XgdfureJAlR23x9Bs1UoaHC7/NAjbDtWxsbim1a/h7hiTlURKfDQbio/2anfIw7XN1DZ5Y7xj9WbqmlxcM+/Y/DpFFQ2cz2B/DWBvZSNRIuRlJrLfmrI5Py+j1Ws+t66YH726lUlDUkiJiyYtIYbL83NJjI3u0t9UKdW+ME8A3o/X6HAxKLH9+XJ8fBO/2QOafZqc7mMXgfspAVQ2OKhrbmnVN97udPtrAP/ceoSqRiczR6X36PWjooTpI9PZWNx7U103WjWU+mYXzS1u1u2r5lBtM7NHe0/osdFRx2oA1q9+p8vDjiN1fC1/BKU1TW3WAFYXlACw80g9k4akICLcfuGkXotbqUgW1j+hkq0E4DtxHu/nf9/O3zYfW5bY1w30qN1Ji9s7h1Czy43dKq9pbOnW3EI9VdXgpMHhajUArCGgCWifdaKcMbJnCcC77yB2ldVT38XJ1ToTOPHegSo7JTVNOF0eXrH65s8YOSigCcju76ppDIzKTGJkRiL7Khs5Utvsn6q6qLyezaW1XD4zlxib+AdxKaV6R1gngNQOEkBlg4Mn3t/HT/+2neYWN8aYVr2AfJoDagBOt6fVc33B5fZQbXdijHe2Tx+700V9cwvRUd5eMslx0Uw4iUnMZo5KxxjYZC2UcrLKAi4of7inErfHmyg/OVhLXmYS43NS2FPRgDGGkmo7ZwfMvpmbnsDorCQ+3FPFZ379Drda1z9e3nCQKIHbL5zI00vmcMcC/eWvVG8K6wSQHOf9ldnWVAofWL1VKhsc/snBPAYSAy6qxkZH0ezy+C8CQ9+PBaixt+CrZASuaNbgcFPX7OL0EYMA74pftqj2ZwHtzLQRgxDxdtE8GbuO1HPoaFOrHkXvWYPM4qyBX2OykxibnUR9s4u9lY3U2FuYPCzVP4ZhREYieVlJ1Da1MCgxln9sOczD/9nD8+uKOXN8Njmp8cwdk8m4nOSTilUp1Vp4JwB/DeDEZo4PiipJS4hhVl46j/53L3VN3iSRmXzsWkFmUizNLe5WCaCvewJVBqxWVRbQrFLT6MTp8jB7dAax0VHMGZ3R1u5dlhIfw4ScFAoOVJ/w3MGjTfz304ouvc71TxVwz5pt/iag6Cjhoz1VAFxsjT8YnZXEuBxvbeXdneUAjMxI9J/Qc9MTWHxGHndeNIl3v3cOY7OT+NU/d5IYG82PvzD5pD6nUqp9YZ0AfBeBj68BGGN4f3cl88ZmsmjWSI7UNfunIshMOja3TmZyLE0tbhqdLpKsmsHxg8He3Vnea+3o0DoBBLar++4PTYvnjVs+w/VnjTnp97pwymDe213JuzvLqah3+Ofa+d2/dvHNv6yjopNVw+xOF8XVdj45WEtZXTNpCTGMyEikqcXNoMQYLpwyGPDOwjl5WCqx0VE8/t4+wLuQ/dThaaQnxpCZFMvIzESWnT2W5Lho/rhoOlfMHsFrN8/XX/1K9aHwTgDWEoB1x10D2FfZyKHaZuaPyyIn1XvCP3jUe/LLCpgfPiMpDmOg1t7C8HTviNmjAQng0NEmvrliPXe/srXDOGqbWnBYC8u8uvEga/dWtbttVcOx1w9sAvLdT42PYWx2MvEx3e//f7ybzh3HpCEp3LJqI2f+6h0uefADXG4Pa/dU4THw+ieHO9x/b4X3YvTh2ma2H6pjSGo8udZxystM4pyJOSw7eyyfO2UwGUmxLDt7rD+RjchI4NvnjWPNzWeeMPp36vA0fnnpaa3+Fkqp3tdpAhCRESLyrojsEJFtInKLVZ4hIm+JyG7r33SrXETkAREpEpEtIjIj4LUWW9vvFpHFffexvHxzvjQ0u3hz2xEWPfYRHo/hI+sEfOa4LP9UBL6BRtkprZuAAKoanQy3ZhetDhgNvKvMW2tYs/nQCSNgA1360Afc+/cdNDnd3PnyFv7w70/b3bZVDcA66Q9KjPGfOH21mt4QF23jgSumEx9jY8qwVKoanfx1QymHrPd9bdPBNve7Y/VmXiooYU/FsYFkG4prGJwWT6419/6YrCTiY2zcedEk0qwVuW48eyzDByWQEu/tz58YG+0flKaU6n9dqQG4gO8aY04B5gI3ichk4E7gbWPMeOBt6zHARcB467YUeBi8CQP4CTAHmA38xJc0+kp8TBS2KKG+uYWP91azdm81h+uaKSpvIDHWxqjMRH+Tz0Fr1tBWTUBWAqhtamFIWjy2KGl1EbiozHsCHJoWz50vf9JqVKuPx2PYX2XntU0HeWdnOc0tHj4prfX3kjleZWANwDrp56TE+RNDb09kNmFwCuvuPp+nl8whNjqK3/7Lm5wunT6cDcVH/c1CDpe3p5TbY3h5w0GeX1fMnopGfD/ePQaGpsYzIsObKEdnnThtdkKsjUeumsmvLjutw2UslVL9o9MEYIw5bIzZYN2vB3YAw4GFwEprs5XAJdb9hcBTxmstMEhEhgIXAm8ZY6qNMTXAW8CCXv00xxERkuOiaXC4qGr0nkAPVDZyoMrOqMwk/1z5gH+q4ayAi8AZAfeTYqNJT4xpdQ2gqLyBrORY/nzldGrsTi558IMTVquqbWrB7THUNbv45Rs7AG830/ZWtapscPibPnw1gOyUOH/PoN6sAQRKiovmzHFZVNQ7yEyK5bbPTQDgof/sYX9lI/Pve4fl7+2lrK7ZvyzjtoO1jMxI9M8tNDgt3r/6Vl4bCQDg1Nw0/8VhpVRwdesagIjkAdOBj4HBxpjD4E0SQI612XCgJGC3UqusvfI+lRIfTUOzy9+2vq+qkf2VjYzO8p6o4qJtpMRF+5uAAteIzQqoDSTGRZOeGNuqBrC7vJ5xOcnMHJXBK9+aR2WDk39sad1u7ks84G1mOj03DYBNJW2Pwq1scDAkLY6EGBtNLW5sUdJqFHNfJQCACyZ7L9rOHZPJiIxElp41hufXFXPZwx9S2eBkU8lR/3FyeQz//bSCsdnJTBmWCninpp4zJoOzJmTrPD1KDQBdTgAikgz8FbjVGFPX0aZtlJkOyo9/n6UiUiAiBRUVXeuK2JHkuGjqml3+JpQ95Y0UV9tbreyVkXxsfv3WF4EDawA20pNi/d1AjTHsLm9gvNW9cVxOCrHRUScsbehr0vGNYr3+rDGkxkezqaTthc2rGpxkJcf5T/SJsTaSY4+d9FM7WOzkZJ0/eTDJcdGcP9mby7+/YBLnTsqhtqmFERkJ7Ku0+y+WgzcJjM1OYvJQbwIYmhZPTko8T107m+wUvYCrVKjrUgIQkRi8J/9njTEvW8VlVtMO1r/lVnkpEDjDWC5wqIPyVowxjxlj8o0x+dnZPZvsLFBqfAwNjhb/VMMfFFXi8hhGBySA9MRYf5u87yJwXHQUiXHHetokxtoYkhrP9kN1bD1YS3m9g/pmF+MHH+ummBRrazVmAI6NG/juBRO4cMpgzp2Uw+kjBrU7AreywUFmUpz/RJ8UG02S1ZtJhFbJoLdlJcex/u7zuWSat2JmixIevXom/73js5x/ymAOVDX6Z/Icb3XPHJudzJwxmdiihLHZ2mVTqYGkK72ABHgC2GGM+X3AU2sAX0+excBrAeXXWL2B5gK1VhPRm8AFIpJuXfy9wCrrU8nx0dQ2ufwnYl/PnVGZx3qfZAb80k+3mluS4qJJiAlMANF894IJpCbEcMXytby8wdtDJrCfemJs9AkJoMqqeZwxNpNHr84nMTaaaSMG8WlZfavawuaSoxTsr/bWAFJij9UA4mwkWYkoOTaaqJMY/dsVCbG2VhdoY2xRDB/knarB7nSzsbiGrOQ4zrKmchibk8z8cVls+OHnGJmpPXqUGki6UgOYD1wNnCsim6zbxcB9wOdEZDfwOesxwOvAXqAIWA58C8AYUw38HFhv3X5mlfWplPhoSmu8UysHTvMQ2EulVVOPdeJPjLW16mvv7TWUxAs3zCUtIYZf/XMngL8JCLwnz6aWtpuAMgLa8c8Yk4nbY7jfmjt/b0UDVy5fyxXL1+J0e8hKiiM1/sQaQF+2/3cmz6oxrd1bTW56AgunDSN/VLq/+cfX1VMpNXB0ekYxxrxP2+33AOe1sb0BbmrntZ4EnuxOgCcrOS7aPxnc9JGD+KCoisRYW6s2al9vnyjxNv0kxUWTFHtcDcA6CeemJ/L0kjlc/siHuD2mVa+hxFgbjY4Tm4DSE2Narb07b1wWi88YxfL39tHgcFF4oIbYaO+avcXV9tY1gFibfxRyMNey9SXMphY3w9MTOC13kC7DqNQAF9brAcCx+YAAZo7K4IOiKn8XUB9fE1BCjLf5IynORmJc6xpA0nG1h9XL5lFe72j1OomxNv9KYj5VjY5WPYt8fvSFyVQ2OPlr4UGibcKDX59B7qAEfvDKJ0wfkc76/d5eQklxx2oAqQnB+3MNG5RArC0Kp9vjH+2rlBrYwj4BpAb8ap6V5x135usC6pNhdff0La+YGBttNQEd+9V+/NKLeVlJJ/R1T4yNpry+9Tq7lQ3OVk1MPtG2KB78+gz/4CpfDeGlZfNaxZ0YayMx1tcEFLwagC1KGJGRwJ6KRv9oX6XUwBb2CSA57thHnDw0laFp8ZyeO6jVNv4agHWSv+7M0SSdUAPo/FAltNMLaMLg9nvHiAjRthNb2Fp1Aw2BawDgrfnsqWgkd5DWAJQKB2GfAHwnzSjx9vB593vnnLCWbEZAExDAZTNzAW9ffxHvqlWJXVh8PTHGht1xYi+gzB4MivJ1A02MjfZ3Rw12AvBdCNYmIKXCQ1jPBgrHagAZSXFERQnxMbYTFlI5PgH4iAjx0VazUFznJ9+kuOhWXTtdbg819pY2m4A641vNLCnuWA0gNYhNQABnjs9i4uAUncBNqTAR9jUA30XgwN46x8s4rgkoUHxMFE0t7hOSQ1u83UADFo+x5g3q6L3bc+waQLS/9hHMawAA50zM4ZyJOZ1vqJQaEMK+BuA7kWZ2cBJOjLURFx3V5kk+Psbmn1W0M4kxNlrcBqfLu6i5b/BZW72AOuNr7kmKtZGVHMeYrCT/nDtKKdUbwr8GYDWfBE7zfDwRISs5rs0aQEKMDWcXp1/w7d/kdBMbHeWfgC6zJ01AAdcA4mNsvPO9c7r9Gkop1ZGwTwC+X9Id1QAAfnDxKQxJOzFJxMXYSHB7uvRevv769hYXacT4J6Dr7L3bMiYriRvOGsM5k05+PiSllGpLBCSAGFLioxnTzvz0Pp8/re056hNiovB4unaYfG31dqd38ZT/7KpABLKT47sXNN5xAnddfEq391NKqa4K+wQQGx3Fu987h7QeTqOcEh/TpfZ/ONaLyO5w86d3inhl40Fu/uw4nSdHKRWSwj4BACe1uPiPvnAKrnaWbzyerwmo0eniz+8WceGUwXz3ggk9fm+llOpLEZEATsa4gNk+O+O7CHykthmny8Oc0Zm69q1SKmSFfTfQ/uS7BlBsLaTek4u/SinVXzQB9KLEGG+FqsRKACfT9KSUUn1NE0Av8s3ZozUApdRAoAmgF/magEprvOvmag1AKRXKNAH0It/EcYdrmxA5tr6wUkqFIk0AvSgqSkiIseEx3jWAuzp+QCmlgkETQC9Lsq4DaPu/UirUaQLoZb6xANr+r5QKdZoAepmvK2hPpoBWSqn+1GkCEJEnRaRcRLYGlN0jIgdFZJN1uzjgubtEpEhEdonIhQHlC6yyIhG5s/c/Smjw1QB6MgW0Ukr1p67UAFYAC9oov98YM826vQ4gIpOBRcAUa5+HRMQmIjbgQeAiYDJwhbVt2PFdA+jJKmBKKdWfOp0LyBjzPxHJ6+LrLQRWGWMcwD4RKQJmW88VGWP2AojIKmvb7d2OOMQlxPiWoNQmIKVUaDuZawA3i8gWq4ko3SobDpQEbFNqlbVXHnZ8g8H0GoBSKtT1NAE8DIwFpgGHgd9Z5W11fDcdlJ9ARJaKSIGIFFRUVPQwvODRbqBKqYGiRwnAGFNmjHEbYzzAco4185QCIwI2zQUOdVDe1ms/ZozJN8bkZ2cPvOUQ/U1AHaxBrJRSoaBHCUBEAtdP/DLg6yG0BlgkInEiMhoYD6wD1gPjRWS0iMTivVC8pudhh65jTUBaA1BKhbZOLwKLyPPAOUCWiJQCPwHOEZFpeJtx9gM3ABhjtonIi3gv7rqAm4wxbut1bgbeBGzAk8aYbb3+aULAl6YNIzk+2r86mFJKhSoxpmvLHQZDfn6+KSgoCHYYSik1oIhIoTEmv7PtdCSwUkpFKE0ASikVoTQBKKVUhNIEoJRSEUoTgFJKRShNAEopFaE0ASilVITSBKCUUhEqpAeCiUgFcOAkXiILqOylcHqTxtU9oRoXhG5sGlf3hGpc0LPYRhljOp1MLaQTwMkSkYKujIbrbxpX94RqXBC6sWlc3ROqcUHfxqZNQEopFaE0ASilVIQK9wTwWLADaIfG1T2hGheEbmwaV/eEalzQh7GF9TUApZRS7Qv3GoBSSql2hGUCEJEFIrJLRIpE5M4gxjFCRN4VkR0isk1EbrHK7xGRgyKyybpdHKT49ovIJ1YMBVZZhoi8JSK7rX/T+zmmiQHHZZOI1InIrcE4ZiLypIiUi8jWgLI2j494PWB957aIyIx+jus3IrLTeu9XRGSQVZ4nIk0Bx+2Rvoqrg9ja/duJyF3WMdslIhf2c1wvBMS0X0Q2WeX9dsw6OEf0z/fMGBNWN7wrju0BxgCxwGZgcpBiGQrMsO6nAJ8Ck4F7gO+FwLHaD2QdV/Zr4E7r/p3Ar4L8tzwCjArGMQPOAmYAWzs7PsDFwBuAAHOBj/s5rguAaOv+rwLiygvcLkjHrM2/nfV/YTMQB4y2/t/a+iuu457/HfDj/j5mHZwj+uV7Fo41gNlAkTFmrzHGCawCFgYjEGPMYWPMBut+PbADGB6MWLphIbDSur8SuCSIsZwH7DHGnMxgwB4zxvwPqD6uuL3jsxB4ynitBQYdt3Z2n8ZljPmXMcZlPVwL5PbFe3emnWPWnoXAKmOMwxizDyjC+/+3X+MSEQG+CjzfF+/dkQ7OEf3yPQvHBDAcKAl4XEoInHRFJA+YDnxsFd1sVeGe7O9mlgAG+JeIFIrIUqtssDHmMHi/nEBOkGIDWETr/5ShcMzaOz6h9L27Fu+vRJ/RIrJRRP4rIp8JUkxt/e1C5Zh9BigzxuwOKOv3Y3bcOaJfvmfhmACkjbKgdnUSkWTgr8Ctxpg64GFgLDANOIy3+hkM840xM4CLgJtE5KwgxXECEYkFvgS8ZBWFyjFrT0h870TkbsAFPGsVHQZGGmOmA98BnhOR1H4Oq72/XUgcM+AKWv/Q6Pdj1sY5ot1N2yjr8TELxwRQCowIeJwLHApSLIhIDN4/7LPGmJcBjDFlxhi3McYDLKePqr2dMcYcsv4tB16x4ijzVSmtf8uDERvepLTBGFNmxRgSx4z2j0/Qv3cishj4AvB1YzUYW80rVdb9Qrzt7BP6M64O/nahcMyigUuBF3xl/X3M2jpH0E/fs3BMAOuB8SIy2voVuQhYE4xArLbFJ4AdxpjfB5QHttl9Gdh6/L79EFuSiKT47uO9iLgV77FabG22GHitv2OztPpVFgrHzNLe8VkDXGP10pgL1Pqq8P1BRBYA3we+ZIyxB5Rni4jNuj8GGA/s7a+4rPdt72+3BlgkInEiMtqKbV1/xgacD+w0xpT6CvrzmLV3jqC/vmf9caW7v294r5R/ijdz3x3EOM7EWz3bAmyybhcDTwOfWOVrgKFBiG0M3h4Ym4FtvuMEZAJvA7utfzOCEFsiUAWkBZT1+zHDm4AOAy14f3ktae/44K2aP2h95z4B8vs5riK8bcO+79kj1raXWX/fzcAG4ItBOGbt/u2Au61jtgu4qD/jsspXAMuO27bfjlkH54h++Z7pSGCllIpQ4dgEpJRSqgs0ASilVITSBKCUUhFKE4BSSkUoTQBKKRWhNAEopVSE0gSglFIRShOAUkpFqP8PfkqIlYyt2MAAAAAASUVORK5CYII=\n",
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"plt.plot(mapt(sum, gens));"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"OK, no problem: after a while the sum settles down and grows at a constant rate. I can figure out what that rate is:"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2580, 2601, 2622]"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[sum(plants) for plants in gens[100:103]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It is growing by 21 each time. So my answer should be 2580 + 21 × (50 billion - 100). More generally:"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1050000000480"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def nth_plant_sum(n, k=100):\n",
" \"The sum of plants in the nth generation, assuming linear growth after k generations.\"\n",
" a, b = map(sum, islice(grow(), k, k + 2))\n",
" return a + (n - k) * (b - a)\n",
"\n",
"nth_plant_sum(50 * 10 ** 9)"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {},
"outputs": [],
"source": [
"assert _ == 1050000000480, 'Day 12.2'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, *why* does it grow by 21 each time? Well, we saw in the plot of lengths above that the length eventually remains constant; we can see the last few:"
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[21, 21, 21]"
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[len(g) for g in gens[-3:]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are 21 plants in each generation; here is one generation:"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{59,\n",
" 60,\n",
" 61,\n",
" 71,\n",
" 72,\n",
" 73,\n",
" 84,\n",
" 85,\n",
" 86,\n",
" 137,\n",
" 138,\n",
" 139,\n",
" 149,\n",
" 150,\n",
" 151,\n",
" 159,\n",
" 160,\n",
" 161,\n",
" 194,\n",
" 195,\n",
" 196}"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gens[100]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that the plants are bunched into groups of three. What happens to a group of three?"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{0: {1, 2, 3},\n",
" 1: {2, 3, 4},\n",
" 2: {3, 4, 5},\n",
" 3: {4, 5, 6},\n",
" 4: {5, 6, 7},\n",
" 5: {6, 7, 8}}"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"dict(zip(range(6), grow(plants={1, 2, 3})))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"They move one to the right each generation; moving 7 groups of 3 one to the right results in adding 21 to the sum."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 13: Mine Cart Madness](https://adventofcode.com/2018/day/13)\n",
"\n",
"I need to do the following:\n",
"\n",
"- Parse the picture of the world into a data structure.\n",
"- Keep track of the carts, and have them make the right moves. \n",
"- Continue until there is a collision.\n",
"\n",
"Since this has to do with headings and turns, I'm going to use complex numbers to represent points, headings, and turns; multiplying a complex heading by a complex turn results in a new heading. Then adding the heading to a point results in a new point. I'll redefine the `X` and `Y` accessors to handle either the complex points used here or the tuple points used previously:"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {},
"outputs": [],
"source": [
"Point = complex\n",
"\n",
"def X(point): return point.real if isinstance(point, complex) else point[0]\n",
"def Y(point): return point.imag if isinstance(point, complex) else point[1]\n",
"\n",
"# Headings: HU, HD, HR, HL = Head up, down, right, left\n",
"# Turns: TL, TR, TS, TB = Turn left, right, straight, backwards\n",
"HU = TL = Point(0, -1)\n",
"HD = TR = -TL\n",
"HR = TS = Point(1, 0)\n",
"HL = TB = -TS\n",
"\n",
"headings = {'>': HR, '<': HL, '^': HU, 'v': HD}\n",
"inverse_headings = dict((headings[ch], ch) for ch in headings)\n",
"\n",
"assert HU * TR == HR and TR ** 4 == TL ** 4 == TS and HR * TB == HL and HU == -HD and TR == -TL"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we need to define a `Cart`, and the `World` they will live in. We use the [`dataclass`](https://docs.python.org/3/library/dataclasses.html) facility from Python 3."
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {},
"outputs": [],
"source": [
"@dataclass\n",
"class Cart:\n",
" name: str\n",
" pos: Point\n",
" heading: Point\n",
" turns: object\n",
" \n",
"@dataclass\n",
"class World:\n",
" grid: tuple\n",
" carts: list\n",
"\n",
" def __init__(self, lines):\n",
" table = str.maketrans('<>^v', '--||')\n",
" names = cycle(alphabet)\n",
" self.grid = [line.translate(table) for line in lines]\n",
" self.carts = [Cart(next(names), Point(x, y), headings[h], cycle((TL, TS, TR)))\n",
" for (y, line) in enumerate(lines)\n",
" for (x, h) in enumerate(line)\n",
" if h in headings]\n",
" \n",
" def __getitem__(self, point): return self.grid[int(Y(point))][int(X(point))]\n",
" \n",
" def show(self):\n",
" \"Print a representation of the world.\"\n",
" for y, line in enumerate(self.grid):\n",
" for x, ch in enumerate(line):\n",
" cart = first(c for c in self.carts if c.pos == Point(x, y))\n",
" ch = inverse_headings[cart.heading] if cart else ch\n",
" print(ch, end='')\n",
" print()\n",
" print()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now the function `madmad(world)`, which simulates moving the carts until a collision."
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [],
"source": [
"def madmad(world, show=False):\n",
" \"Simulate the mine cart madness until a collision.\"\n",
" while True:\n",
" if show: world.show()\n",
" for cart in sorted(world.carts, key=lambda c: (Y(c.pos), X(c.pos))):\n",
" cart.heading *= turn(cart, world)\n",
" cart.pos += cart.heading\n",
" if collision(cart, world):\n",
" if show: world.show()\n",
" return cart.pos\n",
"\n",
"def turn(cart, world):\n",
" \"Which way should the cart turn (depends on character it is on).\"\n",
" ch = world[cart.pos]\n",
" if ch == '+':\n",
" return next(cart.turns) \n",
" if ch == '/':\n",
" return (TR if cart.heading in (HU, HD) else TL)\n",
" if ch == '\\\\': \n",
" return (TR if cart.heading in (HR, HL) else TL)\n",
" else:\n",
" return TS\n",
" \n",
"def collision(cart, world):\n",
" \"Has this cart collided with any other cart?\"\n",
" return any(cart.pos == other.pos for other in world.carts if other is not cart)"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"/->-\\ \n",
"| | /----\\ \n",
"| /-+--+-\\ | \n",
"| | | | v | \n",
"\\-+-/ \\-+--/ \n",
" \\------/\n",
"\n",
"/-->\\ \n",
"| | /----\\ \n",
"| /-+--+-\\ | \n",
"| | | | | | \n",
"\\-+-/ \\-v--/ \n",
" \\------/\n",
"\n",
"/---> \n",
"| | /----\\ \n",
"| /-+--+-\\ | \n",
"| | | | | | \n",
"\\-+-/ \\-+>-/ \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| v /----\\ \n",
"| /-+--+-\\ | \n",
"| | | | | | \n",
"\\-+-/ \\-+->/ \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| | /----\\ \n",
"| /-v--+-\\ | \n",
"| | | | | | \n",
"\\-+-/ \\-+--> \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| | /----\\ \n",
"| /-+>-+-\\ | \n",
"| | | | | ^ \n",
"\\-+-/ \\-+--/ \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| | /----\\ \n",
"| /-+->+-\\ ^ \n",
"| | | | | | \n",
"\\-+-/ \\-+--/ \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| | /----^ \n",
"| /-+-->-\\ | \n",
"| | | | | | \n",
"\\-+-/ \\-+--/ \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| | /---<\\ \n",
"| /-+--+>\\ | \n",
"| | | | | | \n",
"\\-+-/ \\-+--/ \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| | /--<-\\ \n",
"| /-+--+-> | \n",
"| | | | | | \n",
"\\-+-/ \\-+--/ \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| | /-<--\\ \n",
"| /-+--+-\\ | \n",
"| | | | v | \n",
"\\-+-/ \\-+--/ \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| | /<---\\ \n",
"| /-+--+-\\ | \n",
"| | | | | | \n",
"\\-+-/ \\-v--/ \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| | <----\\ \n",
"| /-+--+-\\ | \n",
"| | | | | | \n",
"\\-+-/ \\<+--/ \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| | /----\\ \n",
"| /-+--v-\\ | \n",
"| | | | | | \n",
"\\-+-/ <-+--/ \n",
" \\------/\n",
"\n",
"/---\\ \n",
"| | /----\\ \n",
"| /-+--+-\\ | \n",
"| | | ^ | | \n",
"\\-+-/ \\-+--/ \n",
" \\------/\n",
"\n"
]
},
{
"data": {
"text/plain": [
"(7+3j)"
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"example = r'''\n",
"/->-\\ \n",
"| | /----\\ \n",
"| /-+--+-\\ | \n",
"| | | | v | \n",
"\\-+-/ \\-+--/ \n",
" \\------/ \n",
"'''.strip().splitlines()\n",
"\n",
"madmad(World(example), True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The answer, `7, 3`, is correct, and everything looks good!\n",
"\n",
"Unfortunately, I got an error when trying it on the actual (larger) input.\n",
"\n",
"Even more unfortunately, I ran out of spare time to debug this problem and to move on to the remaining days. Maybe next year!"
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {},
"outputs": [
{
"ename": "IndexError",
"evalue": "string index out of range",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mIndexError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mmadmad\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mWorld\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mInput\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m13\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m\u001b[0m in \u001b[0;36mmadmad\u001b[0;34m(world, show)\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mshow\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mworld\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mshow\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mcart\u001b[0m \u001b[0;32min\u001b[0m \u001b[0msorted\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mworld\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcarts\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mlambda\u001b[0m \u001b[0mc\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mY\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mc\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpos\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mX\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mc\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpos\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0mcart\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mheading\u001b[0m \u001b[0;34m*=\u001b[0m \u001b[0mturn\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcart\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mworld\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 7\u001b[0m \u001b[0mcart\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpos\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0mcart\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mheading\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 8\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mcollision\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcart\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mworld\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;32m\u001b[0m in \u001b[0;36mturn\u001b[0;34m(cart, world)\u001b[0m\n\u001b[1;32m 12\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mturn\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcart\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mworld\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 13\u001b[0m \u001b[0;34m\"Which way should the cart turn (depends on character it is on).\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 14\u001b[0;31m \u001b[0mch\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mworld\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mcart\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpos\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 15\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mch\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m'+'\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 16\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcart\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mturns\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;32m\u001b[0m in \u001b[0;36m__getitem__\u001b[0;34m(self, point)\u001b[0m\n\u001b[1;32m 20\u001b[0m if h in headings]\n\u001b[1;32m 21\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 22\u001b[0;31m \u001b[0;32mdef\u001b[0m \u001b[0m__getitem__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpoint\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mY\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpoint\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mX\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpoint\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 23\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 24\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mshow\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mIndexError\u001b[0m: string index out of range"
]
}
],
"source": [
"madmad(World(Input(13)))"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.0"
}
},
"nbformat": 4,
"nbformat_minor": 2
}