Solutions to Advent of Code 2017.

Many days contain code duplication between part 1 and part 2. In general I didn't re-write part 1 once I saw part 2.

## Utility functions¶

These were written as needed for a specific day, and then moved here if it looked like they'd be useful for a subsequent problem.

### Iteration helpers¶

In [1]:
from itertools import zip_longest

def iter_index(iterable, value):
"Return the 0-based index of value in iterable."
for i, item in enumerate(iterable):
if item == value:
return i
raise ValueError()

def iter_last(iterable, defaultvalue=None):
"Return an iterable's last item; defaultvalue if the iterable is empty."
item = defaultvalue
for item in iterable:
pass
return item

def iter_len(iterable):
"Return the length of an iterable."
return sum(1 for _ in iterable)

def iter_nth(iterable, n):
"Return an iterable's nth item."
return next(x for i, x in enumerate(iterable) if i == n)

def repeatedly(fn, initial):
"Yield fn(initial), fn(fn(initial)), ..."
while True:
initial = fn(initial)
yield initial

# from itertools recipes
def grouper(iterable, n, fillvalue=None):
"Collect data into fixed-length chunks or blocks"
args = [iter(iterable)] * n
return zip_longest(*args, fillvalue=fillvalue)


### Running Examples¶

In [2]:
# Better than assert, because it prints the expected value.
# There's plenty of test runners that due this, but using them inside Jupyter was beyond
# me during the course of the contest.
def example(actual, expected=True):
"Print message if action != expected."
if actual != expected:
raise Exception('Actual = {} ≠ {} = expected'.format(actual, expected))

example(abs(-2), 2)

def examples(fn, *pairs):
assert len(pairs) % 2 == 0, "expected an even number of input, expected arguments; received {}".format(len(pairs))
for arg, expected in grouper(pairs, 2):
example(fn(arg), expected)

examples(abs,
2, 2,
-2, 2)


### Data¶

In [3]:
class InputStr(str):
def __init__(self, day):

@property
def lines(self):
return self.splitlines()

@property
def grid(self):
"Given a text matrix with newlines, return a list of list of ints."
return [list(map(int, line.split()))
for line in self.splitlines()]

def count_filtered(self, pred):
return sum(map(pred, self.lines))

def Input(day):


### Here strings¶

Beef up multiline string literals.

In [4]:
def Here(s):
return InputStr(s.strip('\n'))

def here_lines(s):
return Here(s).lines

here_lines('''
ignoring an initial and final
line break''')

Out[4]:
['Reads a multiline string,', 'ignoring an initial and final', 'line break']
In [5]:
def here_grid(s):
return Here(s).grid

here_grid('''
1 2 3
4 5
''')

Out[5]:
[[1, 2, 3], [4, 5]]

### Other utilities¶

In [6]:
def rot(seq, n):
"Rotate left by n"
return seq[n:] + seq[:n]

example(rot('abcdef', 2), 'cdefab')

In [7]:
import re
from collections import namedtuple

class converting_tuple(object):
"""Like a namedtuple, but converts each value as it's stored.

It's not actually a class like namedtuple, but it pretends to have a constructor."""
def __init__(self, name, matcher=None, **converters):
self.converters = converters
self.constr = namedtuple(name, converters.keys())
self.pattern = matcher
self.matcher = re.compile(matcher).match if isinstance(matcher, str) else matcher

def __call__(self, d):
if isinstance(d, str):
m = self.matcher(d)
assert m, "Couldn't match {} against {}".format(d, self.pattern)
d = m.groupdict()
return self.constr(*(fn(d[k]) for k, fn in self.converters.items()))

TestTuple = converting_tuple('testtuple', matcher=r'(?P<var>.+)=(?P<val>\d+)', var=str.lower, val=int)
t = TestTuple('X=10')

example(t.var, 'x')
example(t.val, 10)


In [8]:
def sum_same_as_next(digits):
return sum(int(c)
for i, c in enumerate(digits)
if c == digits[(i + 1) % len(digits)])

examples(sum_same_as_next,
'1122', 3,
'1111', 4,
'1234', 0,
'91212129', 9)

sum_same_as_next(Input(1))

Out[8]:
1119

### Part 2¶

In [9]:
def sum_same_as_antipode(digits, delta=None):
delta = delta or len(digits) // 2
return sum(int(c)
for i, c in enumerate(digits)
if c == digits[(i + delta) % len(digits)])

examples(sum_same_as_antipode,
'1212', 6,
'1221', 0,
'123425', 4,
'123123', 12,
'12131415', 4)

sum_same_as_antipode(Input(1))

Out[9]:
1420

If I'd seen Part 2 before I wrote Part 1, I would have defined sum_same_as_next in terms of sum_same_as_antipode.

### Alternatives¶

Here's some alternate implementations that I also had in my head when I wrote the one above. With less time pressure, I'd write them all, and keep the one that looked more maintainable.

These can trivially be extended to sum_same_as_antipode.

In [10]:
def sum_same_as_next(digits):
buffered = digits + digits[:1]
return sum(int(c)
for i, c in enumerate(digits)
if c == buffered[i + 1])

def sum_same_as_next(digits):
return sum(int(c1)
for c1, c2 in zip(digits, digits[1:] + digits[:1])
if c1 == c2)

examples(sum_same_as_next,
'1122', 3,
'1111', 4,
'1234', 0,
'91212129', 9)

sum_same_as_next(Input(1))

Out[10]:
1119

## Day 2: Corruption Checksum¶

In [11]:
def checksum(rows):
return sum(max(row) - min(row) for row in rows)

example(checksum(here_grid('''
5 1 9 5
7 5 3
2 4 6 8''')), 18)

checksum(Input(2).grid)

Out[11]:
41887

### Part 2¶

In [12]:
from itertools import combinations

def evenly(rows):
ints = lambda ns: next(p // q for q, p in combinations(sorted(set(ns)), 2) if p % q == 0)
return sum(map(ints, rows))

example(evenly(here_grid('''
5 9 2 8
9 4 7 3
3 8 6 5''')), 9)

evenly(Input(2).grid)

Out[12]:
226

## Day 3: Spiral Memory¶

In [13]:
from itertools import accumulate, chain, count, repeat

def spiral_steps():
p, r = 1, 1j
# one step right, one up, two left, two down, three right, three up, etc.
for w in count(1):
yield from repeat(p, w)
p *= r
yield from repeat(p, w)
p *= r

def spiral_positions():
"Generate (x, y) position along the spiral, starting at (0, 0)."
def c_to_pair(c):
return (int(c.real), int(c.imag))
return map(c_to_pair, accumulate(chain([0j], spiral_steps())))

def steps(n):
"Return the Manhattan distance from 1-based nth element to the center."
x, y = iter_nth(spiral_positions(), n-1)
return abs(x) + abs(y)

def print_spiral(w):
cells = {}
for n, pos in enumerate(spiral_positions(), 1):
x, y = pos
if max(abs(x), abs(y)) > w:
break
cells[pos] = n
for y in range(w, -w-1, -1):
ns = (cells.get((x, y), None) for x in range(-w, w+1))
xs = ('{:4}'.format(n or '') for n in ns)
print(' '.join(xs))

print_spiral(3)

examples(steps,
1, 0,
12, 3,
23, 2,
1024, 31)

steps(361527)

  37   36   35   34   33   32   31
38   17   16   15   14   13   30
39   18    5    4    3   12   29
40   19    6    1    2   11   28
41   20    7    8    9   10   27
42   21   22   23   24   25   26
43   44   45   46   47   48   49

Out[13]:
326

### Part 2¶

In [14]:
from collections import defaultdict

def neighbors(pos):
x, y = pos
return ((x + dx, y + dy)
for dx in (-1, 0, 1)
for dy in (-1, 0, 1)
if dx or dy)

def spiral_sums():
m = defaultdict(int)
for pos in spiral_positions():
a = sum(m[n] for n in neighbors(pos)) or 1
m[pos] = a
yield a

next(n for n in spiral_sums() if n > 361527)

Out[14]:
363010

### Alternatives¶

I kind of like these better, but they read more like Haskell, less like idiomatic Python (as evident from the imports).

Where I to start over, I'd change spiral_positions to return complex numbers instead of tuples, and change its consumers to expect them.

In [15]:
from functools import partial, reduce
from itertools import accumulate, chain, islice

def spiral_positions():
turns = (1j ** n for n in count())
sides = (w for n in count(1) for w in (n, n))  # number of steps in each direction
steps = (d for n, d in zip(sides, turns) for _ in range(n))
yield (0, 0)
yield from ((int(c.real), int(c.imag)) for c in accumulate(steps, add))

def print_spiral(w):
h = w // 2
cells = {pos: n for n, pos in enumerate(islice(spiral_positions(), w**2), 1)}
row = lambda y:[cells.get((x, y), '') for x in range(-h, h+1)]
cell_width = max(len(str(n)) for n in cells.values())
fmt = partial('{:{w}}'.format, w=cell_width)
for y in range(h, -h-1, -1):
print(' '.join(map(fmt, row(y))))

print_spiral(7)

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49


## Day 4: High-Entropy Passphrases¶

In [16]:
def valid_passphrase(phrase):
ws = phrase.split()
return len(ws) == len(set(ws))

examples(valid_passphrase,
'aa bb cc dd ee', True,
'aa bb cc dd aa', False,
'aa bb cc dd aaa', True)

Input(4).count_filtered(valid_passphrase)

Out[16]:
383
In [17]:
def valid_passphrase(phrase):
ws = phrase.split()
return len(ws) == len(set(''.join(sorted(w)) for w in ws))

examples(valid_passphrase,
'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)

Input(4).count_filtered(valid_passphrase)

Out[17]:
265

## Day 5: A Maze of Twisty Trampolines, All Alike¶

In [18]:
def iter_jumps(lines):
jumps = list(map(int, lines))
pc = 0
while 0 <= pc < len(jumps):
yield pc
n = jumps[pc]
jumps[pc] += 1
pc += n

def jump_count(lines):
return iter_len(iter_jumps(lines))

EXAMPLE5 = here_lines('''
0
3
0
1
-3''')

example(jump_count(EXAMPLE5), 5)

jump_count(Input(5).lines)

Out[18]:
372139
In [19]:
def iter_jumps(lines):
jumps = list(map(int, lines))
pc = 0
while 0 <= pc < len(jumps):
yield pc
n = jumps[pc]
jumps[pc] += -1 if n >= 3 else 1
pc += n

example(jump_count(EXAMPLE5), 10)

jump_count(Input(5).lines)

Out[19]:
29629538

## Day 6: Memory Reallocation¶

In [20]:
from operator import add
from itertools import count, starmap

def redistribute(banks):
N = len(banks)
m = max(banks)
b = banks.index(m)
q, r = divmod(m, N)
zeroed = banks[:b] + (0,) + banks[b+1:]  # banks, with the donor set to zero
deltas = [q + 1] * r + [q] * (N - r)

def iter_configs(banks):
banks = tuple(banks)
seen = set()
while banks not in seen:
yield banks
banks = tuple(redistribute(banks))

def count_configs(banks):
return iter_len(iter_configs(banks))

example(count_configs([0, 2, 7, 0]), 5)

count_configs(map(int, Input(6).split()))

Out[20]:
5042

### Part 2¶

In [21]:
def cycle_size(banks):
c = iter_last(iter_configs(banks))
return(iter_len(iter_configs(c)))

example(cycle_size([0, 2, 7, 0]), 4)

cycle_size(map(int, Input(6).split()))

Out[21]:
1086

## Day 7: Recursive Circus¶

In [22]:
import operator
import re
from collections import namedtuple
from functools import reduce

Disc = namedtuple('Disc', ['name', 'weight', 'child_names'])

def parse(lines):
discs = {}
for line in lines:
name, weight, children = re.match(r'(\S+) $(\d+)$(?: -> (.+))?', line).groups()
children = children and children.split(', ') or ()
discs[name] = Disc(name, int(weight), frozenset(children))
return discs

def bottom(lines):
tower = parse(lines)
discs = tower.values()
bottoms = {d.name for d in discs} - reduce(operator.ior, (d.child_names for d in discs))
assert len(bottoms) == 1
return list(bottoms)[0]

example(bottom(here_lines('''
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)''')), 'tknk')

bottom(Input(7).lines)

Out[22]:
'rqwgj'
In [23]:
from functools import lru_cache
from collections import Counter

def mismatched(tower):
"Generates pairs (disc, weight) of discs that would need weight to match their siblings."
def children(disc):
return [tower[s] for s in disc.child_names]
@lru_cache()
def inclusive_weight(disc):
return disc.weight + sum(map(inclusive_weight, children(disc)))
for d in tower.values():
weights = [inclusive_weight(c) for c in children(d)]
if len(set(weights)) > 1:
# if there's two weights, the one occurs only once (not checked here); the other is good
bad_weight, good_weight = (w for w, _ in sorted(Counter(weights).items(), key=lambda t:t[1]))

def correction(lines):
tower = parse(lines)
candidates = list(mismatched(tower))
def descendant_names(d):
return reduce(operator.ior, (descendant_names(tower[c]) for c in d.child_names), set(d.child_names))
subsumed = reduce(operator.ior, (descendant_names(d) for d, _ in candidates))
w, = [w for d, w in candidates if d.name not in subsumed]
return w

example(correction(here_lines('''
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)''')), 60)

correction(Input(7).lines)

Out[23]:
34386

## Day 8: I Heard You Like Registers¶

In [24]:
from collections import defaultdict, namedtuple
from operator import ge, le, gt, lt, eq, ne, add, sub

ops = {'inc': add, 'dec': sub}
rels = {'>': gt, '<': lt, '>=': ge, '<=': le, '==': eq, '!=': ne}
Instr = converting_tuple(
'instr',
r'(?P<v1>\w+) (?P<op>inc|dec) (?P<k1>-?\d+) if (?P<v2>\w+) (?P<rel>\S+) (?P<k2>-?\d+)',
v1=str, v2=str, k1=int, k2=int, rel=rels.__getitem__, op=ops.__getitem__)

def max_register_value(lines):
regs = defaultdict(int)
for instr in map(Instr, lines):
if instr.rel(regs[instr.v2], instr.k2):
regs[instr.v1] = instr.op(regs[instr.v1], instr.k1)
return max(regs.values())

example(max_register_value(here_lines('''
b inc 5 if a > 1
a inc 1 if b < 5
c dec -10 if a >= 1
c inc -20 if c == 10''')), 1)

max_register_value(Input(8).lines)

Out[24]:
4877

### Part 2¶

In [25]:
# I would have written part 1's max_register_value in terms of these, if I'd known what was coming.
# Instead, this funciton is remixed from that one.
def iter_registers_map(lines):
regs = defaultdict(int)
for instr in map(Instr, lines):
if instr.rel(regs[instr.v2], instr.k2):
regs[instr.v1] = instr.op(regs[instr.v1], instr.k1)
yield regs

def max_register_value(lines):
return max(v for regs in iter_registers_map(lines) for v in regs.values())

example(max_register_value(here_lines('''
b inc 5 if a > 1
a inc 1 if b < 5
c dec -10 if a >= 1
c inc -20 if c == 10''')), 10)

max_register_value(Input(8).lines)

Out[25]:
5471

## Day 9: Stream Processing¶

In [26]:
def count_groups(s):
s = re.sub(r'!.', '', s)
s = re.sub(r'<.*?>', '', s)
return s.count('{')

examples(count_groups,
'{}', 1,
'{{{}}}', 3,
'{{},{}}', 3,
'{{{},{},{{}}}}', 6,
'{<{},{},{{}}>}', 1,
'{<a>,<a>,<a>,<a>}', 1,
'{{<a>},{<a>},{<a>},{<a>}}', 5,
'{{<!>},{<!>},{<!>},{<a>}}', 2,
)

def iter_group_depths(s):
s = re.sub(r'!.', '', s)
s = re.sub(r'<.*?>', '', s)
depth = 0
deltas = {'{': 1, '}': -1}
yield depth
for c in s:
if c in deltas:
delta = deltas[c]
depth += delta
if delta > 0:
yield depth

def sum_groups(line):
return sum(iter_group_depths(line))

examples(sum_groups,
'{}', 1,
'{{{}}}', 6,
'{{},{}}', 5,
'{{{},{},{{}}}}', 16,
'{<a>,<a>,<a>,<a>}', 1,
'{{<ab>},{<ab>},{<ab>},{<ab>}}', 9,
'{{<!!>},{<!!>},{<!!>},{<!!>}}', 9,
'{{<a!>},{<a!>},{<a!>},{<ab>}}', 3,
)

sum_groups(Input(9))

Out[26]:
7616

### Part 2¶

In [27]:
def sum_garbage_lengths(s):
s = re.sub(r'!.', '', s)
return sum(map(len, re.findall(r'<(.*?)>', s)))

examples(sum_garbage_lengths,
'<>', 0,
'<random characters>', 17,
'<<<<>', 3,
'<{!>}>', 2,
'<!!>', 0,
'<!!!>>', 0,
'<{o"i!a,<{i<a>', 10,
)

sum_garbage_lengths(Input(9))

Out[27]:
3838

## Day 10: Knot Hash¶

In [28]:
def knot_hash(lengths, lst=range(256)):
lst = list(lst)
pos = 0
for skip, n in enumerate(lengths):
lst = rot(lst, pos)
lst[:n] = lst[n-1::-1]
lst = rot(lst, -pos)
pos += n + skip
pos %= len(lst)
return lst

def knot_hash_check(lengths, lst=range(256)):
a, b, *_ = knot_hash(lengths, lst)
return a * b

assert knot_hash([3, 4, 1, 5], range(5),) == [3, 4, 2, 1, 0]
assert knot_hash_check([3, 4, 1, 5], range(5),) == 12

knot_hash_check(map(int, Input(10).split(',')))

Out[28]:
40602

### Part 2¶

In [29]:
import operator
from functools import reduce

def knot_hash2(chars, lst=range(256)):
lengths = list(map(ord, chars)) + [17, 31, 73, 47, 23]
sparse = knot_hash(lengths * 64, lst)
dense = (reduce(operator.xor, block) for block in grouper(sparse, 16))
return ''.join(map('{:02x}'.format, dense))

examples(knot_hash2,
'', 'a2582a3a0e66e6e86e3812dcb672a272',
'AoC 2017', '33efeb34ea91902bb2f59c9920caa6cd',
'1,2,3', '3efbe78a8d82f29979031a4aa0b16a9d',
'1,2,4', '63960835bcdc130f0b66d7ff4f6a5a8e'
)

knot_hash2(Input(10))

Out[29]:
'35b028fe2c958793f7d5a61d07a008c8'

## Day 11: Hex Ed¶

In [30]:
HEX_DIRS = {'n': 1, 's': -1, 'ne': 1j, 'sw': -1j, 'nw': 1-1j, 'se': -1+1j}

def walk(stepstr):
"Return axial coordinates."
return sum(map(HEX_DIRS.get, stepstr.split(',')))

def hex_len(p):
"Return the Manhattan length of a hex grid axial vector."
q, r = p.real, p.imag
return int(max(map(abs, (q, r, q + r))))

def hex_distance(stepstr):
return hex_len(walk(stepstr))

examples(hex_distance,
'ne,ne,ne', 3,
'ne,ne,sw,sw', 0,
'ne,ne,s,s', 2,
'se,sw,se,sw,sw', 3
)

hex_distance(Input(11))

Out[30]:
687

### Part 2¶

In [31]:
from itertools import accumulate

def iter_walk(stepstr):
yield from accumulate(map(HEX_DIRS.get, stepstr.split(',')))

max(map(hex_len, iter_walk(Input(11))))

Out[31]:
1483

## Day 12: Digital Plumber¶

In [32]:
def groups(lines):
Pipe = converting_tuple('pipe', matcher=r'(?P<p>\S+) <-> (?P<ps>.+)',
p=int, ps=lambda s:set(map(int, s.split(', '))))
groups = set()
for pipe in map(Pipe, lines):
new = pipe.ps | {pipe.p}
merged = {g for g in groups if g & new}
groups -= merged
groups |= {frozenset(reduce(operator.ior, merged, new))}
return groups

def pipe_count(lines):
return len(next(p for p in groups(lines) if 0 in p))

example(pipe_count(here_lines('''
0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5''')), 6)

pipe_count(Input(12).lines)

Out[32]:
152

### Part 2¶

In [33]:
example(len(groups(here_lines('''
0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5'''))), 2)

len(groups(Input(12).lines))

Out[33]:
186

## Day 13: Packet Scanners¶

This ended up being overkill. It's not necessary to know the scanner position, just whether it's at zero.

In [34]:
Layer = converting_tuple('layer',
matcher=r'(?P<depth>\d+): (?P<range>\d+)',
depth=int, range=int)

return {l.depth: l.range for l in map(Layer, lines)}

def iter_caught(layers, delay=0):
def pos(l, t):
"Scanner position of layer #l at time t; None if no layer."
if l not in layers:
return None
r = layers[l]
p = t % (2 * (r - 1))
if p >= r - 1:
p = r - 2 - (p - r)
return p
for i in range(max(layers.keys()) + 1):
if 0 == pos(i, i + delay):
yield i, layers[i]

def severity(lines):
return sum(l * r for l, r in iter_caught(layers))

EXAMPLE13 = here_lines('''
0: 3
1: 2
4: 4
6: 4''')

example(severity(EXAMPLE13), 24)

severity(Input(13).lines)

Out[34]:
1928

### Part 2¶

In [35]:
from itertools import count

def caught(layers, delay=0):
return next((l * r for l, r in iter_caught(layers, delay=delay)), None) is not None

example(caught(ex13, delay=0), True)
example(caught(ex13, delay=10), False)

def find_delay(layers):
return next(i for i in count() if not caught(layers, delay=i))

example(find_delay(ex13), 10)


Out[35]:
3830344

## Day 14: Disk Defragmentation¶

In [36]:
def hash_bin_digits(h, places=128):
s = bin(int(h, 16))[2:]
yield from (c == '1' for c in '0' * (places - len(s)) + s)

print('\n'.join(''.join('#' if c else '.'
for c in hash_bin_digits(knot_hash2('flqrgnkx-{}'.format(i))))[:8]
for i in range(8)))

example(
sum(d for i in range(128) for d in hash_bin_digits(knot_hash2('flqrgnkx-{}'.format(i)))),
8108)

sum(d for i in range(128) for d in hash_bin_digits(knot_hash2('ugkiagan-{}'.format(i))))

##.#.#..
.#.#.#.#
....#.#.
#.#.##.#
.##.#...
##..#..#
.#...#..
##.#.##.

Out[36]:
8292

### Part 2¶

In [37]:
def count_regions(key):
dirs = (0, -1j, 1j, -1, 1)
regions = set()
squares = (i+j*1j
for j in range(128)
for i, d in enumerate(hash_bin_digits(knot_hash2('{}-{}'.format(key, j))))
if d)
for s in squares:
used = frozenset(s + d for d in dirs)
overlaps = [r for r in regions if s in r]
if overlaps:
regions -= set(overlaps)
else:
return len(regions)

example(count_regions('flqrgnkx'), 1242)

count_regions('ugkiagan')

Out[37]:
1069

## Day 15: Dueling Generators¶

In [38]:
def gen(factor, start):
yield from repeatedly(lambda n:n * factor % 2147483647, start)

def matches(starts, count):
factors = (16807, 48271)
g1, g2 = map(gen, factors, starts)
return sum((a ^ b) & 0xffff == 0 for a, b in islice(zip(g1, g2), count))

example(matches((65, 8921), 5))

matches((783, 325), int(4e7))

Out[38]:
650

### Part 2¶

In [39]:
def gen2(factor, start, divisor):
yield from (n for n in gen(factor, start) if n % divisor == 0)

def matches2(starts, count):
factors = (16807, 48271)
divisors = (4, 8)
g1, g2 = map(gen2, factors, starts, divisors)
return sum((a ^ b) & 0xffff == 0 for a, b in islice(zip(g1, g2), count))

example(matches2((65, 8921), 1055), 0)
example(matches2((65, 8921), 1056), 1)
example(matches2((65, 8921), int(5e6)), 309)

matches2((783, 325), int(5e6))

Out[39]:
336

I made things unnecessarily difficult by making apply_move a pure function that constructs a new string, instead of mutating a list.

The latter could have been done with state[i], state[j] = state[j], state[i].

In [40]:
def apply_move(move, state):
m, a = move[0], move[1:]
if '/' in a: a, b = a.split('/')
if   m == 's': return rot(state, -int(a))
elif m == 'x': i, j = int(a), int(b)
elif m == 'p': i, j = state.index(a), state.index(b)
else: raise Exception("unknown move {} in {}".format(m, move))
i, j = sorted([i, j])
a, b = state[i:i+1], state[j:j+1]
pre, mid, post = state[:i], state[i+1:j], state[j+1:]
return pre + b + mid + a + post

example(apply_move('s3', 'abcde'), 'cdeab')
example(apply_move('s1', 'abcde'), 'eabcd')
example(apply_move('x3/4', 'eabcd'), 'eabdc')
example(apply_move('pe/b', 'eabdc'), 'baedc')

def apply_moves(moves, state):
for m in moves.split(','):
state = apply_move(m, state)
return state

example(apply_moves('s1,x3/4,pe/b', 'abcde'), 'baedc')

apply_moves(Input(16), 'abcdefghijklmnop')

Out[40]:
'glnacbhedpfjkiom'

### Part 2¶

In [41]:
def find_period(moves, state):
initial = state
for i in count(1):
state = apply_moves(moves, state)
if state == initial:
return i

def nth_state(moves, state, n=10**9):
p = find_period(moves, state)
for _ in range(n % p):
state = apply_moves(moves, state)
return state

nth_state(Input(16), 'abcdefghijklmnop')

Out[41]:
'fmpanloehgkdcbji'

### Alternative¶

This approach relies more on higher-order functions and iterators.

In [42]:
def find_period(moves, state):
states = repeatedly(lambda s:apply_moves(moves, s), state)
return 1 + iter_index(states, state)

def nth_state(moves, state, n=10**9):
p = find_period(moves, state)
states = repeatedly(lambda s:apply_moves(moves, s), state)
return iter_nth(states, n % p - 1)

nth_state(Input(16), 'abcdefghijklmnop')

Out[42]:
'fmpanloehgkdcbji'

## Day 17: Spinlock¶

In [43]:
def spinlock(stride, count):
buf = []
pos = 0
for i in range(count):
buf.insert(pos + 1, i)
pos += stride + 1
pos %= len(buf)
return buf

example(spinlock(3, 4), [0, 2, (3), 1])
example(spinlock(3, 10), [0, (9), 5, 7, 2, 4, 3, 8, 6, 1])

def after(steps, last=2017):
buf = spinlock(steps, last+1)
return (buf + buf)[buf.index(last) + 1]

example(after(3), 638)

after(337)

Out[43]:
600
In [44]:
from numba import jit

@jit # 9.19 s -> 427 ms
def spinlock2(stride, last):
buflen = 0
pos = 0
x = None
for i in range(last + 1):
if pos == 0:
x = i
buflen += 1
pos += stride + 1
pos %= buflen
return x

spinlock2(337, 50000000)

Out[44]:
31220910

## Day 18: Duet¶

In [45]:
from collections import defaultdict
import string
import operator

def iplay(lines):
R = defaultdict(int)
snd = None
pc = 0
while 0 <= pc < len(lines):
line = lines[pc]
op, *args = line.split()
if len(args) < 2: args += args
x, y = args
X = R[x]
Y = int(y) if y[0] in string.digits + '-' else R[y]
if op in ops: R[x] = ops[op](X, Y)
elif op == 'snd': snd = X
elif op == 'set': R[x] = Y
elif op == 'rcv':
if X > 0: yield snd
elif op == 'jgz':
if X > 0: pc += Y - 1
else: raise Exception("Unknown op: {} in {}".format(op, lines[pc]))
pc += 1

def play(lines):
return next(iplay(lines))

example(play(here_lines('''
set a 1
mul a a
mod a 5
snd a
set a 0
rcv a
jgz a -1
set a 1
jgz a -2''')), 4)

play(Input(18).lines)

Out[45]:
3188

### Part 2¶

In [46]:
from queue import Queue

def performer(lines, n, qin, qout):
def ev(s): return int(s) if s[0] in string.digits + '-' else R[s]
R = defaultdict(int, {'p': n})
pc = 0
while 0 <= pc < len(lines):
line = lines[pc]
op, x, y, *_ = line.split() + ['0']
X, Y = ev(x), ev(y)
def assign(val): R[x] = val
yield op
if op in ops: assign(ops[op](X, Y))
elif op == 'snd': qout.put(X)
elif op == 'set': assign(Y)
elif op == 'rcv':
while qin.empty():
yield 'blocked'
assign(qin.get())
elif op == 'jgz':
if X > 0:
pc += Y - 1
else:
raise Exception("Unknown op: {} in {}".format(op, lines[pc]))
pc += 1

def duet(lines):
q1, q2 = Queue(), Queue()
g1 = performer(lines, 0, q2, q1)
g2 = performer(lines, 1, q1, q2)
s1 = s2 = None
n = 0
while s1 != 'blocked' or s2 != 'blocked':
s1 = next(g1)
s2 = next(g2)
if s2 == 'snd':
n += 1
return n

example(duet(here_lines('''
snd 1
snd 2
snd p
rcv a
rcv b
rcv c
rcv d''')), 3)

duet(Input(18).lines)

Out[46]:
7112

### Alternative¶

In [47]:
from itertools import takewhile, zip_longest

def duet(lines):
q1, q2 = Queue(), Queue()
g1 = performer(lines, 0, q2, q1)
g2 = performer(lines, 1, q1, q2)
all_blocked_set = {'blocked'}
any_running = lambda states:set(states) != all_blocked_set
state_pairs = takewhile(any_running, zip_longest(g1, g2))
return sum(s == 'snd' for _, s in state_pairs)

example(duet(here_lines('''
snd 1
snd 2
snd p
rcv a
rcv b
rcv c
rcv d''')), 3)

duet(Input(18).lines)

Out[47]:
7112

## Day 19: A Series of Tubes¶

In [48]:
import string

def ifollow(rows):
# which cell values are valid for a given direction
valid = {d: string.ascii_letters + '+' + ('-' if d.real else '|')
for d in (1, -1, 1j, -1j)}
p, d = rows[0].index('|'), 1j  # start at the first-row |, heading south
def at(p):
try:
return rows[int(p.imag)][int(p.real)]
except IndexError:
return ' '
while True:
p0 = p
p += d
c = at(p)
if c == ' ':
for d1 in (1j * d, -1j * d):
p1 = p0 + d1
if at(p1) in valid[d1]:
p, d = p1, d1
c = at(p) or ' '
break
if c == ' ': return
yield p, c

def follow(rows):
return ''.join(c for _, c in ifollow(rows) if c in string.ascii_letters)

example(follow(here_lines('''
|
|  +--+
A  |  C
F---|----E|--+
|  |  |  D
+B-+  +--+
''')), 'ABCDEF')

follow(Input(19).lines)

Out[48]:
'KGPTMEJVS'

### Part 2¶

In [49]:
def steps(rows):
return 1 + iter_len(ifollow(rows))

example(steps(here_lines('''
|
|  +--+
A  |  C
F---|----E|--+
|  |  |  D
+B-+  +--+
''')), 38)

steps(Input(19).lines)

Out[49]:
16328

## Day 20: Particle Swarm¶

In [50]:
import numpy as np

def closest(lines):
S = np.array([list(map(int, re.findall(r'-?\d+', line))) for line in lines])
P, V, A = S[:,:3], S[:,3:6], S[:,6:]
# TODO repeat until sign(P) or sign(V) == sign(V) && sign(V) or sign(A) == sign(A).
# Then return the slowest particle.
for _ in range(10000):
V += A
P += V
return abs(P).sum(1).argmin()

example(closest(here_lines('''
p=< 3,0,0>, v=< 2,0,0>, a=<-1,0,0>
p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>
''')), 0)

closest(Input(20).lines)

Out[50]:
119

### Part 2¶

In [51]:
def closest(lines):
S = np.array([list(map(int, re.findall(r'-?\d+', line))) for line in lines])
P, V, A = (S[:,n:n+3] for n in range(0, 9, 3))
for _ in range(1000):
V += A
P += V
D = np.array([np.all(P == P[i,:], axis = 1) for i in range(S.shape[0])]).sum(axis=1)
S = S[D == 1]
return S.shape[0]

example(closest(here_lines('''
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>''')), 1)

closest(Input(20).lines)

Out[51]:
471

## Day 21: Fractal Art¶

This ended up with much more code than the other days. It was fun to right, but it makes me suspect I'm doing it wrong.

Some of these methods are assertions and printable representations that aren't strictly necessary to compute the answer, but that I needed in order to keep from getting lost along the way. I'm not counting those as the “much more code”.

In [52]:
import operator
from functools import reduce
from itertools import product

class Grid(list):
"A Grid is a sequence of sequences of characters."

def __init__(self, rows):
"""Construct a grid from a sequence of sequence of characters, a sequence of strings, or a string
'abc/def/ghi."""
if isinstance(rows, str):
rows = rows.split('/')
rows = list(map(list, rows))
assert all(isinstance(c, str) and len(c) == 1 for row in rows for c in row), "cells must be characters"
assert set(map(len, rows)) == {len(rows)}, "must be square"
return super().__init__(rows)

def __repr__(self):
return 'Grid({!r})'.format('/'.join(map(''.join, self)))

def __str__(self):
return '\n'.join(map(''.join, self))

@property
def key(self):
"A value (it happens to be a string) used as a key in the rule table."
return '/'.join(map(''.join, self))

def transpose(self):
"Return the transpose of the grid, as a grid."
return Grid(zip(*self))

@property
def T(self):
"A property synonym for Grid.transpose(). By analogy with numpy."
return self.transpose()

@property
def tiles(self):
"Find the smallest non-unary divisor N, and tile the grid into tiles N✖️N in size."
N = len(self)
w = next(i for i in count(2) if N % i == 0)
return [[Grid(self[i+x][j:j+w] for x in range(w))
for i in range(0, N, w)]
for j in range(0, N, w)]

@classmethod
def untile(k, tiles):
"Create a Grid from a list of list of tiles."
return k(reduce(operator.add, r) for t in zip(*tiles) for r in zip(*t))

@property
def symmetries(self):
"Generate the dihedral symmetries."
flips = (lambda x:x, lambda x:x[::-1])
for g, hflip, vflip in product((self, self.T), flips, flips):
yield Grid(vflip(list(map(hflip, g))))

print(Grid('.#./..#/###'), '\n')
print('transpose ='); print(Grid('.#./..#/###').T, '\n')
print('tiles ='); print(Grid('1234/5678/9ABC/DEFG').tiles, '\n')
print('untile ->'); print(Grid.untile(Grid('1234/5678/9ABC/DEFG').tiles), '\n')
print('symmetries ='); print(list(Grid('12/34').symmetries))

.#.
..#
###

transpose =
..#
#.#
.##

tiles =
[[Grid('12/56'), Grid('9A/DE')], [Grid('34/78'), Grid('BC/FG')]]

untile ->
1234
5678
9ABC
DEFG

symmetries =
[Grid('12/34'), Grid('34/12'), Grid('21/43'), Grid('43/21'), Grid('13/24'), Grid('24/13'), Grid('31/42'), Grid('42/31')]

In [53]:
def parse_rules(lines):
return {sym.key: Grid(rhs)
for line in lines
for lhs, rhs in [line.split(' => ')]
for sym in Grid(lhs).symmetries}

EXAMPLE_RULES = here_lines('''
../.# => ##./#../...
.#./..#/### => #..#/..../..../#..#''')

parse_rules(EXAMPLE_RULES)

Out[53]:
{'###/#../.#.': Grid('#..#/..../..../#..#'),
'###/..#/.#.': Grid('#..#/..../..../#..#'),
'##./#.#/#..': Grid('#..#/..../..../#..#'),
'#../#.#/##.': Grid('#..#/..../..../#..#'),
'#./..': Grid('##./#../...'),
'.##/#.#/..#': Grid('#..#/..../..../#..#'),
'.#./#../###': Grid('#..#/..../..../#..#'),
'.#./..#/###': Grid('#..#/..../..../#..#'),
'.#/..': Grid('##./#../...'),
'..#/#.#/.##': Grid('#..#/..../..../#..#'),
'../#.': Grid('##./#../...'),
'../.#': Grid('##./#../...')}
In [54]:
def enhance(grid, rules):
return Grid.untile([rules[tile.key] for tile in row] for row in grid.tiles)

enhance(Grid('.#./..#/###'), parse_rules(EXAMPLE_RULES))

Out[54]:
Grid('#..#/..../..../#..#')
In [55]:
FRACTAL_ART_INITIAL = Grid('.#./..#/###')

def art(rules='', n=1, grid=FRACTAL_ART_INITIAL):
rules = parse_rules(rules)
for _ in range(n):
grid = enhance(grid, rules)
return grid

def count_pixels(rules, n=5):
return str(art(rules=rules, n=n)).count('#')

print(art(EXAMPLE_RULES, 2))

example(count_pixels(EXAMPLE_RULES, 2), 12)

count_pixels(Input(21).lines)

##.##.
#..#..
......
##.##.
#..#..
......

Out[55]:
186

### Part 2¶

In [56]:
count_pixels(Input(21).lines, n=18)

Out[56]:
3018423

## Day 22: Sporifica Virus¶

In [57]:
def show(infections, p):
#x0, x1, y0, y1 = map(int, (m(map(coord, infections))
#                           for coord in (lambda c:c.real, lambda c:c.imag)
#                           for m in (min, max)))
x0, x1, y0, y1 = -5, 5, -5, 5
print('-' * 60)
for y in range(y0, y1 + 1):
print(''.join(([' {} ', '[{}]'][-y + x*1j == p]).format('.#'[-y + x*1j in infections])
for x in range(x0, x1 + 2)))

def virus(lines, n=10000):
enum = lambda seq:enumerate(seq, -(len(seq) // 2))
infections = {-y + x*1j
for y, line in enum(lines)
for x, c in enum(line)
if c == '#'}
p, d = 0, 1
a = 0
for _ in range(n):
infected = p in infections
d *= 1j if infected else -1j
(set.remove if infected else set.add)(infections, p)
if not infected: a += 1
p += d
return a

EXAMPLE22 = here_lines('''
..#
#..
...''')

example(virus(EXAMPLE22, 70), 41)

virus(Input(22).lines)

Out[57]:
5330

### Part 2¶

In [58]:
from collections import defaultdict

def show(states, p):
print('-' * 60)
x0, x1, y0, y1 = -5, 5, -5, 5
for y in range(y0, y1 + 1):
print(''.join(([' {} ', '[{}]'][-y + x*1j == p]).format(states[-y + x*1j]) for x in range(x0, x1 + 2)))

def virus(lines, n=10000000):
enum = lambda seq:enumerate(seq, -(len(seq) // 2))
states = defaultdict(lambda:'.',
((-y + x*1j, c)
for y, line in enum(lines)
for x, c in enum(line)))
transitions = {'.': ('W', -1j), 'W': ('#', 1), '#': ('F', 1j), 'F': ('.', -1)}
counts = defaultdict(int)
p, d = 0, 1
for _ in range(n):
s, t = transitions[states[p]]
counts[s] += 1
states[p] = s
d *= t
p += d
return counts['#']

example(virus(EXAMPLE22, 100), 26)

virus(Input(22).lines)

Out[58]:
2512103

## Day 23: Coprocessor Conflagration¶

In [59]:
def co1(lines, a=0):
def ev(s): return int(s) if s[0] in string.digits + '-' else R[s]
R = defaultdict(int, {'a': 0})
pc = 0
while 0 <= pc < len(lines):
line = lines[pc]
op, x, y, *_ = line.split()
yield pc, op, x, y, R
X, Y = ev(x), ev(y)
if   op == 'set': R[x]  = Y
elif op == 'sub': R[x] -= Y
elif op == 'mul': R[x] *= Y
elif op == 'jnz':
if X != 0:
pc += Y - 1
else: raise Exception("Unknown op: {} in {}".format(op, lines[pc]))
pc += 1

sum(op == 'mul' for _, op, *_ in co1(Input(23).lines))

Out[59]:
3969

### Part 2¶

I punted on part 2. It's obviously engineered to take too long to simulate. The right way to do it is either to disassemble the code, or run it for a while and look for patterns. Neither of these looked fun, so I'm slowly developing code to collect a higher-level view of what's going on instead.

In [60]:
countdown = 5
spies = [14, 19]
prev = {}
for pc, op, x, y, R in co1(Input(23).lines, 1):
#print(op, x, R.get(y, y), ' '.join(map(lambda x:'{}={}'.format(x[0], x[1]), sorted(R.items()))))
if (pc in spies if spies else op == 'jnz'):
#print(pc, R[x] != 0, ' '.join(map(lambda kv:'{}={}'.format(*kv), sorted(R.items()))))
print(pc, R[x] != 0, ' '.join(map(lambda kv:'{}={} ({})'.format(kv[0], kv[1], kv[1] - prev.get(kv[0], kv[1])), sorted(R.items()))))
prev = R.copy()
if R[x] == 0: break
countdown -= 1
if countdown <= 0: break

14 True a=0 (0) b=65 (0) c=65 (0) d=2 (0) e=2 (0) f=1 (0) g=-61 (0)
19 True a=0 (0) b=65 (0) c=65 (0) d=2 (0) e=3 (1) f=1 (0) g=-62 (-1)
14 True a=0 (0) b=65 (0) c=65 (0) d=2 (0) e=3 (0) f=1 (0) g=-59 (3)
19 True a=0 (0) b=65 (0) c=65 (0) d=2 (0) e=4 (1) f=1 (0) g=-61 (-2)
14 True a=0 (0) b=65 (0) c=65 (0) d=2 (0) e=4 (0) f=1 (0) g=-57 (4)


## Day 24: Electromagnetic Moat¶

In [61]:
def bridges(lines):
components = list(tuple(map(int, l.split('/'))) for l in lines)
# Assume <=1 component per (a, b) pair. Else rewrite to use [] for components
assert len(components) == len(set(components))
d = defaultdict(set)  # {port: [components that connect to that port]}
for c in components:
for p in c:
def extend(bridge, p):
"Generate all the bridges that extend bridge, that ends at port p."
yield bridge
yield from (b
for c in d[p]
if c not in bridge
for b in extend(bridge + (c,), sorted(c, key=lambda p0:p0==p)[0]))
return extend((), 0)

def strength(bridge):
return sum(p for c in bridge for p in c)

def strongest(lines):
return max(map(strength, bridges(lines)))

data24 = here_lines('''
0/2
2/2
2/3
3/4
3/5
0/1
10/1
9/10
''')

example(strongest(data24), 31)

strongest(Input(24).lines)

Out[61]:
1868

The function above was re-written after a false start involving dynamic programming. Building a table of bridge $i \leftrightarrow j$, and iteratively joining $i \leftrightarrow j \leftrightarrow k$, ended up taking longer than the implementation above.

Using set for the component and/or bridge produces only a marginal improvement. Using a dotted pair class (with __slots__) is about 50% slower.

### Part 2¶

In [62]:
def strongest_longest(lines):
return strength(max(bridges(lines), key=lambda b:(len(b), strength(b))))

example(strongest_longest(data24), 19)

strongest_longest(Input(24).lines)

Out[62]:
1841

## Day 25: The Halting Problem¶

In [63]:
MACHINE_SOURCE = '''
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.'''.strip()

In [64]:
import re
from collections import defaultdict, Counter

def parse(source):
q0 = re.match(r'Begin in state (\S+?)\.', source).group(1)
N = int(re.search(r'Perform a diagnostic checksum after (\d+)', source).group(1))
matcher = re.compile('.*?'.join([r'If the current value is (\w+):',
r'Write the value (\w+)',
r'Move .*? to the (\w+)',
'Continue with state (\w+)']),
re.DOTALL)
def transitions(text):
return {s: t for s, *t in matcher.findall(text)}
verses = re.findall(r'In state (\S+?):(.+?)(?:\n\n|\$)', source, re.DOTALL)
return q0, N, {q: transitions(body) for q, body in verses}

def run(source):
q, N, δ = parse(source)
Γ, j = defaultdict(lambda:'0'), 0
for _ in range(N):
Γ[j], shift, q = δ[q][Γ[j]]
j += {'left': -1, 'right': 1}[shift]
return Counter(Γ.values())['1']

example(run(MACHINE_SOURCE), 3)

run(Input(25))

Out[64]:
3145