Advent of Code, 2017!

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.

Helper Functions & Global Imports

In [ ]:
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)
In [ ]:
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)))

Part B

Change part A to include an offset argument

In [ ]:
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)))
In [ ]:
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)))

Part B

In [ ]:
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)))

Day 3: Spiral Memory

Part A

Also possible to calculate this directly given the patterns, but this solution makes part B trivial

In [ ]:
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)))

Part B

In [ ]:
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)))
In [ ]:
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))))

Part B

In [ ]:
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))))
In [ ]:
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)))

Part B

In [ ]:
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)))
In [ ]:
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)))

Day 7: Recursive Circus

Part A & B

Easiest to combine it all.

In [ ]:
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)))
In [ ]:
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())))
In [ ]:
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))))
In [ ]:
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)))

Part B

In [ ]:
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())))

Day 11: Hex Ed

Amit's tutorial for the win!

Part A & B

In [ ]:
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)))
In [ ]:
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))))

Part B

In [ ]:
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)))
In [ ]:
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)))

Part B

Probably smartest to find LCM or something, but a hack in part A to duck out early makes it fast enough.

In [ ]:
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)))
In [ ]:
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)))

Part B

In [ ]:
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)))
In [ ]:
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)))

Day B

In [ ]:
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)))
In [ ]:
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)))

Day B

In [ ]:
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)))
In [ ]:
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)))
In [ ]:
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)))
In [ ]:
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))

Day B

In [ ]:
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))
In [ ]:
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))))

Day 20: Particle Swarm

Part A & Part B

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.

In [ ]:
_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))))
In [ ]:
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)))
In [ ]:
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)))
In [ ]:
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)))
In [ ]:
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))

Part B

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.

In [ ]:
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)))
In [ ]:
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)))
In [ ]:
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)))