Advent of Code 2017

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):
        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'))

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('''
Reads a multiline string,
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
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
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
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
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
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
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)
    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()))
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
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]))
            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)
Out[23]:
34386
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
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
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)

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)
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

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))
Out[35]:
3830344
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)
            regions.add(reduce(operator.ior, overlaps, used))
        else:
            regions.add(used)
    return len(regions)

example(count_regions('flqrgnkx'), 1242)

count_regions('ugkiagan')
Out[37]:
1069
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

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)
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
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
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
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
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)
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
    # 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)
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
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