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_len(iterable):
    return sum(1 for _ in iterable)

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

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):
    if actual != expected:
        print('Actual = {}{} = expected'.format(actual, expected))

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)

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

Helpers for input data files…

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

…and here strings:

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

Part 2

In [7]:
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[7]:
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 [8]:
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[8]:
1119
In [9]:
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[9]:
41887

Part 2

In [10]:
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[10]:
226
In [11]:
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 nth_spiral_position(n):
    "Return the x, y position of the cell that holds n."
    return next(pos for i, pos in enumerate(spiral_positions(), 1) if i == n)

def steps(n):
    "Return the Manhattan distance from 1-based nth element to the center."
    x, y = nth_spiral_position(n)
    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 = ['{:4d}'.format(n) if n else '    ' 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[11]:
326

Part 2

In [12]:
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[12]:
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 [13]:
from functools import 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())
    def fmt(n): return '{:{}}'.format(n, 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 [14]:
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[14]:
383
In [15]:
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[15]:
265
In [16]:
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

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

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

example(jump_count(jumps), 5)
jump_count(Input(5).lines)
Out[16]:
372139
In [17]:
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(jumps), 10)
jump_count(Input(5).lines)
Out[17]:
29629538
In [18]:
def rot(seq, n):
    "Rotate left by n"
    return seq[n:] + seq[:n]

rot('abcdef', 2)
Out[18]:
'cdefab'
In [19]:
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[19]:
5042

Part 2

In [20]:
def iter_last(iterable, defaultvalue=None):
    item = defaultvalue
    for item in iterable:
        pass
    return item
    
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[20]:
1086
In [21]:
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[21]:
'rqwgj'
In [22]:
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[22]:
34386
In [23]:
import re
from collections import defaultdict, namedtuple
from operator import ge, le, gt, lt, eq, ne, add, sub

class converting_tuple(object):
    """This is like 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.matcher = re.compile(matcher).match if isinstance(matcher, str) else matcher
        
    def __call__(self, d):
        if isinstance(d, str):
            d = self.matcher(d).groupdict()
        return self.constr(*(fn(d[k]) for k, fn in self.converters.items()))

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[23]:
4877
In [24]:
# I would have written part 1's max_register_value in terms of these, if I'd known what was coming.
# Instead, this is remixed from that.
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[24]:
5471
In [25]:
def count_groups(s):
    s = re.sub(r'!.', '', s)
    s = re.sub(r'<.*?>', '', s)
    return sum(c == '{' for c in s)

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[25]:
7616
In [26]:
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[26]:
3838
In [27]:
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_mul(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_mul([3, 4, 1, 5], range(5),) == 12

knot_hash_mul(map(int, Input(10).split(',')))
Out[27]:
40602
In [28]:
def knot_hash_rounds(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_hash_rounds,
         '', 'a2582a3a0e66e6e86e3812dcb672a272',
         'AoC 2017', '33efeb34ea91902bb2f59c9920caa6cd',
         '1,2,3', '3efbe78a8d82f29979031a4aa0b16a9d',
         '1,2,4', '63960835bcdc130f0b66d7ff4f6a5a8e'
        )
knot_hash_rounds(Input(10))
Out[28]:
'35b028fe2c958793f7d5a61d07a008c8'
In [34]:
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.__getitem__, 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[34]:
687
In [30]:
from itertools import accumulate

def iter_walk(stepstr):
    return accumulate(map(HEX_DIRS.__getitem__, stepstr.split(',')))

max(map(hex_len, iter_walk(Input(11))))
Out[30]:
1483