{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Advent of Code 2017](http://adventofcode.com/2017)\n",
"\n",
"The fastest 100 solutions score points.\n",
"Times for the 100th person to have both parts done were :\n",
"\n",
" 1 6:08 sum of matched digits - read list of numbers & analyze\n",
" 2 6:13 sum of max minus min - read list of numbers & analyze\n",
" 3 23:19 number spiral 2D - compute properties of grid given a number\n",
" 4 3:40 unique and non-anagram words - read lines of words, count duplicates & anagrams\n",
" 5 4:46 jump around in a list - list of numbers as instructions, \"running\" it\n",
" 6 9:30 redistributing values until repeat - processing list of numbers with a recipe\n",
" 7 25:21 tree balancing - parse lines into a tree, analyze tree\n",
" 8 8:22 parsing numerical expressions - parse each line, update named registers\n",
" 9 11:37 matching nested {} and <> - parsing text, matching, regex\n",
" 10 25:24 foldhash hashing function - bits, crypto\n",
" 11 11:43 hex 2D grid - positions & distance given path directions\n",
" 12 9:06 graph search - read in graph, compute connected parts\n",
" 13 21:46 avoiding scanners cycling back and forth - somewhat unclear description\n",
" 14 25:06 adjacent parts of bit grid from foldhash (see days 10,12) - continues day 10, algorithm from 12\n",
" 15 9:02 mod arithmentic and low 16 bit comparisons - bit arithmetic\n",
" 16 26:37 quasi permutations - not quite same as groupt theory but similar; brute force\n",
" 17 15:51 fifty million skips and inserts - a repeated list iteration\n",
" 18 41:02 instruction execution, two jobs with send & receive - an assembly machine simulation\n",
" 19 18:04 following a ascii maze : --A--|----+\n",
" 20 21:33 3D integer particle collisions, constant acceleration\n",
" 21 44:51 2D grid of #. growing by pattern match rules\n",
" 22 20:29 2D grid of #. evolving with agent at one spot (similar grid, different rules than 21)\n",
" 23 54:41 interpreting assembly language numeric loops ; variation of day 18 ... but need to understand it\n",
" 24 21:02 tree search of domino matching - search problem , bit tricky data type\n",
" 25 11:16 explicit turing simulation + all other problems\n",
" \n",
"My times are more like half an hour at best but more typically a couple of hours.\n",
"\n",
"Jim Mahoney | jim@mahoney.cc | cs.marlboro.edu "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## imports and utility functions"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3.5.2 |Anaconda custom (x86_64)| (default, Jul 2 2016, 17:52:12) \n",
"[GCC 4.2.1 Compatible Apple LLVM 4.2 (clang-425.0.28)]\n"
]
}
],
"source": [
"from matplotlib.pyplot import plot\n",
"import matplotlib.pyplot as plt\n",
"import numpy as np\n",
"import math\n",
"import re\n",
"import time\n",
"import urllib.request\n",
"import string\n",
"import sys; print(sys.version)\n",
"\n",
"# -------------------------------------------------------------------------\n",
"# Peter Norvig's Dec 2016 advent of code imports and utility functions \n",
"# ... with a few changes. I've used some of these, but in practice have \n",
"# found that I don't know them well enough and am writing my own.\n",
"\n",
"from collections import Counter, defaultdict, namedtuple, deque\n",
"from functools import lru_cache\n",
"from itertools import permutations, combinations, chain, cycle, product\n",
"from heapq import heappop, heappush\n",
"\n",
"def Input(day):\n",
" \"Open this day's input file.\"\n",
" filename = 'inputs/{}.txt'.format(day)\n",
" try:\n",
" return open(filename)\n",
" except FileNotFoundError:\n",
" # urllib.request.urlopen(\"http://norvig.com/ipython/\" + filename)\n",
" print(\"Oops - couldn't find input.\")\n",
"\n",
"def transpose(matrix): return zip(*matrix)\n",
"\n",
"def first(iterable): return next(iter(iterable))\n",
"\n",
"def firsttrue(iterable): return first(it for it in iterable if it)\n",
"\n",
"def counttrue(iterable): return sum(bool(it) for it in iterable)\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",
"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(_callstr(f, args), result))\n",
" return result\n",
" return traced_f\n",
"\n",
"def trace(f):\n",
" \"Print a trace of the call and args on one line, and the return on another.\"\n",
" def traced_f(*args):\n",
" print(_callstr(f, args))\n",
" trace.indent += 1\n",
" try:\n",
" result = f(*args)\n",
" finally:\n",
" trace.indent -= 1\n",
" print('{} = {}'.format(_callstr(f, args), result))\n",
" return result\n",
" return traced_f\n",
"trace.indent = 0\n",
"\n",
"def _callstr(f, args):\n",
" \"Return a string representing f(*args).\"\n",
" return '{}{}({})'.format('> ' * trace.indent, f.__name__, ', '.join(map(str, args)))\n",
"\n",
"# --------------------------------------------------------------------------------\n",
"# My utility functions which seemed like they might be useful for more than one problem.\n",
"\n",
"def Point(x,y):\n",
" \"2D points as numpy arrays\"\n",
" # which means they can be added and scaled\n",
" return np.array((x,y), dtype=np.int32)\n",
"\n",
"def neighbors8(point):\n",
" \"list of eight neighboring points, including diagonals\"\n",
" return [(point + Point(x,y)) for x in (-1,0,1) for y in (-1,0,1) if x!=0 or y != 0]\n",
"\n",
"def neighbors4(point):\n",
" return [(point[0]+1, point[1]), (point[0]-1, point[1]), \n",
" (point[0], point[1]+1), (point[0], point[1]-1)]\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## tests and examples of utility functions"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([3, 7], dtype=int32)"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Point(1,2) + Point(2,5)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[array([9, 9], dtype=int32),\n",
" array([ 9, 10], dtype=int32),\n",
" array([ 9, 11], dtype=int32),\n",
" array([10, 9], dtype=int32),\n",
" array([10, 11], dtype=int32),\n",
" array([11, 9], dtype=int32),\n",
" array([11, 10], dtype=int32),\n",
" array([11, 11], dtype=int32)]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"neighbors8(Point(10,10))"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"((1, 4), (2, 5), (3, 6))"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tuple(transpose( ((1,2,3),(4,5,6)) ))"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'h'"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"first('hello')"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"firsttrue([None, False, 1, 2])"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"counttrue([None, False, 1, 2])"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'onetwo'"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cat(('one', 'two'))"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[89, 144, 233, 377, 610]"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@lru_cache(maxsize=None)\n",
"def fib(n):\n",
" if n < 2:\n",
" return 1\n",
" else:\n",
" return fib(n-1) + fib(n-2)\n",
"[fib(i) for i in range(10,15)]"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"simplefunc(3)\n",
"simplefunc(3) = 4\n"
]
},
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@trace\n",
"def simplefunc(x):\n",
" return x+1\n",
"simplefunc(3)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"((), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3))"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tuple(powerset([1,2,3]))"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"defaultdict(list, {3: ['one', 'two'], 4: ['four'], 5: ['three']})"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"groupby(('one', 'two', 'three', 'four'), key=len)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"the first\n",
"and the second\n"
]
}
],
"source": [
"grep('the', (\"the first\", \"and the second\", \"and third\"))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"--------\n",
"# [Day 1](http://adventofcode.com/2017/day/1) : Inverse Captcha"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'5228833336355848549915459366737982598312959583817455621545976784792489468198365998232722734876612332352376192813552949814275947575774339529811976644361517795586998319242241614813622734255797569571577699238592667287428166398221572885869416419682687759743978434571821267146514338394624525648338739929479912368172669885577319718389278168766844487948761697438722556857882433224393723131298876252626643517236883999115665656935521675772866516185899317132494716723615493476397115627687887665194781746377341468995954554518252916859227397693885254329628812355612487594445522395853551734567498838382248616137969637971369615443599973588326388792893969924855316437952313492551671545714262784738343517166544197194547173515155927244175447296474282154114951181648317875827525814453758846194548872789943372281952995222779173812444186491115426476188672253249744478946863317915136832199132868917891243591195719354721129116229164688256853628339233919671468781913167415624214152793864585332944468428849171876873433621524242289488135675313544498245498637424139153782925723745249728743885493877792648576673196889949568317234125863369187953788611841388353999875519172896329524346527265231767868839696693328273381772726782949166112932954356923757485139367298699922984925977724972944277991686823219295939734313874834861796179591659174726432357533113896212781566659154939419866797488347448551719481632572231632463575591599696388223344219228325134233238538854289437756331848887242423387542214691157226725179683638967415678697625138177633444765126223885478348951332634398291612134852858683942466178329922655822225426534359191696177633167962839847985826676955417426617126288255366123169174674348417932158291334646767637764323226842771523598562429399935789788215958367362467652444854123951972118358417629679454978687337137675495295768451719631999398617828287671937584998697959425845883145736323818225129311845997214987663433375689621746665629187252511643969315283316269222835744532431378945137649959158495714472963839397214332815241141327714672141875129895'"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input = Input(1).readline()[:-1] # last char is newline; skip it.\n",
"input"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(('1', 'a'), ('2', 'b'), ('3', 'c'))"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def after(string, i):\n",
" \"\"\" next digit \"\"\"\n",
" return string[(i+1) % len(string)]\n",
"\n",
"def match_next(string, i):\n",
" \"\"\" True if next digit matches\"\"\"\n",
" return string[i] == after(string, i)\n",
"\n",
"def day1sum(string):\n",
" \"\"\" sum of all digits such that following digit is same, wrap at end.\"\"\"\n",
" total = 0\n",
" for i in range(len(string)):\n",
" if match_next(string, i):\n",
" total += int(string[i])\n",
" return total\n",
"\n",
"tuple(zip('123', 'abc'))"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['2', '3', '4', '1']"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[after('1234', i) for i in range(4)]"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('a', 'a')"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tuple(filter(lambda x:x=='a', 'abca'))"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(3, 4, 0, 9)"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The examples given.\n",
"tuple(map(day1sum, ('1122', '1111', '1234', '91212129')))"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1216"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"day1sum(input)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"1216 is correct ... with rank 568 on the leaderboard (12:20am). On to part 2."
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def half_around(string, i):\n",
" \"\"\" next digit \"\"\"\n",
" return string[(i + len(string)//2) % len(string)]\n",
"\n",
"def match_half_around(string, i):\n",
" \"\"\" True if next digit matches\"\"\"\n",
" return string[i] == half_around(string, i)\n",
"\n",
"def day1sum_2(string):\n",
" \"\"\" sum of all digits such that half around digit is same.\"\"\"\n",
" total = 0\n",
" for i in range(len(string)):\n",
" if match_half_around(string, i):\n",
" total += int(string[i])\n",
" return total\n"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(6, 0, 4, 12, 4)"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The examples given.\n",
"tuple(map(day1sum_2, ('1212', '1221', '123425', '123123', '12131415')))"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1072"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"day1sum_2(input)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"1072 is correct ... with rank 656 on the leaderboard (12:36am)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---------"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(1216, 1072)"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Alternative entirely functional terse version.\n",
"def day1_alt(s, m):\n",
" \"\"\" sum of digits of string s such that s[i]==s[i+m] with wrap around. \"\"\"\n",
" return sum(tuple(map(lambda y: int(y[0]), \n",
" filter(lambda x: x[0]==x[1], \n",
" zip(s, s[m:] + s[:m])))))\n",
"day1_alt(input, 1), day1_alt(input, len(input)//2)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 2](http://adventofcode.com/2017/day/2) : Corruption Checksum"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"matrix([[5048, 177, 5280, 5058, 4504, 3805, 5735, 220, 4362, 1809, 1521,\n",
" 230, 772, 1088, 178, 1794],\n",
" [6629, 3839, 258, 4473, 5961, 6539, 6870, 4140, 4638, 387, 7464,\n",
" 229, 4173, 5706, 185, 271],\n",
" [5149, 2892, 5854, 2000, 256, 3995, 5250, 249, 3916, 184, 2497,\n",
" 210, 4601, 3955, 1110, 5340],\n",
" [ 153, 468, 550, 126, 495, 142, 385, 144, 165, 188, 609,\n",
" 182, 439, 545, 608, 319],\n",
" [1123, 104, 567, 1098, 286, 665, 1261, 107, 227, 942, 1222,\n",
" 128, 1001, 122, 69, 139],\n",
" [ 111, 1998, 1148, 91, 1355, 90, 202, 1522, 1496, 1362, 1728,\n",
" 109, 2287, 918, 2217, 1138],\n",
" [ 426, 372, 489, 226, 344, 431, 67, 124, 120, 386, 348,\n",
" 153, 242, 133, 112, 369],\n",
" [1574, 265, 144, 2490, 163, 749, 3409, 3086, 154, 151, 133,\n",
" 990, 1002, 3168, 588, 2998],\n",
" [ 173, 192, 2269, 760, 1630, 215, 966, 2692, 3855, 3550, 468,\n",
" 4098, 3071, 162, 329, 3648],\n",
" [1984, 300, 163, 5616, 4862, 586, 4884, 239, 1839, 169, 5514,\n",
" 4226, 5551, 3700, 216, 5912],\n",
" [1749, 2062, 194, 1045, 2685, 156, 3257, 1319, 3199, 2775, 211,\n",
" 213, 1221, 198, 2864, 2982],\n",
" [ 273, 977, 89, 198, 85, 1025, 1157, 1125, 69, 94, 919,\n",
" 103, 1299, 998, 809, 478],\n",
" [1965, 6989, 230, 2025, 6290, 2901, 192, 215, 4782, 6041, 6672,\n",
" 7070, 7104, 207, 7451, 5071],\n",
" [1261, 77, 1417, 1053, 2072, 641, 74, 86, 91, 1878, 1944,\n",
" 2292, 1446, 689, 2315, 1379],\n",
" [ 296, 306, 1953, 3538, 248, 1579, 4326, 2178, 5021, 2529, 794,\n",
" 5391, 4712, 3734, 261, 4362],\n",
" [2426, 192, 1764, 288, 4431, 2396, 2336, 854, 2157, 216, 4392,\n",
" 3972, 229, 244, 4289, 1902]])"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input = list(map(lambda line: list(map(int, line.rstrip().split('\\t'))), Input(2).readlines()))\n",
"np.matrix(input)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [],
"source": [
"def list_diff(row):\n",
" return np.max(row) - np.min(row)\n",
"\n",
"def checksum(m):\n",
" \"\"\" Return sum((max - min) for each row ) \"\"\"\n",
" return sum(list(map(list_diff, m)))"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"58975"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# part a\n",
"checksum(input)"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def dividend(row):\n",
" for i in range(len(row)):\n",
" for j in range(len(row)):\n",
" if i != j and row[i] >= row[j]:\n",
" if row[i] % row[j] == 0:\n",
" return row[i] // row[j]\n",
" print(\"dividend not found\")\n",
" return 0\n",
"\n",
"def checksum2(m):\n",
" \"\"\" Return sum of dividends \"\"\"\n",
" return sum(list(map(dividend, m)))"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"308"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# part b\n",
"checksum2(input)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"I have the correct answer for both in 37 min ... which puts me a bit over the 1000'th person to solve it. Most of that time was getting the input matrix into a numeric list of lists. I didn't bother with the tests this time."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 3](http://adventofcode.com/2017/day/3) : Spiral in Memory"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"We want to find (x,y) coordinates for an integer n where \n",
"the numbers are put into a spiral like this, with 1 at (0,0).\n",
"\n",
" 37 36 35 34 33 32 31\n",
" 38 17 16 15 14 13 30\n",
" 39 18 5 4 3 12 28\n",
" 40 19 6 1 2 11 28 ^\n",
" 41 20 7 8 9 10 27 .\n",
" 42 21 22 23 24 25 26 .\n",
" 43 44 45 46 47 48 49 50\n",
"\n",
"Some algebra and a bit of thought shows that the\n",
"numbers going down to the right from 1 are \n",
"squares of the odd numbers - more on that below.\n",
"\n",
"So to see where n goes, we can first find out which outer shell it's in\n",
"by taking its square root to find the closest perfect square of an odd integer,\n",
"then count around with the remainder.\n",
"\n",
"I will define the following variables to describe the pattern\n",
"numbers along the diagonal going down to the right \n",
"\n",
" i = diagonal steps from center of spiral = (0,1,2,3,...)\n",
" l = spiral side length = 1+2*i = (1,3,5,7,...)\n",
" d = digits in side = 4 * l - 4 = 4*(l-1) = (0,8,16,...)\n",
" \n",
" n = number at bottom right of spiral \n",
" = 1 + sum(d) , at position (i, -i)\n",
" = 1 + sum over i ( 4 * (1+2*i) - 1) \n",
" = 1 + sum ( 8*i ) = 1 + 4 * i * (i + 1) \n",
" = 1 + 4*i**2 + 4*i\n",
" = (2*i+1)**2\n",
"\n",
" i l d n\n",
" ------------------------\n",
" 0 1 0 1 = 1**2\n",
" 1 3 8 9 = 3**2\n",
" 2 5 16 25 = 5**2\n",
" 3 7 24 49 = 7**2\n"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [],
"source": [
"def xy(n):\n",
" \"\"\" Return (x,y) coords of n in the spiral pattern. \"\"\"\n",
" if n==0:\n",
" return (0,0)\n",
" # Find l for the last completed fully filled square.\n",
" last_l = int(math.sqrt(float(n)))\n",
" if last_l % 2 == 0: # If even, lower by 1 to make odd.\n",
" last_l = last_l - 1\n",
" last_i = (last_l - 1)/2\n",
" this_i = last_i + 1\n",
" # Starting at that position L, move along the spiral around\n",
" # the outermost square, like this:\n",
" #\n",
" # 2 < < 1\n",
" # v ^\n",
" # v L 0\n",
" # 3 > > 4\n",
" #\n",
" # L is the last_i corner of a complete inner square,\n",
" # with value last_i**2 at coordinate (last_i, -last_i).\n",
" #\n",
" # The spiral path moves to the places marked (0,1,2,3,4)\n",
" # moving (right, up, left, down, right) and a number of \n",
" # steps which as most (1, side-2, side-1, side-1, side-1) \n",
" # where side = length_of_side = 2*this_i+1.\n",
" #\n",
" # I'll use number vectors since they understand addition and scaling.\n",
" position = np.matrix([last_i, -last_i])\n",
" #print(\"position = {}\".format(position))\n",
" direction = list(map(lambda v: np.matrix(v), \n",
" [[1,0], [0,1], [-1,0], [0,-1], [1,0]]))\n",
" #print(\"direction = {}\".format(direction))\n",
" distance = [1, 2 * this_i - 1] + [2 * this_i] * 3\n",
" #print(\"distance = {}\".format(distance))\n",
" remaining_n = n - last_l**2\n",
" index = 0 # which direction and distance we're working on.\n",
" while remaining_n > 0:\n",
" #print(\" remaining_n = {}\".format(remaining_n))\n",
" if remaining_n <= distance[index]:\n",
" position = position + remaining_n * direction[index]\n",
" remaining_n = 0\n",
" else:\n",
" position = position + distance[index] * direction[index]\n",
" remaining_n = remaining_n - distance[index]\n",
" index = index + 1\n",
" #print(\" new position = {}\".format(position))\n",
" return (int(position[0,0]), int(position[0,1]))\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [],
"source": [
"\n",
"# 37 36 35 34 33 32 31\n",
"# 38 17 16 15 14 13 30\n",
"# 39 18 5 4 3 12 28\n",
"# 40 19 6 1 2 11 28 ^\n",
"# 41 20 7 8 9 10 27 .\n",
"# 42 21 22 23 24 25 26 .\n",
"# 43 44 45 46 47 48 49 50\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(-2, 1)"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"xy(18)"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(-185, 295)"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"xy(347991)"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"480"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# part a - answer\n",
"185+295"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now that I can see the second day, it looks like I will need to work directly with the grid itself - the algebraic shortcut from the first part won't work again."
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [],
"source": [
"\n",
"# I've set Points in the utility section at the top of the page.\n",
"\n",
"class Spiral:\n",
" def __init__(self, size=600, n=1):\n",
" # 600 is big enough so that 600**2 > 347991 , the size of the day1 part1 input.\n",
" self.size = size\n",
" self.halfsize = size // 2\n",
" self.data = np.zeros((size,size), dtype=np.int32)\n",
" self.position = Point(0,0) # place where last value was placed.\n",
" self.set_value(self.position, 1) # initial state with innermost 1 by 1 square filled\n",
" self.side = 3 # side length = (1,3,5,7) ; i = (side-1)//2 = (0,1,2,...)\n",
" self.index = 0 # distance & direction to next position ; = 0 to 4 looping\n",
" self.steps = 0 # step counter along side; 0 <= steps < side\n",
" self.direction = [Point(1,0), Point(0,1), Point(-1,0), Point(0,-1), Point(1,0)]\n",
" self.distance = self.get_distance()\n",
" if n > 1:\n",
" self.do_linear_upto(n)\n",
" def get_distance(self):\n",
" return [1, self.side - 2] + [self.side - 1]*3\n",
" def get_rowcol(self, point):\n",
" # point coords (x,y) have x increasing to right, y increasing up, (0,0) in center\n",
" # matrix coords (row,col) have col increasing to right, row increasing down, (0,0) at top left\n",
" return (self.halfsize - point[1], self.halfsize + point[0]) # (row, column)\n",
" def set_value(self, point, n):\n",
" (row, col) = self.get_rowcol(point)\n",
" self.data[row, col] = n\n",
" def get_value(self, point):\n",
" (row, col) = self.get_rowcol(point)\n",
" return self.data[row, col]\n",
" def put_next(self, value):\n",
" \"\"\" Move self.position to the next spiral position and put value there.\"\"\"\n",
" #print( \"position={}, index={}, direction={}, distance={}, steps={}, value={}\".format(\n",
" # self.position, self.index, self.direction[self.index], self.distance[self.index], self.steps, value))\n",
" self.position = self.position + self.direction[self.index]\n",
" self.set_value(self.position, value)\n",
" self.steps += 1\n",
" if self.steps >= self.distance[self.index]: # at a corner so turn\n",
" self.steps = 0\n",
" if self.index < 4:\n",
" self.index += 1\n",
" else: \n",
" self.index = 0 # filled a square so next layer\n",
" self.side += 2\n",
" self.distance = self.get_distance()\n",
" def as_grid(self, int_width=4):\n",
" margin = ' '\n",
" result = ''\n",
" # self.side is length of outer square being worked on.\n",
" imax = (self.side + 2 - 1) // 2 # border of 1 or 2 : (-imax ... imax)\n",
" int_form = ' {{:{}}}'.format(int_width)\n",
" for y in range(imax, -(imax+1), -1 ):\n",
" result += margin\n",
" for x in range(-imax, imax+1):\n",
" value = self.get_value(Point(x, y))\n",
" if value == 0:\n",
" result += ' '*int_width + '.'\n",
" else:\n",
" result += int_form.format(value)\n",
" #print(\" ({},{}) => {}\".format(x,y,value))\n",
" result += '\\n'\n",
" return result\n",
" def do_linear_upto(self, n):\n",
" \"\"\" put linear values (1,2,3,4,5,...,n) into each next position, \n",
" starting at current value and position \"\"\"\n",
" value = self.get_value(self.position)\n",
" for how_many in range(n - value):\n",
" value += 1\n",
" self.put_next(value)\n",
" def sum_adjacent_values(self, position):\n",
" \"\"\" Return the sum of the eight values adjacent to the given position \"\"\"\n",
" # See utility functions at top of page for neighbors8\n",
" return sum([self.get_value(p) for p in neighbors8(position)])\n",
" def put_next_adjacent_sum(self):\n",
" \"\"\" Put sum of adjacent values into next position.\"\"\"\n",
" self.put_next(0) # Go to next position, put 0 there.\n",
" adjacent_sum = self.sum_adjacent_values(self.position) # Find sum of values around it.\n",
" self.set_value(self.position, adjacent_sum) # Put that value there.\n",
"\n",
" def do_adjacent_sums_upto(self, n):\n",
" \"\"\" put sums of adjacent values into next position until we reach a value larger than n.\"\"\"\n",
" while self.get_value(self.position) < n:\n",
" self.put_next_adjacent_sum()\n"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [ 0, 0, 0, 65, 64, 63, 62, 61, 60, 59, 58, 57, 0, 0, 0],\n",
" [ 0, 0, 0, 66, 37, 36, 35, 34, 33, 32, 31, 56, 0, 0, 0],\n",
" [ 0, 0, 0, 67, 38, 17, 16, 15, 14, 13, 30, 55, 0, 0, 0],\n",
" [ 0, 0, 0, 68, 39, 18, 5, 4, 3, 12, 29, 54, 0, 0, 0],\n",
" [ 0, 0, 0, 69, 40, 19, 6, 1, 2, 11, 28, 53, 0, 0, 0],\n",
" [ 0, 0, 0, 70, 41, 20, 7, 8, 9, 10, 27, 52, 0, 0, 0],\n",
" [ 0, 0, 0, 71, 42, 21, 22, 23, 24, 25, 26, 51, 0, 0, 0],\n",
" [ 0, 0, 0, 72, 43, 44, 45, 46, 47, 48, 49, 50, 0, 0, 0],\n",
" [ 0, 0, 0, 73, 74, 75, 76, 77, 78, 79, 80, 0, 0, 0, 0],\n",
" [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], dtype=int32)"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"b = Spiral(size=15, n=80)\n",
"b.data"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" . . . . . . . . . . .\n",
" . 65 64 63 62 61 60 59 58 57 .\n",
" . 66 37 36 35 34 33 32 31 56 .\n",
" . 67 38 17 16 15 14 13 30 55 .\n",
" . 68 39 18 5 4 3 12 29 54 .\n",
" . 69 40 19 6 1 2 11 28 53 .\n",
" . 70 41 20 7 8 9 10 27 52 .\n",
" . 71 42 21 22 23 24 25 26 51 .\n",
" . 72 43 44 45 46 47 48 49 50 .\n",
" . 73 74 75 76 77 78 79 80 . .\n",
" . . . . . . . . . . .\n",
"\n"
]
}
],
"source": [
"print(b.as_grid())"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"44"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# test adjacent values ... should be 2+3+4+5+6+7+8+9 = 44\n",
"b.sum_adjacent_values(Point(0,0))"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# part a problem, to see if it works with this Spiral\n",
"day1a = Spiral(n=347991)"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([-185, 295], dtype=int32)"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"day1a.position"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"480"
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Answer to part a , with this explict brute force Spiral : OK.\n",
"np.sum(np.abs(day1a.position))"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [],
"source": [
"c = Spiral()"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" . . . . . . .\n",
" . 147 142 133 122 59 .\n",
" . 304 5 4 2 57 .\n",
" . 330 10 1 1 54 .\n",
" . 351 11 23 25 26 .\n",
" . 362 . . . . .\n",
" . . . . . . .\n",
"\n"
]
}
],
"source": [
"for i in range(20):\n",
" c.put_next_adjacent_sum()\n",
"print(c.as_grid())"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([-2, 4], dtype=int32)"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"c.do_adjacent_sums_upto(347991)\n",
"c.position"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" . . . . . . . . . . .\n",
" . . . 349975 330785 312453 295229 279138 266330 130654 .\n",
" . . 6591 6444 6155 5733 5336 5022 2450 128204 .\n",
" . . 13486 147 142 133 122 59 2391 123363 .\n",
" . . 14267 304 5 4 2 57 2275 116247 .\n",
" . . 15252 330 10 1 1 54 2105 109476 .\n",
" . . 16295 351 11 23 25 26 1968 103128 .\n",
" . . 17008 362 747 806 880 931 957 98098 .\n",
" . . 17370 35487 37402 39835 42452 45220 47108 48065 .\n",
" . . . . . . . . . . .\n",
" . . . . . . . . . . .\n",
"\n"
]
}
],
"source": [
"print(c.as_grid(6))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 4](http://adventofcode.com/2017/day/4) : : High-Entropy Passphrases\n",
"\n",
"This one can be done very quickly with the right tools. Python's collections have sets (to see if there are duplicates) and a Counter class (a specialized dictionary for counting how many of each) which can be used for checking for anagrams."
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['oaoe', 'rxeq', 'vssdqtu', 'xrk', 'cjv', 'yaoqp', 'loo']\n"
]
},
{
"data": {
"text/plain": [
"512"
]
},
"execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"wordlists = list(map( lambda line: line.rstrip().split(' '), Input(4).readlines()))\n",
"print(wordlists[0])\n",
"len(wordlists)"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"386"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# part a\n",
"\n",
"def are_unique(words):\n",
" return len(set(words)) == len(words)\n",
"\n",
"unique_wordlists = list(filter(are_unique, wordlists))\n",
"len(unique_wordlists)"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def word_signature(word):\n",
" return "
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"208"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# part b\n",
"\n",
"# Can use dictionary Counter for anagram signature.\n",
"def no_anagrams(words):\n",
" counters = map(Counter, words)\n",
" counter_signatures = list(map(lambda c: str(sorted(list(c.items()))), counters))\n",
" return are_unique(counter_signatures)\n",
"\n",
"anagram_free_words = list(filter(no_anagrams, wordlists))\n",
"len(anagram_free_words)\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [],
"source": [
"# I wanted to use a characteristic signature for each Counter \n",
"# since I don't know what equality looks like in their implementation\n",
"# ... though the class probably does the right thing without this.\n",
"\n",
"# Something like \n",
"# str(sorted(list(a.items())))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finished in about 30min, including starting about 10min after midnight & looking up a few things.\n",
"That put me about 100th to submit - I'm not suprised that lots of folks were fast with this one."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 5](http://adventofcode.com/2017/day/5) : A Maze of Twisty Trampolines, All Alike"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def jump(offsets, i):\n",
" \"\"\" return (offsets, i) after one jump \"\"\"\n",
" # i is an index into the list of offsets, 0 <= i < len(offsets)\n",
" delta_i = offsets[i]\n",
" offsets[i] += 1\n",
" return (offsets, i + delta_i) "
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [],
"source": [
"(state, i) = ([0, 3, 0, 1, -3], 0)"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1, 3, 0, 1, -3] 0\n",
"[2, 3, 0, 1, -3] 1\n",
"[2, 4, 0, 1, -3] 4\n",
"[2, 4, 0, 1, -2] 1\n"
]
}
],
"source": [
"for x in range(4):\n",
" (state, i) = jump(state, i)\n",
" print(state, i)"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def exit_reached(offsets):\n",
" i = 0\n",
" steps = 0\n",
" state = list(offsets) # make a copy\n",
" len_offsets = len(offsets)\n",
" while 0 <= i < len_offsets:\n",
" (state, i) = jump(state, i)\n",
" steps += 1\n",
" return steps\n",
"\n",
"exit_reached([0, 3, 0, 1, -3])"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [],
"source": [
"input = Input(5).readlines()\n",
"offsets_1 = list(map(lambda line: int(line.rstrip()), input))\n",
"#print(offsets_1)"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"339351"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# -- answer for part 1\n",
"exit_reached(offsets_1)"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def jump_2(offsets, i):\n",
" \"\"\" return (offsets, i) after one jump with part algorithm\"\"\"\n",
" delta_i = offsets[i]\n",
" if offsets[i] >= 3:\n",
" offsets[i] -= 1\n",
" else:\n",
" offsets[i] += 1\n",
" return (offsets, i + delta_i) \n",
"\n",
"def exit_reached_2(offsets):\n",
" i = 0\n",
" steps = 0\n",
" state = list(offsets) # make a copy\n",
" len_offsets = len(offsets)\n",
" while 0 <= i < len_offsets:\n",
" (state, i) = jump_2(state, i)\n",
" steps += 1\n",
" return steps\n",
"\n",
"exit_reached_2([0, 3, 0, 1, -3])\n"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"24315397"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# -- answer for part 2 ... takes a few seconds\n",
"exit_reached_2(offsets_1)"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# ... and Merlin dropped out of the top 100 scores today."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 6](http://adventofcode.com/2017/day/6) : Memory Reallocation"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [],
"source": [
"input = [2, 8, 8, 5, 4, 2, 3, 1, 5, 5, 1, 2, 15, 13, 5, 14] # short so I just copied it."
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"\n",
"def redistribute(_banks):\n",
" \"\"\" find lowest; spread into remaining \"\"\"\n",
" banks = list(_banks) # work on a copy\n",
" blocks = max(banks) # store biggest entry\n",
" i = banks.index(blocks) # get position of lowest\n",
" banks[i] = 0 # empty that one.\n",
" while blocks > 0:\n",
" i = (i + 1) % len(banks)\n",
" blocks -= 1\n",
" banks[i] += 1\n",
" return banks\n",
"\n",
"def cycles_to_repeat(banks):\n",
" \"\"\" find number of redistributions to repeat\"\"\"\n",
" seen = {str(banks): 0} # states that have been seen & first cycle when seen\n",
" cycles = 0\n",
" while True:\n",
" cycles += 1\n",
" banks = redistribute(banks)\n",
" str_banks = str(banks)\n",
" if str_banks in seen:\n",
" return (cycles, cycles - seen[str_banks])\n",
" else:\n",
" seen[str_banks] = cycles\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a = [3, 2, 3, 5, 2, 7]\n",
"min(a) # lowest value"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a.index(2) # first location of that value"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'[3, 2, 3, 5, 2, 7]'"
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"str(a)"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(3156, 1610)"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# -- part 1\n",
"cycles_to_repeat(input)"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(3156, 1610)"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# -- part 2 , after change to find size of loop\n",
"cycles_to_repeat(input)"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# about 600'th solution on leaderboard."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 7](http://adventofcode.com/2017/day/7) : Recursive Circus"
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['mqdjo (83)',\n",
" 'jzgxy (15) -> usdayz, zvbru',\n",
" 'altep (75)',\n",
" 'gaieus (117) -> unkring, wjgvjlg',\n",
" 'ejlbps (59)',\n",
" 'uralh (17)',\n",
" 'tzdmi (891) -> mhzwwo, mgybhs, pptdd',\n",
" 'whntvd (2133) -> vuzxyz, hcfgnt, kuvek',\n",
" 'aoqjxqk (99) -> qjfdh, vmusp, yqmclp',\n",
" 'wwmjf (404) -> vvoadnv, sgujp']"
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input = list(map(lambda x: x.rstrip(), Input(7).readlines()))\n",
"input[:10]"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1171"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(input)"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('tzdmi', '891', ' -> ', 'mhzwwo, mgybhs, pptdd')"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# This is the result of several attempts. \n",
"# Rather than try to parse everything at once,\n",
"# This captures the children as a string that can be split later.\n",
"re.match(r'(\\w+) \\((\\d+)\\)( -> )?(.*)?', 'tzdmi (891) -> mhzwwo, mgybhs, pptdd').groups()"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('tzdmi', '891', None, '')"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Make sure it works if there aren't any children.\n",
"re.match(r'(\\w+) \\((\\d+)\\)( -> )?(.*)?', 'tzdmi (891)').groups()"
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {},
"outputs": [],
"source": [
"# OK, using that parse string, put all the data into a single dictionary\n",
"def parse_lines(data):\n",
" result = {}\n",
" for line in data:\n",
" g = re.match(r'(\\w+) \\((\\d+)\\)( -> )?(.*)?', line).groups()\n",
" key = g[0]\n",
" weight = int(g[1]) \n",
" result[key] = {'weight':weight, 'children':[]}\n",
" if g[2]:\n",
" result[key]['children'] = g[3].split(', ')\n",
" return result\n",
"\n",
"tree = parse_lines(input) "
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1171"
]
},
"execution_count": 72,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Number of entries is consistent with size of input - OK.\n",
"len(tree)"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'children': ['unkring', 'wjgvjlg'], 'weight': 117}\n",
"{'children': [], 'weight': 83}\n",
"{'children': ['mhzwwo', 'mgybhs', 'pptdd'], 'weight': 891}\n"
]
}
],
"source": [
"# Checking out a few entries to see that it looks good.\n",
"print(tree['gaieus'])\n",
"print(tree['mqdjo'])\n",
"print(tree['tzdmi'])"
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {},
"outputs": [],
"source": [
"# Loop through all the nodes and store each one's parent.\n",
"def assign_parents(tree):\n",
" for node in tree:\n",
" for child in tree[node]['children']:\n",
" tree[child]['parent'] = node\n",
" return tree\n",
"\n",
"tree = assign_parents(tree)"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {},
"outputs": [],
"source": [
"# Start anywhere and go towards parent to find top.\n",
"def find_root(tree):\n",
" name = 'mqdjo'\n",
" while 'parent' in tree[name]:\n",
" name = tree[name]['parent']\n",
" return name"
]
},
{
"cell_type": "code",
"execution_count": 76,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'dtacyn'"
]
},
"execution_count": 76,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# - part 1\n",
"root = find_root(tree)\n",
"root"
]
},
{
"cell_type": "code",
"execution_count": 77,
"metadata": {},
"outputs": [],
"source": [
"# OK, weights.\n",
"\n",
"# Recursively find and store total weight (weight of node and those below) of each node.\n",
"# (Do this with a cache so nothing needs to be done twice.)\n",
"def total_weight(node):\n",
" if 'total_weight' in tree[node]:\n",
" return tree[node]['total_weight']\n",
" tw = tree[node]['weight']\n",
" if len(tree[node]['children']) != 0:\n",
" tw += sum(list(map(total_weight, tree[node]['children'])))\n",
" tree[node]['total_weight'] = tw\n",
" return tw\n",
"\n",
"# Now run that on each node.\n",
"for name in tree:\n",
" x = total_weight(name)\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 78,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"446999"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Check: this is the weight seen at the root.\n",
"tree[root]['total_weight']"
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"446999"
]
},
"execution_count": 79,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# And this is the explicit weight of all the nodes - should be the same.\n",
"sum(list(map(lambda x: tree[x]['weight'], tree.keys())))"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['xvuxc', 'eyyrn', 'udtsgjk', 'zprkrrn', 'rhhdc', 'rtdpm']"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Starting at the top : children 1 down\n",
"level1 = tree['dtacyn']['children']; level1"
]
},
{
"cell_type": "code",
"execution_count": 81,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[74497, 74492, 74492, 74492, 74492, 74492]"
]
},
"execution_count": 81,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# weights at level 1\n",
"list(map(lambda node: tree[node]['total_weight'], level1))"
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['nieyygi', 'hmcjz', 'ceizm']"
]
},
"execution_count": 82,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# So the unbalanced one is the first, xvuxc. It's children are\n",
"tree['xvuxc']['children']"
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[11781, 11776, 11776]"
]
},
"execution_count": 83,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# And their weights are \n",
"list(map(lambda node: tree[node]['total_weight'], ['nieyygi', 'hmcjz', 'ceizm'] ))"
]
},
{
"cell_type": "code",
"execution_count": 84,
"metadata": {},
"outputs": [],
"source": [
"# OK, time to stop doing this manually and get real.\n",
"\n",
"# First look at each one and store whether or not it's balanced.\n",
"for node in tree:\n",
" if len(tree[node]['children']) == 0:\n",
" tree[node]['balanced'] = True\n",
" else:\n",
" maxchild = max(list(map(lambda x: tree[x]['total_weight'], tree[node]['children'])))\n",
" minchild = min(list(map(lambda x: tree[x]['total_weight'], tree[node]['children'])))\n",
" if maxchild != minchild:\n",
" tree[node]['balanced'] = False\n",
" else:\n",
" tree[node]['balanced'] = True"
]
},
{
"cell_type": "code",
"execution_count": 85,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"dtacyn is unbalanced\n",
"xvuxc is unbalanced\n",
"nieyygi is unbalanced\n"
]
}
],
"source": [
"# Now trace down from the top to find the ones that aren't balanced.\n",
"node = root\n",
"while True:\n",
" if not tree[node]['balanced']:\n",
" print(node + ' is unbalanced')\n",
" new_node = ''\n",
" for child in tree[node]['children']:\n",
" if not tree[child]['balanced']:\n",
" new_node = child\n",
" if new_node == '':\n",
" break\n",
" else:\n",
" node = new_node "
]
},
{
"cell_type": "code",
"execution_count": 86,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['ptshtrn', 'mxgpbvf', 'cfqdsb', 'yfejqb']"
]
},
"execution_count": 86,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Hmmm. I guess I stopped the manual search too soon - \n",
"# going once more by hand would have shown the culprit.\n",
"\n",
"# Here are the children of the last unbalanced one.\n",
"tree['nieyygi']['children']"
]
},
{
"cell_type": "code",
"execution_count": 87,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1122, 1117, 1117, 1117]"
]
},
"execution_count": 87,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# And here are it's weights.\n",
"list(map(lambda node: tree[node]['total_weight'], ['ptshtrn', 'mxgpbvf', 'cfqdsb', 'yfejqb'] ))"
]
},
{
"cell_type": "code",
"execution_count": 88,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'balanced': True,\n",
" 'children': ['uslizt', 'pjqtv', 'bzbdorp', 'atvkttc'],\n",
" 'parent': 'nieyygi',\n",
" 'total_weight': 1122,\n",
" 'weight': 526}"
]
},
"execution_count": 88,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# So this is the one with the wrong weight.\n",
"tree['ptshtrn']"
]
},
{
"cell_type": "code",
"execution_count": 89,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"521"
]
},
"execution_count": 89,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# ptshtrn has the wrong weight.\n",
"#\n",
"# Its children are all the same weight (which \n",
"# we know because it is a balanced node)\n",
"# but it is making its parent nieyygi unbalanced by \n",
"# by not having the right weight itself.\n",
"#\n",
"# Looking at the total weights of nieyygi's children,\n",
"# we can see that nieyygi is too high by 1122 - 1117 = 5.\n",
"#\n",
"# Therefore ptshtrn should be lower by 5. \n",
"# And since it's current weight is 526, \n",
"# can see that it's weight should be ...\n",
"\n",
"# part 2\n",
"526 - (1122 - 1117)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Two hours on this one puts me at about the 1200th person to finish it.\n",
"\n",
"Slow on python regex - had one that only found the first two children at first - and slow to trace throught the \"unbalanced\" implications.\n",
"\n",
"I also spent too much time typing - in several places I could have defined short cuts, such as children_of(node) and parent_of(node) and weight_of(node).\n",
"\n",
"(I also see looking back that my language for the tree in the what I've written above puts the root at the top, as CS folks typically do, even though the verbiage in the problem has it at the bottom.)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 8](http://adventofcode.com/2017/day/8) : I Heard You Like Registers"
]
},
{
"cell_type": "code",
"execution_count": 90,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['smi inc 781 if epx > -2',\n",
" 'yrf dec -813 if jzm != 6',\n",
" 'ben dec -383 if sp == 0',\n",
" 'tlj dec -356 if sp <= 4',\n",
" 'ssv dec -128 if tlj <= 360',\n",
" 'vlh dec -978 if ih == 0',\n",
" 'ben dec -28 if bwj > -5',\n",
" 'w dec 216 if ben == 411',\n",
" 'ke dec -540 if blg <= 9',\n",
" 'ty dec 469 if yrf > 810']"
]
},
"execution_count": 90,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input = list(map(lambda x: x.rstrip(), Input(8).readlines()))\n",
"input[:10]"
]
},
{
"cell_type": "code",
"execution_count": 91,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('ssv', 'dec', '-128', 'tlj', '<=', '360')"
]
},
"execution_count": 91,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"re.match(r'(\\w+) (\\w+) (-?\\d+) if (\\w+) (..?) (-?\\d+)', 'ssv dec -128 if tlj <= 360').groups()\n"
]
},
{
"cell_type": "code",
"execution_count": 92,
"metadata": {},
"outputs": [],
"source": [
"def parse_input(data):\n",
" \"\"\" Return list of instructions\"\"\"\n",
" instructions = []\n",
" for line in data:\n",
" m = re.match(r'(\\w+) (\\w+) (-?\\d+) if (\\w+) (..?) (-?\\d+)', line)\n",
" (name, what, change, ifname, condition, ifvalue) = m.groups()\n",
" instructions.append({'name' : name,\n",
" 'what' : what,\n",
" 'change' : int(change),\n",
" 'ifname': ifname,\n",
" 'condition' : condition,\n",
" 'ifvalue' : int(ifvalue)\n",
" })\n",
" return instructions\n",
"\n",
"code = parse_input(input)"
]
},
{
"cell_type": "code",
"execution_count": 93,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1000"
]
},
"execution_count": 93,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(code)"
]
},
{
"cell_type": "code",
"execution_count": 94,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1000"
]
},
"execution_count": 94,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(input)"
]
},
{
"cell_type": "code",
"execution_count": 95,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[{'change': 781,\n",
" 'condition': '>',\n",
" 'ifname': 'epx',\n",
" 'ifvalue': -2,\n",
" 'name': 'smi',\n",
" 'what': 'inc'},\n",
" {'change': -813,\n",
" 'condition': '!=',\n",
" 'ifname': 'jzm',\n",
" 'ifvalue': 6,\n",
" 'name': 'yrf',\n",
" 'what': 'dec'},\n",
" {'change': -383,\n",
" 'condition': '==',\n",
" 'ifname': 'sp',\n",
" 'ifvalue': 0,\n",
" 'name': 'ben',\n",
" 'what': 'dec'},\n",
" {'change': -356,\n",
" 'condition': '<=',\n",
" 'ifname': 'sp',\n",
" 'ifvalue': 4,\n",
" 'name': 'tlj',\n",
" 'what': 'dec'}]"
]
},
"execution_count": 95,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"code[0:4]"
]
},
{
"cell_type": "code",
"execution_count": 96,
"metadata": {},
"outputs": [],
"source": [
"def run(commands):\n",
" \"\"\" Return memory after running commands\"\"\"\n",
" mem = {}\n",
" highest = 0\n",
" for c in commands:\n",
" condition = c['condition']\n",
" ifname = c['ifname']\n",
" name = c['name']\n",
" what = c['what']\n",
" change = c['change']\n",
" ifvalue = c['ifvalue']\n",
" if not name in mem:\n",
" mem[name] = 0\n",
" if not ifname in mem:\n",
" mem[ifname] = 0\n",
" if condition == '<':\n",
" truthvalue = mem[ifname] < ifvalue\n",
" elif condition == '<=':\n",
" truthvalue = mem[ifname] <= ifvalue\n",
" elif condition == '>':\n",
" truthvalue = mem[ifname] > ifvalue\n",
" elif condition == '>=':\n",
" truthvalue = mem[ifname] >= ifvalue\n",
" elif condition == '==':\n",
" truthvalue = mem[ifname] == ifvalue\n",
" elif condition == '!=':\n",
" truthvalue = mem[ifname] != ifvalue\n",
" if truthvalue:\n",
" if what == 'inc':\n",
" mem[name] += change\n",
" else:\n",
" mem[name] -= change\n",
" if mem[name] > highest:\n",
" highest = mem[name]\n",
" mem['_highest_'] = highest\n",
" return mem\n",
"\n",
"values = run(code)\n"
]
},
{
"cell_type": "code",
"execution_count": 97,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6056"
]
},
"execution_count": 97,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# -- part 1\n",
"max(values.values())"
]
},
{
"cell_type": "code",
"execution_count": 98,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6056"
]
},
"execution_count": 98,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# -- part 2\n",
"values['_highest_']"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"32 minutes ... about the 1000th person to finish\n",
"\n",
"Maybe it would have been faster would have been to translate these into something that could be \"evaled\", in python or in another language ... like this second approach. :)"
]
},
{
"cell_type": "code",
"execution_count": 99,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" part 1 : max register is 5102\n",
" part 2 : highwater mark is 6056\n"
]
}
],
"source": [
"# Second spiffier approach, using the fact that expression works in python :\n",
"# foo += 17 if bar < 22 else 0\n",
"# (in which \"17 if bar < 22 else 0\" is evaluates to either 17 or 0)\n",
"# and the exec(python_code, globals_dict) builtin which executes python code\n",
"# using globals_dict as its variables.\n",
"\n",
"def run_program(data):\n",
" # Storage for what we want to calculate.\n",
" mem = {}\n",
" highwater = 0\n",
" pattern = re.compile(r'(\\w+) (\\w+) (-?\\d+) if (\\w+) (..?) (-?\\d+)')\n",
" # Initialize memory registers to zero.\n",
" for line in data:\n",
" (name1, ignore1, ignore2, name2, ignore3, ignore4) = pattern.match(line).groups()\n",
" mem[name1] = mem[name2] = 0\n",
" # Store a copy of the variable names, since the mem dict will also have a bunch\n",
" # of system globals in it when we're done.\n",
" variables = mem.copy()\n",
" # Modify the syntax of each line to make it consistent with python's\n",
" # ternary \"if\" construct, and execute it using mem as the global variables.\n",
" for line in input:\n",
" (name1, ignore1, ignore2, name2, ignore3, ignore4) = pattern.match(line).groups()\n",
" code = line.replace(' inc ', ' += ').replace(' dec ', ' -= ') + ' else 0'\n",
" exec(code, mem)\n",
" # Check to see if the most recent variable has the highest-so-far value.\n",
" if mem[name1] > highwater:\n",
" highwater = mem[name1]\n",
" # And print the results\n",
" print(\" part 1 : max register is \", max([mem[x] for x in variables.keys()]))\n",
" print(\" part 2 : highwater mark is \", highwater)\n",
"\n",
"run_program(input)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 9](http://adventofcode.com/2017/day/9) : Stream Processing"
]
},
{
"cell_type": "code",
"execution_count": 100,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'{{{{{{!!!!!!\">},{!!>}},{<},!,!!!>}e!!!>{!'"
]
},
"execution_count": 100,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input = Input(9).readline().rstrip()\n",
"input[:50]"
]
},
{
"cell_type": "code",
"execution_count": 101,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"16753"
]
},
"execution_count": 101,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(input)"
]
},
{
"cell_type": "code",
"execution_count": 102,
"metadata": {},
"outputs": [],
"source": [
"input = re.sub('!.', '', input)\n",
"input = re.sub('<[^>]*>', '', input)"
]
},
{
"cell_type": "code",
"execution_count": 103,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'{{{{{{},{}},{},{}},{{{}}},{{{},{,{{}}},{{{},},{{}},{{{{},{{}}},{{},{}}},{}}}}}},{{{},{,},{{{},},{{},{}},{{,},{{}}}}},{{{{{},},{{{},}}},{{{}},{{{}},{{}}}},{{},}},{{{{},{}}},{{},{,{{},{}}}}},{{{{{,},{{{}},{{},{}}},{{},}}},{{{,},{{},{}},{,}},{{{},{}},{{{}},{,}},{{{},{{}}},}},{{{{{{},{}},{,{}},{{}}}},{{{{{{{}},{}},{{},{{},{}}}},{{{}},{,{}}}},{{},{{}}},{{}}},{{{,{{},}}},{{},{{},}}},{{,},{,{{},{{}}}},{}}},{{},{{{}}}}},{{,{}},{{}},{{{{,},},}}},{{{{{}}}},{,},{{{{}},},{}}}},{{{},{}},{{{},}},{{},{{}}}}},{{{},{}}}},{{{}},{{{},{}},{},{{{}},{,{{},}}}},{{},{}}},{{{{{},{}}}},{{{{{}},},{{{}},{}},{{}}},{{,{}}}}},{{,{}},{{},{}}}}}},{{{{{,}}},{{{{},},{{},{{{}},{{}}}}},{{,{}},{{}},{,}},{{{,{}},{},{{},}},{{{{},{{{{},},{,},{{},}},{{,{}},},{{{{},{}},{,{}},{{,{}}}},{},{{},{{}}}}},{{},}}},{{},{}},{{{}},{}},{{{{}},{{{{{}},}}},{{},}},{{{}},{{{{{}},}}},{{{}},{,}}}}}}},{{},{{{}},{{},{}}}}},{{,}},{{{,{{},}},{}},{{},}},{{{{},{}},{{,{}}}}}},{{{,}},{{{{}},{{},{{{}},}},{{{,{}}}}},{},{}},{{,{}}},{{,{}},{{},{}},{}}}},{{{{{},{}},{},{{,{,{,}}}}},{{},{{},},{{}}},{{{{{{{}},{}},{,}},{{{{},{}},{{{{,{,{}}},{}}},},{{{},},}},{{},{}},{{},{}}},{{{{},{}},{{{}},},{,{}}}},{{}}},{}},{{{},{}},{{{,{}},{}}},{,}}}},{{{{},{{,{}}}}}},{{{},{,{{{{{}},{}}},{}}},{{{},}}},{{{},{},{{},}},{{},{{},{}}}},{{{,},{{},{{},{}}},{{{},{}}}},{{},{}},{,{}}},{{,},{}}},{{{{},},{{{}}}},{{{,},{}},{{},{{{}},{{{},{}}}},{{},{{}}}},{{{},{,{}}},{},{}}},{{},{}},{{{}},{},{,{}}}}},{{{{{},{}},{{{,},{{}},{,{}}}},{{{{,{}}}},{,{}}},{{},{{},{}}}},{{{}},{{{},},{{{},}},{{},{,}}}}},{{{}},{{{}}},{{{},{{}}},{{},{{{{},{}}},{{{},},{}}},{,}}},{{,{}},{},{{{}},{{,}},{{}}}}},{{{},{{{}}},{{{}},{{},}}}}},{{{{,}},{{,{}},{}},{{{},},{{},{{{}}}}},{{{{}}},{{{{},{}}},{{},{}},{{,{,{}}},}},{{},{{},}}}},{{{{},{}}},{{,},{,},{{{{}},{{},},{}},{{{},{}},{}}}},{{{},},{},{}}},{{{{{{}},},{},{}},{{},{{},{,{}},{{},}}},{}},{{,},{{},}},{{,{}},{{},{}}},{{{},},{{,{}},{}}}},{{{},{{},{}},{{}}}}},{{{{{},{,},{{}}}},{{{}},{,{}},{{}}}},{{{{{{},{{,{}}},{{},{}}}},{{{{},{,{{}}},{}}}}},{{{{{},{}},{{{{}},{{,}}}}},{{{},{{{{},},{{},{}}}}}},{{},{{}},{}},{{{},{{{{},},}},{}},{},{{{{{},},},{{},{}},{{{,},{{{{},{}},{{{{},},}}}}},{{,},{{{{{{},},{}},{}},{,},{{{{{}},{,}},{{}},{}},{{{},{}}},{{,{}},{{{{}},},{}},{{},}}}},{{},{{}}}}}}},{{{{{,{}}},{{,{}}},{}},{{{}},{{},}},{{},}},{{{{}},},{{}},{{}}}}}}},{{},{{}},{{}}},{{},{,{}}},{{,},{,{}},{{},}}},{}},{{{},{}},{{{}},{{}}},{{,{}},{},{,{}}},{{{{{}},{,{}}},{{,{}}}},{,{{},}},{}}},{{{},{,{}},{}},{{},{},{{{}},{{},}}},{{{{{,}},{,{}}}},{}}},{{{,},{{{}},},{,}},{{{{}},{{},{}},{{},{,{{}}}}}},{{{{}}},{{{},{}},{},{{}}},{}}}},{{{{{},{{},{{{{},{}}},{,{}},{{{},},{}}},{{}}}},{{,},{,},{{}}},{{{{{{},{{}}},{{}}},{{},{}},{{},{}}},{},{{},{{},{}}}},{{{},},{{{},{{},{{}}}}}},{{}},{{},{{{}},{,{}}},{{{{},},{}},{{},},{}}}},{{{}},{,},{}}}}},{{{{{},},{{}},{,{{},{,{{}}}}}},{{},{},{,{{},}}},{{{{}},},{}}},{{{{}}}},{{{{{{},},}},{{,}},{{{{},{}}}},{}},{{{{{}},{}},{{{},}}}},{{{{{},{{}}}},{{}},{{{{}},{}},{{}},{{},}}}},{{{{},{{},{{}}}},{{}},{{},{{},{{}}}}},{{{,},{{}}},{,},{{,},{},{}}},{{{}}},{{},{{}}}},{{{,},{}}}},{{{{},{}}},{{{{}},{}},{{{},{}}},{,{}}},{{{}}}},{{{{{{,{}}},{},{{}}}},{{{}}}},{{{{,{}},{}},{{}},{{{},{},{{},}},{{,}},{,{,}}},{{,},{{{{,{{{}},{}}}},}},{{}}}},{{{,{}},},{,{}},{{},}},{{{{,},}},{{}}},{{{},}}},{},{{{},{{}}},{{{{}},{}}}},{{{{{}},{}},{,},{{},{}}},{{{{{}},},{{,{}}}},{,}},{{,}},{{{,}},{{},}}}}}},{{{{}},{{{{}},{{{{},}},}},{,{}}},{{},{{{}},},{{,{}},{}}}},{{{{}},{{},}},{{{}},{,{,{}}},{{}}},{{{{{}}},{{}},{{},}}}},{{{{},},{{},}},{{{}},{{}},{{},{}}},{{},{,{{},{}}},{{{{}},{{}},{{}}},{},{{}}}}}}}'"
]
},
"execution_count": 103,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input"
]
},
{
"cell_type": "code",
"execution_count": 104,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10820"
]
},
"execution_count": 104,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def group_value(text):\n",
" depth = 0\n",
" total = 0\n",
" i = 0\n",
" while i < len(text):\n",
" if text[i] == '{':\n",
" depth += 1\n",
" elif text[i] == '}':\n",
" total += depth\n",
" depth -= 1\n",
" i += 1\n",
" return total\n",
"\n",
"# -- part 1 answer\n",
"group_value(input)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"part 1 : 10820."
]
},
{
"cell_type": "code",
"execution_count": 105,
"metadata": {},
"outputs": [],
"source": [
"input = Input(9).readline().rstrip()\n",
"input = re.sub('!.', '', input)\n"
]
},
{
"cell_type": "code",
"execution_count": 106,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{{{{{{<\">},{}},{<},}e{{,i,<}>},{}},{{{\n",
"\"\n",
"('\"',)\n",
"\n",
"e\n",
"\n",
"e\n",
"('e',)\n",
"\n",
"},}e{{,i,<}\n",
"<},}e{{,i,<}>\n",
"},}e{{,i,<}\n",
"('},}e{{,i,<}',)\n",
"\n"
]
}
],
"source": [
"# Testing \"search then replace\" technique.\n",
"\n",
"input = Input(9).readline().rstrip()\n",
"input = re.sub('!.', '', input)\n",
"\n",
"print(input[:60])\n",
"print()\n",
"\n",
"for i in range(3):\n",
" s = re.search('<([^>]*)>', input)\n",
" print(s.groups()[0])\n",
" print(s.group(0))\n",
" print(s.group(1))\n",
" print(s.groups(0))\n",
" print()\n",
" input = re.sub('<[^>]*>', '', input, count=1)\n"
]
},
{
"cell_type": "code",
"execution_count": 107,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5547"
]
},
"execution_count": 107,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input = Input(9).readline().rstrip()\n",
"input = re.sub('!.', '', input)\n",
"\n",
"def count_garbage(text):\n",
" # First try : using regular expressions.\n",
" # Gave the wrong answer (618) on the first attempt; had s.groups(0) which gave group list,\n",
" # when what I wanted was the first match which is s.groups()[0] or s.group(1) \n",
" # since (I guess) s.group(0) is the match ... even though that's not in s.groups().\n",
" # (Hmmm - the python regex stuff is easy to mess up.)\n",
" total = 0\n",
" while True:\n",
" s = re.search('<([^>]*)>', text)\n",
" if s == None:\n",
" break\n",
" total += len(s.groups()[0])\n",
" text = re.sub('<[^>]*>', '', text, count=1)\n",
" return total\n",
"\n",
"## -- part 2\n",
"count_garbage(input)"
]
},
{
"cell_type": "code",
"execution_count": 108,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5547"
]
},
"execution_count": 108,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Alternative approach : explicit counting of chars inside <..>,\n",
"# similar to what I did in part 1.\n",
"\n",
"input = Input(9).readline().rstrip()\n",
"input = re.sub('!.', '', input)\n",
"\n",
"def count_garbage2(text):\n",
" total = 0\n",
" i = 0\n",
" while i < len(text):\n",
" if text[i] == '<':\n",
" i += 1 # now we're in the garbage\n",
" while text[i] != '>':\n",
" total += 1\n",
" i += 1\n",
" else:\n",
" i += 1\n",
" return total\n",
"\n",
"count_garbage2(input)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"part 2 - 5547"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 10](http://adventofcode.com/2017/day/10) : Knot Hash"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6952"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input = [31,2,85,1,80,109,35,63,98,255,0,13,105,254,128,33] # short; pasted in.\n",
"\n",
"knot_length = 256\n",
"#knot_length = 5 # test\n",
"knot = {'list': list(range(knot_length)), 'index': 0, 'skip': 0}\n",
"\n",
"def reverse(alist):\n",
" result = alist.copy()\n",
" result.reverse() # python does this in place. Ugh.\n",
" return result\n",
"\n",
"def twist(number):\n",
" # Reverse number elements starting at index. Wrap at end.\n",
" index = knot['index']\n",
" thelist = knot['list'] + knot['list'] # duplicate to handle wrapping.\n",
" thelist[index: index+number] = reverse(thelist[index: index+number])\n",
" thelist[0:index] = thelist[knot_length : knot_length+index]\n",
" knot['list'] = thelist[:knot_length]\n",
" knot['index'] = (knot['index'] + number + knot['skip']) % knot_length # wrap\n",
" knot['skip'] += 1\n",
"\n",
"# test\n",
"#for n in [3, 4, 1, 5]:\n",
"# twist(n)\n",
"# print(knot)\n",
" \n",
"for n in input:\n",
" twist(n)\n",
"\n",
"# -- part 1\n",
"knot['list'][0] * knot['list'][1]\n",
"\n",
"# Got 272 on first try, which was wrong ... wasn't wrapping index correctly.\n",
"# Correct for part 1 is 6952"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"28e7c4360520718a5dc811d3942cf1fd\n"
]
}
],
"source": [
"input = '31,2,85,1,80,109,35,63,98,255,0,13,105,254,128,33' # it's a string of chars this time.\n",
"\n",
"def knot_hash(chars):\n",
" length = 256\n",
" knotlist = list(range(length))\n",
" index = 0\n",
" skip = 0\n",
" numbers = [ord(i) for i in chars] + [17, 31, 73, 47, 23]\n",
" #print(numbers)\n",
" for i in range(64):\n",
" for number in numbers: \n",
" # 64 times twist(sequence)\n",
" thelist = knotlist + knotlist # duplicate to handle wrapping.\n",
" thelist[index: (index+number)] = reverse(thelist[index: (index+number)])\n",
" thelist[0: index] = thelist[length: (length+index)]\n",
" knotlist = thelist[:length]\n",
" index = (index + number + skip) % length\n",
" skip += 1\n",
" result = ''\n",
" offset = 0\n",
" for i in range(16):\n",
" xorsum = 0\n",
" for j in range(16):\n",
" xorsum = xorsum ^ knotlist[offset]\n",
" offset += 1\n",
" twochar = hex(xorsum)[2:]\n",
" if len(twochar) == 1:\n",
" twochar = '0' + twochar\n",
" result = result + twochar\n",
" return result\n",
"\n",
"# print(knot_hash('1,2,3')) # should be 3efbe78a8d82f29979031a4aa0b16a9d ... check (finally!)\n",
"# print(knot_hash('')) # should be a2582a3a0e66e6e86e3812dcb672a272 ... check (finally!)\n",
"\n",
"# I was getting the wrong answers for quite some time, feeling very stuck.\n",
"# Rewrote the whole thing a couple different ways, lots of printing.\n",
"# Error was that I read the instructions incorrectly : \n",
"# I was doing 64 passes on each number, not 64 passes on the sequence. (Oops.)\n",
"\n",
"# part 2 - correct is 28e7c4360520718a5dc811d3942cf1fd\n",
"\n",
"print(knot_hash(input))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"\n",
"# [Day 11](http://adventofcode.com/2017/day/11) : Hex Ed"
]
},
{
"cell_type": "code",
"execution_count": 113,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['se', 'nw', 'ne', 's', 'sw', 'sw', 'sw', 'sw', 'nw', 'sw']"
]
},
"execution_count": 113,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input = Input(11).readline().rstrip().split(',')\n",
"input[:10]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" \\ n /\n",
" nw +--+ ne\n",
" / \\\n",
" -+ +-\n",
" \\ /\n",
" sw +--+ se\n",
" / s \\\n",
"\n",
"I'll use [cube coords](https://www.redblobgames.com/grids/hexagons/)\n",
"(x,y,z) with the property that x+y+x=0 . \n",
"\n",
"Looks like the number of steps from the origin is max(abs((x,y,z))."
]
},
{
"cell_type": "code",
"execution_count": 115,
"metadata": {},
"outputs": [],
"source": [
"\n",
"# Numpy array from x,y,z\n",
"hexit = lambda x,y,z: np.array([x,y,z])\n",
"\n",
"# directions\n",
"go = {'n' : hexit(0, 1, -1),\n",
" 'ne' : hexit(1, 0, -1),\n",
" 'se' : hexit(1, -1, 0),\n",
" 's' : hexit(0, -1, 1), \n",
" 'sw' : hexit(-1, 0, 1),\n",
" 'nw' : hexit(-1, 1, 0), \n",
" }\n",
"\n",
"# current position\n",
"p = hexit(0,0,0)"
]
},
{
"cell_type": "code",
"execution_count": 116,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([ 326, 458, -784])"
]
},
"execution_count": 116,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"for i in input:\n",
" p = p + go[i]\n",
"p"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"part 1 : the position is 784 steps from the starting position."
]
},
{
"cell_type": "code",
"execution_count": 118,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1558"
]
},
"execution_count": 118,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"steps = lambda position: np.max(np.abs(position))\n",
"\n",
"furthest = 0\n",
"p = hexit(0,0,0)\n",
"\n",
"for i in input:\n",
" p = p + go[i]\n",
" s = steps(p)\n",
" if s > furthest:\n",
" furthest = s\n",
"\n",
"furthest\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"part 2 : the furthest position from the starting spot is 1558 steps away."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"\n",
"# [Day 12](http://adventofcode.com/2017/day/12) : Digital Plumber"
]
},
{
"cell_type": "code",
"execution_count": 250,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2000\n",
"{'308': ('151', '443', '1205'), '320': ('394',), '675': ('1452', '1531'), '211':\n"
]
}
],
"source": [
"input12 = list(map( lambda x: x.rstrip().split(' <-> '), Input(12).readlines()))\n",
"\n",
"forest = dict([(x[0] , tuple(x[1].split(', '))) for x in input12])\n",
"print(len(forest))\n",
"print(str(forest)[:80])\n"
]
},
{
"cell_type": "code",
"execution_count": 251,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('480', '1750')"
]
},
"execution_count": 251,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"forest['0']"
]
},
{
"cell_type": "code",
"execution_count": 252,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"number of nodes in tree is 288\n"
]
}
],
"source": [
"# part 1 : how many nodes are connected to '0' ?\n",
"# Do a tree search.\n",
"\n",
"def treesearch(start, forest):\n",
" seen = {start: True}\n",
" fringe = [n for n in forest[start]]\n",
" while fringe:\n",
" node = fringe.pop()\n",
" if not node in seen:\n",
" seen[node] = True\n",
" for n in forest[node]:\n",
" fringe.append(n)\n",
" return list(seen.keys())\n",
"\n",
"tree = treesearch('0', forest)\n",
"print(\"number of nodes in tree is {}\".format(len(tree)))\n"
]
},
{
"cell_type": "code",
"execution_count": 253,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The number of trees is 211\n"
]
}
],
"source": [
"# part 2 : how many trees are there in the forest?\n",
"# Count how many searches it takes to cover all the nodes.\n",
"\n",
"def counttrees(forest):\n",
" nodes = list(forest.keys())\n",
" total = 0\n",
" seen = {}\n",
" trees = []\n",
" while total < len(forest):\n",
" # Find one that we haven't looked at yet.\n",
" i = 0\n",
" while nodes[i] in seen:\n",
" i += 1\n",
" # Do a search starting there.\n",
" tree = treesearch(nodes[i], forest)\n",
" trees.append(tree) # list of trees\n",
" total += len(tree)\n",
" for n in tree:\n",
" seen[n] = True\n",
" return len(trees)\n",
"\n",
"print(\"The number of trees is {}\".format( counttrees(forest) ))\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"\n",
"# [Day 13](http://adventofcode.com/2017/day/13) : Packet Scanners"
]
},
{
"cell_type": "code",
"execution_count": 123,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"43\n"
]
},
{
"data": {
"text/plain": [
"[['0', '5'],\n",
" ['1', '2'],\n",
" ['2', '3'],\n",
" ['4', '4'],\n",
" ['6', '6'],\n",
" ['8', '4'],\n",
" ['10', '8'],\n",
" ['12', '6'],\n",
" ['14', '6'],\n",
" ['16', '8'],\n",
" ['18', '6'],\n",
" ['20', '9'],\n",
" ['22', '8'],\n",
" ['24', '10'],\n",
" ['26', '8'],\n",
" ['28', '8'],\n",
" ['30', '12'],\n",
" ['32', '8'],\n",
" ['34', '12'],\n",
" ['36', '10'],\n",
" ['38', '12'],\n",
" ['40', '12'],\n",
" ['42', '12'],\n",
" ['44', '12'],\n",
" ['46', '12'],\n",
" ['48', '14'],\n",
" ['50', '12'],\n",
" ['52', '14'],\n",
" ['54', '12'],\n",
" ['56', '14'],\n",
" ['58', '12'],\n",
" ['60', '14'],\n",
" ['62', '14'],\n",
" ['64', '14'],\n",
" ['66', '14'],\n",
" ['68', '14'],\n",
" ['70', '14'],\n",
" ['72', '14'],\n",
" ['76', '14'],\n",
" ['80', '18'],\n",
" ['84', '14'],\n",
" ['90', '18'],\n",
" ['92', '17']]"
]
},
"execution_count": 123,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input = list(map( lambda x: x.rstrip().split(': '), Input(13).readlines()))\n",
"print(len(input))\n",
"input"
]
},
{
"cell_type": "code",
"execution_count": 124,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# (x,y) : x is coordinate, y is range 0:(y-1)\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 125,
"metadata": {},
"outputs": [],
"source": [
"# initialize wall, robots, traveler\n",
"# (x,y) in input means x = column (depth) of robot in wall, y = range (i.e. 0 ... (range-1)\n",
"# wall = np.zeros((20, 101)) # (y, x) i.e. (row, column)\n",
"robots = {}\n",
"state = {'traveler': -1, 'cost': 0}\n",
"for (x,y) in input:\n",
" x=int(x)\n",
" y=int(y)\n",
" # wall[0,x] = 1 # position of a scanner\n",
" robots[x] = {'at': 0, 'depth':y, 'direction':-1} # state for each scanner\n",
"\n",
"def init():\n",
" state['traveler'] = -1\n",
" state['cost'] = 0\n",
" # wall[:,:] = 0\n",
" for (x,y) in input:\n",
" x=int(x)\n",
" y=int(y)\n",
" # wall[0,x] = 1 # position of a scanner\n",
" robots[x] = {'at': 0, 'depth':y, 'direction':-1} # state for each scanner\n",
"\n",
"def tick(verbose=False):\n",
" \"\"\" move everything forward one clock tick \"\"\"\n",
" # move into a new column\n",
" state['traveler'] += 1\n",
" t = state['traveler']\n",
" if verbose:\n",
" print(\"travler at {}\".format(t))\n",
" # did we hit a robot?\n",
" if t in robots.keys():\n",
" r = robots[t]\n",
" if verbose:\n",
" print(\"robot {} at {}\".format(t, r['at'])) \n",
" if r['at'] == 0:\n",
" # yup, we hit something.\n",
" state['cost'] += r['depth'] * t # depth * x\n",
" else:\n",
" if verbose:\n",
" print(\"no robot {}\".format(t))\n",
" if verbose:\n",
" print()\n",
" # update the robots\n",
" for x in robots.keys():\n",
" r = robots[x]\n",
" if (r['at'] == 0) or (r['at'] == (r['depth'] - 1)):\n",
" r['direction'] = r['direction'] * (-1)\n",
" # wall[r['at'], x] = 0\n",
" r['at'] = r['at'] + r['direction']\n",
" # wall[r['at'], x] = 1\n",
"\n",
"def tick_fail():\n",
" \"\"\" move everything forward one clock tick , return True if no hit, Fail if hit\"\"\"\n",
" # move into a new column\n",
" state['traveler'] += 1\n",
" t = state['traveler']\n",
" # did we hit a robot?\n",
" if t in robots.keys():\n",
" r = robots[t]\n",
" if r['at'] == 0:\n",
" return False\n",
" for x in robots.keys():\n",
" r = robots[x]\n",
" if (r['at'] == 0) or (r['at'] == (r['depth'] - 1)):\n",
" r['direction'] = r['direction'] * (-1)\n",
" r['at'] = r['at'] + r['direction']\n",
" return True\n",
" \n",
"def try_delay1(t):\n",
" # delay 0 => traveler starts at -1\n",
" init()\n",
" state['traveler'] = -1 - t\n",
" for i in range(100 + t): # oops : didn't add in +t here at first: BUG!\n",
" tick()\n",
" return state['cost']\n",
"\n",
"def try_delay2(t):\n",
" init()\n",
" state['traveler'] = -1 - t\n",
" i = -1 - t\n",
" while i < 100:\n",
" if tick_fail():\n",
" i = i + 1\n",
" else:\n",
" return False\n",
" return True\n",
"\n",
"def search():\n",
" delay = 0\n",
" while True:\n",
" if try_delay2(delay):\n",
" print(delay)\n",
" else:\n",
" delay += 1"
]
},
{
"cell_type": "code",
"execution_count": 126,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'traveler': 99, 'cost': 1840}\n"
]
}
],
"source": [
"# debug\n",
"# for i in range(5):\n",
"# print(wall[0:10, 0:10])\n",
"# tick()\n",
"\n",
"# part 1\n",
"\n",
"for j in range(100):\n",
" tick()\n",
"\n",
"print(state)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"part 1 : cost is 1840"
]
},
{
"cell_type": "code",
"execution_count": 127,
"metadata": {},
"outputs": [],
"source": [
"# search() # ... this runs for too long."
]
},
{
"cell_type": "code",
"execution_count": 128,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# brute force search is taking too long, even when I quit as soon as I see a collision.\n",
"# I guess I need to be smarter. Shouldn't need to simulate each move, as long as we're \n",
"# just looking for any collision."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Each robot is at 0 at t=0.\n",
"\n",
"After that it will be at 0 again at t=2*(depth-1)*i for i=1,2,3,4,... \n",
"\n",
"If we delay by t, then we reach hit x at time t+x \n",
"\n",
"So we need a t such that \n",
" for each robot at x ,\n",
" (t + x) is not 2*(depth-1)*i for some i,\n",
" in other words, (t+x) is not a multiple of 2*(depth-1).\n",
" \n",
"And we want the smallest t where this works.\n"
]
},
{
"cell_type": "code",
"execution_count": 129,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0, 1, 2, 4, 6, 8, 76, 10, 12, 66, 14, 16, 92, 18, 20, 22, 24, 68, 26, 28, 90, 30, 32, 80, 34, 36, 70, 38, 40, 64, 42, 44, 46, 48, 72, 50, 52, 54, 56, 84, 58, 60, 62]\n"
]
}
],
"source": [
"x = list(robots.keys())\n",
"print(x)"
]
},
{
"cell_type": "code",
"execution_count": 130,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[8, 2, 4, 6, 10, 6, 26, 14, 10, 26, 10, 14, 32, 10, 16, 14, 18, 26, 14, 14, 34, 22, 14, 34, 22, 18, 26, 22, 22, 26, 22, 22, 22, 26, 26, 22, 26, 22, 26, 26, 22, 26, 26]\n"
]
}
],
"source": [
"cycles=list(map(lambda x: 2*(x['depth']-1), robots.values()))\n",
"print(cycles)"
]
},
{
"cell_type": "code",
"execution_count": 131,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"43"
]
},
"execution_count": 131,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(robots.keys())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"I wrote a C program to do the search, with the number lists pasted in.\n",
"It found the correct part 2 answer, 3850260, in 0.04 sec.\n",
"\n",
"(On older hardware, int's wouldn't be able to hold 3.8M without a \"long\" or even \"long long\" \n",
"declaration. But on an x86 machine, \n",
"\n",
" /***********\n",
" * search13.c\n",
" *\n",
" * $ cc search13.c -o search13 # (Apple LLVM clang9 x86_64)\n",
" * $ time ./search13\n",
" * t = 3850260 \n",
" * real 0m0.042s\n",
" * user 0m0.038s\n",
" * sys 0m0.001s\n",
" **********/\n",
" #include \n",
"\n",
" int main(){\n",
"\n",
" /* scanner positions */\n",
" int x[] = {0, 1, 2, 4, 6, 8, 76, 10, 12, 66, 14, 16, 92, 18, 20, 22, \n",
" 24, 68, 26, 28, 90, 30, 32, 80, 34, 36, 70, 38, 40, 64, \n",
" 42, 44, 46, 48, 72, 50, 52, 54, 56, 84, 58, 60, 62};\n",
"\n",
" /* time it takes for that robot to do a cycle, i.e. 2*(depth-1) */\n",
" int cycle[] = {8, 2, 4, 6, 10, 6, 26, 14, 10, 26, 10, 14, 32, 10, 16, \n",
" 14, 18, 26, 14, 14, 34, 22, 14, 34, 22, 18, 26, 22, 22, \n",
" 26, 22, 22, 22, 26, 26, 22, 26, 22, 26, 26, 22, 26, 26};\n",
"\n",
" int N = 43; /* number of robots */\n",
" int t = 0; /* delay before we try running past the scanners */\n",
" int r; /* which robot */\n",
" int OK; /* boolean flag */\n",
" int limit = 100000000; /* maximum delay */\n",
"\n",
" while(1){\n",
" t += 1; /* try the next time delay */\n",
" OK = 1;\n",
" for (r=0; r limit){\n",
" printf(\" Oops: hit limit of %i \\n\", limit);\n",
" return 0;\n",
" }\n",
" }\n",
"\n",
" return 0;\n",
" }\n"
]
},
{
"cell_type": "code",
"execution_count": 132,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import time"
]
},
{
"cell_type": "code",
"execution_count": 133,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"t = 3850260\n",
"elapsed time is 3.315701961517334\n"
]
}
],
"source": [
"# Same here in the jupyter notebook ...\n",
"start = time.time()\n",
"\n",
"N = 43\n",
"t = 0\n",
"while(True):\n",
" t += 1\n",
" OK = True\n",
" for r in range(N):\n",
" if (t+x[r]) % cycles[r] == 0:\n",
" OK = False\n",
" break\n",
" if OK:\n",
" print(\"t = {}\".format(t))\n",
" break\n",
"\n",
"print(\"elapsed time is {}\".format(time.time() - start))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So doing it using the division algorithm rather than trying to simulate the scanner is still fast enought, though about 100 times slower than the C code."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"\n",
"# [Day 14](http://adventofcode.com/2017/day/14) : Disk Defragmentation"
]
},
{
"cell_type": "code",
"execution_count": 171,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"input = 'hfdlxzhv'\n",
"\n",
"def hashn(n, inputstring):\n",
" \"\"\" hash for row 0 <= n < 128 of the 128x128 grid \"\"\"\n",
" return knot_hash(inputstring + \"-\" + str(n))"
]
},
{
"cell_type": "code",
"execution_count": 172,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'cfa5c87a53bb95ebfe061138b9fa4995'"
]
},
"execution_count": 172,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a14 = hashn(0, input) # knot_hash of \"hfdlxzhv-0\"\n",
"a14"
]
},
{
"cell_type": "code",
"execution_count": 173,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"276010990282806422253464287164510128533"
]
},
"execution_count": 173,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"b14 = eval('0x' + a14) # integer of that hex number\n",
"b14"
]
},
{
"cell_type": "code",
"execution_count": 165,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'11001111101001011100100001111010010100111011101110010101111010111111111000000110000100010011100010111001111110100100100110010101'"
]
},
"execution_count": 165,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"c14 = format(b14, '0128b') # converted to bitstring of 128 0's and 1's\n",
"c14"
]
},
{
"cell_type": "code",
"execution_count": 170,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Counter({'0': 58, '1': 70})"
]
},
"execution_count": 170,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Counter(c14)"
]
},
{
"cell_type": "code",
"execution_count": 174,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"8230"
]
},
"execution_count": 174,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def count_ones(inputstring):\n",
" total = 0\n",
" for row in range(128):\n",
" kh = hashn(row, inputstring) # i.e. 'cfa587...'\n",
" bitstring = format(eval('0x'+kh), '0128b') # i.e. '11001111...'\n",
" total += Counter(bitstring)['1']\n",
" return total\n",
"\n",
"count_ones(input)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So the answer to part 1 is 8230."
]
},
{
"cell_type": "code",
"execution_count": 241,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[1, 1, 0, ..., 1, 0, 1],\n",
" [0, 1, 0, ..., 0, 1, 0],\n",
" [1, 1, 0, ..., 1, 0, 0],\n",
" ..., \n",
" [1, 1, 0, ..., 0, 0, 0],\n",
" [1, 0, 1, ..., 1, 1, 0],\n",
" [0, 0, 0, ..., 0, 0, 0]])"
]
},
"execution_count": 241,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def tonumbers(s):\n",
" \"\"\" i.e. '11000' => [1, 1, 0, 0, 0] \"\"\"\n",
" return list(map(lambda i: int(i), list(s)))\n",
"\n",
"\n",
"def make_disk(inputstring):\n",
" \"\"\" return numpy 128x128 array\"\"\"\n",
" disk = np.zeros((128, 128), dtype=int)\n",
" for row in range(128):\n",
" kh = hashn(row, inputstring) # i.e. 'cfa587...'\n",
" bitstring = format(eval('0x'+kh), '0128b') # i.e. '11001111...'\n",
" disk[row, :] = tonumbers(bitstring)\n",
" return disk\n",
"\n",
"disk = make_disk(input)\n",
"disk\n"
]
},
{
"cell_type": "code",
"execution_count": 242,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Counter({0: 8154, 1: 8230})"
]
},
"execution_count": 242,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Check that this is consistent with what we had before.\n",
"# There should be 8230 1's\n",
"Counter(list(np.reshape(disk, (128*128,))))"
]
},
{
"cell_type": "code",
"execution_count": 255,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# And now we want to count the number of regions of contiguous ones.\n",
"#\n",
"# This is the same problem as in Day 12 - counting the number of trees in a forest - \n",
"# once we turn the disk into a graph of points and their neighbors.\n",
"\n",
"# I had to rewrite the functions for day 12 to make them more self contained ...\n",
"# which took a bit more debugging than I'd like to admit.\n",
"# That old global variable trap ...\n",
"\n",
"graph = {}\n",
"for row in range(128):\n",
" for col in range(128):\n",
" point = (row, col)\n",
" if disk[point] == 1:\n",
" graph[point] = []\n",
" for p in neighbors4(point):\n",
" if 0 <= p[0] < 128 and 0 <= p[1] < 128:\n",
" if disk[p] == 1:\n",
" if not p in graph[point]:\n",
" graph[point].append(p)\n"
]
},
{
"cell_type": "code",
"execution_count": 244,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'{(50, 96): [(49, 96), (50, 95)], (116, 84): [(117, 84), (115, 84), (116, 83)], (53, 53): [(54, 53)], (74, 106): [(73, 106)], (114, 5): [(115, 5), (113, 5), (114, 6), (114, 4)], (80, 125): [(81, 125), '"
]
},
"execution_count": 244,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"str(graph)[:200]"
]
},
{
"cell_type": "code",
"execution_count": 254,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1103"
]
},
"execution_count": 254,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"counttrees(graph)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The answer to part 2 is 1103.\n",
"\n",
"This one reused pieces from both day 10 & 12.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"\n",
"# [Day 15](http://adventofcode.com/2017/day/15) : Dueling Generators"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"start_numbers = {'a' : 873, 'b': 583}"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import time"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def count_matches(start, iterations):\n",
" start_time = time.time()\n",
" i = 0\n",
" count = 0\n",
" a = start['a']\n",
" b = start['b']\n",
" sixteenbits = 2**16 - 1\n",
" while i < iterations:\n",
" i += 1\n",
" a = (a * 16807) % 2147483647\n",
" b = (b * 48271) % 2147483647\n",
" if (a & sixteenbits) == (b & sixteenbits):\n",
" count += 1\n",
" print(\" elapsed time is {}\".format(time.time() - start_time))\n",
" return count\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" elapsed time is 38.15414905548096\n"
]
},
{
"data": {
"text/plain": [
"631"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"count_matches(start_numbers, 40000000)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So the answer to part 1 is 631"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" elapsed time is 28.756922006607056\n"
]
},
{
"data": {
"text/plain": [
"279"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Need to recode part 1 so that the \"next number\" functions of a, b are independent.\n",
"# Could do with python generators, or just explicitly as I do here.\n",
"\n",
"def count_matches2(start, iterations):\n",
" start_time = time.time()\n",
" i = 0\n",
" count = 0\n",
" a = start['a']\n",
" b = start['b']\n",
" sixteenbits = 2**16 - 1\n",
" while i < iterations:\n",
" i += 1\n",
" \n",
" while True:\n",
" a = (a * 16807) % 2147483647\n",
" if a % 4 == 0:\n",
" break\n",
" \n",
" while True:\n",
" b = (b * 48271) % 2147483647\n",
" if b % 8 == 0:\n",
" break\n",
"\n",
" if (a & sixteenbits) == (b & sixteenbits):\n",
" count += 1\n",
" \n",
" print(\" elapsed time is {}\".format(time.time() - start_time))\n",
" return count\n",
"\n",
"count_matches2(start_numbers, 5000000)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And the answer to part 2 is 279.\n",
"\n",
"Both the \"int\" and \"uint\" C formats in my x86 mac cc compiler have INT_MAX = 2147483647 ,\n",
"which I expect is why it didn't behave as expected.\n",
"\n",
"But there is an __int128 format which works, and runs in about a second.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 16](http://adventofcode.com/2017/day/16) : Permutation Promenade"
]
},
{
"cell_type": "code",
"execution_count": 96,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['x12/14', 's11', 'x10/4', 's7', 'pb/o', 'x12/7', 's5', 'x3/10', 's10', 'x6/4']\n"
]
},
{
"data": {
"text/plain": [
"10000"
]
},
"execution_count": 96,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input16 = Input(16).readline().rstrip().split(',')\n",
"print(input16[:10])\n",
"len(input16)"
]
},
{
"cell_type": "code",
"execution_count": 97,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'namdgkbhifpceloj'"
]
},
"execution_count": 97,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"\n",
"def step16(instruction, dancers):\n",
" if instruction[0] == 'x':\n",
" locations = instruction[1:].split('/')\n",
" (i, j) = (int(locations[0]), int(locations[1]))\n",
" (dancers[i], dancers[j]) = (dancers[j], dancers[i])\n",
" elif instruction[0] == 'p':\n",
" (swap1, swap2) = (instruction[1], instruction[3])\n",
" for i in range(len(dancers)):\n",
" if dancers[i] == swap1:\n",
" dancers[i] = swap2\n",
" elif dancers[i] == swap2:\n",
" dancers[i] = swap1\n",
" elif instruction[0] == 's':\n",
" shift = len(dancers) - int(instruction[1:])\n",
" dancers = dancers[shift:] + dancers[:shift]\n",
" else:\n",
" print(\"Oops - instruction is '{}'\", instruction)\n",
" return dancers\n",
"\n",
"#step16('s1', ['a', 'b', 'c', 'd', 'e']) # 'eabcd'\n",
"#step16('x3/4', ['e', 'a', 'b', 'c', 'd']) # 'eabdc'\n",
"# step16('pe/b', ['e', 'a', 'b', 'd', 'c']) # 'baedc'\n",
"\n",
"def dance(instructions, dancers):\n",
" # list(map(lambda c: chr(c+ord('a')), range(16))) # ['a', 'b', ... , 'p']\n",
" for ins in instructions:\n",
" dancers = step16(ins, dancers)\n",
" return dancers\n",
"\n",
"dancers = list(map(lambda c: chr(c+ord('a')), range(16)))\n",
"''.join(dance(input16, dancers)) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So the part1 sanswer is namdgkbhifpceloj ."
]
},
{
"cell_type": "code",
"execution_count": 98,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# Repat that 1e9 times rather than 1 times.\n",
"\n",
"# Brute force is going to be too slow here.\n",
"# Instead, we break that permutation down into its disjoint cycles.\n",
"#\n",
"# a b c d e f g h i j k l m n o p\n",
"# n a m d g k b h i f p c e l o j\n",
"#\n",
"# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16\n",
"# 14 1 13 4 7 11 2 8 9 6 16 3 5 12 15 10\n",
"#\n",
"# GAP will do this for is, or by hand, or write code to trace \n",
"# where each one goes, where that goes, etc. \n",
"# I will use \"X -> Y\" to mean \"X goes to where Y started\".\n",
"# Then the cycles are\n",
"#\n",
"# a -> b -> g -> e -> m -> c -> l -> n -> a length 8\n",
"# o -> o length 1\n",
"# d -> d length 1\n",
"# h -> h length 1\n",
"# i -> i length 1\n",
"# f -> j -> p -> k -> f length 4\n",
"\n",
"# Then we need to do some mod arithmetic to see \n",
"# how many times these cycles are done in 1e9 permutations\n"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"1000000000 % 8"
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 74,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"1000000000 % 4"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# So after a billion repitions, everything returns to its original position."
]
},
{
"cell_type": "code",
"execution_count": 77,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"16\n"
]
},
{
"data": {
"text/plain": [
"'abcdefghijklmnop'"
]
},
"execution_count": 77,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"part2_16 = ''.join(list(map(lambda c: chr(c+ord('a')), range(16))))\n",
"print(len(part2_16))\n",
"part2_16\n"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# ... but the adventofcode says that's not the right answer ... even though it does say that namdgkbhifpceloj is correct."
]
},
{
"cell_type": "code",
"execution_count": 91,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[14, 1, 13, 4, 7, 11, 2, 8, 9, 6, 16, 3, 5, 12, 15, 10]"
]
},
"execution_count": 91,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# I want to look at this permuation as a rearragnment of digits :\n",
"list(map(lambda c: ord(c) - ord('a') + 1, 'namdgkbhifpceloj'))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"I'm trying this with the gap algebra program, and it's giving me this answer too.\n",
"\n",
" $ gap\n",
" gap> list16 := [14, 1, 13, 4, 7, 11, 2, 8, 9, 6, 16, 3, 5, 12, 15, 10];\n",
" gap> perm16 := PermList(list16);\n",
" gap> a;\n",
" (1,14,12,3,13,5,7,2)(6,11,16,10)\n",
" gap> Order(a);\n",
" 8\n",
" gap> ListPerm(a);\n",
" [ 14, 1, 13, 4, 7, 11, 2, 8, 9, 6, 16, 3, 5, 12, 15, 10 ]\n",
" gap> a^8;\n",
" ()\n",
" gap a^1000000000;\n",
" ()\n",
"\n",
"So doing this permutation a billion times is the identity,\n",
"which means that the end result is the same as the start.\n",
"\n",
"But adventofcode doesn't agree ... and I have no idea why."
]
},
{
"cell_type": "code",
"execution_count": 104,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'aekmnjpcfodghlib'"
]
},
"execution_count": 104,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Here's running the program (that gave the correct answer for part 1) eight times.\n",
"\n",
"original16 = list(map(lambda c: chr(c+ord('a')), range(16)))\n",
"\n",
"def doit16(n):\n",
" dancers = list(map(lambda c: chr(c+ord('a')), range(16)))\n",
" for i in range(n):\n",
" dancers = dance(input16, dancers)\n",
" return dancers\n",
"\n",
"''.join(doit16(8))\n"
]
},
{
"cell_type": "code",
"execution_count": 88,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# Hmmm. I guess I'm analyzing the permutation incorrectly"
]
},
{
"cell_type": "code",
"execution_count": 112,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 abcdefghijklmnop\n",
"1 namdgkbhifpceloj\n",
"2 jlfmgkchaionepdb\n",
"3 aofblkcedinhmjpg\n",
"4 ihmbefcndojpalkg\n",
"5 iklmepbcdfojagnh\n",
"6 kcloednpafihmgjb\n",
"7 admolnejpfighckb\n",
"8 aekmnjpcfodghlib\n",
"9 afkcbdjgnpoemlih\n"
]
}
],
"source": [
"for i in range(10):\n",
" print(i, \" \", ''.join(doit16(i)))"
]
},
{
"cell_type": "code",
"execution_count": 110,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# Ah - the light dawns. The instructions are *not* pure permuations, \n",
"# since some of them are \"swap letter X with letter Y\" which will do\n",
"# different things for different starting sequences. \n",
"#\n",
"# So I do need to find the cycle length, but that does need to be done\n",
"# by brute force.\n"
]
},
{
"cell_type": "code",
"execution_count": 114,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" loop at i = 60\n"
]
}
],
"source": [
"i = 0\n",
"dancers = list(map(lambda c: chr(c+ord('a')), range(16)))\n",
"original16 = list(map(lambda c: chr(c+ord('a')), range(16)))\n",
"while True:\n",
" dancers = dance(input16, dancers)\n",
" i += 1\n",
" if str(dancers) == str(original16):\n",
" print(\" loop at i = {}\".format(i))\n",
" break\n",
" \n",
" "
]
},
{
"cell_type": "code",
"execution_count": 115,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"40"
]
},
"execution_count": 115,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"1000000000 % 60"
]
},
{
"cell_type": "code",
"execution_count": 117,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'ibmchklnofjpdeag'"
]
},
"execution_count": 117,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# So the answer is that the billionth iteration is the same as the 40th iteration.\n",
"''.join(doit16(40))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The answer to part 2 is ibmchklnofjpdeag ."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Day 17](http://adventofcode.com/2017/day/17) : Spinlock"
]
},
{
"cell_type": "code",
"execution_count": 118,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"input17 = 376"
]
},
{
"cell_type": "code",
"execution_count": 133,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 [0]\n",
"1 [0, 1]\n",
"1 [0, 2, 1]\n",
"2 [0, 2, 3, 1]\n",
"2 [0, 2, 4, 3, 1]\n",
"1 [0, 5, 2, 4, 3, 1]\n",
"5 [0, 5, 2, 4, 3, 6, 1]\n",
"2 [0, 5, 7, 2, 4, 3, 6, 1]\n",
"6 [0, 5, 7, 2, 4, 3, 8, 6, 1]\n",
"1 [0, 9, 5, 7, 2, 4, 3, 8, 6, 1]\n",
"[1512, 1134, 151, 2017, 638, 1513, 851]\n"
]
}
],
"source": [
"buffer17 = [0]\n",
"\n",
"def step17(index, buffer, stepsize=input17):\n",
" lastvalue = buffer[index]\n",
" newindex = (index + stepsize) % len(buffer) + 1\n",
" buffer.insert(newindex, lastvalue+1)\n",
" return (newindex, buffer)\n",
"\n",
"# Here's the test case that they give.\n",
"(index, buffer) = (0, [0])\n",
"for i in range(10):\n",
" print(index, buffer)\n",
" (index, buffer) = step17(index, buffer, stepsize=3)\n",
"for i in range(2017 - 10):\n",
" (index, buffer) = step17(index, buffer, stepsize=3)\n",
"index2017 = buffer.index(2017)\n",
"print(buffer[index2017-3:index2017+4])\n"
]
},
{
"cell_type": "code",
"execution_count": 135,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1605, 1267, 1657, 2017, 777, 729, 58]\n"
]
}
],
"source": [
"# part 1\n",
"(index, buffer) = (0, [0])\n",
"for i in range(2017):\n",
" (index, buffer) = step17(index, buffer)\n",
"index2017 = buffer.index(2017)\n",
"print(buffer[index2017-3:index2017+4])"
]
},
{
"cell_type": "code",
"execution_count": 142,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 1 [0]\n",
"1 2 [0, 1]\n",
"2 3 [0, 1, 2]\n",
"1 4 [0, 3, 1, 2]\n",
"2 5 [0, 3, 4, 1, 2]\n",
"4 6 [0, 3, 4, 1, 5, 2]\n",
"3 7 [0, 3, 4, 6, 1, 5, 2]\n",
"2 8 [0, 3, 7, 4, 6, 1, 5, 2]\n",
"3 9 [0, 3, 7, 8, 4, 6, 1, 5, 2]\n",
"2 10 [0, 3, 9, 7, 8, 4, 6, 1, 5, 2]\n",
"9 11 [0, 3, 9, 7, 8, 4, 6, 1, 5, 10]\n",
"1 12 [0, 11, 3, 9, 7, 8, 4, 6, 1, 5]\n",
"6 13 [0, 11, 3, 9, 7, 8, 12, 4, 6, 1]\n",
"6 14 [0, 11, 3, 9, 7, 8, 13, 12, 4, 6]\n",
"5 15 [0, 11, 3, 9, 7, 14, 8, 13, 12, 4]\n",
"7 16 [0, 11, 3, 9, 7, 14, 8, 15, 13, 12]\n"
]
}
],
"source": [
"# part 2\n",
"# hmmm. 50 million inserts ... brute force sounds doubtful.\n",
"# part 1\n",
"(index, buffer) = (0, [0])\n",
"for i in range(16):\n",
" print(index, len(buffer), buffer[:10])\n",
" (index, buffer) = step17(index, buffer)\n",
"\n",
"# Got up to 1431198 ... maybe it would have finished if I'd waited."
]
},
{
"cell_type": "code",
"execution_count": 148,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 1\n",
" new value after 0 = 1\n",
"1 2\n",
"2 3\n",
" new value after 0 = 3\n",
"1 4\n",
"2 5\n",
"4 6\n",
"3 7\n",
"2 8\n",
"3 9\n",
"2 10\n",
"9 11\n",
" new value after 0 = 11\n",
"1 12\n",
"6 13\n",
"6 14\n",
"5 15\n",
"7 16\n"
]
}
],
"source": [
"# Since we only need the number after 0, we only need to look at the insertions after 0.\n",
"# We can keep track of which number is to be inserted, and where it is to be inserted\n",
"# without using the list - just a bit of arithmetic.\n",
"\n",
"# Here's the check, to see if I can replicate the numbers above.\n",
"\n",
"(index, lastvalue) = (0, 0) # length of buffer is (lastvalue+1)\n",
"stepsize = input17\n",
"for i in range(16):\n",
" print(index, lastvalue+1)\n",
" newindex = (index + stepsize) % (lastvalue + 1) + 1\n",
" (index, lastvalue) = (newindex, lastvalue + 1)\n",
" if index == 1:\n",
" print(\" new value after 0 = {}\".format(lastvalue))\n"
]
},
{
"cell_type": "code",
"execution_count": 149,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"39289581"
]
},
"execution_count": 149,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# That should be something that can be done to 50000000\n",
"\n",
"(index, lastvalue) = (0, 0) # length of buffer is (lastvalue+1)\n",
"afterone = 0\n",
"stepsize = input17\n",
"for i in range(50000000):\n",
" #print(index, lastvalue+1)\n",
" newindex = (index + stepsize) % (lastvalue + 1) + 1\n",
" (index, lastvalue) = (newindex, lastvalue + 1)\n",
" if index == 1:\n",
" afterone = lastvalue\n",
" #print(\" new value after 0 = {}\".format(lastvalue))\n",
"\n",
"afterone"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And we have the answer to part 2 : 39289581 ."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 18](http://adventofcode.com/2017/day/18) : Duet"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['set i 31',\n",
" 'set a 1',\n",
" 'mul p 17',\n",
" 'jgz p p',\n",
" 'mul a 2',\n",
" 'add i -1',\n",
" 'jgz i -2',\n",
" 'add a -1',\n",
" 'set i 127',\n",
" 'set p 464',\n",
" 'mul p 8505',\n",
" 'mod p a',\n",
" 'mul p 129749',\n",
" 'add p 12345',\n",
" 'mod p a',\n",
" 'set b p',\n",
" 'mod b 10000',\n",
" 'snd b',\n",
" 'add i -1',\n",
" 'jgz i -9',\n",
" 'jgz a 3',\n",
" 'rcv b',\n",
" 'jgz b -1',\n",
" 'set f 0',\n",
" 'set i 126',\n",
" 'rcv a',\n",
" 'rcv b',\n",
" 'set p a',\n",
" 'mul p -1',\n",
" 'add p b',\n",
" 'jgz p 4',\n",
" 'snd a',\n",
" 'set a b',\n",
" 'jgz 1 3',\n",
" 'snd b',\n",
" 'set f 1',\n",
" 'add i -1',\n",
" 'jgz i -11',\n",
" 'snd a',\n",
" 'jgz f -16',\n",
" 'jgz a -19']"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input18 = list(map( lambda x: x.rstrip(), Input(18).readlines()))\n",
"input18"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import string"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" first rcv is 1187\n"
]
},
{
"data": {
"text/plain": [
"{'_index_': 26,\n",
" '_sound_': 1187,\n",
" 'a': 1187,\n",
" 'b': 1187,\n",
" 'f': 0,\n",
" 'i': 126,\n",
" 'p': 1041971187}"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"\n",
"def get18(s, state):\n",
" \"\"\" Return the value of register s given a machine state. \"\"\"\n",
" # Registers that have never been accessed before are initialized to zero.\n",
" if s in string.ascii_lowercase:\n",
" if not s in state:\n",
" state[s] = 0\n",
" return state[s]\n",
" else:\n",
" return int(s)\n",
"\n",
"def run18(code, state={}):\n",
" # Execute the given lines of code. Return the final machine state.\n",
" state['_index_'] = 0\n",
" while True:\n",
" line = code[state['_index_']] # e.g. \"mul p -1\"\n",
" \n",
" state['_index_'] += 1 # Increment instruction index.\n",
" \n",
" what = line[:3] # e.g. \"mul\"\n",
" first = line[4] # e.g. \"p\"\n",
" rest = line[6:] # e.g. \"-1\"\n",
" \n",
" if what == 'snd':\n",
" state['_sound_'] = get18(first, state)\n",
" elif what == 'set':\n",
" state[first] = get18(rest, state)\n",
" elif what == 'add':\n",
" state[first] = get18(first, state) + get18(rest, state)\n",
" elif what == 'mul':\n",
" state[first] = get18(first, state) * get18(rest, state)\n",
" elif what == 'mod':\n",
" state[first] = get18(first, state) % get18(rest, state)\n",
" elif what == 'rcv':\n",
" if first in state:\n",
" if state[first] != 0:\n",
" state[first] = state['_sound_']\n",
" print(\" first rcv is {}\".format(state['_sound_']))\n",
" return state\n",
" elif what == 'jgz':\n",
" if get18(first, state) > 0:\n",
" state['_index_'] += get18(rest, state) - 1\n",
" else:\n",
" print(\"ERROR : line is {}\".format(line))\n",
" \n",
" if state['_index_'] < 0 or state['_index_'] >= len(code):\n",
" print(\"DONE\")\n",
" return state\n",
"\n",
"run18(input18)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"part 1 answer is 1187 ; in 33 min, about 450 on the leaderboard."
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"5969\n"
]
}
],
"source": [
"\n",
"# Now I need two machines, which read and write to each other asynchronously.\n",
"\n",
"# I'm sure there are elegant ways to do this ... but I'm just going to be super explicit.\n",
"\n",
"def init_state(which):\n",
" return { '_index_' : 0, # which line of code is next to run.\n",
" '_snd_' : [], # write_to_other_process buffer\n",
" '_snd_count_' : 0, # number of snd instructions\n",
" '_rcv_' : [], # read_from_other_process buffer\n",
" '_running_' : True, # i.e. index not out of bounds\n",
" '_want_rcv_': False, # True means suspended, waiting for input.\n",
" 'p' : which # which machine i.e. 0 or 1\n",
" }\n",
"\n",
"def not_runnable(state):\n",
" \"\"\" Return True if the machine cannot be run from this state. \"\"\"\n",
" # Can't run if either\n",
" # i) stopped because index is outside of code bounds, or\n",
" # ii) want to read data but is nothing available to read.\n",
" return not state['_running_'] or (state['_want_rcv_'] and not state['_rcv_'])\n",
"\n",
"def run18b(code, state):\n",
" \"\"\" Run this machine for as long as possible. Return its state.\"\"\"\n",
" # The snd commands write (push) to a state['_snd_'] list.\n",
" # The rcv commands read (pop) from a state['_rcv_'] list until its empty.\n",
" if not_runnable(state):\n",
" return state\n",
" while True:\n",
" line = code[state['_index_']] # e.g. \"mul p -1\"\n",
" state['_index_'] += 1\n",
" what = line[:3] # e.g. \"mul\"\n",
" first = line[4] # e.g. \"p\"\n",
" rest = line[6:] # e.g. \"-1\"\n",
" if what == 'snd':\n",
" state['_snd_'].append( get18(first, state) ) # on right end of 'send' list. Keep going.\n",
" state['_snd_count_'] += 1 # count number of times 'snd\" happens.\n",
" elif what == 'set':\n",
" state[first] = get18(rest, state)\n",
" elif what == 'add':\n",
" state[first] = get18(first, state) + get18(rest, state)\n",
" elif what == 'mul':\n",
" state[first] = get18(first, state) * get18(rest, state)\n",
" elif what == 'mod':\n",
" state[first] = get18(first, state) % get18(rest, state)\n",
" elif what == 'rcv':\n",
" if state['_rcv_']: # do we have a number to read?\n",
" state[first] = state['_rcv_'].pop(0) # yes! read from left & continue,\n",
" state['_want_rcv_'] = False # and reset the \"need data\" flag.\n",
" else:\n",
" state['_want_rcv_'] = True # Set \"I want input!\" flag.\n",
" state['_index_'] -= 1 # Do this line again later,\n",
" return state # but for now, suspend.\n",
" elif what == 'jgz':\n",
" if get18(first, state) > 0:\n",
" state['_index_'] += get18(rest, state) - 1\n",
" else:\n",
" print(\"ERROR : line is {}\".format(line))\n",
" if state['_index_'] < 0 or state['_index_'] >= len(code):\n",
" state['_running_'] = False\n",
" return state\n",
"\n",
"def run_both(code):\n",
" \"\"\" Run two machines, alternating, until both are not runnable. Return their states.\"\"\"\n",
" states = [init_state(0), init_state(1)]\n",
" i = 0\n",
" while True:\n",
" other = (i + 1) % 2 # other machine index\n",
"\n",
" if not_runnable(states[i]) and not_runnable(states[other]):\n",
" return states\n",
" \n",
" # run mahine i.\n",
" states[i] = run18b(code, states[i])\n",
" \n",
" # transfer machine i's snd data to other's rcv buffer.\n",
" sent = states[i]['_snd_'] # This was sent.\n",
" states[i]['_snd_'] = [] # Clear that buffer.\n",
" states[other]['_rcv_'] += sent # Append sent data to readable data in other.\n",
"\n",
" # switch to the other machine\n",
" i = other\n",
" \n",
"\n",
"states = run_both(input18)\n",
"\n",
"# And now that we're stopped, dispay the value that the problem asks for.\n",
"print(states[1]['_snd_count_'])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And the answer to part 2 is 5969. (Which just happens to be part of my phone number. Go figure)\n",
"\n",
"Did the whole thing in about 90min, which put me at 416 on the leaderboard.\n",
"\n",
"For this problem, both part 1 & part 2 gave the correct answer the first time it ran without errors ... though particularly for part 2, there were a lot of \"key index\" errors while I was working out inconsistent or mistyped stuff.\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 19](http://adventofcode.com/2017/day/19) : A Series of Tubes"
]
},
{
"cell_type": "code",
"execution_count": 124,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"----|-|-----------|-------|---\n",
" | | | | | | \n",
"----|-------------|-------|---\n",
" | | | | | | \n",
" | | | | | +-+ \n",
" | | | | | | \n",
" | | | | | | \n",
" | | | | | | \n",
"+---|-+ | +---|-|-----\n",
"| | | | | \n"
]
}
],
"source": [
"input19 = list(map(lambda x: x.rstrip(), Input(19).readlines()))\n",
"\n",
"maxwidth = max([len(s) for s in input19])\n",
"\n",
"# Add one extra space around the whole thing,\n",
"# and fill each line with spaces out to maxwidth.\n",
"padded = [' '*(maxwidth+2)] + \\\n",
" [' ' + input19[i] + ' '*(maxwidth + 1 - len(input19[i])) for i in range(height) ] + \\\n",
" [' '*(maxwidth+2)]\n",
"\n",
"# Here's a sample :\n",
"for row in range(20, 30):\n",
" print(padded[row][20:50])\n",
"\n",
"# Check to make sure that all the rows are the same length\n",
"assert min([len(p) for p in padded]), max([len(p) for p in padded])"
]
},
{
"cell_type": "code",
"execution_count": 125,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'ABCDEFGHIJKLMNOPQRSTUVWXYZ'"
]
},
"execution_count": 125,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import string\n",
"string.ascii_uppercase"
]
},
{
"cell_type": "code",
"execution_count": 130,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"PVBSCMEQHY\n",
"17736\n"
]
}
],
"source": [
"# I'll use a (row, column) coord system, with (0,0) at the top left.\n",
"\n",
"# The movement directions are\n",
"(up, down, left, right) = (Point(-1,0), Point(1,0), Point(0,-1), Point(0,1))\n",
"\n",
"# The initial state of my finger as I trace through the maze is :\n",
"def init_state():\n",
" return {'at': Point(1, padded[1].index('|')), \n",
" 'direction': down, \n",
" 'letters': [], \n",
" 'going': True,\n",
" 'steps': 0\n",
" }\n",
"\n",
"def char19(p):\n",
" \"\"\" Return the printable character at given position in the maze \"\"\"\n",
" # char19(start_position) is '|'\n",
" row = p[0]\n",
" col = p[1]\n",
" return padded[row][col]\n",
"\n",
"def move19(s):\n",
" \"\"\" Look at direction we're going and the character we're standing on, and change state accordingly. \"\"\"\n",
" what = char19(s['at'])\n",
" s['steps'] += 1\n",
" if what in string.ascii_uppercase: # letter - remember it.\n",
" s['letters'].append(what) \n",
" elif what == '+': # turning :\n",
" if str(s['direction']) in (str(right), str(left)): # moving left or right ...\n",
" if char19(s['at'] + up) == ' ': # space above plus ?\n",
" s['direction'] = down\n",
" else:\n",
" s['direction'] = up\n",
" else: # moving up or down ...\n",
" if char19(s['at'] + right) == ' ': # space to right of plus ?\n",
" s['direction'] = left \n",
" else:\n",
" s['direction'] = right\n",
" elif what == ' ': # no symbol, so stop.\n",
" s['steps'] -= 1 # don't count this as a step.\n",
" s['going'] = False\n",
" return s\n",
" s['at'] += s['direction'] # move\n",
" return s # return new state\n",
" \n",
"\n",
"def run19():\n",
" \"\"\" Run through the whole maze.\"\"\"\n",
" state = init_state()\n",
" while state['going']:\n",
" state = move19(state)\n",
" print(''.join(state['letters']))\n",
" print(state['steps'])\n",
"\n",
"run19()\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The answer to part 1 is PVBSCMEQHY , and the answer to part 2 is 17736 .\n",
"\n",
"I did this one the day after it was posted ... took about 90min."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 20](http://adventofcode.com/2017/day/20) : Particle Swarm"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"number of particles = 1000\n",
"\n",
"-- first 10 input lines --\n",
"p=<-833,-499,-1391>, v=<84,17,61>, a=<-4,1,1>\n",
"p=<-168,3586,-2721>, v=<-61,-58,61>, a=<7,-13,8>\n",
"p=<364,223,1877>, v=<31,-11,-71>, a=<-5,0,-3>\n",
"p=<769,-854,-8705>, v=<-20,4,64>, a=<0,1,9>\n",
"p=<6985,-3666,3653>, v=<-112,99,-23>, a=<-4,0,-4>\n",
"p=<7688,-2445,1026>, v=<-55,66,-142>, a=<-8,0,6>\n",
"p=<7281,-151,-5042>, v=<-177,99,41>, a=<-1,-5,5>\n",
"p=<-2191,71,1322>, v=<174,17,-93>, a=<-6,-1,3>\n",
"p=<1509,2624,-5338>, v=<-40,5,-8>, a=<0,-4,8>\n",
"p=<1213,5658,175>, v=<120,-39,-119>, a=<-8,-6,6>\n",
"\n",
"-- first 10 accelerations --\n",
"[-4, 1, 1]\n",
"[7, -13, 8]\n",
"[-5, 0, -3]\n",
"[0, 1, 9]\n",
"[-4, 0, -4]\n",
"[-8, 0, 6]\n",
"[-1, -5, 5]\n",
"[-6, -1, 3]\n",
"[0, -4, 8]\n",
"[-8, -6, 6]\n"
]
}
],
"source": [
"input20 = list(map(lambda x: x.rstrip(), Input(20).readlines()))\n",
"print(\"number of particles = \", len(input20))\n",
"N20 = len(input20) # number of particles\n",
"print()\n",
"\n",
"print(\"-- first 10 input lines --\")\n",
"for line in input20[:10]:\n",
" print(line)\n",
"\n",
"def manhattan(p):\n",
" return abs(p[0]) + abs(p[1]) + abs(p[2])\n",
" \n",
"def initstate20():\n",
" state = {'p':[], 'v':[], 'a':[]} # position, velocity, acceleration\n",
" pattern = re.compile(r'.+<(.+)>.+<(.+)>.+<(.+)>')\n",
" index = 0\n",
" for line in input20:\n",
" (p, v, a) = pattern.match(line).groups()\n",
" state['p'].append(list(map(int, p.split(','))))\n",
" state['v'].append(list(map(int, v.split(','))))\n",
" state['a'].append(list(map(int, a.split(','))))\n",
" return state\n",
"\n",
"init20 = initstate20()\n",
"\n",
"print()\n",
"print(\"-- first 10 accelerations --\")\n",
"for line in init20['a'][:10]:\n",
" print(line)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"smallest acceleration is 1\n",
"which is at index 21\n"
]
}
],
"source": [
"# These particles are all moving with constant acceleration,\n",
"# and so \"in the long run\", high acceleration => high velocity => far from origin.\n",
"\n",
"# So my first guess was that the smallest acceleration would give the particle closest to the origin.\n",
"\n",
"# minimum acceleration :\n",
"man_accel = list(map(manhattan, init20['a']))\n",
"min_accel = min(man_accel)\n",
"min_index = man_accel.index(min_accel)\n",
"print(\"smallest acceleration is \", min_accel)\n",
"print(\"which is at index \", min_index)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# ... but \"21\" is not the right answer.\n",
"\n",
"# Maybe there is more than one with that lowest acceleration ? \n",
"\n",
"# Or maybe the \"manhatttan distance\" rather than euclidean means \n",
"# that there is something trickier going on?\n",
"\n",
"[i for i in range(N20) if man_accel[i] == 1]\n"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [],
"source": [
"# ... and 457 *is* the closest, and the answer to part 1 (It must have a smaller initial velocity.)\n",
"\n",
"# OK, collisions. Now I will need to simulate it.\n",
"# I'll set the position to None in the state for destroyed particles\n",
"\n",
"def vectoradd(a, b):\n",
" return [a[0]+b[0], a[1]+b[1], a[2]+b[2]]\n",
"\n",
"def tick(s):\n",
" \"\"\" Advance positions and velocities by one clock tick. \"\"\"\n",
" for i in range(N20):\n",
" if s['p'][i] != None:\n",
" s['v'][i] = vectoradd(s['v'][i], s['a'][i])\n",
" s['p'][i] = vectoradd(s['p'][i], s['v'][i])\n",
" return s\n",
"\n",
"def collide(s):\n",
" \"\"\" Remove particles that are in the same position. \"\"\"\n",
" c = {}\n",
" for i in range(N20):\n",
" if s['p'][i] == None: # skip destroyed particles\n",
" continue\n",
" key = (s['p'][i][0], s['p'][i][1], s['p'][i][2])\n",
" if key in c:\n",
" # collision !\n",
" s['p'][i] = None # remove this one\n",
" s['p'][c[key]] = None # ... and the other one\n",
" else:\n",
" c[key] = i # Add this position with its index\n",
" return s\n",
"\n",
"def count20(s):\n",
" \"\"\" Return number of remaining particles \"\"\"\n",
" return len([i for i in range(N20) if s['p'][i] != None])\n",
"\n",
"# After all the collisions are resolved ...\n",
"#\n",
"# Hmmm. It isn't obvious how long this needs to run.\n",
"#\n",
"# I could go until all the distances between pairs of particles are increasing\n",
"# ... or just it run it for a long time.\n"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"count = 1000 at t = 15\n"
]
}
],
"source": [
"state = initstate20()\n",
"state = collide(state)\n",
"count = last_count = count20(state)\n",
"print(\"count = \", count, \" at t = \", t)\n",
"t = 0"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"count is 448 at t = 2000\n"
]
}
],
"source": [
"#while count == last_count:\n",
"while t < 2000:\n",
" t += 1\n",
" state = tick(state)\n",
" state = collide(state)\n",
" count = count20(state)\n",
"\n",
"print(\"count is \", count, \" at t = \", t)\n",
"last_count = count"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"count at 2000 is the same as count at 1000 ... maybe that's \"after has settled down\"\n",
"\n",
"Yes, the answer to part 2 is 448.\n",
"\n",
"It took me a long time to debug this. \n",
"\n",
"On my first attempt, I was updating the velocities & positions in the wrong order.\n",
"There were no collisions even after running for a long, and I was trying to figure out why\n",
"without a log of success. Starting to think I needed to do number theory on relative \n",
"particle positions or something to get it to work out to really big numbers of iterations.\n",
"\n",
"Total elapsed time was about two hours."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 21](http://adventofcode.com/2017/day/21) : Fractal Art"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"'####' -> '.##.###.#'\n",
"'#########' -> '.##.##........#.'\n",
"'########.' -> '#...##..##.#.###'\n",
"'#######.#' -> '##..#...##.###..'\n",
"'#######..' -> '.######.#.....#.'\n",
"'######.#.' -> '#.#..###..#.#.#.'\n",
"'######...' -> '.#.########.####'\n",
"'#####.#.#' -> '##....###.#.##..'\n",
"'#####.#..' -> '...#.######.####'\n",
"'#####....' -> '#.##.#...#..#...'\n"
]
}
],
"source": [
"input21 = list(map(lambda x: x.rstrip(), Input(21).readlines()))\n",
"patterns21 = {}\n",
"for line in input21:\n",
" (left, right) = line.split(' => ')\n",
" left = left.replace('/', '') # don't need these - all square\n",
" right = right.replace('/', '')\n",
" patterns21[left] = right\n",
"for key in list(sorted(patterns21.keys())[:10]):\n",
" print(\"'{}' -> '{}'\".format(key, patterns21[key]))"
]
},
{
"cell_type": "code",
"execution_count": 84,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-- 0 -> 1 -- \n",
".#.\n",
"..#\n",
"###\n",
"\n",
".#.#\n",
"#.#.\n",
"#...\n",
"##.#\n",
"\n",
"-- 1 -> 2 -- \n",
".#.#\n",
"#.#.\n",
"#...\n",
"##.#\n",
"\n",
"......\n",
"#..#..\n",
"##.##.\n",
"#####.\n",
"#..#..\n",
"####..\n",
"\n",
"-- 2 -> 3 -- \n",
"......\n",
"#..#..\n",
"##.##.\n",
"#####.\n",
"#..#..\n",
"####..\n",
"\n",
"##.##..##\n",
"#..#....#\n",
"#..#..##.\n",
".########\n",
".###..#.#\n",
"#.####..#\n",
"######.##\n",
"#..#....#\n",
"########.\n",
"\n",
"-- 3 -> 4 -- \n",
"##.##..##\n",
"#..#....#\n",
"#..#..##.\n",
".########\n",
".###..#.#\n",
"#.####..#\n",
"######.##\n",
"#..#....#\n",
"########.\n",
"\n",
".#...#..####\n",
".#...#..##..\n",
"...#...#.##.\n",
"##..##..##.#\n",
"..#...#####.\n",
"...#####.##.\n",
"#..#######.#\n",
"...#.####...\n",
"..##..######\n",
"##########..\n",
"########.##.\n",
".###.#####.#\n",
"\n",
"-- 4 -> 5 -- \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"
]
}
],
"source": [
"def pattern2grid(p):\n",
" \"\"\" convert 'xxxxxxxxx' or 'xxxx' into a 3x3 or 2x2 grid \"\"\"\n",
" result = np.array(list(p))\n",
" size = int(np.sqrt(len(p)))\n",
" return result.reshape(size, size)\n",
"\n",
"def grid2pattern(p):\n",
" \"\"\" convert 3x3 or 2x2 grid into 'xxxxxxxxx' or 'xxxxx' \"\"\"\n",
" size = p.shape[0] * p.shape[1]\n",
" return ''.join(list(p.reshape(size)))\n",
"\n",
"def symmetric_patterns(patterns):\n",
" \"\"\" return longer dict with rotated and flipped patterns \"\"\"\n",
" result = patterns.copy()\n",
" for p in patterns.keys():\n",
" grid = pattern2grid(p)\n",
" flipped = np.fliplr(grid)\n",
" result[grid2pattern(flipped)] = patterns[p]\n",
" for m in (grid, flipped):\n",
" for r in range(3):\n",
" m = np.rot90(m)\n",
" result[grid2pattern(m)] = patterns[p]\n",
" return result\n",
"\n",
"allpatterns = symmetric_patterns(patterns21)\n",
"\n",
"# tests\n",
"if False:\n",
" x = 'abcd'\n",
" print(x)\n",
" xgrid = pattern2grid(x)\n",
" print(xgrid)\n",
" print(np.fliplr(xgrid)) # flip left right\n",
" print(np.rot90(xgrid)) # rotate 90 degrees\n",
" print(grid2pattern(xgrid))\n",
"\n",
"def printgrid(p):\n",
" for row in p[:,]:\n",
" print(''.join(row))\n",
"\n",
"def growgrid(generations=5, start=\".#...####\", transform=allpatterns, show=True):\n",
" \"\"\" iterate rules a given number of times\"\"\"\n",
" grid = pattern2grid(start)\n",
" for i in range(generations):\n",
" if show:\n",
" print('-- {} -> {} -- '.format(i, i+1))\n",
" printgrid(grid)\n",
" print()\n",
" size = grid.shape[0]\n",
" if size % 2 == 0:\n",
" old_block_size = 2\n",
" new_block_size = 3\n",
" else:\n",
" old_block_size = 3\n",
" new_block_size = 4\n",
" n_blocks = size // old_block_size\n",
" new_size = n_blocks * new_block_size\n",
" new_grid = pattern2grid('x'*(new_size)**2)\n",
" for row in range(n_blocks):\n",
" old_row_start = row * old_block_size\n",
" old_row_end = (row+1) * old_block_size\n",
" new_row_start = row * new_block_size\n",
" new_row_end = (row+1) * new_block_size\n",
" for col in range(n_blocks):\n",
" old_col_start = col * old_block_size\n",
" old_col_end = (col+1) * old_block_size\n",
" new_col_start = col * new_block_size\n",
" new_col_end = (col+1) * new_block_size\n",
" p = grid[old_row_start:old_row_end, old_col_start:old_col_end]\n",
" new_p = pattern2grid(transform[grid2pattern(p)])\n",
" new_grid[new_row_start:new_row_end, new_col_start:new_col_end] = new_p\n",
" if show:\n",
" printgrid(new_grid)\n",
" print()\n",
" grid = new_grid\n",
" return grid2pattern(new_grid)\n",
"\n",
"after5 = growgrid()\n"
]
},
{
"cell_type": "code",
"execution_count": 78,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'###.#####.##.######.#..##.#..#.###.#..###...###.#.#..######.#####.###...#.##..#.##..#..#....##....##..#####..##...###.########..##..#.#.###..#.###.##...##.####..###.######.#######.#..#.##...###..#..#....#####.#####..###.#####.##.######.#.###.#.##.###.#..##.#..##.##.#..####.#####.#####...#...###...###..#..####.#####.######.'"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"after5"
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"203"
]
},
"execution_count": 79,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(after5.replace('.', ''))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So the answer to part1 is 203."
]
},
{
"cell_type": "code",
"execution_count": 85,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3342470"
]
},
"execution_count": 85,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"after18 = growgrid(generations=18, show=False)\n",
"len(after18.replace('.', ''))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And the answer to part2 (which took a few seconds to work through) is 3342470 ."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 22](http://adventofcode.com/2017/day/22) : Sporifica Virus"
]
},
{
"cell_type": "code",
"execution_count": 89,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"width : 25\n",
"height: 25\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": [
"input22 = list(map(lambda x: x.rstrip(), Input(22).readlines()))\n",
"print(\"width : \", len(input22[0]))\n",
"print(\"height: \", len(input22))\n",
"for line in input22:\n",
" print(line)"
]
},
{
"cell_type": "code",
"execution_count": 92,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"##########..#.###...##..#\n",
"##....#...#....#..####.#.\n",
"#..#.##..#..##.###..#.###\n",
".#.#.......####.....#.#..\n",
"...######....#.##########\n",
"##.#.....#.#####.#....###\n",
"#.####.#..#.#.#...#.#..##\n",
"#.##..#####..###..###.##.\n",
"#.####.#.##.##...#.#.#.##\n",
"#.#.#......##.##..###.#.#\n",
"#...#.#..#.##....#.##..##\n",
".#.....##.##..#.####..##.\n",
".#......#.#.########..###\n",
"##....###.#.#.###...##..#\n",
"..##.###....#.....#...#.#\n",
"....##...##...##.##.#..##\n",
"..#.#.#..#######..###..##\n",
"......#####.#####..#.#..#\n",
".####.#......#..###..#.##\n",
"#....####.#..#.##.###.##.\n",
"####.#...##....###...#.#.\n",
"#####.#......#.#..###.##.\n",
"#.##.#..#..#..#.....#.#.#\n",
"#...#.#.##.#.####.#.#..#.\n",
".##.##..#..###.##.....###\n"
]
}
],
"source": [
"# Using the functions from day22 :\n",
"grid = pattern2grid(''.join(input22))\n",
"printgrid(grid)"
]
},
{
"cell_type": "code",
"execution_count": 169,
"metadata": {},
"outputs": [],
"source": [
"input22 = list(map(lambda x: x.rstrip(), Input(22).readlines()))\n",
"\n",
"(up, down, left, right) = (Point(-1,0), Point(1,0), Point(0,-1), Point(0,1))\n",
"\n",
"turnright = {str(up):right, str(right):down, str(down):left, str(left):up}\n",
"turnleft = {str(up):left, str(left):down, str(down):right, str(right):up}\n",
"turnreverse = {str(up):down, str(left):right, str(down):up, str(right):left}\n",
"\n",
"def initstate22():\n",
" return {'grid': pattern2grid(''.join(input22)),\n",
" 'at': Point(12, 12), # row, column\n",
" 'direction' : up,\n",
" 'time' : 0,\n",
" 'newinfect' : 0\n",
" }"
]
},
{
"cell_type": "code",
"execution_count": 177,
"metadata": {},
"outputs": [],
"source": [
"def padgrid(state, n):\n",
" \"\"\" pad grid with empty space \"\"\"\n",
" grid = state['grid']\n",
" size = grid.shape[0]\n",
" newsize = size + 2*n\n",
" result = np.array(list('.'*newsize**2)).reshape(newsize, newsize)\n",
" result[n:(n+size), n:(n+size)] = grid\n",
" state['grid'] = result\n",
" state['at'] += Point(n, n) # shift position to match\n",
" return state\n"
]
},
{
"cell_type": "code",
"execution_count": 183,
"metadata": {},
"outputs": [],
"source": [
"def tick22(state):\n",
" \"\"\" make one move; return new state \"\"\"\n",
" # Moving off the edge will throw an error.\n",
" (row, col) = (state['at'][0], state['at'][1])\n",
" grid = state['grid']\n",
" if grid[row, col] == '#':\n",
" grid[row, col] = '.'\n",
" state['direction'] = turnright[str(state['direction'])]\n",
" else:\n",
" grid[row, col] = '#'\n",
" state['newinfect'] += 1\n",
" state['direction'] = turnleft[str(state['direction'])]\n",
" state['at'] += state['direction']\n",
" state['grid'] = grid\n",
" return state\n"
]
},
{
"cell_type": "code",
"execution_count": 184,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5182"
]
},
"execution_count": 184,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"state = initstate22()\n",
"state = padgrid(state, 100)\n",
"\n",
"for i in range(10000):\n",
" state = tick22(state)\n",
" \n",
"state['newinfect']\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So the answer to part 1 is 5182"
]
},
{
"cell_type": "code",
"execution_count": 182,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# part 2 has a new evolution :\n",
"# clean -> weak -> infected -> flagged -> clean\n",
"# . -> W -> # -> F -> .\n",
"# and new direction changes :\n",
"\n",
"def tick22_part2(state):\n",
" \"\"\" make one move; return new state \"\"\"\n",
" # Moving off the edge will throw an error ... so don't do that.\n",
" (row, col) = (state['at'][0], state['at'][1])\n",
" grid = state['grid']\n",
" if grid[row, col] == '#':\n",
" grid[row, col] = 'F'\n",
" state['direction'] = turnright[str(state['direction'])]\n",
" elif grid[row, col] == '.':\n",
" grid[row, col] = 'W'\n",
" state['direction'] = turnleft[str(state['direction'])]\n",
" elif grid[row, col] == 'F':\n",
" grid[row, col] = '.'\n",
" state['direction'] = turnreverse[str(state['direction'])]\n",
" else: # W\n",
" grid[row, col] = '#'\n",
" state['newinfect'] += 1\n",
" state['at'] += state['direction']\n",
" state['grid'] = grid\n",
" return state\n"
]
},
{
"cell_type": "code",
"execution_count": 187,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"part 2 answer is 2512008\n",
"elapsed seconds is 1091.0379519462585\n"
]
}
],
"source": [
"starttime = time.time()\n",
"\n",
"state = initstate22()\n",
"state = padgrid(state, 200)\n",
"\n",
"for i in range(10000000):\n",
" state = tick22_part2(state)\n",
" \n",
"print(\"part 2 answer is \", state['newinfect'])\n",
"print(\"elapsed seconds is \", time.time() - starttime)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And the right answer is 2512008 ... but it took a long time to run - almost 20 minutes (!!)\n",
"\n",
"The numpy arrays can be fast for numeric manipulations, but I'm doing something here\n",
"that is allocating memory or thrashing or something which is very slow.\n",
"\n",
"Looking at the reddit thread, I see lots of code that runs much, much faster - like 20 sec or so. \n",
"\n",
"Tricks to speed things up :\n",
"\n",
" Use complex numbers for coords : add to get new coord, multiply to rotate, fast & numeric.\n",
"\n",
" Use a dictionary with complex keys for cllsl that get used.\n",
" \n",
" Use numbers, not stings or symbols.\n"
]
},
{
"cell_type": "code",
"execution_count": 198,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"infected = 2512008\n",
"elapsed 6.227190017700195\n"
]
}
],
"source": [
"# Here's some code similar to what I saw on reddit, from Shemetz ,\n",
"# which gives the part 2 answer in 6 seconds : 200 times faster than my code above.\n",
"\n",
"from collections import defaultdict\n",
"\n",
"grid = defaultdict(lambda: 0) # dictionary with 0 as default\n",
"(clean, weak, infected, flagged) = (0, 1, 2, 3) # ... which lets us get the next one by adding 1\n",
"rotation = [1j, 1, -1j, -1] # ... turn for each ,\n",
" # (clean => left, weak => no turn, \n",
" # infected => right, flagged => reverse)\n",
"(Nrows, Ncols) = (len(input22), len(input22[0]))\n",
"def coord(row, col): \n",
" # return complex (x + i y) given matrix[row][col] coordinates, where\n",
" # (x,y) have their usual (postive to the right, positive up) definitions.\n",
" return (col - Ncols//2) + 1j * (Nrows//2 - row)\n",
"\n",
"# initialize grid entries from input\n",
"# (ignore . since the defaultdict will give 0 there; just need infected places)\n",
"for row in range(Nrows):\n",
" for col in range(Ncols):\n",
" if input22[row][col] == '#':\n",
" grid[coord(row, col)] = infected\n",
"\n",
"# run the simulation\n",
"# Note that updates to direction & state are all numeric, without ifs i.e. fast!\n",
"position = 0 + 0j\n",
"direction = 1j\n",
"infected = 0\n",
"starttime = time.time()\n",
"for _ in range(10000000):\n",
" status = grid[position]\n",
" direction *= rotation[status] # rotation with complex number lookup\n",
" if status == 1:\n",
" infected += 1\n",
" grid[position] = (grid[position] + 1) % 4 # clean -> weak -> infected -> flagged\n",
" position += direction # update position with complex addition\n",
"\n",
"print(\"infected = \", infected)\n",
"print(\"elapsed \", time.time() - starttime)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 23](http://adventofcode.com/2017/day/23) : Coprocessor Conflagration"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['set b 67',\n",
" 'set c b',\n",
" 'jnz a 2',\n",
" 'jnz 1 5',\n",
" 'mul b 100',\n",
" 'sub b -100000',\n",
" 'set c b',\n",
" 'sub c -17000',\n",
" 'set f 1',\n",
" 'set d 2',\n",
" 'set e 2',\n",
" 'set g d',\n",
" 'mul g e',\n",
" 'sub g b',\n",
" 'jnz g 2',\n",
" 'set f 0',\n",
" 'sub e -1',\n",
" 'set g e',\n",
" 'sub g b',\n",
" 'jnz g -8',\n",
" 'sub d -1',\n",
" 'set g d',\n",
" 'sub g b',\n",
" 'jnz g -13',\n",
" 'jnz f 2',\n",
" 'sub h -1',\n",
" 'set g b',\n",
" 'sub g c',\n",
" 'jnz g 2',\n",
" 'jnz 1 3',\n",
" 'sub b -17',\n",
" 'jnz 1 -23']"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input23 = list(map(lambda x: x.rstrip(), Input(23).readlines()))\n",
"input23"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# The start is similar to Day 18. I've grabbed that code and am adapting it."
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-- start - check in every 10000 --\n",
" h = 0 at check = 1\n",
" h = 0 at check = 2\n",
" h = 0 at check = 3\n",
"-- done --\n"
]
},
{
"data": {
"text/plain": [
"defaultdict(.>,\n",
" {'_counter_': 34136,\n",
" '_index_': 32,\n",
" '_mul_count': 4225,\n",
" 'a': 0,\n",
" 'b': 67,\n",
" 'c': 67,\n",
" 'd': 67,\n",
" 'e': 67,\n",
" 'f': 1,\n",
" 'g': 0,\n",
" 'h': 0})"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"\n",
"def get23(s, state):\n",
" \"\"\" Return the value of register s given a machine state. \"\"\"\n",
" # Using a defaultdict that gives 0 for things not yet seen.\n",
" if s in string.ascii_lowercase:\n",
" return state[s]\n",
" else:\n",
" return int(s)\n",
"\n",
"def run23(code, part2=False, check=10000):\n",
" # Execute the given lines of code. Return the final machine state.\n",
" state = defaultdict(lambda:0)\n",
" state['h'] = 0\n",
" state['_index_'] = 0\n",
" if part2:\n",
" state['a'] = 1\n",
" print(\"-- start - check in every {} --\".format(check))\n",
" while True:\n",
" \n",
" try:\n",
" line = code[state['_index_']] # e.g. \"mul p -1\"\n",
" except:\n",
" print(\"OOPS\")\n",
" print(\" state index is \", state['_index_'])\n",
" print(\" count is \", state['_count_'])\n",
" print(\"\")\n",
" raise\n",
" \n",
" state['_index_'] += 1 # Increment instruction index.\n",
" \n",
" state['_counter_'] += 1 # number of steps taken.\n",
" \n",
" what = line[:3] # e.g. \"mul\"\n",
" first = line[4] # e.g. \"p\"\n",
" rest = line[6:] # e.g. \"-1\"\n",
" \n",
" if what == 'set':\n",
" state[first] = get23(rest, state)\n",
" elif what == 'sub':\n",
" state[first] -= get23(rest, state)\n",
" elif what == 'mul':\n",
" state[first] *= get23(rest, state)\n",
" state['_mul_count'] += 1\n",
" elif what == 'jnz':\n",
" if get23(first, state) != 0:\n",
" state['_index_'] += get23(rest, state) - 1\n",
" else:\n",
" print(\"ERROR : line is {}\".format(line))\n",
" \n",
" if state['_counter_'] % check == 0:\n",
" print(\" h = {} at check = {}\".format(state['h'], state['_counter_'] // check))\n",
" \n",
" if (state['_index_'] < 0) or (state['_index_'] >= len(code)):\n",
" print(\"-- done --\")\n",
" return state\n",
"\n",
"run23(input23)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And the answer to part 1 is 4225."
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-- start - check in every 1000000 --\n",
" h = 0 at check = 1\n",
" h = 0 at check = 2\n",
" h = 0 at check = 3\n",
" h = 0 at check = 4\n",
" h = 0 at check = 5\n",
" h = 0 at check = 6\n",
" h = 0 at check = 7\n",
" h = 0 at check = 8\n",
" h = 0 at check = 9\n",
" h = 0 at check = 10\n",
" h = 0 at check = 11\n",
" h = 0 at check = 12\n",
" h = 0 at check = 13\n",
" h = 0 at check = 14\n",
" h = 0 at check = 15\n",
" h = 0 at check = 16\n",
" h = 0 at check = 17\n",
" h = 0 at check = 18\n",
" h = 0 at check = 19\n",
" h = 0 at check = 20\n",
" h = 0 at check = 21\n",
" h = 0 at check = 22\n",
" h = 0 at check = 23\n",
" h = 0 at check = 24\n",
" h = 0 at check = 25\n",
" h = 0 at check = 26\n",
" h = 0 at check = 27\n",
" h = 0 at check = 28\n",
" h = 0 at check = 29\n",
" h = 0 at check = 30\n",
" h = 0 at check = 31\n",
" h = 0 at check = 32\n",
" h = 0 at check = 33\n",
" h = 0 at check = 34\n",
" h = 0 at check = 35\n",
" h = 0 at check = 36\n",
" h = 0 at check = 37\n",
" h = 0 at check = 38\n",
" h = 0 at check = 39\n",
" h = 0 at check = 40\n",
" h = 0 at check = 41\n"
]
},
{
"ename": "KeyboardInterrupt",
"evalue": "",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mKeyboardInterrupt\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[0mrun23\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minput23\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpart2\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mTrue\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcheck\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m1000000\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;36mrun23\u001b[0;34m(code, part2, check)\u001b[0m\n\u001b[1;32m 51\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\" h = {} at check = {}\"\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstate\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'h'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstate\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'_counter_'\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m//\u001b[0m \u001b[0mcheck\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 52\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 53\u001b[0;31m \u001b[0;32mif\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mstate\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'_index_'\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mstate\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'_index_'\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m>=\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcode\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 54\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"-- done --\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 55\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mstate\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mKeyboardInterrupt\u001b[0m: "
]
}
],
"source": [
"run23(input23, part2=True, check=1000000)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"32"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(input23)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Looking at the instructions.\n",
"\n",
"(\"You'll need to optimize the program if it has any hope of completing before Santa needs that printer working.\")\n",
"\n",
"\n",
" b = 67 b = 67\n",
" c = b c = 67 \n",
" a != 0 ? -> A always in part 2 \n",
" jnz 1 5 -> B\n",
" A: b *= 100 b = 6700\n",
" b -= 100000 b = 106700\n",
" c = b \n",
" c -= 17000 ---------- here back only runs once c = 123700 (doesn't change)\n",
" B: f = 1\n",
" d = 2\n",
" E: e = 2\n",
" D: g = d\n",
" g *= e\n",
" g -= b\n",
" g != 0 ? -> C need g == 0 here to set f=0 to change h ... i.e. d*e == b\n",
" f = 0\n",
" C: e -= 1\n",
" g = e\n",
" g -= b\n",
" g != 0 ? -> D\n",
" d -= 1b\n",
" g = d\n",
" g -= b\n",
" g != 0 ? -> E need g == 0 to change h ... i.e. d == b\n",
" f != 0 ? -> F need f == 0 to change h ... its a 0 or 1 flag\n",
" h -= -1\n",
" F: g = b\n",
" g -= c\n",
" g = 0? -> G exit if g == 0, i.e. if b == c after h changes\n",
" jnz 1 3 -> DONE\n",
" G: b -= -17 only place b changes \n",
" jnz 1 -> B"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"I can see that :\n",
"\n",
" - with a=1, the first prelude happens once, initilizing b & c.\n",
"\n",
" - c is at 95000 and doesn't change.\n",
"\n",
" - b counts upward in increments of 17.\n",
"\n",
" - g is just used as a register to set up the jump tests\n",
"\n",
" - h counts upwards (subtract a negative one)\n",
"\n",
" - There are essentially three nested loops :\n",
"\n",
" while (b != c , steps of 17){\n",
"\n",
" while (d != b , starts at 2, steps of 1){\n",
"\n",
"\n",
" the flag is set to 0 when d * e = b ...\n",
"\t i.e. when there exist factors of b.\n",
"\t So f=1 means b is prime.\n",
"\n",
"\t h increments when f is 0 ... so when b is *not* prime.\n",
"\n",
" while e != b, starts at 2, steps of -1){\n",
"\n",
" }\n",
"\n",
" }\n",
" }\n",
"\n",
"So the answer I think is 106700 <= n <= 123700 such that prime(n) == false.\n",
"\n",
"I had a prime number sieve in C, and so just adapted that. The code is in day23_primes.c,\n",
"and gave 905 which is the correct answer ... after several missed attempts from fencepost errors and doing the simple arithmentic to get the limits wrong."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 24](http://adventofcode.com/2017/day/24) : Electromagnetic Moat"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['24/14', '30/24', '29/44', '47/37', '6/14']\n",
"57\n"
]
}
],
"source": [
"input24 = list(map(lambda x: x.rstrip(), Input(24).readlines()))\n",
"print(input24[:5])\n",
"print(len(input24))"
]
},
{
"cell_type": "code",
"execution_count": 99,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"57\n"
]
}
],
"source": [
"ports24 = {}\n",
"id = 0\n",
"for line in input24:\n",
" id += 1\n",
" (left, right) = list(map(int, line.split('/')))\n",
" ports24[id] = {'left': left, 'right': right}\n",
"\n",
"print(len(ports24))"
]
},
{
"cell_type": "code",
"execution_count": 100,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"sys.setrecursionlimit(100)"
]
},
{
"cell_type": "code",
"execution_count": 101,
"metadata": {},
"outputs": [],
"source": [
"# So the trick here is that each thing (port) can match in one of two ways,\n",
"# and if it is removed from the available ones then both sides of its sides\n",
"# need to be removed.\n",
"\n",
"# That means that just a dictionary lookup with lists of matching ports\n",
"# doesn't seem like it'll work, since each port would be in two lists.\n",
"# A data structure like that could work though it would need to \n",
"# have remove & insert routines that handled this complication.\n",
"\n",
"# But for now I'm doing something simpler but slower, \n",
"# settling for a simple O(n) search through the ports \n",
"# to find those matching.\n",
"\n",
"def open_port_ids(ports, socket):\n",
" \"\"\" Return list of ids of ports with given socket on left or right \"\"\"\n",
" return list(filter(lambda i: ports[i]['left']==socket or ports[i]['right']==socket, \n",
" ports.keys()))\n",
"\n",
"def other_socket(port, socket):\n",
" if port['left'] == socket:\n",
" return port['right']\n",
" else:\n",
" return port['left']\n",
"\n",
"def strength_of(port):\n",
" return port['left'] + port['right']"
]
},
{
"cell_type": "code",
"execution_count": 102,
"metadata": {},
"outputs": [],
"source": [
"\n",
"def best_strength(ports, socket, best):\n",
" matching_port_ids = open_port_ids(ports, socket)\n",
" if len(matching_port_ids) == 0:\n",
" return best\n",
" strengths = [] \n",
" for id in matching_port_ids:\n",
" port = ports[id]\n",
" del ports[id] # take it out ...\n",
" strengths.append(best_strength(ports,\n",
" other_socket(port, socket),\n",
" best + strength_of(port)\n",
" ))\n",
" ports[id] = port # ... put it back.\n",
" return max(strengths)\n"
]
},
{
"cell_type": "code",
"execution_count": 103,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"result is 2006\n",
"elapsed seconds : 4.756611108779907\n"
]
}
],
"source": [
"starttime=time.time()\n",
"answer24_1 = best_strength(ports24, 0, 0)\n",
"print(\"result is \", answer24_1)\n",
"print(\"elapsed seconds : \" , time.time() - starttime)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And I have the answer for part 1 : 2006 - faster than I expected."
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(12, 7)"
]
},
"execution_count": 83,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# part 2 : strength of longest bridge (or if more than one, the strongest of them)\n",
"\n",
"# The same approach should work, modified to return (length, strength)\n",
"# and take the max of those, since python has an ordering relation on tuples\n",
"# which should do the right thing.\n",
"\n",
"max( (10, 9), (12, 3), (12, 7) ) # length, strength"
]
},
{
"cell_type": "code",
"execution_count": 104,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def best_length_strength(ports, socket, best):\n",
" (l, s) = best\n",
" matching_port_ids = open_port_ids(ports, socket)\n",
" if len(matching_port_ids) == 0:\n",
" return best\n",
" ls = [] # (length, strength)\n",
" for id in matching_port_ids:\n",
" port = ports[id]\n",
" del ports[id] # take it out ...\n",
" ls.append(best_length_strength(ports,\n",
" other_socket(port, socket),\n",
" (l + 1, s + strength_of(port))\n",
" ))\n",
" ports[id] = port # ... put it back.\n",
" return max(ls)"
]
},
{
"cell_type": "code",
"execution_count": 105,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"result is (34, 1994)\n",
"elapsed seconds : 4.77583909034729\n"
]
}
],
"source": [
"starttime=time.time()\n",
"answer24_2 = best_length_strength(ports24, 0, (0,0))\n",
"print(\"result is \", answer24_2)\n",
"print(\"elapsed seconds : \" , time.time() - starttime)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And that worked : the part 2 answer is 1994. I had the 595th answer, in just under two hours."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# [Day 25](http://adventofcode.com/2017/day/25) : The Halting Problem"
]
},
{
"cell_type": "code",
"execution_count": 122,
"metadata": {},
"outputs": [],
"source": [
"\n",
"steps = 12994925\n",
"\n",
"day25 = { 'tape' : '0',\n",
" 'start' : 'A',\n",
" 'accept' : [],\n",
" 'reject' : [],\n",
" 'blank' : '0',\n",
" # state read new_state write move\n",
" 'machine':[['A', 0, 'B', 1, 'right'],\n",
" ['A', 1, 'F', 0, 'left'],\n",
" \n",
" ['B', 0, 'C', 0, 'right'],\n",
" ['B', 1, 'D', 0, 'right'],\n",
" \n",
" ['C', 0, 'D', 1, 'left'],\n",
" ['C', 1, 'E', 1, 'right'],\n",
" \n",
" ['D', 0, 'E', 0, 'left'],\n",
" ['D', 1, 'D', 0, 'left'],\n",
" \n",
" ['E', 0, 'A', 0, 'right'],\n",
" ['E', 1, 'C', 1, 'right'],\n",
" \n",
" ['F', 0, 'A', 1, 'left'],\n",
" ['F', 1, 'A', 1, 'right']\n",
" ]\n",
" }\n",
"\n",
"# number of ones ?"
]
},
{
"cell_type": "code",
"execution_count": 141,
"metadata": {},
"outputs": [],
"source": [
"# I have a turing machine simulator from my Formal Languages Course.\n",
"\n",
"def tape_state_string(tape, position, state, steps):\n",
" \"\"\" Return a string representation of current turing machine status \"\"\"\n",
" line = \" {:6d} \".format(steps)\n",
" for i in range(len(tape)):\n",
" if i == position:\n",
" line += \"<{}>\".format(tape[i])\n",
" else:\n",
" line += \" {} \".format(tape[i])\n",
" line += \" : {}\".format(state)\n",
" return line\n",
"\n",
"def run(turing, verbose=True, N_steps=500):\n",
" \"\"\" Simulate a Turing machine,\n",
" printing each step if verbose is True. \"\"\"\n",
"\n",
" offset = {'right': 1, 'left': -1, 'stay': 0}\n",
" \n",
" # Initialize the machine.\n",
" state = turing['start'] # e.g. 'start'\n",
" tape = list(turing['tape']) # e.g. ['0', '0', '1']\n",
" position = 0 # position of read head on tape\n",
"\n",
" # Convert the machine table into a more convenient dictionary form.\n",
" rules = {}\n",
" for rule in turing['machine']:\n",
" rule = map(str, rule)\n",
" (this_state, read_symbol, next_state, write_symbol , move) = rule\n",
" if not this_state in rules:\n",
" rules[this_state] = {}\n",
" rules[this_state][read_symbol] = {'next': next_state,\n",
" 'write': write_symbol,\n",
" 'move': move }\n",
"\n",
" # Run the machine.\n",
" steps = 0\n",
" while True and steps < N_steps:\n",
" \n",
" if verbose:\n",
" print(tape_state_string(tape, position, state, steps))\n",
"\n",
" steps += 1\n",
"\n",
" #if state in turing['accept']:\n",
" # if verbose:\n",
" # print(\" ** Accept **\")\n",
" # return\n",
" #\n",
" #if state in turing['reject']:\n",
" # if verbose:\n",
" # print(\" ** Reject **\")\n",
" # return\n",
" #\n",
" \n",
" #try:\n",
" \n",
" update = {}\n",
" symbol = tape[position]\n",
" for what in ('next', 'write', 'move'):\n",
" update[what] = rules[state][symbol][what]\n",
" \n",
" #except KeyError:\n",
" # if verbose:\n",
" # print(\" ** HALT ** (No matching rule)\")\n",
" # return\n",
"\n",
" #try: \n",
" \n",
" state = update['next']\n",
" tape[position] = update['write']\n",
" position += offset[update['move']]\n",
" \n",
" #except KeyError:\n",
" # if verbose:\n",
" # print(\" ** HALT ** (Movement {} not recognized)\".format(\n",
" # update['move'])\n",
" # return\n",
" \n",
" while position < 0: # moved off left edge of tape\n",
" tape = [ turing['blank'] ] + tape\n",
" position += 1\n",
" \n",
" while position >= len(tape): # moved off right edge of tape\n",
" tape = tape + [ turing['blank'] ]\n",
"\n",
" if not verbose:\n",
" print(tape_state_string(tape, position, state, steps))\n",
" print(\"number of 1s is {}\".format(len(list(filter(lambda x:x=='1', tape)))))"
]
},
{
"cell_type": "code",
"execution_count": 142,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 0 <0> : A\n",
" 1 1 <0> : B\n",
" 2 1 0 <0> : C\n",
" 3 1 <0> 1 : D\n",
" 4 <1> 0 1 : E\n",
" 5 1 <0> 1 : C\n",
" 6 <1> 1 1 : D\n",
" 7 <0> 0 1 1 : D\n",
" 8 <0> 0 0 1 1 : E\n",
" 9 0 <0> 0 1 1 : A\n",
" 10 0 1 <0> 1 1 : B\n",
" 11 0 1 0 <1> 1 : C\n",
" 12 0 1 0 1 <1> : E\n",
" 13 0 1 0 1 1 <0> : C\n",
" 14 0 1 0 1 <1> 1 : D\n",
" 15 0 1 0 <1> 0 1 : D\n",
" 16 0 1 <0> 0 0 1 : D\n",
" 17 0 <1> 0 0 0 1 : E\n",
" 18 0 1 <0> 0 0 1 : C\n",
" 19 0 <1> 1 0 0 1 : D\n",
" 20 <0> 0 1 0 0 1 : D\n",
" 21 <0> 0 0 1 0 0 1 : E\n",
" 22 0 <0> 0 1 0 0 1 : A\n",
" 23 0 1 <0> 1 0 0 1 : B\n",
" 24 0 1 0 <1> 0 0 1 : C\n",
" 25 0 1 0 1 <0> 0 1 : E\n",
" 26 0 1 0 1 0 <0> 1 : A\n",
" 27 0 1 0 1 0 1 <1> : B\n",
" 28 0 1 0 1 0 1 0 <0> : D\n",
" 29 0 1 0 1 0 1 <0> 0 : E\n",
" 30 0 1 0 1 0 1 0 <0> : A\n",
" 31 0 1 0 1 0 1 0 1 <0> : B\n",
" 32 0 1 0 1 0 1 0 1 0 <0> : C\n",
" 33 0 1 0 1 0 1 0 1 <0> 1 : D\n",
" 34 0 1 0 1 0 1 0 <1> 0 1 : E\n",
" 35 0 1 0 1 0 1 0 1 <0> 1 : C\n",
" 36 0 1 0 1 0 1 0 <1> 1 1 : D\n",
" 37 0 1 0 1 0 1 <0> 0 1 1 : D\n",
" 38 0 1 0 1 0 <1> 0 0 1 1 : E\n",
" 39 0 1 0 1 0 1 <0> 0 1 1 : C\n",
" 40 0 1 0 1 0 <1> 1 0 1 1 : D\n",
" 41 0 1 0 1 <0> 0 1 0 1 1 : D\n",
" 42 0 1 0 <1> 0 0 1 0 1 1 : E\n",
" 43 0 1 0 1 <0> 0 1 0 1 1 : C\n",
" 44 0 1 0 <1> 1 0 1 0 1 1 : D\n",
" 45 0 1 <0> 0 1 0 1 0 1 1 : D\n",
" 46 0 <1> 0 0 1 0 1 0 1 1 : E\n",
" 47 0 1 <0> 0 1 0 1 0 1 1 : C\n",
" 48 0 <1> 1 0 1 0 1 0 1 1 : D\n",
" 49 <0> 0 1 0 1 0 1 0 1 1 : D\n",
" 50 <0> 0 0 1 0 1 0 1 0 1 1 : E\n",
" 51 0 <0> 0 1 0 1 0 1 0 1 1 : A\n",
" 52 0 1 <0> 1 0 1 0 1 0 1 1 : B\n",
" 53 0 1 0 <1> 0 1 0 1 0 1 1 : C\n",
" 54 0 1 0 1 <0> 1 0 1 0 1 1 : E\n",
" 55 0 1 0 1 0 <1> 0 1 0 1 1 : A\n",
" 56 0 1 0 1 <0> 0 0 1 0 1 1 : F\n",
" 57 0 1 0 <1> 1 0 0 1 0 1 1 : A\n",
" 58 0 1 <0> 0 1 0 0 1 0 1 1 : F\n",
" 59 0 <1> 1 0 1 0 0 1 0 1 1 : A\n",
" 60 <0> 0 1 0 1 0 0 1 0 1 1 : F\n",
" 61 <0> 1 0 1 0 1 0 0 1 0 1 1 : A\n",
" 62 1 <1> 0 1 0 1 0 0 1 0 1 1 : B\n",
" 63 1 0 <0> 1 0 1 0 0 1 0 1 1 : D\n",
" 64 1 <0> 0 1 0 1 0 0 1 0 1 1 : E\n",
" 65 1 0 <0> 1 0 1 0 0 1 0 1 1 : A\n",
" 66 1 0 1 <1> 0 1 0 0 1 0 1 1 : B\n",
" 67 1 0 1 0 <0> 1 0 0 1 0 1 1 : D\n",
" 68 1 0 1 <0> 0 1 0 0 1 0 1 1 : E\n",
" 69 1 0 1 0 <0> 1 0 0 1 0 1 1 : A\n",
" 70 1 0 1 0 1 <1> 0 0 1 0 1 1 : B\n",
" 71 1 0 1 0 1 0 <0> 0 1 0 1 1 : D\n",
" 72 1 0 1 0 1 <0> 0 0 1 0 1 1 : E\n",
" 73 1 0 1 0 1 0 <0> 0 1 0 1 1 : A\n",
" 74 1 0 1 0 1 0 1 <0> 1 0 1 1 : B\n",
" 75 1 0 1 0 1 0 1 0 <1> 0 1 1 : C\n",
" 76 1 0 1 0 1 0 1 0 1 <0> 1 1 : E\n",
" 77 1 0 1 0 1 0 1 0 1 0 <1> 1 : A\n",
" 78 1 0 1 0 1 0 1 0 1 <0> 0 1 : F\n",
" 79 1 0 1 0 1 0 1 0 <1> 1 0 1 : A\n",
" 80 1 0 1 0 1 0 1 <0> 0 1 0 1 : F\n",
" 81 1 0 1 0 1 0 <1> 1 0 1 0 1 : A\n",
" 82 1 0 1 0 1 <0> 0 1 0 1 0 1 : F\n",
" 83 1 0 1 0 <1> 1 0 1 0 1 0 1 : A\n",
" 84 1 0 1 <0> 0 1 0 1 0 1 0 1 : F\n",
" 85 1 0 <1> 1 0 1 0 1 0 1 0 1 : A\n",
" 86 1 <0> 0 1 0 1 0 1 0 1 0 1 : F\n",
" 87 <1> 1 0 1 0 1 0 1 0 1 0 1 : A\n",
" 88 <0> 0 1 0 1 0 1 0 1 0 1 0 1 : F\n",
" 89 <0> 1 0 1 0 1 0 1 0 1 0 1 0 1 : A\n",
" 90 1 <1> 0 1 0 1 0 1 0 1 0 1 0 1 : B\n",
" 91 1 0 <0> 1 0 1 0 1 0 1 0 1 0 1 : D\n",
" 92 1 <0> 0 1 0 1 0 1 0 1 0 1 0 1 : E\n",
" 93 1 0 <0> 1 0 1 0 1 0 1 0 1 0 1 : A\n",
" 94 1 0 1 <1> 0 1 0 1 0 1 0 1 0 1 : B\n",
" 95 1 0 1 0 <0> 1 0 1 0 1 0 1 0 1 : D\n",
" 96 1 0 1 <0> 0 1 0 1 0 1 0 1 0 1 : E\n",
" 97 1 0 1 0 <0> 1 0 1 0 1 0 1 0 1 : A\n",
" 98 1 0 1 0 1 <1> 0 1 0 1 0 1 0 1 : B\n",
" 99 1 0 1 0 1 0 <0> 1 0 1 0 1 0 1 : D\n"
]
}
],
"source": [
"run(day25, verbose=True, N_steps=100)"
]
},
{
"cell_type": "code",
"execution_count": 143,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 12994925 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 <0> 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 1 : D\n",
"number of 1s is 2846\n",
"elapsed sec 9.396818161010742\n"
]
}
],
"source": [
"starttime = time.time()\n",
"run(day25, verbose=False, N_steps = 12994925)\n",
"print('elapsed sec ', time.time() - starttime)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Answer to part 1 via brute force simulation is 2846."
]
},
{
"cell_type": "code",
"execution_count": 144,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# ... and apparently there is no part 2, just whether or not you've done the 1st 49."
]
}
],
"metadata": {
"anaconda-cloud": {},
"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.9.1"
}
},
"nbformat": 4,
"nbformat_minor": 2
}