Skip to content

Instantly share code, notes, and snippets.

@shaharz

shaharz/advent2018.ipynb

Last active April 5, 2021 14:38
Show Gist options
  • Save shaharz/7fd82b80b6d9db8aa0a6baa552a217ca to your computer and use it in GitHub Desktop.
Save shaharz/7fd82b80b6d9db8aa0a6baa552a217ca to your computer and use it in GitHub Desktop.
Download ZIP
Advent of Code 2018 solutions
Display the source blob
Display the rendered blob
Raw
advent2018.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import numpy as np\n",
"\n",
"def solve(input):\n",
" instr = input.split(\", \")\n",
" pos = np.array([0, 0])\n",
" heading = np.array([0, 1])\n",
" R = np.array([[0, -1], [1, 0]])\n",
" \n",
" visited = {tuple(pos)}\n",
"\n",
" for ins in instr:\n",
" heading = np.dot(heading, R if ins[0] == 'R' else -R)\n",
" for i in range(int(ins[1:])):\n",
" pos += heading\n",
" if tuple(pos) in visited:\n",
" return np.sum(np.absolute(pos))\n",
" \n",
" visited.add(tuple(pos))\n",
" \n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data = \"R5, L2, L1, R1, R3, R3, L3, R3, R4, L2, R4, L4, R4, R3, L2, L1, L1, R2, R4, R4, L4, R3, L2, R1, L4, R1, R3, L5, L4, L5, R3, L3, L1, L1, R4, R2, R2, L1, L4, R191, R5, L2, R46, R3, L1, R74, L2, R2, R187, R3, R4, R1, L4, L4, L2, R4, L5, R4, R3, L2, L1, R3, R3, R3, R1, R1, L4, R4, R1, R5, R2, R1, R3, L4, L2, L2, R1, L3, R1, R3, L5, L3, R5, R3, R4, L1, R3, R2, R1, R2, L4, L1, L1, R3, L3, R4, L2, L4, L5, L5, L4, R2, R5, L4, R4, L2, R3, L4, L3, L5, R5, L4, L2, R3, R5, R5, L1, L4, R3, L1, R2, L5, L1, R4, L1, R5, R1, L4, L4, L4, R4, R3, L5, R1, L3, R4, R3, L2, L1, R1, R2, R2, R2, L1, L1, L2, L5, L3, L1\"\n",
"solve(data)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 2"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"keypad = [[None, None, 1, None, None],\n",
" [None, 2, 3, 4, None],\n",
" [5,6,7,8,9],\n",
" [None,'A','B','C',None],\n",
" [None, None, 'D', None, None]]\n",
"ds = {'L': np.array([0,-1]),\n",
" 'R': np.array([0,1]),\n",
" 'U': np.array([-1,0]),\n",
" 'D': np.array([1,0])}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def solve(input):\n",
" data = input.split('\\n')\n",
" pos = np.array([2,0])\n",
" for s in data:\n",
" for d in s:\n",
" nxt = np.clip(pos + ds[d], 0, 4)\n",
" pos = nxt if keypad[nxt[0]][nxt[1]] else pos\n",
" yield str(keypad[pos[0]][pos[1]])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"assert \"\".join(solve(\"ULL\\nRRDDD\\nLURDL\\nUUUUD\")) == \"5DB3\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data = \"\"\"UULLULLUULLLURDLDUURRDRRLDURDULLRURDUDULLLUULURURLRDRRRRULDRUULLLLUUDURDULDRRDRUDLRRLDLUDLDDRURURUURRRDDDLLRUDURDULUULLRRULLRULDUDRDRLDLURURUDDUDLURUDUDURLURURRURLUDDRURRDLUURLLRURRDUDLULULUDULDLLRRRDLRDLDUDRDDDRRUURRRRRUURRDRRDLURDRRURDLLUULULLRURDLDDDRRLLRRUURULURUUDDLRRUDDRURUUDLRLRDLRURRRDULLDLRUDDUULRDULURUURDULUDLLRRLDDLRDLRUDRLDDRLRRRDURDULLRRRDRRLUURURDRRDRRLDLUDURURLDUURDRUDRDDRLDRRLDLURURULLUURUDUUDLRLL\n",
"LLLULLULDDULRLLURLLLRUUDDLRUULRLULLDLLRRDRLRLRLLDRUUURULDRDDLUDLLDUDULLLRLULLLRULDRDRUDLLRLRLLUDULRRRLDRUULDDULLDULULLUDUDLDRDURDLDLLDUDRRRDLUURRUURULLURLDURLRRLLDDUUULDRLUUDUDLURLULUDURRDRLLDDDDDRRULLRLDULULDDRUURRDLUDDDUDURDDRDRULULLLLUURDURUUUULUDLRURRULRDDRURURLLRLUUDUUURDLLDDLUDRLLLUDLLLLULRLURDRRRDUUDLLDLDDDURRDDRURUURDDRURRLDDDURDLLUURUUULRLUURRUDRLLDLURDUDRLULDLRLULULUDDLRDUDRUDLUULUULDURDRRRRLRULLUDRDDRDLDUDRDRRLDLLLLUDDLRULDLLDDUULDDRRULRRUURUDRDURLLLDDUUDRUUDLULLDR\n",
"UDUUULLDDDDLUDLDULRLRDLULLDDRULDURRLURRUDLRRUDURRDUDRRRUULRLLRLUDLDRRDUURDDRDRDUUUDUDLDLLRRLUURLUUUDDDUURLULURRLURRRDRDURURUDRLRUURUDRUDDDRDRDLDRDURDLDRRDUUDLLURLDDURRRLULDRDRLLRLLLRURLDURDRLDRUURRLDLDRLDDDRLDLRLDURURLLLLDDRDUDLRULULLRDDLLUDRDRRLUUULDRLDURURDUDURLLDRRDUULDUUDLLDDRUUULRRULDDUDRDRLRULUUDUURULLDLLURLRRLDDDLLDRRDDRLDDLURRUDURULUDLLLDUDDLDLDLRUDUDRDUDDLDDLDULURDDUDRRUUURLDUURULLRLULUURLLLLDUUDURUUDUULULDRULRLRDULDLLURDLRUUUDDURLLLLDUDRLUUDUDRRURURRDRDDRULDLRLURDLLRRDRUUUURLDRURDUUDLDURUDDLRDDDDURRLRLUDRRDDURDDRLDDLLRR\n",
"ULDRUDURUDULLUDUDURLDLLRRULRRULRUDLULLLDRULLDURUULDDURDUUDLRDRUDUDDLDRDLUULRRDLRUULULUUUDUUDDRDRLLULLRRDLRRLUDRLULLUUUUURRDURLLRURRULLLRLURRULRDUURRLDDRRDRLULDDRRDRLULLRDLRRURUDURULRLUDRUDLUDDDUDUDDUDLLRDLLDRURULUDRLRRULRDDDDDRLDLRRLUUDLUURRDURRDLDLDUDRLULLULRLDRDUDLRULLULLRLDDRURLLLRLDDDLLLRURDDDLLUDLDLRLUULLLRULDRRDUDLRRDDULRLLDUURLLLLLDRULDRLLLUURDURRULURLDDLRRUDULUURRLULRDRDDLULULRRURLDLRRRUDURURDURDULURULLRLDD\n",
"DURLRRRDRULDLULUDULUURURRLULUDLURURDDURULLRRUUDLRURLDLRUDULDLLRRULLLLRRLRUULDLDLLRDUDLLRLULRLLUUULULRDLDLRRURLUDDRRLUUDDRRUDDRRURLRRULLDDULLLURRULUDLRRRURRULRLLLRULLRRURDRLURULLDULRLLLULLRLRLLLDRRRRDDDDDDULUUDUDULRURDRUDRLUULURDURLURRDRRRRDRRLLLLUDLRRDURURLLULUDDLRLRLRRUURLLURLDUULLRRDURRULRULURLLLRLUURRULLLURDDDRURDUDDULLRULUUUDDRURUUDUURURRDRURDUDRLLRRULURUDLDURLDLRRRRLLUURRLULDDDUUUURUULDLDRLDUDULDRRULDRDULURRUURDU\"\"\"\n",
"\"\".join(solve(data))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 3"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data = open(\"day3.txt\").read().split('\\n')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import re\n",
"def check(tri):\n",
" tri = sorted(tri)\n",
"# print(tri)\n",
" return int(tri[0] + tri[1] > tri[2])\n",
"\n",
"tris = [list(map(int, re.findall(r'\\d+', x))) for x in data if x]\n",
"tris = np.rot90(tris).flatten()\n",
"\n",
"# sum(check(map(int, re.findall(r'\\d+', x))) for x in data if x)\n",
"sum(check(tris[x:x+3]) for x in range(0, len(tris), 3))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 4"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from scipy.stats import itemfreq\n",
"from functools import cmp_to_key"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import re\n",
"\n",
"def cmp(a, b): return (a>b)-(a<b)\n",
"\n",
"def comp(x, y):\n",
" res = cmp(int(x[1]), int(y[1]))\n",
" return res if res != 0 else cmp(ord(y[0]), ord(x[0]))\n",
"\n",
"def solve(input):\n",
" last_dash = input.rfind(\"-\")\n",
" checksum = re.findall(\"\\[(\\w+)\\]$\", input)[0]\n",
" freqs = sorted(itemfreq(list(re.sub(r'-', '', input[:last_dash]))), key=cmp_to_key(comp), reverse=True)[:5]\n",
" return checksum == ''.join(map(lambda x: x[0], freqs))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"assert solve(\"a-b-c-d-e-f-g-h-987[abcde]\")\n",
"assert solve(\"aaaaa-bbb-z-y-x-123[abxyz]\")\n",
"assert solve(\"not-a-real-room-404[oarel]\")\n",
"assert solve(\"totally-real-room-200[decoy]\") == False"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data = open(\"day4.txt\").read().split('\\n')[:-1]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def sector(room): return int(re.findall(r'(\\d+)\\[\\w+\\]$', room)[0])\n",
"real_rooms = [line for line in data if solve(line)]\n",
"sum(sector(room) for room in real_rooms)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def shift(s, by):\n",
" return ''.join([chr((ord(c) - ord('a') + by) % (ord('z')-ord('a')+1) + ord('a')) for c in list(s)])\n",
"next(filter(lambda room: \"north\" in shift(re.sub(r'-', '', room[:-11]), sector(room)), real_rooms))\n",
"# [shift(re.sub(r'-', '', room[:-11]), sector(room)) for room in real_rooms[:15]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 5"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from hashlib import md5"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"p = [None]*8\n",
"i = 0\n",
"found = 0\n",
"while found < 8 and i < 1e8:\n",
" d = md5(b\"ojvtpuvg\" + bytes(str(i).encode('utf-8'))).hexdigest()\n",
" if d.startswith('00000'):\n",
" try:\n",
" idx = int(d[5])\n",
" if idx >= 0 and idx < len(p) and p[idx] == None:\n",
" p[idx] = d[6]\n",
" found = found + 1\n",
" except ValueError:\n",
" pass\n",
" i = i + 1\n",
"print(''.join(p), i)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"p"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 6"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"data = open(\"day6.txt\").read().split('\\n')[:-1]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"arr2d = np.array([np.array(list(l)) for l in data])\n",
"def solve(l):\n",
" (values,counts) = np.unique(l,return_counts=True)\n",
" ind=np.argmin(counts)\n",
" return values[ind]\n",
"\n",
"''.join(reversed(list(map(solve, np.rot90(arr2d)))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 7"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import re\n",
"regex = re.compile('(\\w+)(?:\\[(\\w+)\\])?')\n",
"\n",
"def check_abba(s):\n",
" for i in range(len(s) - 3):\n",
" if s[i] == s[i + 3] and s[i] != s[i+1] and s[i+1] == s[i+2]:\n",
" return True\n",
" return False\n",
"\n",
"def solve(input):\n",
" parts = regex.findall(input)\n",
" if any(check_abba(p[1]) for p in parts):\n",
" return False\n",
" \n",
" return any(check_abba(p[0]) for p in parts)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data = open(\"day7.txt\").read().split('\\n')[:-1]\n",
"sum(solve(l) for l in data)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def find_abas(s):\n",
" for i in range(len(s) - 2):\n",
" if s[i] == s[i + 2] and s[i] != s[i+1]:\n",
" yield s[i+1] + s[i] + s[i+1] # ABA->BAB\n",
"\n",
"def flatten(z): return (x for y in z for x in y)\n",
"\n",
"def solve2(input):\n",
" parts = regex.findall(input)\n",
" BABs = flatten(find_abas(p[1]) for p in parts)\n",
" return any(BAB in p[0] for BAB in BABs for p in parts)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data = open(\"day7.txt\").read().split('\\n')[:-1]\n",
"sum(solve2(l) for l in data)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 8"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import numpy as np\n",
"import re"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"screen = np.zeros((6, 50), dtype=np.bool)\n",
"parser = re.compile(\"(rect|rotate)\\s(row|column|(?:(\\d+)x(\\d+)))(?:\\s[yx]=(\\d+)\\sby\\s(\\d+))?\")\n",
"\n",
"def reset(): screen.fill(False)\n",
"def rect(w,h): screen[:w,:h] = True\n",
"def rotate_row(row, shift): screen[row,:] = np.roll(screen[row,:], shift)\n",
"def rotate_col(col, shift): screen[:,col] = np.roll(screen[:,col], shift)\n",
"\n",
"def parse(s):\n",
" g = parser.match(s).groups()\n",
" if g[0] == \"rect\":\n",
" rect(int(g[3]), int(g[2]))\n",
" elif g[1] == \"row\":\n",
" rotate_row(int(g[4]), int(g[5]))\n",
" elif g[1] == \"column\":\n",
" rotate_col(int(g[4]), int(g[5]))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data = open(\"day8.txt\").read().split('\\n')[:-1]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"reset()\n",
"for d in data: parse(d)\n",
"[''.join(list('#' if x else '.' for x in s)) for s in screen]\n",
"# np.count_nonzero(screen)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# ds = [\"rect 4x1\",\n",
"# \"rotate row y=2 by 13\",\n",
"# \"rotate row y=0 by 5\"]\n",
"# import re\n",
"# [re.match(\"(rect|rotate)\\s(row|column|(?:(\\d+)x(\\d+)))(?:\\s[yx]=(\\d)\\sby\\s(\\d+))?\", d).groups() for d in ds]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 9"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import re"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"re_comp = re.compile(r'\\((\\d+)x(\\d+)\\)')\n",
"\n",
"def decompress(data):\n",
" pos = 0\n",
" while True:\n",
" m = re_comp.search(data[pos:])\n",
" if not m: break\n",
" n, times = [int(n) for n in m.groups()]\n",
" yield data[pos:pos+m.start()]\n",
" yield decompress(data[pos+m.end():pos+m.end()+n]*times)\n",
" pos = pos + m.end() + n\n",
" yield data[pos:]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"assert ''.join(decompress(\"X(8x2)(3x3)ABCY\")) == \"X(3x3)ABC(3x3)ABCY\"\n",
"assert ''.join(decompress(\"A(1x5)BC\")) == \"ABBBBBC\"\n",
"assert ''.join(decompress(\"(3x3)XYZ\")) == \"XYZXYZXYZ\"\n",
"assert ''.join(decompress(\"A(2x2)BCD(2x2)EFG\")) == \"ABCBCDEFEFG\"\n",
"assert ''.join(decompress(\"(6x1)(1x3)A\")) == \"(1x3)A\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data = open(\"day9.txt\").read()\n",
"data = re.sub(r'\\s', '', data)\n",
"# inefficient solution (only length needed) ¯\\_(ツ)_/¯\n",
"%time sum(len(chunk) for chunk in decompress(data))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 10"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"data = open(\"day10.txt\").read().split('\\n')[:-1]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data[40:60]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import re\n",
"from collections import defaultdict"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"bots = defaultdict(list)\n",
"instr = defaultdict(list)\n",
"for line in data:\n",
" if line.startswith('value'):\n",
" v, b = re.findall(r'\\d+', line)\n",
" bots[b].append(int(v))\n",
" else:\n",
" m = re.match(r'bot (\\d+) gives low to (\\w+) (\\d+) and high to (\\w+) (\\d+)', line).groups()\n",
" instr[m[0]].append(m)\n",
"\n",
"while True:\n",
" try:\n",
" b = next(b for b in bots if len(bots[b]) == 2)\n",
" except StopIteration:\n",
" print(\"done?\")\n",
" break\n",
"\n",
" _, dl, nl, dh, nh = instr[b][0]\n",
" instr[b] = instr[b][1:]\n",
" l, h = sorted(bots[b])\n",
"\n",
" del bots[b]\n",
"# print(dl, nl, dh, nh)\n",
" if dl == 'bot':\n",
" bots[nl].append(l)\n",
" elif dl == 'output':\n",
" print('output', nl, l)\n",
" if dh == 'bot':\n",
" bots[nh].append(h)\n",
" elif dh == 'output':\n",
" print('output', nh, h)\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"# Day 11"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Test\n",
"The first floor contains a hydrogen-compatible microchip and a lithium-compatible microchip.\n",
"The second floor contains a hydrogen generator.\n",
"The third floor contains a lithium generator.\n",
"The fourth floor contains nothing relevant."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Input\n",
"The first floor contains a thulium generator, a thulium-compatible microchip, a plutonium generator, and a strontium generator.\n",
"\n",
"The second floor contains a plutonium-compatible microchip and a strontium-compatible microchip.\n",
"The third floor contains a promethium generator, a promethium-compatible microchip, a ruthenium generator, and a ruthenium-compatible microchip.\n",
"The fourth floor contains nothing relevant."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"### SLOW\n",
"from collections import defaultdict, namedtuple\n",
"from copy import deepcopy\n",
"from itertools import chain, combinations\n",
"from heapq import *\n",
"\n",
"BaseDist = namedtuple('Dist', ['elev', 'fs', 'dist', 'parent'])\n",
"\n",
"class Dist(BaseDist):\n",
" def __hash__(self):\n",
" return hash(str(self.elev) + str(self.fs))\n",
" def __lt__(self, other):\n",
" return hash(self) < hash(other)\n",
" \n",
"# Contents = namedtuple('Contents', ['M', 'G'])\n",
"initial = Dist(\n",
" 0,\n",
" [\n",
" {'M': frozenset(['H', 'L']), 'G': frozenset()},\n",
" {'G': frozenset(['H']), 'M': frozenset()},\n",
" {'G': frozenset(['L']), 'M': frozenset()},\n",
" {'M': frozenset(), 'G': frozenset()}\n",
" ],\n",
" 0,\n",
" None\n",
")\n",
"\n",
"cat = ''.join\n",
" \n",
"def prn(dist):\n",
" for i, v in enumerate(reversed(dist.fs)):\n",
" curfl = dist.elev == 3-i\n",
" print(4-i, ' E'[curfl], 'M' + cat(v['M']) , 'G' + cat(v['G']))\n",
" if dist.parent:\n",
" print(\"##############\")\n",
" prn(dist.parent)\n",
"\n",
"# can't get on elevator empty handed\n",
"# elevator capacity = 2\n",
"# XG + YM = bad\n",
"# XG + XM = protected from other YG\n",
"# can pass through floor with XG if holding XM\n",
"def valid(ms, gs): return not gs or not (ms - gs)\n",
"def valid_move(cur, move, dms, dgs):\n",
" return valid(cur.fs[cur.elev]['M']-dms, cur.fs[cur.elev]['G']-dgs) \\\n",
" and valid(cur.fs[cur.elev+move]['M']|dms, cur.fs[cur.elev+move]['G']|dgs)\n",
" \n",
"\n",
"def gen_elev(cur, dms, dgs, queue, visited):\n",
" # move elevator down\n",
" \n",
" if cur.elev > 0 and valid_move(cur, -1, dms, dgs):\n",
" new_fs = deepcopy(cur.fs)\n",
" new_fs[cur.elev]['M'] -= dms\n",
" new_fs[cur.elev-1]['M'] |= dms\n",
" new_fs[cur.elev]['G'] -= dgs\n",
" new_fs[cur.elev-1]['G'] |= dgs\n",
" if not hash(str(cur.elev-1) + str(new_fs)) in visited:\n",
" res = Dist(\n",
" fs=new_fs,\n",
" dist=cur.dist+1,\n",
" elev=cur.elev-1,\n",
" parent=None\n",
" )\n",
" heappush(queue, (heuristic(res), res))\n",
"\n",
" # move elevator up\n",
" if cur.elev < 3 and valid_move(cur, 1, dms, dgs):\n",
" new_fs = deepcopy(cur.fs)\n",
" new_fs[cur.elev]['M'] -= dms\n",
" new_fs[cur.elev+1]['M'] |= dms\n",
" new_fs[cur.elev]['G'] -= dgs\n",
" new_fs[cur.elev+1]['G'] |= dgs\n",
" if not hash(str(cur.elev-1) + str(new_fs)) in visited:\n",
" res = Dist(\n",
" fs=new_fs,\n",
" dist=cur.dist+1,\n",
" elev=cur.elev+1,\n",
" parent=None\n",
" )\n",
" heappush(queue, (heuristic(res), res))\n",
"\n",
" \n",
"def powerset(iterable, mn, mx):\n",
" \"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)\"\n",
" s = list(iterable)\n",
" return chain.from_iterable(combinations(s, r) for r in range(mn, mx+1))\n",
"\n",
"def heuristic(d):\n",
" return d.dist - (len(d.fs[3]['M']) + len(d.fs[3]['G'])) * 5\n",
"\n",
"def search(initial):\n",
" visited = set()\n",
" queue = []\n",
" heappush(queue, (heuristic(initial), initial))\n",
" while queue:\n",
" _, cur = heappop(queue)\n",
" visited.add(hash(cur))\n",
"# print(visited)\n",
" if not any(f['G'] or f['M'] for f in cur.fs[:3]):\n",
" print(\"match\", cur.dist)\n",
" continue\n",
" \n",
" yield cur\n",
" \n",
" ms = cur.fs[cur.elev]['M']\n",
" gs = cur.fs[cur.elev]['G']\n",
" lms = len(ms)\n",
" lgs = len(gs)\n",
" if lms > 1:\n",
" for s in powerset(ms, 1, 2): gen_elev(cur, set(s), set(), queue, visited)\n",
" if lgs > 1:\n",
" for s in powerset(gs, 1, 2): gen_elev(cur, set(), set(s), queue, visited)\n",
" if lms > 0:\n",
" for m in ms: gen_elev(cur, {m}, set(), queue, visited)\n",
" if lgs > 0:\n",
" for g in gs: gen_elev(cur, set(), {g}, queue, visited)\n",
" if lms > 0 and lgs > 0:\n",
" for m,g in ((m,g) for m in ms for g in gs): gen_elev(cur, {m}, {g}, queue, visited)\n",
" "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"test = Dist(\n",
" 0,\n",
" [\n",
" {'M': frozenset(['T', 'E', 'D']), 'G': frozenset(['T', 'PL', 'S', 'E', 'D'])},\n",
" {'M': frozenset(['PL', 'S']), 'G': frozenset()},\n",
" {'M': frozenset(['PR','R']), 'G': frozenset(['PR', 'R'])},\n",
" {'M': frozenset(), 'G': frozenset()}\n",
" ],\n",
" 0,\n",
" None\n",
")\n",
"\n",
"s = search(test)\n",
"max_d = 0"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false,
"scrolled": false
},
"outputs": [],
"source": [
"while True:\n",
" c = next(s)\n",
" if max_d < c.dist:\n",
" if max_d > 70: break\n",
" max_d = c.dist\n",
" print(max_d)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 12"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data = open(\"day12.txt\").read().split('\\n')\n",
"# data = \"\"\"cpy 41 a\n",
"# inc a\n",
"# inc a\n",
"# dec a\n",
"# jnz a 2\n",
"# dec a\"\"\".split('\\n')\n",
"\n",
"def r2i(r): return ord(r) - ord('a')\n",
"\n",
"def parse(d):\n",
" regs = [0, 0, 1, 0]\n",
" ip = 0\n",
" while ip < len(data):\n",
" ins = data[ip].split(' ')\n",
" yield ins, regs\n",
" if ins[0] == 'cpy':\n",
" regs[r2i(ins[2])] = int(ins[1]) if ins[1].isdigit() else regs[r2i(ins[1])]\n",
" elif ins[0] == 'inc':\n",
" regs[r2i(ins[1])] += 1\n",
" elif ins[0] == 'dec':\n",
" regs[r2i(ins[1])] -= 1\n",
" elif ins[0] == 'jnz':\n",
" if (ins[1].isdigit() and ins[1] != 0) or regs[r2i(ins[1])]:\n",
" ip += int(ins[2])\n",
" continue\n",
" ip += 1\n",
" yield regs"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"p = parse(data)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"while True:\n",
" try:\n",
" r = next(p)\n",
" except StopIteration:\n",
" print(r)\n",
" break"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"# Day 13"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import numpy as np\n",
"\n",
"POPCOUNT_TABLE16 = [0] * 2**16\n",
"for index in range(len(POPCOUNT_TABLE16)):\n",
" POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]\n",
"\n",
"def popcount32_table16(v):\n",
" return (POPCOUNT_TABLE16[ v & 0xffff] +\n",
" POPCOUNT_TABLE16[(v >> 16) & 0xffff])\n",
"\n",
"def wall(v):\n",
" return popcount32_table16(v) % 2"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from heapq import *\n",
"magic = 1350\n",
"\n",
"x,y = np.indices((2500,2500))\n",
"maze = np.rot90(np.fliplr(np.vectorize(wall)(x*x + 3*x + 2*x*y + y + y*y + magic)))\n",
"\n",
"def heuristic(a, b): return b[0]-a[0]+b[1]-a[1]\n",
"\n",
"dirs = [np.array([1,0]), np.array([0,1]), np.array([-1,0]), np.array([0, -1])]\n",
" \n",
"def shortest_path(a, b):\n",
" queue = []\n",
" heappush(queue, (heuristic(a, b), 0, a))\n",
" maze[a] = 2 # visited\n",
" while queue:\n",
" _, sofar, pt = heappop(queue)\n",
" print(pt)\n",
" if pt == b:\n",
" print(\"done\", sofar)\n",
" return\n",
" \n",
" for offs in dirs:\n",
" nextpt = tuple(np.clip(pt + offs, 0, maze.shape[0]-1))\n",
" if not maze[nextpt]:\n",
" maze[nextpt] = 2 # visited\n",
"# print(\"inserting\", sofar + heuristic(nextpt, b), sofar + 1, nextpt)\n",
" heappush(queue, (sofar + heuristic(nextpt, b), sofar + 1, nextpt))\n",
"# yield queue\n",
" \n",
"def reachable(a, max_steps):\n",
" queue = []\n",
" heappush(queue, (0, 0, a))\n",
" maze[a] = 2 # visited\n",
" while queue:\n",
" _, sofar, pt = heappop(queue)\n",
" \n",
" if sofar == max_steps: return\n",
" for offs in dirs:\n",
" nextpt = tuple(np.clip(pt + offs, 0, maze.shape[0]-1))\n",
" if not maze[nextpt]:\n",
" maze[nextpt] = 2 # visited\n",
"# print(\"inserting\", sofar + heuristic(nextpt, b), sofar + 1, nextpt)\n",
" heappush(queue, (0, sofar + 1, nextpt))\n",
"# yield queue\n",
"\n",
"# [''.join('.#O'[y] for y in x) for x in maze]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"target = (39,31)\n",
"start = (1,1)\n",
"\n",
"# shortest_path(start, target)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"maze[target] = 3\n",
"[''.join(('.#OX'[y]) for y in x) for x in maze]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"reachable(start, 50)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"np.count_nonzero(maze == 2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 14"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from hashlib import md5\n",
"from collections import deque"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"hexd = ['{:x}'.format(d) for d in range(0, 16)]\n",
"repeats3 = [d*3 for d in hexd]\n",
"repeats5 = [d*5 for d in hexd]\n",
"\n",
"def solve(salt):\n",
" last1000 = deque([], 1000)\n",
" i = 0\n",
" found = set()\n",
" while True:\n",
" h = md5(salt + bytes(str(i), 'utf-8')).hexdigest()\n",
" for _ in range(2016):\n",
" h = md5(bytes(h,'utf-8')).hexdigest()\n",
" match = [r[0] for r in repeats5 if r in h]\n",
" if match:\n",
" print(i, h, match)\n",
" for i2,h2 in last1000:\n",
" match3 = match[0]*3\n",
" ma = h2.find(match3)\n",
" repeat3 = all(h2.find(r) > ma for r in repeats3 if r != match3 and r in h2)\n",
" if i2 == 15578: print(\"ASDFSDFD\", h2, ma, repeat3, (i2 not in found))\n",
" if ma > -1 and repeat3 and (i2 not in found):\n",
" n = len(found)\n",
" print(n, i2,h2)\n",
" if n == 80:\n",
" return found\n",
" found.add(i2)\n",
" last1000.append((i,h))\n",
"\n",
"# yield from ((i2,h2) for (i2,h2) in last1000 if repeat3 in h2)\n",
" i += 1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"x = solve(b'qzyelonm')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"sorted(x)[63]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 15"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"input = \"\"\"Disc #1 has 17 positions; at time=0, it is at position 1.\n",
"Disc #2 has 7 positions; at time=0, it is at position 0.\n",
"Disc #3 has 19 positions; at time=0, it is at position 2.\n",
"Disc #4 has 5 positions; at time=0, it is at position 0.\n",
"Disc #5 has 3 positions; at time=0, it is at position 0.\n",
"Disc #6 has 13 positions; at time=0, it is at position 5.\n",
"Disc #7 has 11 positions; at time=0, it is at position 0.\n",
"\"\"\"\n",
"\n",
"import re\n",
"lines = input.split('\\n')[:-1]\n",
"npo = [[int(n) for n in re.match(r'Disc #(\\d) has (\\d+) positions; at time=0, it is at position (\\d).', line).groups()] for line in lines]\n",
"\n",
"def l(n,p,o): return lambda t: ((t+n+o) % p)\n",
"fs = [l(n,p,o) for i, (n, p, o) in enumerate(npo)]\n",
"for t in range(1, 10000000):\n",
" if all(f(t) == 0 for f in fs):\n",
" print(t)\n",
" break"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 16"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def flip(input): return ['01'[c == '0'] for c in reversed(input)]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def checksum(input):\n",
" return [str(int(input[i]==input[i+1])) for i in range(0,len(input),2)]\n",
"\n",
"def go(input, l):\n",
" output = input\n",
" while len(output) < l:\n",
" output = output + ['0'] + flip(output)\n",
" cs = checksum(output[:l])\n",
" while len(cs) % 2 == 0:\n",
" cs = checksum(cs)\n",
" return ''.join(cs)\n",
" "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# l = 20\n",
"# initial = list('10000')\n",
"\n",
"go(list('10011111011011001'), 35651584)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 17"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from hashlib import md5\n",
"from collections import deque"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def hsh(salt, path): return md5(bytes(salt + path, 'utf-8')).hexdigest()\n",
"def opendirs(hsh): return [c in 'bcdef' for c in hsh[:4]]\n",
"\n",
"def solve(passcode):\n",
" queue = [((0,0), '')]\n",
" maxpath = ''\n",
"\n",
" while queue:\n",
" (x,y), path = queue.pop()\n",
" if (x,y) == (3,3):\n",
" if len(path) > len(maxpath):\n",
" maxpath = path\n",
" if len(maxpath) >= 300 or len(maxpath) % 100 == 0: print(len(maxpath))\n",
" continue\n",
" \n",
" uok,dok,lok,rok = opendirs(hsh(passcode, path))\n",
" \n",
" if x < 3 and rok:\n",
" newpath = path + 'R'\n",
" queue.append(((x+1,y), newpath))\n",
" if x > 0 and lok:\n",
" newpath = path + 'L'\n",
" queue.append(((x-1,y), newpath))\n",
" if y < 3 and dok:\n",
" newpath = path + 'D'\n",
" queue.append(((x,y+1), newpath))\n",
" if y > 0 and uok:\n",
" newpath = path + 'U'\n",
" queue.append(((x,y-1), newpath))\n",
" return maxpath"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"solve('yjjvjgan')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 18"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"is_trap = ['^^.','.^^','^..','..^']\n",
"\n",
"def next_row(prev_row):\n",
" prev = '.' + prev_row + '.'\n",
"# print([prev[i-1:i+2] for i in range(1,len(prev)-1)])\n",
" return ''.join('^' if prev[i-1:i+2] in is_trap else '.' for i in range(1,len(prev)-1))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"r = '......^.^^.....^^^^^^^^^...^.^..^^.^^^..^.^..^.^^^.^^^^..^^.^.^.....^^^^^..^..^^^..^^.^.^..^^..^^^..'\n",
"safe = 0\n",
"for _ in range(400000):\n",
"# print(r)\n",
" safe += r.count('.')\n",
" r = next_row(r)\n",
"print(safe)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 19"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def run(elves): \n",
" N = len(elves)\n",
" eliminated = 0\n",
" for i in range(int(math.ceil(N / 3))):\n",
" across = i + eliminated + (N // 2) \n",
" elves[across] = None\n",
" N -= 1\n",
" eliminated += 1\n",
" return list(filter(None, elves[i+1:] + elves[:i+1]))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def runall(n):\n",
" l = list(range(1,n+1))\n",
" while len(l) > 1:\n",
" l = run(l)\n",
" return l\n",
"\n",
"runall(3005290)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# list(filter(lambda x: x, [n if runall(n) == 0 else None for n in range(4,140)]))\n",
"[(n,runall(n)) for n in range(4,40)]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"seed = 3005290\n",
"import math\n",
"# [(n, 2*(n - 2**math.floor(math.log(n)/math.log(2)))) for n in range(4,20)]\n",
"2*(seed - 2**math.floor(math.log(seed)/math.log(2)))+1 # +1 so it's one-based"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 20"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from operator import itemgetter\n",
"from itertools import tee\n",
"\n",
"def pairwise(iterable):\n",
" \"s -> (s0,s1), (s1,s2), (s2, s3), ...\"\n",
" a, b = tee(iterable)\n",
" next(b, None)\n",
" return zip(a, b)\n",
"\n",
"def split(l):\n",
" s = l.split('-')\n",
" return (int(s[0]), int(s[1]))\n",
"\n",
"def go(lines):\n",
" lastcomp = None\n",
" for (sa, sb),(sc, sd) in pairwise(sorted((split(l) for l in lines), key=itemgetter(0))):\n",
" if lastcomp:\n",
" (sa,sb) = lastcomp\n",
" \n",
" if sb > sd:\n",
" lastcomp = (sa,sb)\n",
" else: lastcomp = None\n",
" \n",
" if sb + 1 < sc:\n",
" yield (sc - (sb + 1))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data = open(\"day20.txt\").read().split('\\n')[:-1]\n",
"# go(data)\n",
"sum(go(data)) + 4294967295 - (sorted((split(l) for l in data), key=itemgetter(1))[-1][1])\n",
"# print(list(sorted((split(l) for l in data), key=itemgetter(0))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 21"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"swap position X with position Y means that the letters at indexes X and Y (counting from 0) should be swapped. \n",
"swap letter X with letter Y means that the letters X and Y should be swapped (regardless of where they appear in the string). \n",
"rotate left/right X steps means that the whole string should be rotated; for example, one right rotation would turn abcd into dabc. \n",
"rotate based on position of letter X means that the whole string should be rotated to the right based on the index of letter X (counting from 0) as determined before this instruction does any rotations. Once the index is determined, rotate the string to the right one time, plus a number of times equal to that index, plus one additional time if the index was at least 4. \n",
"reverse positions X through Y means that the span of letters at indexes X through Y (including the letters at X and Y) should be reversed in order. \n",
"move position X to position Y means that the letter which is at index X should be removed from the string, then inserted such that it ends up at index Y. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def go(line, input):\n",
" parts = line.split(' ')\n",
" if parts[0] == 'swap':\n",
" x,y = parts[2], parts[5]\n",
" if parts[1] == 'letter':\n",
" x,y = input.find(x), input.find(y)\n",
" else:\n",
" x,y = int(x), int(y)\n",
" l = list(input)\n",
" l[x], l[y] = l[y], l[x]\n",
" input = ''.join(l)\n",
" elif parts[0] == 'rotate':\n",
" l = len(input)\n",
" if parts[1] == 'based':\n",
" r = input.find(parts[6])\n",
" r = l - (1 + (r + 1 if r >= 4 else r) % l)\n",
" else:\n",
" r = int(parts[2]) % l\n",
" if parts[1] == 'right': r = l - r\n",
" input = input[r:] + input[:r]\n",
" elif parts[0] == 'reverse':\n",
" a,b = int(parts[2]), int(parts[4])\n",
" input = input[:a] + ''.join(reversed(input[a:b+1])) + input[b+1:]\n",
" elif parts[0] == 'move':\n",
" a,b = int(parts[2]), int(parts[5])\n",
" if a < b: \n",
" input = input[:a] + input[a+1:b+1] + input[a] + input[b+1:]\n",
" else:\n",
" input = input[:b] + input[a] + input[b:a] + input[a+1:]\n",
" return input"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"assert go('swap position 4 with position 0', 'abcde') == 'ebcda'\n",
"assert go('swap letter d with letter b', 'ebcda') == 'edcba'\n",
"assert go('reverse positions 0 through 4', 'edcba') == 'abcde'\n",
"assert go('rotate left 1 step', 'abcde') == 'bcdea'\n",
"assert go('move position 1 to position 4', 'bcdea') == 'bdeac'\n",
"assert go('move position 3 to position 0', 'bdeac') == 'abdec'\n",
"assert go('rotate based on position of letter b', 'abdec') == 'ecabd'\n",
"assert go('rotate based on position of letter d', 'ecabd') == 'decab'"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"data = open(\"day21.txt\").read().split('\\n')[:-1]\n",
"def scramble(p):\n",
" for l in data:\n",
" p = go(l, p)\n",
" return pwd\n",
"\n",
"scramble('abcdefgh')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 22"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import re\n",
"from collections import namedtuple\n",
"Node = namedtuple('Node', ['pos', 'size', 'used', 'avail'])\n",
"data = open(\"day22.txt\").read().split('\\n')[2:-1]\n",
"# data = \"\"\"/dev/grid/node-x0-y0 10T 8T 2T 80%\n",
"# /dev/grid/node-x0-y1 11T 6T 5T 54%\n",
"# /dev/grid/node-x0-y2 32T 28T 4T 87%\n",
"# /dev/grid/node-x1-y0 9T 7T 2T 77%\n",
"# /dev/grid/node-x1-y1 8T 0T 8T 0%\n",
"# /dev/grid/node-x1-y2 11T 7T 4T 63%\n",
"# /dev/grid/node-x2-y0 10T 6T 4T 60%\n",
"# /dev/grid/node-x2-y1 9T 8T 1T 88%\n",
"# /dev/grid/node-x2-y2 9T 6T 3T 66%\"\"\".split('\\n')\n",
"\n",
"def parse(line):\n",
" name,size,used,avail,_ = re.split(r'\\s+', line)\n",
" y,x = re.match(r'/dev/grid/node-x(\\d+)-y(\\d+)', name).groups()\n",
" return Node((int(x),int(y)), int(size[:-1]), int(used[:-1]), int(avail[:-1]))\n",
"\n",
"nodes = [parse(line) for line in data]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from itertools import permutations\n",
"sum((ua and ab >= ua) for (_,_,ua,aa),(_,_,ub,ab) in permutations(nodes, 2))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import numpy as np\n",
"my, mx = max(nodes, key=lambda x: x[0])[0]\n",
"grid = np.zeros((my+1,mx+1), dtype='O')\n",
"for node in nodes:\n",
" grid[node[0]] = node"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"grid[0,0],grid[0,mx]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"sorted(nodes, key=lambda x: x[2]/x[1])[0]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def draw(x):\n",
" if x.pos == (0,mx):\n",
" return 'G'\n",
" if x.size > 100:\n",
" return '#'\n",
" if x.used == 0:\n",
" return '_'\n",
" return '.'\n",
"[''.join(draw(x) for x in y) for y in grid]\n",
"# grid[mx,0].used, [n for n in nodes if n.avail > grid[mx,0].used]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from heapq import *\n",
"\n",
"def heuristic(a, b):\n",
" return abs(a.pos[0] - b.pos[0]) + abs(a.pos[1] - b.pos[1])\n",
"\n",
"def search(start, goal, banned=None):\n",
" queue = []\n",
" heappush(queue, (heuristic(start, goal), start, [start]))\n",
" visited = set()\n",
" while queue:\n",
" _, n, ns = heappop(queue)\n",
" if n.pos == goal.pos:\n",
" return ns #, len(ns))\n",
" if n == banned: continue\n",
"# yield n\n",
" for d in [(1,0),(0,1),(-1,0),(0,-1)]:\n",
" p = np.array(n.pos)+d\n",
" if any(p < (0,0)) or any(p > (my,mx)): continue\n",
" nn = grid[tuple(p)]\n",
"# if nn.used > n.size: print(n.pos, nn.pos)\n",
" if not nn.pos in visited and nn.used <= n.size:\n",
" visited.add(nn.pos)\n",
"# print(nn.pos, heuristic(nn, goal))\n",
" heappush(queue, (heuristic(nn, goal), nn, ns + [nn]))\n",
" return visited"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"move1 = search(grid[6,19], grid[0,mx])\n",
"free = grid[0,mx]\n",
"G = move1[-2]\n",
"\n",
"total = len(move1)\n",
"nextfree = grid[G.pos[0], G.pos[1]-1]\n",
"while nextfree.pos != (0,0):\n",
" nextfree = grid[G.pos[0], G.pos[1]-1]\n",
" print(\"moving {} to {}\".format(free.pos, nextfree.pos))\n",
" move = search(free, nextfree, G)\n",
" free = G\n",
" G = nextfree\n",
" total += len(move)\n",
"total-1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 23"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# data = open(\"day12.txt\").read().split('\\n')\n",
"data = \"\"\"cpy a b\n",
"dec b\n",
"cpy a d\n",
"cpy 0 a\n",
"cpy b c\n",
"inc a\n",
"dec c\n",
"jnz c -2\n",
"dec d\n",
"jnz d -5\n",
"dec b\n",
"cpy b c\n",
"cpy c d\n",
"dec d\n",
"inc c\n",
"jnz d -2\n",
"tgl c\n",
"cpy -16 c\n",
"jnz 1 c\n",
"cpy 74 c\n",
"jnz 88 d\n",
"inc a\n",
"inc d\n",
"jnz d -2\n",
"inc c\n",
"jnz c -5\"\"\".splitlines()\n",
"\n",
"def r2i(r): return ord(r) - ord('a')\n",
"\n",
"def parse(d):\n",
" d = [[(x if x.isalpha() else int(x)) for x in line.split()] for line in d]\n",
" regs = dict(a=12, b=0, c=0, d=0)\n",
" ip = 0\n",
" def idtoval(x): return (regs[x] if x in regs else x)\n",
" total_len = len(d)\n",
" while 0 <= ip < total_len:\n",
" ins = d[ip]\n",
" yield ip, ins, regs\n",
" if ins[0] == 'cpy':\n",
" if ins[2] in regs:\n",
" regs[ins[2]] = idtoval(ins[1])\n",
" elif ins[0] == 'inc':\n",
" regs[ins[1]] += 1\n",
" elif ins[0] == 'dec':\n",
" regs[ins[1]] -= 1\n",
" elif ins[0] == 'jnz':\n",
" if idtoval(ins[1]):\n",
" ip += idtoval(ins[2])\n",
" continue\n",
" elif ins[0] == 'tgl':\n",
" offs = ip + idtoval(ins[1])\n",
" if 0 <= offs < total_len:\n",
" if d[offs][0] in ['dec', 'tgl']:\n",
" d[offs][0] = 'inc'\n",
" elif d[offs][0] == 'inc':\n",
" d[offs][0] = 'dec'\n",
" elif d[offs][0] == 'jnz':\n",
" d[offs][0] = 'cpy'\n",
" else:\n",
" d[offs][0] = 'jnz'\n",
" ip += 1\n",
" yield regs"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"p = parse(data)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"while True:\n",
" try:\n",
" r = next(p)\n",
"# print(r[0])\n",
" except StopIteration:\n",
" print(r)\n",
" break"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 24"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from heapq import *\n",
"\n",
"def heuristic(pos, visited):\n",
" return 8 - len(visited) + abs(pos[0] - zero[0]) + abs(pos[1] - zero[1])\n",
"\n",
"def search(start):\n",
" queue = []\n",
" heappush(queue, (0, (start, '0'), []))\n",
" path_cost = {(start, '0'): 0}\n",
" while queue:\n",
" _, s0, path = heappop(queue)\n",
" ((x0,y0), visited) = s0\n",
"\n",
" for x1,y1 in [(1,0),(0,1),(-1,0),(0,-1)]:\n",
" c = maze[y0+y1][x0+x1]\n",
" if c != '#':\n",
" new_cost = path_cost[s0] + 1\n",
" visited1 = (visited if c == '.' or c in visited else ''.join(sorted(visited + c)))\n",
" s1 = ((x0+x1, y0+y1), visited1)\n",
" if s1 not in path_cost or new_cost < path_cost[s1]:\n",
"# print(path, visited1)\n",
" path1 = path + [s1[0]]\n",
" h = heuristic(s1[0], visited1)\n",
" if h == 0: return path1, len(path1), visited1\n",
" path_cost[s1] = new_cost\n",
" heappush(queue, (h + path_cost[s1], (s1[0], visited1), path1))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"maze = open(\"day24.txt\").read().splitlines()\n",
"# maze = \"\"\"###########\n",
"# #0.1.....2#\n",
"# #.#######.#\n",
"# #4.......3#\n",
"# ###########\"\"\".splitlines()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"zero = next((x, y) for y, row in enumerate(maze) for x, c in enumerate(row) if c == '0')\n",
"search(zero)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 25"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# data = open(\"day12.txt\").read().split('\\n')\n",
"data = \"\"\"cpy a d\n",
"cpy 11 c\n",
"cpy 231 b\n",
"inc d\n",
"dec b\n",
"jnz b -2\n",
"dec c\n",
"jnz c -5\n",
"cpy d a\n",
"jnz 0 0\n",
"cpy a b\n",
"cpy 0 a\n",
"cpy 2 c\n",
"jnz b 2\n",
"jnz 1 6\n",
"dec b\n",
"dec c\n",
"jnz c -4\n",
"inc a\n",
"jnz 1 -7\n",
"cpy 2 b\n",
"jnz c 2\n",
"jnz 1 4\n",
"dec b\n",
"dec c\n",
"jnz 1 -4\n",
"jnz 0 0\n",
"out b\n",
"jnz a -19\n",
"jnz 1 -21\"\"\".splitlines()\n",
"\n",
"def r2i(r): return ord(r) - ord('a')\n",
"\n",
"def parse(d, sa):\n",
" d = [[(x if x.isalpha() else int(x)) for x in line.split()] for line in d]\n",
" regs = dict(a=sa, b=0, c=0, d=0)\n",
" ip = 0\n",
" def idtoval(x): return (regs[x] if x in regs else x)\n",
" total_len = len(d)\n",
" while 0 <= ip < total_len:\n",
" ins = d[ip]\n",
"# yield ip, ins, regs\n",
" if ins[0] == 'cpy':\n",
" if ins[2] in regs:\n",
" regs[ins[2]] = idtoval(ins[1])\n",
" elif ins[0] == 'inc':\n",
" regs[ins[1]] += 1\n",
" elif ins[0] == 'dec':\n",
" regs[ins[1]] -= 1\n",
" elif ins[0] == 'jnz':\n",
" if idtoval(ins[1]):\n",
" ip += idtoval(ins[2])\n",
" continue\n",
" elif ins[0] == 'tgl':\n",
" offs = ip + idtoval(ins[1])\n",
" if 0 <= offs < total_len:\n",
" if d[offs][0] in ['dec', 'tgl']:\n",
" d[offs][0] = 'inc'\n",
" elif d[offs][0] == 'inc':\n",
" d[offs][0] = 'dec'\n",
" elif d[offs][0] == 'jnz':\n",
" d[offs][0] = 'cpy'\n",
" else:\n",
" d[offs][0] = 'jnz'\n",
" elif ins[0] == 'out':\n",
" yield idtoval(ins[1])\n",
" ip += 1\n",
" yield regs"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from itertools import islice\n",
"res = [0,1]*5\n",
"\n",
"for i in range(1000):\n",
" if list(islice(parse(data, i), 10)) == res:\n",
" print(i)\n",
" break\n",
" if i % 10 == 0:\n",
" print(i)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"list(islice(parse(data, 189), 100))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Python [conda root]",
"language": "python",
"name": "conda-root-py"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment