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.
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.
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)
# 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)
class InputStr(str):
def __init__(self, day):
self.fname = 'data/advent-2017/input-{}.txt'.format(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):
with open('data/advent-2017/input-{}.txt'.format(day)) as f:
return InputStr(f.read().rstrip('\n'))
Beef up multiline string literals.
def Here(s):
return InputStr(s.strip('\n'))
def here_lines(s):
return Here(s).lines
here_lines('''
Reads a multiline string,
ignoring an initial and final
line break''')
['Reads a multiline string,', 'ignoring an initial and final', 'line break']
def here_grid(s):
return Here(s).grid
here_grid('''
1 2 3
4 5
''')
[[1, 2, 3], [4, 5]]
def rot(seq, n):
"Rotate left by n"
return seq[n:] + seq[:n]
example(rot('abcdef', 2), 'cdefab')
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)
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))
1119
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))
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
.
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
.
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))
1119
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)
41887
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)
226
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
326
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)
363010
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.
from functools import partial, reduce
from itertools import accumulate, chain, islice
from operator import add
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
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)
383
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)
265
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)
372139
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)
29629538
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)
return tuple(starmap(add, zip(zeroed, rot(deltas, -b-1))))
def iter_configs(banks):
banks = tuple(banks)
seen = set()
while banks not in seen:
yield banks
seen.add(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()))
5042
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()))
1086
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)
'rqwgj'
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]))
bad_child = next(c for c in children(d) if inclusive_weight(c) == bad_weight)
yield bad_child, bad_child.weight + good_weight - bad_weight
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)
34386
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)
4877
# 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)
5471
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))
7616
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))
3838
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(',')))
40602
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))
'35b028fe2c958793f7d5a61d07a008c8'
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))
687
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))))
1483
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)
152
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))
186
This ended up being overkill. It's not necessary to know the scanner position, just whether it's at zero.
Layer = converting_tuple('layer',
matcher=r'(?P<depth>\d+): (?P<range>\d+)',
depth=int, range=int)
def read_layers(lines):
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):
layers = read_layers(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)
1928
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
ex13 = read_layers(EXAMPLE13)
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)
find_delay(read_layers(Input(13).lines))
3830344
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))))
##.#.#.. .#.#.#.# ....#.#. #.#.##.# .##.#... ##..#..# .#...#.. ##.#.##.
8292
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)
regions.add(reduce(operator.ior, overlaps, used))
else:
regions.add(used)
return len(regions)
example(count_regions('flqrgnkx'), 1242)
count_regions('ugkiagan')
1069
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))
650
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))
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]
.
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')
'glnacbhedpfjkiom'
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')
'fmpanloehgkdcbji'
This approach relies more on higher-order functions and iterators.
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')
'fmpanloehgkdcbji'
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)
600
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)
31220910
from collections import defaultdict
import string
import operator
ops = {'add': operator.add, 'mul': operator.mul, 'mod': operator.mod}
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
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''')), 4)
play(Input(18).lines)
3188
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)
7112
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)
7112
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)
'KGPTMEJVS'
def steps(rows):
return 1 + iter_len(ifollow(rows))
example(steps(here_lines('''
|
| +--+
A | C
F---|----E|--+
| | | D
+B-+ +--+
''')), 38)
steps(Input(19).lines)
16328
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)
119
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)
471
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”.
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')]
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)
{'###/#../.#.': Grid('#..#/..../..../#..#'), '###/..#/.#.': Grid('#..#/..../..../#..#'), '##./#.#/#..': Grid('#..#/..../..../#..#'), '#../#.#/##.': Grid('#..#/..../..../#..#'), '#./..': Grid('##./#../...'), '.##/#.#/..#': Grid('#..#/..../..../#..#'), '.#./#../###': Grid('#..#/..../..../#..#'), '.#./..#/###': Grid('#..#/..../..../#..#'), '.#/..': Grid('##./#../...'), '..#/#.#/.##': Grid('#..#/..../..../#..#'), '../#.': Grid('##./#../...'), '../.#': Grid('##./#../...')}
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))
Grid('#..#/..../..../#..#')
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)
##.##. #..#.. ...... ##.##. #..#.. ......
186
count_pixels(Input(21).lines, n=18)
3018423
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)
5330
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)
2512103
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))
3969
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.
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)
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
# or add a uid.
assert len(components) == len(set(components))
d = defaultdict(set) # {port: [components that connect to that port]}
for c in components:
for p in c:
d[p].add(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)
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.
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)
1841
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()
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))
3145