I try to use Advent of Code to learn something new; this year, I realized I should do it in Python 3 in a Jupyter notebook. I didn't actually realize that until after I completed day 12, so the first half of the notebook is mostly moving my work into notebook cells.
I figured others might be curious about how different folks have solved the problems, so I'm going ahead and publishing this on my blog. I'm not completely proud of all of these answers; there is a chunk in the middle and the end that take longer to run than I would like! Still, I figured someone else might get some value out of looking at what I've done.
I've cleared away the outputs, which are mostly just the specific answer for the day in question.
import itertools
import re
import collections
import pprint
import math
def read_input_data(day_number):
if isinstance(day_number, int):
day_number = "{:02d}".format(day_number)
return open("data/{}.txt".format(day_number)).read()
def check_test_data(f, vals):
for input, output in vals.items():
if f(input) != output:
assert False, "Failure! f({}) == {}, should be {}".format(input, f(input), output)
def give_pairs(n, offset):
for i in range(len(n)):
yield n[i], n[(i+offset)%len(n)]
def calc_total(n, offset):
return sum(int(x) for x,y in give_pairs(n, offset) if x == y)
d1a_examples = {"1122":3, "1111":4, "1234":0, "91212129":9}
check_test_data(lambda x:calc_total(x,1), d1a_examples)
d1_data = read_input_data(1).strip()
print("Day 1, Part A: {}".format(calc_total(d1_data,1)))
Change part A to include an offset argument
d1b_examples = {"1212":6, "1221":0, "123425":4, "123425":4, "123123":12, "12131415":4}
check_test_data(lambda x:calc_total(x, len(x)//2), d1b_examples)
print("Day 1, Part B: {}".format(calc_total(d1_data, len(d1_data)//2)))
day2a_example = """5 1 9 5
7 5 3
2 4 6 8"""
def line_delta(line):
line = [int(x) for x in line.split()]
return max(line)-min(line)
def spreadsheet_checksum(lines):
return sum(line_delta(x) for x in lines.splitlines() if x.strip())
assert spreadsheet_checksum(day2a_example) == 18
d2_data = read_input_data(2)
print("Day 2, Part A: {}".format(spreadsheet_checksum(d2_data)))
def line_divisor(line):
line = [int(x) for x in line.split()]
for a,b in itertools.permutations(line, 2):
if a % b == 0:
return a//b
def spreadsheet_checksum(lines):
return sum(line_divisor(line) for line in lines.splitlines())
day2b_example = """5 9 2 8
9 4 7 3
3 8 6 5"""
assert spreadsheet_checksum(day2b_example) == 9
print("Day 2, Part B: {}".format(spreadsheet_checksum(d2_data)))
Also possible to calculate this directly given the patterns, but this solution makes part B trivial
def yield_deltas():
"""Function that gives the deltas to spiral outward"""
yield 1,0
n = 2
while True:
for _ in range(n-1):
yield 0,1
for _ in range(n):
yield -1, 0
for _ in range(n):
yield 0, -1
for _ in range(n+1):
yield 1,0
n+=2
def steps(n):
x,y = 0,0
deltas = yield_deltas()
for _ in range(n-1):
dx, dy = next(deltas)
x,y = x+dx, y+dy
return abs(x)+abs(y)
day3a_examples = {1:0, 12:3, 23:2, 1024:31}
check_test_data(steps, day3a_examples)
day3_data = int(read_input_data(3).strip())
print("Day 3, Part A: {}".format(steps(day3_data)))
def spiral_to(target):
existing = collections.defaultdict(int)
deltas = yield_deltas()
x,y = 0,0
existing[(x,y)] = 1
while True:
dx,dy = next(deltas)
x,y = x+dx,y+dy
total = sum(existing[(x+dx, y+dy)] for dx, dy in itertools.product( (1,0,-1), (1,0,-1)))
if total > target:
return total
existing[(x,y)] = total
day3b_examples = {805:806, 134:142}
check_test_data(spiral_to, day3b_examples)
print("Day 3, Part B: {}".format(spiral_to(day3_data)))
def passphrase_valid(l):
l = l.strip().split()
return len(l) == len(set(l))
day4a_examples = {'aa bb cc dd ee': True, 'aa bb cc dd aa':False, 'aa bb cc dd aaa':True}
check_test_data(passphrase_valid, day4a_examples)
day4_data = [x.strip() for x in read_input_data(4).splitlines()]
print("Day 4, Part A: {}".format(sum(1 for s in day4_data if passphrase_valid(s))))
def passphrase_valid(l):
l = l.strip().split()
return len(l) == len(set(tuple(sorted(x)) for x in l))
day4b_examples = {'abcde fghij':True, 'abcde xyz ecdab':False, 'a ab abc abd abf abj':True,
'iiii oiii ooii oooi oooo':True, 'oiii ioii iioi iiio':False}
check_test_data(passphrase_valid, day4b_examples)
print("Day4, Part B: {}".format(sum(1 for s in day4_data if passphrase_valid(s))))
def movements(offsets):
steps = 0
index = 0
while True:
if index >= len(offsets):
return steps
steps += 1
old_index = index
index += offsets[index]
offsets[old_index] += 1
assert movements([0,3,0,1,-3]) == 5
data = [int(x) for x in read_input_data(5).splitlines()]
print("Day 5, Part A: {}".format(movements(data)))
def movements(offsets):
steps = 0
index = 0
while index < len(offsets):
steps += 1
todo = offsets[index]
offsets[index] += -1 if todo >= 3 else 1
index += todo
return steps
assert movements([0,3,0,1,-3]) == 10
data = [int(x) for x in read_input_data(5).splitlines()]
print("Day 5, Part B: {}".format(movements(data)))
def distribute(index, length, quantity):
rv = [0]*length
for n in range(quantity):
rv[(index+1+n)%length] += 1
return rv
def step(l):
index = l.index(max(l))
rem = [0]*len(l)
rem[index] = -1*l[index]
rv = tuple(sum(x) for x in
zip(rem, l, distribute(index, len(l), l[index])))
return rv
def run(l):
seen = {}
n = 0
while True:
if l in seen:
return n, n - seen[l]
else:
seen[l] = n
l = step(l)
n+=1
#print(l)
assert run((0,2,7,0)) == (5, 4)
data = tuple(int(x) for x in read_input_data(6).split())
print("Day 6, Part A: {}\nPart B: {}".format(*run(data)))
class Node:
_RE_LINE = re.compile('(?P<name>[a-z]+) \((?P<weight>[0-9]+)\)( \-\> )*(?P<children>[a-z, ]*)')
_RE_CHILDREN = re.compile('[a-z]+')
def __init__(self, line):
l = self._RE_LINE.search(line)
self.name = l.group('name')
self.weight = int(l.group('weight'))
self.children_names = self._RE_CHILDREN.findall(l.group('children'))
self.parent = None
self.children = None
self.sum_weight = None
#print (self.name, self.weight, self.children_names)
def __str__(self):
return 'Node "{}"{} ({}, {}), with children: {}'.format(self.name, '' if self.balanced_children else '!',
self.weight, self.sum_weight,
', '.join('{}{} ({}, {})'.format(x.name, '' if x.balanced_children else '!',x.weight, x.sum_weight) for x in self.children))
def sum_children(self):
self.sum_weight = self.weight
if self.children:
self.sum_weight += sum(c.sum_children() for c in self.children)
return self.sum_weight
def delta_needed(self, amount):
child_weights = collections.defaultdict(list)
for child in self.children:
child_weights[child.sum_weight].append(child)
if len(child_weights) == 1:
return self.weight + amount
for kids in child_weights.values():
if len(kids) == 1:
return kids[0].delta_needed(amount)
assert False #shouldn't reach
def build_tree(txt):
lines = [x.strip() for x in txt.splitlines()]
nodes = {}
orphan_nodes = set()
for line in lines:
n = Node(line)
nodes[n.name] = n
orphan_nodes.add(n.name)
for node in nodes.values():
if node.children_names:
node.children = [nodes[x] for x in node.children_names]
orphan_nodes.difference_update(node.children_names)
for child in node.children:
child.parent = node
assert len(orphan_nodes) == 1
root = nodes[next(iter(orphan_nodes))]
root.sum_children()
return root
def find_needed_weight(root):
child_weights = [x.sum_weight for x in root.children]
delta = min(child_weights) - max(child_weights)
return root.delta_needed(delta)
inp = """pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)"""
test_tree = build_tree(inp)
assert test_tree.name == 'tknk'
real_tree = build_tree(read_input_data(7))
print("Day 7, Part A: {}".format(real_tree.name))
assert find_needed_weight(test_tree) == 60
print("Day 7, Part B: {}".format(find_needed_weight(real_tree)))
OPS = {'>': lambda a,b:a>b,
'<': lambda a,b:a<b,
'>=':lambda a,b:a>=b,
'==':lambda a,b:a==b,
'<=':lambda a,b:a<=b,
'!=':lambda a,b:a!=b,}
def process(lines):
highest = 0
registers = collections.defaultdict(int)
for row in lines:
#print (registers)
register, incdec, amount, _, loc, op, val = row.split()
amount, val, op = int(amount), int(val), OPS[op]
#print (register, incdec, amount, loc, op, val)
if not op(registers[loc], val):
continue
if incdec == 'inc':
registers[register] += amount
else:
registers[register] -= amount
highest = max(highest, max(registers.values()))
#print (registers)
return max(registers.values()), highest
input = """b inc 5 if a > 1
a inc 1 if b < 5
c dec -10 if a >= 1
c inc -20 if c == 10"""
assert process(x.strip() for x in input.splitlines() if x.strip()) == (1,10)
print("Day 8, Part A: {}, Part B: {}".format(*process(x.strip() for x in read_input_data(8).splitlines() if x.strip())))
def consume_garbage(s):
n = 0
while s:
c,s = s[0], s[1:]
if c == '!':
s = s[1:]
continue
if c == '>':
break
n+=1
return s, n-1
garbage_samples = """<>
<random characters>
<<<<>
<{!>}>
<!!>
<!!!>>
<{o"i!a,<{i<a>"""
check_test_data(lambda x:consume_garbage(x)[0],
{k.strip()+"sentinal":"sentinal" for k in garbage_samples.splitlines()})
def parse_string(s):
score = 0
stack = 0
total_garbage = 0
while s:
c, s = s[0], s[1:]
if c == '<':
s, consumed = consume_garbage(s)
total_garbage += consumed
continue
if c == '{':
stack+=1
score += stack
continue
if c =='}':
stack-=1
continue
return score, total_garbage
d9a_test = {"{}":1,
"{{{}}}":6,
"{{},{}}":5,
"{{{},{},{{}}}}":16,
"{<a>,<a>,<a>,<a>}":1,
"{{<ab>},{<ab>},{<ab>},{<ab>}}":9,
"{{<!!>},{<!!>},{<!!>},{<!!>}}":9,
"{{<a!>},{<a!>},{<a!>},{<ab>}}":3}
check_test_data(lambda x: parse_string(x)[0], d9a_test)
d9b_test = {"<>":0, "<random characters>":17, "<<<<>":3, "<{!>}>":2, "<!!>":0, "<!!!>>":0, '<{o"i!a,<{i<a>':10}
d9b_test = {k+"sentinal":("sentinal", v) for k,v in d9b_test.items()}
check_test_data(consume_garbage, d9b_test)
print("Day 9, Part A: {}, Part B: {}".format(*parse_string(read_input_data(9))))
def build_utils(length):
def reversing_iterator(start, end):
while start < end:
yield start % length, end % length
start, end = start + 1, end -1
def increment(start, amount):
return (start + amount)%length
return reversing_iterator, increment
def transform(length, commands):
rev, inc = build_utils(length)
v = list(x for x in range(length))
skip = 0
pos = 0
for c in commands:
for s,e in rev(pos, pos+c-1):
v[s], v[e] = v[e], v[s]
pos = inc(pos, c+skip)
skip += 1
return v
def solve(length, commands):
rv = transform(length, commands)
return rv[0]*rv[1]
assert transform(5, [3,4,1,5]) == [3,4,2,1,0]
assert solve(5, [3,4,1,5]) == 12
d10_data = [int(x) for x in read_input_data(10).strip().split(',')]
print("Day 10, Part A: {}".format(solve(256, d10_data)))
def transform(commands):
length = 256
rev, inc = build_utils(length)
v = list(x for x in range(length))
skip = 0
pos = 0
for n in range(64):
for c in commands:
for s,e in rev(pos, pos+c-1):
v[s], v[e] = v[e], v[s]
pos = inc(pos, c+skip)
skip += 1
#print skip, pos, v
return v
def xor_seq(s):
rv = s[0]
for val in s[1:]:
rv ^= val
return rv
def knot_hash(key):
key = key.strip()
key = [ord(c) for c in key]
key.extend([17, 31, 73, 47, 23])
v = transform(key)
rv = []
for n in range(0, 256, 16):
rv.append(xor_seq(v[n:n+16]))
return ''.join('{:02X}'.format(chunk).lower() for chunk in rv)
d10_test = {'':'a2582a3a0e66e6e86e3812dcb672a272',
'AoC 2017':'33efeb34ea91902bb2f59c9920caa6cd',
'1,2,3':'3efbe78a8d82f29979031a4aa0b16a9d',
'1,2,4':'63960835bcdc130f0b66d7ff4f6a5a8e'}
check_test_data(knot_hash, d10_test)
print("Day 10, Part B: {}".format(knot_hash(read_input_data(10).strip())))
movements = {'n':(0,1,-1), 'ne':(1,0,-1),
'se':(1,-1,0), 's': (0,-1,1),
'sw':(-1,0,1), 'nw':(-1,1,0)}
def process(path):
max_distance = 0
x,y,z = 0,0,0
for d in path:
dx,dy,dz = movements[d]
x,y,z=x+dx,y+dy,z+dz
max_distance = max( (abs(x)+abs(y)+abs(z))//2, max_distance)
return (abs(x)+abs(y)+abs(z))//2, max_distance
d11_test = {'ne,ne,ne':3,
'ne,ne,sw,sw':0,
'ne,ne,s,s':2,
'se,sw,se,sw,sw':3}
check_test_data(lambda x:process(x.split(','))[0], d11_test)
d11_data = read_input_data(11).strip().split(',')
print("Day 11, Part A:{}\nPart B:{}".format(*process(d11_data)))
def build_graph(lines):
graph = collections.defaultdict(set)
for line in lines:
frm, to = line.strip().split(' <-> ')
frm = int(frm.strip())
to = [int(x.strip()) for x in to.split(',')]
graph[frm].update(to)
for t in to:
graph[t].add(frm)
return graph
def get_neighborhood(graph, start):
seen = set([start])
todo = set([start])
while todo:
current = todo.pop()
todo.update(graph[current].difference(seen))
seen.update(graph[current])
return seen
d12_test = """0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5"""
d12_test_graph = build_graph(d12_test.splitlines())
assert len(get_neighborhood(d12_test_graph, 0)) == 6
d12_graph = build_graph(read_input_data(12).splitlines())
print("Day 12, Part A: {}".format(len(get_neighborhood(d12_graph,0))))
def count_neighborhoods(graph):
count = 0
all_nodes = set(graph.keys())
while all_nodes:
count += 1
start = all_nodes.pop()
all_nodes.difference_update(get_neighborhood(graph, start))
return count
assert count_neighborhoods(d12_test_graph) == 2
print("Day 12, Part B: {}".format(count_neighborhoods(d12_graph)))
def trip_severity(states, delay):
rv = []
for level, depth in states:
mod = depth*2-2
if (level+delay) % mod == 0:
rv.append((level,depth))
if delay:
return rv
return rv
def parse_states(states):
states = [state.strip().split(':') for state in states]
states = [(int(level), int(depth.strip())) for level, depth in states]
return states
d13_sample = """0: 3
1: 2
4: 4
6: 4""".splitlines()
d13_sample = parse_states(d13_sample)
assert trip_severity(d13_sample, 0) == [(0,3), (6,4)]
d13_data = parse_states(read_input_data(13).splitlines())
print("Day 13, Part A: {}".format(trip_severity(d13_data, 0)))
Probably smartest to find LCM or something, but a hack in part A to duck out early makes it fast enough.
def calc_delay(states):
delay_max = 10**8
for n in range(delay_max):
if not trip_severity(states, n):
return n
assert False, "Didn't find it in {} delay".format(delay_max)
assert calc_delay(d13_sample) == 10
print("Day 13, Part B: {}".format(calc_delay(d13_data)))
hex = {}
def count_ones(s):
assert len(s) == 32
return (''.join(bin(int(x, 16)) for x in s)).count("1")
def ones_in_grid(key):
rv = 0
for n in range(128):
rv += count_ones(knot_hash("{}-{}".format(key, n)))
return rv
d14a_test = {'flqrgnkx':8108}
check_test_data(ones_in_grid, d14a_test)
d14_data = read_input_data(14).strip()
print("Day 14, Part A: {}".format(ones_in_grid(d14_data)))
hex_transform = {"{:x}".format(n):[bool(n & (1<<(3-m))) for m in range(4)] for n in range(16) }
def build_grid(key):
rows = []
for n in range(128):
hsh = knot_hash("{}-{}".format(key, n))
rows.append(list(itertools.chain(*[hex_transform[x] for x in hsh])))
return rows
neighbor_deltas = ( (0,1), (0,-1), (1,0), (-1,0))
def neighbors(x,y):
for dx, dy in neighbor_deltas:
rx, ry = dx+x, dy+y
if rx < 0 or rx > 127 or ry < 0 or ry > 127:
continue
yield rx, ry
def pick_neighborhood(grid):
for x in range(128):
for y in range(128):
if grid[y][x]:
return (x,y)
return None
def eliminate_neighborhood(grid):
start = pick_neighborhood(grid)
if not start:
return False
todo = set([start])
while todo:
x,y = todo.pop()
grid[y][x] = False
for tmpx,tmpy in neighbors(x,y):
if grid[tmpy][tmpx]:
todo.add( (tmpx, tmpy))
return True
def count_neighborhoods(key):
grid = build_grid(key)
n = 0
while eliminate_neighborhood(grid):
n += 1
if n > 5000:
return
return n
"""
def show_grid(grid, width, height):
for y in range(height):
print(''.join('X' if x else '.' for x in grid[y][:width]))
test_grid = build_grid('flqrgnkx')
show_grid(test_grid, 8,8)
print("\n"+"="*20)
eliminate_neighborhood(test_grid)
show_grid(test_grid, 8,8)
"""
assert count_neighborhoods('flqrgnkx') == 1242
print("Day 14, Part B: {}".format(count_neighborhoods(d14_data)))
sixteen_bits = int('1'*16, 2)
def generator(last, factor):
modulus = 2147483647
while True:
last = ((last*factor)%modulus)
yield last & sixteen_bits
def find_differences(startA, startB):
A,B = generator(startA, 16807), generator(startB, 48271)
steps = 40*10**6
count = 0
for _ in range(steps):
if next(A) == next(B):
count += 1
return count
assert find_differences(65, 8921) == 588
d15_data = [int(x.split()[-1]) for x in read_input_data(15).splitlines()]
print("Day 15, Part A: {}".format(find_differences(*d15_data)))
sixteen_bits = int('1'*16,2)
def generator(last, factor, mult):
modulus = 2147483647
while True:
last = (last*factor)%modulus
if last % mult == 0:
yield last & sixteen_bits
def find_differences(startA, startB):
A,B = generator(startA, 16807, 4), generator(startB, 48271, 8)
steps = 5*10**6
count = 0
for _ in range(steps):
if next(A) == next(B):
count += 1
return count
assert find_differences(65, 8921) == 309
print("Day 15, Part B: {}".format(find_differences(*d15_data)))
def spin(s, x):
x = int(x)
return s[-x:] + s[:-x]
def exchange(s, positions):
a,b = [int(x) for x in positions.split('/')]
s[a], s[b] = s[b],s[a]
return s
def partner(s, letters):
a,b = letters.split('/')
m = {a:b, b:a}
return [m[x] if x in m else x for x in s]
def process(s, commands):
s = list(s)
cmds = {'s':spin, 'x':exchange, 'p':partner}
for c in commands:
s = cmds[c[0]](s, c[1:])
return ''.join(s)
d16a_test = ['s1', 'x3/4', 'pe/b']
assert process('abcde', d16a_test) == 'baedc'
d16_data = read_input_data(16).strip().split(',')
print("Day 16, Part A: {}".format(process('abcdefghijklmnop', d16_data)))
def multiple_times(s, cmds, rounds):
position_map = [ord(x) - ord('a') for x in process(s, [x for x in cmds if x[0] in ('s','x')])]
letter_map = {k:v for k,v in zip(s,process(s, [x for x in cmds if x[0] == 'p']) )}
steps = [s]
while True:
nxt = ''.join(letter_map[steps[-1][n]] for n in position_map)
if steps[0] == nxt:
break
steps.append(nxt)
return steps[rounds % len(steps)]
assert multiple_times('abcde', d16a_test, 1) == 'baedc'
assert multiple_times('abcde', d16a_test, 2) == 'ceadb'
print("Day 16, Part B: {}".format(multiple_times('abcdefghijklmnop', d16_data, 1000000000)))
class Node:
@staticmethod
def make_root(val):
n = Node(0)
n.nxt = n.prv = n
return n
def __init__(self, val, nxt = None, prv = None):
self.nxt = nxt
self.prv = prv
self.val = val
def __str__(self):
return "{} <- ({}) -> {}".format(self.prv.val,
self.val, self.nxt.val)
def after(self, val):
self.nxt = Node(val, self.nxt, self)
return self.nxt
def spin(root, steps, target):
n = root
for i in range(1, target+1):
for _ in range(steps):
n = n.nxt
n = n.after(i)
return n.nxt.val
assert spin(Node.make_root(0), 3, 2017) == 638
d17_data = int(read_input_data(17).strip())
print("Day 17, Part A: {}".format(spin(Node.make_root(0), d17_data, 2017)))
def fast_spin(steps, target):
next_val = -1
active = 0
size = 1
for i in range(1, target+1):
active = (steps + active) % size
if active == 0:
next_val = i
size += 1
active += 1
return next_val
zero = Node.make_root(0)
spin(zero, 3, 2017)
sample_final = zero.nxt.val
assert fast_spin(3, 2017) == sample_final
print("Day 17, Part B: {}".format(fast_spin(d17_data, 50000000)))
class DuetMachine:
def __init__(self, cmds):
self.registers = collections.defaultdict(int)
self.last_sound = None
self.recovered_sound = None
self.pc = 0
self.cmds = [self.cmd_builder(c) for c in cmds]
def cmd_builder(self, s):
op, args = s.strip().split(' ', 1)
args = args.split()
if op == 'snd':
def f():
self.last_sound = self.translate(args[0])
self.pc += 1
elif op == 'set':
def f():
self.registers[args[0]] = self.translate(args[1])
self.pc += 1
elif op == 'add':
def f():
self.registers[args[0]] = self.translate(args[0]) + self.translate(args[1])
self.pc += 1
elif op == 'mul':
def f():
self.registers[args[0]] = self.translate(args[0]) * self.translate(args[1])
self.pc += 1
elif op == 'mod':
def f():
self.registers[args[0]] = self.translate(args[0]) % self.translate(args[1])
self.pc += 1
elif op == 'rcv':
def f():
if self.translate(args[0]) != 0:
self.recovered_sound = self.last_sound
self.pc = -1
return
self.pc += 1
elif op == 'jgz':
def f():
if self.translate(args[0]) > 0:
self.pc += self.translate(args[1])
else:
self.pc += 1
else:
assert False, "Bad command, "+s
f.name = s
return f
def __str__(self):
regs = ', '.join('{0}:{1}'.format(*x) for x in self.registers.items())
if not self.done():
return 'DM: [{:3}] <{:12}> ({})'.format(self.pc,self.cmds[self.pc].name, regs)
return 'DM: [DONE] ({}), Recovered Sound: {}'.format(regs, self.recovered_sound)
def translate(self, name):
if name.isalpha():
return self.registers[name]
return int(name)
def done(self):
return not (0<= self.pc < len(self.cmds))
def step(self):
if not self.done():
self.cmds[self.pc]()
d18_test = [x.strip() for x in """set a 1
add a 2
mul a a
mod a 5
snd a
set a 0
rcv a
jgz a -1
set a 1
jgz a -2""".splitlines()]
dm = DuetMachine(d18_test)
while not dm.done():
dm.step()
assert dm.recovered_sound == 4
d18_data = read_input_data(18).splitlines()
dm = DuetMachine(d18_data)
while not dm.done():
dm.step()
print("Day 18, Part A: {}".format(dm.recovered_sound))
class DuetMachine:
def __init__(self, cmds, p):
self.registers = collections.defaultdict(int)
self.registers['p'] = p
self.pc = 0
self.cmds = [self.cmd_builder(c) for c in cmds]
self.q = []
self.other = None
self.blocked = False
self.snd_count = 0
def cmd_builder(self, s):
op, args = s.strip().split(' ', 1)
args = args.split()
if op == 'snd':
def f():
self.other.q.append(self.translate(args[0]))
self.pc += 1
self.snd_count += 1
elif op == 'set':
def f():
self.registers[args[0]] = self.translate(args[1])
self.pc += 1
elif op == 'add':
def f():
self.registers[args[0]] = self.translate(args[0]) + self.translate(args[1])
self.pc += 1
elif op == 'mul':
def f():
self.registers[args[0]] = self.translate(args[0]) * self.translate(args[1])
self.pc += 1
elif op == 'mod':
def f():
self.registers[args[0]] = self.translate(args[0]) % self.translate(args[1])
self.pc += 1
elif op == 'rcv':
def f():
if self.q:
self.registers[args[0]] = self.q[0]
self.q = self.q[1:]
self.pc += 1
self.blocked = False
else:
self.blocked = True
elif op == 'jgz':
def f():
if self.translate(args[0]) > 0:
self.pc += self.translate(args[1])
else:
self.pc += 1
else:
assert False, "Bad command, "+s
f.name = s
return f
def __str__(self):
regs = ', '.join('{0}:{1}'.format(*x) for x in self.registers.items())
return 'DM: [{:3}] <{:12}> ({}) {}'.format(self.pc,self.cmds[self.pc].name, regs, self.blocked)
def translate(self, name):
if name.isalpha():
return self.registers[name]
return int(name)
def step(self):
self.cmds[self.pc]()
d18b_test = """snd 1
snd 2
snd p
rcv a
rcv b
rcv c
rcv d""".splitlines()
def setup_machines(cmds):
dms = [DuetMachine(cmds, n) for n in range(2)]
dms[1].other, dms[0].other = dms
return dms
def run_till_done(machines):
while any(not m.blocked for m in machines):
for m in machines:
m.step()
zero, one = setup_machines(d18b_test)
run_till_done([zero, one])
assert one.snd_count == 3
zero, one = setup_machines(d18_data)
run_till_done([zero, one])
print("Day 18, Part B: {}".format(one.snd_count))
def prep_map(m):
m = ['${}$'.format(x[:-1]) for x in m.splitlines() if x.strip()]
m.append('$'*len(m[0]))
m.insert(0, '$'*len(m[0]))
return m
def locate_start(m):
y = 1
for x in range(1, len(m)):
if m[y][x] == '|':
return x,y
_directions = {'n':(0,-1), 'e':(1,0), 's':(0,1), 'w':(-1,0)}
_turns = {'n':('e', 'w'), 'e':('n', 's'), 's':('e','w'), 'w':('n', 's')}
def walk_map(m, x, y, direction):
while True:
if m[y][x] == '+':
for d in _turns[direction]:
dx, dy = _directions[d]
candidate = m[y+dy][x+dx]
if candidate in ('|', '-', '+') or candidate.isalpha():
x, y, direction = x+dx, y+dy, d
break
else:
dx, dy = _directions[direction]
x, y = x+dx, y+dy
if m[y][x] in ('$', ' '):
break
yield (x,y)
def read_sequence(m):
x,y = locate_start(m)
rv = []
n = 1
for x,y in walk_map(m, x, y, 's'):
if m[y][x].isalpha():
rv.append(m[y][x])
n+=1
return ''.join(rv), n
d19_sample = '''
|
| +--+
A | C
F---|----E|--+
| | | D
+B-+ +--+
'''
d19_sample_prepped = prep_map(d19_sample)
assert read_sequence(d19_sample_prepped) == ('ABCDEF', 38)
d19_data = read_input_data(19)
print("Day 19, Part A: {}\nPart B: {}".format(*read_sequence(prep_map(d19_data))))
I'm going to guess I can reduce all these particles to equations, and do some clever matrix stuff to eliminate duplicates. Or I can simulate it.
_numbers = re.compile('[-0-9]+')
class Particle:
def __init__(self, n, desc):
self.n = n
nums = [int(x) for x in _numbers.findall(desc)]
self.p, self.v, self.a = [tuple(nums[i:i+3]) for i in range(0,9,3)]
def total_accel(self):
return sum(abs(x) for x in self.a)
def step(self):
self.v = tuple(q+dq for q,dq in zip(self.v, self.a))
self.p = tuple(q+dq for q,dq in zip(self.v, self.p))
d20a_test = """p=< 3,0,0>, v=< 2,0,0>, a=<-1,0,0>
p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>""".splitlines()
def generate_particles(descriptions):
particles = [Particle(n, p) for n,p in enumerate(descriptions)]
particles.sort(key=lambda x:x.total_accel())
return particles
assert generate_particles(d20a_test)[0].n == 0
d20_data = read_input_data(20).splitlines()
print("Day 20, Part A: {}".format(generate_particles(d20_data)[0].n))
def remove_collided(particles):
count = collections.Counter(p.p for p in particles)
collisions = set(p for p, instances in count.items() if instances > 1)
return [p for p in particles if p.p not in collisions]
d20b_test = """p=<-6,0,0>, v=< 3,0,0>, a=< 0,0,0>
p=<-4,0,0>, v=< 2,0,0>, a=< 0,0,0>
p=<-2,0,0>, v=< 1,0,0>, a=< 0,0,0>
p=< 3,0,0>, v=<-1,0,0>, a=< 0,0,0>""".splitlines()
def run_simulation(particles):
clean_run = 0
while clean_run < 1000:
clean_run += 1
for p in particles:
p.step()
len_p = len(particles)
particles = remove_collided(particles)
if len(particles) != len_p:
clean_run = 0
return len(particles)
assert run_simulation(generate_particles(d20b_test)) == 1
print("Day 20, Part B: {}".format(run_simulation(generate_particles(d20_data))))
def rotate(grid):
return list(zip(*reversed(grid)))
def flip(grid):
return [list(reversed(x)) for x in grid]
def stringify(grid):
return ''.join(''.join(x) for x in grid)
def parse_rule(line):
left, right = [x.strip() for x in line.split(' => ')]
left = left.split('/')
right = right.split('/')
rv = {}
for rotation in range(4):
left = rotate(left)
rv[stringify(left)] = right
rv[stringify(flip(left))] = right
return rv
def parse_rules(lines):
rv = {}
for line in lines.splitlines():
rv.update(parse_rule(line))
return rv
def chunk(grid):
mod = 2 if len(grid)% 2 == 0 else 3
for j in range(0, len(grid), mod):
for i in range(0, len(grid), mod):
yield ''.join(grid[dj][i:i+mod] for dj in range(j,j+mod)), j//mod
def step(grid, rules):
raw = []
for s,j in chunk(grid):
if j > len(raw)-1:
raw.append([])
raw[-1].append(rules[s])
rv = []
for big_row in raw:
rv.extend(''.join(x) for x in zip(*big_row))
return rv
def do_steps(grid, rules, steps):
for n in range(steps):
grid = step(grid, rules)
return grid
def count_pixels(grid, rules, steps):
rules = parse_rules(rules)
return sum(x.count('#') for x in do_steps(grid, rules, steps))
d21_sample_rules = """../.# => ##./#../...
.#./..#/### => #..#/..../..../#..#"""
d21_start_grid = [x.strip() for x in """.#.
..#
###""".splitlines()]
assert count_pixels(d21_start_grid, d21_sample_rules, 2) == 12
d21_rules = read_input_data(21)
print("Day 21, Part A: {}".format(count_pixels(d21_start_grid, d21_rules, 5)))
print("Day 21, Part B: {}".format(count_pixels(d21_start_grid, d21_rules, 18)))
def parse_map(lines):
lines = [l.strip() for l in lines.splitlines() if l.strip()]
rv = set()
for y, line in enumerate(lines):
for x, c in enumerate(line):
if c == '#':
rv.add((x,y))
return rv, (len(lines)//2, len(lines[0])//2)
_direction = [(0,-1), (1,0), (0,1), (-1,0)]
def step(mp, n):
mp, loc = parse_map(mp)
x,y = loc
d = 0
infections = 0
for _ in range(n):
if (x,y) in mp:
d = (d+1)%len(_direction)
mp.remove((x,y))
else:
d = (d-1)%len(_direction)
mp.add( (x,y) )
infections +=1
dx, dy = _direction[d]
x,y = x+dx, y+dy
return infections
d22_test = """..#
#..
..."""
check_test_data(lambda n:step(d22_test, n), {7:5, 70:41, 10000:5587})
d22_data = read_input_data(22)
print("Day 22, Part A: {}".format(step(d22_data, 10000)))
def step(mp, n):
infected, loc = parse_map(mp)
x,y = loc
weakened = set()
flagged = set()
infections = 0
d = 0
for _ in range(n):
here = (x,y)
if here in weakened:
weakened.remove(here)
infected.add(here)
infections += 1
elif here in flagged:
d = (d+2)%len(_direction)
flagged.remove(here)
elif here in infected:
d = (d+1)%len(_direction)
infected.remove(here)
flagged.add(here)
else: #clean
d = (d-1)%len(_direction)
weakened.add(here)
dx,dy = _direction[d]
x,y = x+dx, y+dy
return infections
check_test_data(lambda n:step(d22_test, n), {100:26, 10000000:2511944})
print("Day 22, Part B: {}".format(step(d22_data, 10000000)))
class Cmd:
def __init__(self, p, l):
self.p = p
_, self.X, self.Y = l.strip().split()
self.name = l
def lookup(self, val):
if val in self.p.registers:
return self.p.registers[val]
return int(val)
def inc(self, n=1):
self.p.pc += n
class SetCmd(Cmd):
def run(self):
self.p.registers[self.X] = self.lookup(self.Y)
self.inc()
class SubCmd(Cmd):
def run(self):
self.p.registers[self.X] -= self.lookup(self.Y)
self.inc()
class MulCmd(Cmd):
def run(self):
self.p.registers[self.X] *= self.lookup(self.Y)
self.inc()
self.p.mul_count += 1
class JnzCmd(Cmd):
def run(self):
if self.lookup(self.X) != 0:
self.inc(self.lookup(self.Y))
else:
self.inc()
_CMD_MAP = {'set':SetCmd, 'sub':SubCmd, 'mul':MulCmd, 'jnz':JnzCmd}
class Coprocessor:
def __init__(self, commands):
self.registers = {k:0 for k in 'abcdefgh'}
self.pc = 0
self.cmds = [self.cmd_builder(l) for l in commands.splitlines()]
self.mul_count = 0
def __str__(self):
return '[{: <3}] ({:<15}) {}'.format(self.pc, self.cmds[self.pc].name,
' '.join('{}:{}'.format(*x) for x in self.registers.items()))
def cmd_builder(self, l):
cmd, _ = l.strip().split(' ', 1)
return _CMD_MAP[l.strip().split()[0]](self, l)
def lookup(self, s):
if s in self.registers:
return self.registers[s]
return int(s)
def step(self):
if self.running():
#print(self.cmds[self.pc].name)
self.cmds[self.pc].run()
def running(self):
return 0 <= self.pc < len(self.cmds)
d23_data = read_input_data(23)
proc = Coprocessor(d23_data)
while proc.running():
proc.step()
print("Day 23, Part A: {}".format(proc.mul_count))
I optimized, I worked, I fought, and in the end... I reread the description and realized I needed to figure out what was going on in my puzzle input, and then I needed to write a more efficient version of whatever terrible algorithm was in my puzzle input. I like writing something that solves the generic problem, clearly, so this is an attempt to eat my cake and have it too, making some assumptions about what other puzzle inputs probably look like.
def get_parameters(data):
proc = Coprocessor(data)
proc.registers['a'] = 1
for n in range(7):
proc.step()
low, high = proc.registers['b'], proc.registers['c']
step = int(re.search(r'[0-9]+', data.splitlines()[-2]).group(0))
return low, high, step
def cheat_on_day_22(data):
low, high, step = get_parameters(data)
#print(low,high,step)
results = [x for x in range(low,high+1,step)]
initial = len(results)
results = [x for x in results if x%2 != 0]
for n in range(3, math.floor(math.sqrt(high)), 2):
results = [x for x in results if x % n != 0]
return initial - len(results)
print("Day 23, Part B: {}".format(cheat_on_day_22(d23_data)))
def parse_inputs(lines):
rv = []
for line in lines.splitlines():
rv.append(tuple(int(x) for x in line.strip().split('/')))
return rv
def score_path(path):
if not path:
return -1
return sum(x+y for x,y in path)
def walk_paths(path, nxtval, segments):
rv = []
for n,s in enumerate(segments):
if nxtval not in s:
continue
x,y = s
segs = segments[:n]+segments[n+1:]
if x == nxtval:
rv.extend(walk_paths(path+[s], y, segs))
if y == nxtval:
rv.extend(walk_paths(path+[s], x, segs))
if path:
rv.append(path)
return rv
def find_strongest_bridge(components):
segs = parse_inputs(components)
return max(score_path(x) for x in walk_paths([], 0, segs))
def find_strongest_longest(components):
segs = parse_inputs(components)
bridges = walk_paths([], 0, segs)
bridges.sort(key=lambda x:(len(x), score_path(x)))
return score_path(bridges[-1])
d24_test = """0/2
2/2
2/3
3/4
3/5
0/1
10/1
9/10"""
assert find_strongest_bridge(d24_test) == 31
d24_test = read_input_data(24)
print("Day 24, Part A: {}".format(find_strongest_bridge(d24_test)))
print("Day 24, Part B: {}".format(find_strongest_longest(d24_test)))
number = re.compile(r'[0-9]+')
def parse_action(inp):
#(write, cursor move, next_state)
return (inp[0][-1] == '1', 1 if inp[1].endswith('right') else -1, inp[2][-1])
def parse_state(inp):
inp = [x.strip(':').strip('.').strip() for x in inp]
name = inp[0][-1]
return name, parse_action(inp[2:5]), parse_action(inp[6:9])
def parse_all(inp):
inp = inp.splitlines()
start = inp[0][-2]
steps = int(number.search(inp[1]).group(0))
inp = inp[3:]
ones = {}
zeros = {}
for n in range(0, len(inp), 10):
name, zero, one = parse_state(inp[n:n+10])
ones[name] = one
zeros[name] = zero
return start, steps, ones, zeros
def run_turing(inp):
state, steps, ones, zeros = parse_all(inp)
tape = set()
cursor = 0
for _ in range(steps):
if cursor in tape:
actions = ones[state]
else:
actions = zeros[state]
write, move, nxt = actions
if write:
tape.add(cursor)
elif cursor in tape:
tape.remove(cursor)
cursor += move
state = nxt
return len(tape)
d25_sample = """Begin in state A.
Perform a diagnostic checksum after 6 steps.
In state A:
If the current value is 0:
- Write the value 1.
- Move one slot to the right.
- Continue with state B.
If the current value is 1:
- Write the value 0.
- Move one slot to the left.
- Continue with state B.
In state B:
If the current value is 0:
- Write the value 1.
- Move one slot to the left.
- Continue with state A.
If the current value is 1:
- Write the value 1.
- Move one slot to the right.
- Continue with state A."""
assert run_turing(d25_sample) == 3
d25_data = read_input_data(25)
print("Day 25, Part A: {}".format(run_turing(d25_data)))