my answers in Python

Advent of Code 2018.md

Advent of Code 2018

my answers in Python (see also Haskell branch and Kotlin branch)

day1.py

from collections import defaultdict

with open('day1.txt') as puzzle_file:
    puzzle_input = [int(line.strip()) for line in puzzle_file]

def part2(diffs):
    total, seen = 0, {0}
    for d in diffs:
        total += d
        if total in seen:
            return d
    f = 0
    group = defaultdict(list)
    for i, d in enumerate(diffs):
        f += d
        group[f % total].append((f, i))
    return min((abs(y - x), j, x) for g in group.values() for x, i in g for y, j in g
               if i != j and (total < 0) == (x < y))[2]

print(sum(puzzle_input))
print(part2(puzzle_input))

day10.py

from collections import Counter, namedtuple
import re

Point = namedtuple('Point', 'x y dx dy')

with open('day10.txt') as puzzle_file:
    pattern = re.compile(r'-?\d+')
    points = [Point(*(int(m.group()) for m in pattern.finditer(line))) for line in puzzle_file]

times = Counter()
for i, p1 in enumerate(points):
    x1, y1, dx1, dy1 = p1
    for j in range(i + 1, len(points)):
        x2, y2, dx2, dy2 = points[j]
        if dx1 != dx2 and (x1 - x2) % (dx2 - dx1) == 0:
            times[(x1 - x2) // (dx2 - dx1)] += 1
        if dy1 != dy2 and (y1 - y2) % (dy2 - dy1) == 0:
            times[(y1 - y2) // (dy2 - dy1)] += 1
t, _ = times.most_common(1)[0]
points = {(x + dx * t, y + dy * t) for x, y, dx, dy in points}
min_x, min_y = min(x for (x, y) in points), min(y for (x, y) in points)
max_x, max_y = max(x for (x, y) in points), max(y for (x, y) in points)
for y in range(min_y, max_y + 1):
    print(''.join(u'░▓'[(x, y) in points] for x in range(min_x, max_x + 1)))
print(t)

day11.py

from functools import partial
from multiprocessing import Pool

with open('day11.txt') as puzzle_file:
    serial = int(puzzle_file.read().strip())

def tabulate(serial, size=300):
    table = [(size + 1) * [0]]
    for y in range(1, size + 1):
        row = [0]
        for x in range(1, size + 1):
            p = (((x + 10) * y + serial) * (x + 10)) // 100 % 10 - 5
            row.append(table[-1][x] + row[-1] - table[-1][x - 1] + p)
        table.append(row)
    return table

def max_box(table, size, n):
    return max((table[y][x] - table[y + n][x] - table[y][x + n] + table[y + n][x + n], x, y, n)
               for x in range(size - n + 1) for y in range(size - n + 1))

def part1(table, size=300):
    _, x, y, _ = max_box(table, size, 3)
    return '{},{}'.format(x + 1, y + 1)

def part2(table, size=300):
    p = Pool()
    _, x, y, n = max(p.imap_unordered(partial(max_box, table, size), range(1, size + 1)))
    p.close()
    return '{},{},{}'.format(x + 1, y + 1, n)

table = tabulate(serial)
print(part1(table))
print(part2(table))

day12.py

with open('day12.txt') as puzzle_file:
    initial = puzzle_file.readline()[15:-1]
    mappings = dict(line.strip().split(' => ') for line in puzzle_file if line.strip())

def recenter(offset, state):
    l = state.find('#')
    return (0, '') if l < 0 else (offset + l, state[l:state.rfind('#', l) + 1])

def step(offset, state):
    extended = '....' + state + '....'
    return recenter(offset - 2, ''.join(
        mappings.get(extended[i:i + 5], '.') for i in range(len(state) + 4)))

def run(n):
    seen = {}
    offset, state = recenter(0, initial)
    i = 0
    while i < n:
        seen[state] = (i, offset)
        offset, state = step(offset, state)
        i += 1
        if state in seen:
            prev_i, prev_offset = seen[state]
            offset += (n - i) // (i - prev_i) * (offset - prev_offset)
            i = n - (n - i) % (i - prev_i)
    return sum(offset + i for i, c in enumerate(state) if c == '#')

print(run(20))
print(run(50000000000))

day13.py

from collections import OrderedDict, namedtuple
import sys

if sys.version_info >= (3, ):
    maketrans = str.maketrans
else:
    from string import maketrans

Cart = namedtuple('Cart', 'orientation crossings')
nesw, nwse = maketrans('^<v>', '>v<^'), maketrans('^<v>', '<^>v')
spins = maketrans('^<v>', '<v>^'), maketrans('', ''), maketrans('^<v>', '>^<v')
crosses = {
    '/': lambda cart: cart._replace(orientation=cart.orientation.translate(nesw)),
    '\\': lambda cart: cart._replace(orientation=cart.orientation.translate(nwse)),
    '+': lambda cart: cart._replace(
        orientation=cart.orientation.translate(spins[cart.crossings % 3]),
        crossings=cart.crossings + 1)
}
moves = {
    '^': lambda pos: (pos[0] - 1, pos[1]),
    '<': lambda pos: (pos[0], pos[1] - 1),
    'v': lambda pos: (pos[0] + 1, pos[1]),
    '>': lambda pos: (pos[0], pos[1] + 1)
}

crossings, carts = {}, {}
with open('day13.txt') as puzzle_file:
    for y, line in enumerate(puzzle_file):
        for x, c in enumerate(line):
            if c in crosses:
                crossings[(y, x)] = crosses[c]
            elif c in moves:
                carts[(y, x)] = Cart(c, 0)

while len(carts) > 1:
    queue, carts = OrderedDict(sorted(carts.items())), {}
    while queue:
        pos, cart = queue.popitem(last=False)
        pos = moves[cart.orientation](pos)
        if carts.pop(pos, None) or queue.pop(pos, None):
            print('{1},{0}'.format(*pos))
            continue
        carts[pos] = crossings[pos](cart) if pos in crossings else cart
print('{1},{0}'.format(*next(iter(carts))))

day14.py

from itertools import islice

with open('day14.txt') as puzzle_file:
    puzzle_input = puzzle_file.read().strip()

def windowed(iterable, size):
    window = size * [None]
    iterator = iter(iterable)
    for pos in range(size - 1):
        window[pos] = next(iterator)
    pos = size - 1
    for element in iterator:
        window[pos] = element
        yield window[pos + 1:] + window[:pos + 1]
        pos = (pos + 1) % size

def game():
    i, j, scores = 0, 1, [3, 7]
    for score in scores:
        yield score
    while True:
        a, b = scores[i], scores[j]
        s = a + b
        if s > 9:
            scores.append(s // 10)
            yield s // 10
        scores.append(s % 10)
        yield s % 10
        i, j = (i + a + 1) % len(scores), (j + b + 1) % len(scores)

offset = int(puzzle_input)
print(''.join(map(str, islice(game(), offset, offset + 10))))
needle = list(map(int, puzzle_input))
print(next(i for i, window in enumerate(windowed(game(), len(needle))) if window == needle))

day15.py

from collections import OrderedDict

class Unit(object):
    def __init__(self, is_elf, hp=200):
        self.is_elf, self.hp = is_elf, hp

walls, initial_units = set(), {}
with open('day15.txt') as puzzle_file:
    for y, line in enumerate(puzzle_file):
        for x, c in enumerate(line):
            if c == '#':
                walls.add((y, x))
            elif c == 'E':
                initial_units[(y, x)] = True
            elif c == 'G':
                initial_units[(y, x)] = False

def adjs(pos):
    y, x = pos
    return ((y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x))

def nearest(start, goals, excludes):
    visited, queue = set(excludes), {start}
    while queue:
        reached = queue.intersection(goals)
        if reached:
            return min(reached)
        visited.update(queue)
        queue = {adj for pos in queue for adj in adjs(pos) if adj not in visited}
    return None

def dbg(units):
    for y in range(min(y for y, _ in walls), max(y for y, _ in walls) + 1):
        row = ''.join('#' if (y, x) in walls else 'GE'[units[(y, x)].is_elf]
                      if (y, x) in units else '.'
                      for x in range(min(x for _, x in walls), max(x for _, x in walls) + 1))
        etc = ', '.join('{}({})'.format('GE'[unit.is_elf], unit.hp)
                        for _, unit in sorted(
                            ((pos[1], unit) for pos, unit in units.items() if pos[0] == y),
                            key=lambda item: item[1]))
        print(row + '   ' + etc if etc else row)

for elf_power in range(3, 201):
    dead_elves, full_rounds = 0, 0
    units = {pos: Unit(is_elf) for pos, is_elf in initial_units.items()}
    while len(set(unit.is_elf for unit in units.values())) > 1:
        #print('After {} round{}:'.format(full_rounds, 's' if full_rounds > 1 else '') if full_rounds else 'Initially:')
        #dbg(units)
        #print('')
        queue, units = OrderedDict(sorted(units.items())), {}
        while queue:
            pos, unit = queue.popitem(last=False)
            other_units = units.copy()
            other_units.update(queue)
            excludes = walls.union(other_units)
            enemies = {k: v for k, v in other_units.items() if unit.is_elf != v.is_elf}
            if not set(adjs(pos)).intersection(enemies):
                enemy_ranges = {adj for enemy_pos in enemies.keys() for adj in adjs(enemy_pos)}
                nearest_enemy_range = nearest(pos, enemy_ranges, excludes)
                if nearest_enemy_range:
                    pos = nearest(nearest_enemy_range, adjs(pos), excludes) or pos
            adjacent_enemies = [(adj, enemies[adj]) for adj in adjs(pos) if adj in enemies]
            if adjacent_enemies:
                target, enemy = min(adjacent_enemies, key=lambda item: (item[1].hp, item[0]))
                enemy.hp -= elf_power if unit.is_elf else 3
                if enemy.hp <= 0:
                    units.pop(target, None)
                    queue.pop(target, None)
                    if enemy.is_elf:
                        dead_elves += 1
            units[pos] = unit
            if not enemies:
                units.update(queue)
                break
        else:
            full_rounds += 1
    #print('Finally:')
    #dbg(units)
    #print('')
    total_hp = sum(unit.hp for unit in units.values())
    print(u'power: {}\trounds: {}\t\u2211hp: {}\tscore: {}\tdead: {}'.format(
        elf_power, full_rounds, total_hp, full_rounds * total_hp, dead_elves))
    #print('\n')
    if not dead_elves:
        break

day16.py

from collections import namedtuple
from functools import wraps
from itertools import groupby
import operator
import re

ops = (lambda regs, a, b: regs[a] + regs[b], lambda regs, a, b: regs[a] + b,
       lambda regs, a, b: regs[a] * regs[b], lambda regs, a, b: regs[a] * b,
       lambda regs, a, b: regs[a] & regs[b], lambda regs, a, b: regs[a] & b,
       lambda regs, a, b: regs[a] | regs[b], lambda regs, a, b: regs[a] | b,
       lambda regs, a, b: regs[a], lambda regs, a, b: a, lambda regs, a, b: int(a > regs[b]),
       lambda regs, a, b: int(regs[a] > b), lambda regs, a, b: int(regs[a] > regs[b]),
       lambda regs, a, b: int(a == regs[b]), lambda regs, a, b: int(regs[a] == b),
       lambda regs, a, b: int(regs[a] == regs[b]))

class Sample(namedtuple('Sample', 'r0 r1 op a b c')):
    def valid_ops(self):
        ret = set()
        for op in ops:
            tmp = list(self.r0)
            tmp[self.c] = op(tmp, self.a, self.b)
            if tmp == self.r1:
                ret.add(op)
        return ret

samples = []
with open('day16.txt') as puzzle_input:
    pattern = re.compile(r'\d+')
    for key, group in groupby((line.strip() for line in puzzle_input), key=bool):
        if not key:
            continue
        group = list(group)
        if len(group) == 3 and group[0].startswith('Before:') and group[2].startswith('After:'):
            r0 = [int(match.group()) for match in pattern.finditer(group[0])]
            r1 = [int(match.group()) for match in pattern.finditer(group[2])]
            op, a, b, c = (int(match.group()) for match in pattern.finditer(group[1]))
            samples.append(Sample(r0, r1, op, a, b, c))
        else:
            isns = [[int(match.group()) for match in pattern.finditer(line)] for line in group]

print(sum(len(sample.valid_ops()) >= 3 for sample in samples))
pending, ops_map = {sample.op: sample.valid_ops() for sample in samples}, {}
while pending:
    done = {k: next(iter(v)) for k, v in pending.items() if len(v) == 1}
    assert done
    ops_map.update(done)
    for k in done.keys():
        del pending[k]
    for v in pending.values():
        v.difference_update(done.values())
regs = 4 * [0]
for op, a, b, c in isns:
    regs[c] = ops_map[op](regs, a, b)
print(regs[0])

day17.py

from inspect import isgenerator
import re

SPACE = 0
WALL = 1
STAGNANT = 2
FLOWING = 3
START_X = 500

field = {}
min_y, max_y, min_x, max_x = float('inf'), float('-inf'), float('inf'), float('-inf')
with open('day17.txt') as puzzle_file:
    pattern = re.compile(r'\d+')
    for line in puzzle_file:
        a, b, c = (int(match.group()) for match in pattern.finditer(line))
        if line.startswith('x'):
            field.update(((y, a), WALL) for y in range(b, c + 1))
            min_y, max_y, min_x, max_x = min(min_y, b), max(max_y, c), min(min_x, a), max(max_x, b)
        elif line.startswith('y'):
            field.update(((a, x), WALL) for x in range(b, c + 1))
            min_y, max_y, min_x, max_x = min(min_y, a), max(max_y, a), min(min_x, b), max(max_x, c)
min_x, max_x = min_x - 1, max_x + 1

def ranges(iterable):
    l, r = None, None
    for value in iterable:
        if l is None or r is None:
            l, r = value, value + 1
        elif l - 1 <= value <= r:
            l, r = min(l, value), max(r, value + 1)
        else:
            yield (l, r)
            l, r = value, value + 1
    if l is not None and r is not None:
        yield (l, r)

def flood(y, x0, x1):
    if y > max_y:
        yield False
        return
    blocked = all(field.get((y, x)) != FLOWING for x in range(x0, x1))
    for x0, x1 in ranges(x for x in range(x0, x1) if (y, x) not in field):
        if not (yield flood(y + 1, x0, x1)):
            for x in range(x0, x1):
                field[(y, x)] = FLOWING
            blocked = False
            continue
        left = x0
        while (y, left - 1) not in field:
            left -= 1
            if field.get((y + 1, left), SPACE) in (SPACE, FLOWING):
                break
        right = x1
        while (y, right) not in field:
            right += 1
            if field.get((y + 1, right - 1), SPACE) in (SPACE, FLOWING):
                break
        for x in range(x0, x1):
            field[(y, x)] = WALL
        blocked_left = left >= x0 or (yield flood(y, left, x0))
        blocked_right = right <= x1 or (yield flood(y, x1, right))
        elt = STAGNANT if blocked_left and blocked_right else FLOWING
        for x in range(left, right):
            field[(y, x)] = elt
        blocked = blocked and blocked_left and blocked_right
    yield blocked

stack, ret = [flood(min_y, START_X, START_X + 1)], None
while stack:
    ret = stack[-1].send(ret)
    if isgenerator(ret):
        stack.append(ret)
        ret = None
    else:
        stack.pop()

if False:
    print(''.join('.+'[x == START_X] for x in range(min_x, max_x + 1)))
    for y in range(min_y, max_y + 1):
        print(''.join('.#~|'[field.get((y, x), SPACE)] for x in range(min_x, max_x + 1)))
print(sum(elt in (STAGNANT, FLOWING) for elt in field.values()))
print(sum(elt == STAGNANT for elt in field.values()))

day18.py

from collections import Counter
from itertools import product

with open('day18.txt') as puzzle_file:
    puzzle_input = ['.' + line.strip() + '.' for line in puzzle_file]
    puzzle_input[:0] = puzzle_input[len(puzzle_input):] = [len(puzzle_input[0]) * '.']
    puzzle_input = tuple(puzzle_input)

lookup = {
    ''.join(area): '|' if area[4] == '.' and c['|'] > 2 else '#'
    if area[4] == '|' and c['#'] > 2 else '.'
    if area[4] == '#' and (c['|'] < 1 or c['#'] < 2) else area[4]
    for area in product(
        '.|#', repeat=9) for c in (Counter(area), )
}

def solve(state, target):
    n, cache = 0, {}
    while n < target:
        if state in cache:
            target = n + 1 + (target - n - 1) % (n - cache[state])
        else:
            cache[state] = n
        state = tuple(
            row if y in (0, len(state) - 1) else ''.join(
                c if x in (0, len(row) - 1) else
                lookup[state[y - 1][x - 1:x + 2] + row[x - 1:x + 2] + state[y + 1][x - 1:x + 2]]
                for x, c in enumerate(row)) for y, row in enumerate(state))
        n += 1
    c = Counter(''.join(state))
    return c['|'] * c['#']

print(solve(puzzle_input, 10))
print(solve(puzzle_input, 1000000000))

day19.py

ops = {
    'addr': lambda regs, a, b: regs[a] + regs[b],
    'addi': lambda regs, a, b: regs[a] + b,
    'mulr': lambda regs, a, b: regs[a] * regs[b],
    'muli': lambda regs, a, b: regs[a] * b,
    'banr': lambda regs, a, b: regs[a] & regs[b],
    'bani': lambda regs, a, b: regs[a] & b,
    'borr': lambda regs, a, b: regs[a] | regs[b],
    'bori': lambda regs, a, b: regs[a] | b,
    'setr': lambda regs, a, b: regs[a],
    'seti': lambda regs, a, b: a,
    'gtir': lambda regs, a, b: int(a > regs[b]),
    'gtri': lambda regs, a, b: int(regs[a] > b),
    'gtrr': lambda regs, a, b: int(regs[a] > regs[b]),
    'eqir': lambda regs, a, b: int(a == regs[b]),
    'eqri': lambda regs, a, b: int(regs[a] == b),
    'eqrr': lambda regs, a, b: int(regs[a] == regs[b])
}

with open('day19.txt') as puzzle_file:
    ip = int(puzzle_file.readline().strip()[3:])
    isns = [(op, int(a), int(b), int(c)) for line in puzzle_file
            for op, a, b, c in (line.split(), )]

def sum_factors(n):
    total, d = 0, 1
    while d * d < n:
        if n % d == 0: total += d + n // d
        d += 1
    if d * d == n: total += d
    return total

def cheat(regs):
    base = regs[ip]
    if base + 14 >= len(isns):
        return False
    op, a, b, i = isns[base]
    if op != 'seti' or a != 1 or i == ip:
        return False
    op, a, b, j = isns[base + 1]
    if op != 'seti' or a != 1 or j in (ip, i):
        return False
    op, a, b, k = isns[base + 2]
    if op != 'mulr' or a != i or b != j or k in (ip, i, j):
        return False
    op, a, n, c = isns[base + 3]
    if op != 'eqrr' or a != k or n in (ip, i, j, k) or c != k:
        return False
    op, a, b, c = isns[base + 4]
    if op != 'addr' or a != k or b != ip or c != ip:
        return False
    op, a, b, c = isns[base + 5]
    if op != 'addi' or a != ip or b != 1 or c != ip:
        return False
    op, a, b, m = isns[base + 6]
    if op != 'addr' or a != i or b != 0 or m in (ip, i, j, k, n):
        return False
    op, a, b, c = isns[base + 7]
    if op != 'addi' or a != j or b != 1 or c != j:
        return False
    op, a, b, c = isns[base + 8]
    if op != 'gtrr' or a != j or b != n or c != k:
        return False
    op, a, b, c = isns[base + 9]
    if op != 'addr' or a != ip or b != k or c != ip:
        return False
    op, a, _, c = isns[base + 10]
    if op != 'seti' or a != base + 1 or c != ip:
        return False
    op, a, b, c = isns[base + 11]
    if op != 'addi' or a != i or b != 1 or c != i:
        return False
    op, a, b, c = isns[base + 12]
    if op != 'gtrr' or a != i or b != n or c != k:
        return False
    op, a, b, c = isns[base + 13]
    if op != 'addr' or a != k or b != ip or c != ip:
        return False
    op, a, _, c = isns[base + 14]
    if op != 'seti' or a != base or c != ip:
        return False
    goal = regs[n]
    if goal < 1:
        return False
    regs[ip], regs[i], regs[j], regs[k] = base + 15, goal + 1, goal + 1, 1
    regs[m] += sum_factors(goal)
    return True

def run(regs):
    while 0 <= regs[ip] < len(isns):
        if cheat(regs):
            continue
        op, a, b, c = isns[regs[ip]]
        regs[c] = ops[op](regs, a, b)
        regs[ip] += 1
    return regs

print(run(6 * [0])[0])
print(run([1] + 5 * [0])[0])

day2.py

from collections import Counter
from itertools import combinations

with open('day2.txt') as puzzle_file:
    puzzle_input = [line.strip() for line in puzzle_file]

def part1(words):
    c2, c3 = 0, 0
    for word in words:
        c = Counter(word).values()
        c2 += 2 in c
        c3 += 3 in c
    return c2 * c3

def part2(words):
    for x, y in combinations(words, 2):
        common = [a for a, b in zip(x, y) if a == b]
        if len(x) == len(y) == len(common) + 1:
            return ''.join(common)

print(part1(puzzle_input))
print(part2(puzzle_input))

day20.py

from collections import defaultdict, deque

directions, edges = {'N': 0 + 1j, 'E': 1 + 0j, 'S': 0 - 1j, 'W': -1 + 0j}, defaultdict(set)
with open('day20.txt') as puzzle_file:
    close_stack, open_stack, current = [], [], {0 + 0j}
    for c in puzzle_file.read().strip().lstrip('^').rstrip('$'):
        if c in directions:
            subsequent = [p + directions[c] for p in current]
            for p, q in zip(current, subsequent):
                edges[p].add(q)
                edges[q].add(p)
            current = subsequent
        elif c == '(':
            close_stack.append(set())
            open_stack.append(current)
        elif c == '|':
            close_stack[-1].update(current)
            current = open_stack[-1]
        elif c == ')':
            close_stack[-1].update(current)
            open_stack.pop()
            current = close_stack.pop()

far_count, queue, seen = 0, deque(((0, 0 + 0j), )), set()
while queue:
    depth, p = queue.popleft()
    far_count += depth >= 1000
    queue.extend((depth + 1, q) for q in edges[p] if q not in seen)
    seen.update(edges[p])
print(depth)
print(far_count)

day21.py

ops = {
    'addr': lambda regs, a, b: regs[a] + regs[b],
    'addi': lambda regs, a, b: regs[a] + b,
    'mulr': lambda regs, a, b: regs[a] * regs[b],
    'muli': lambda regs, a, b: regs[a] * b,
    'banr': lambda regs, a, b: regs[a] & regs[b],
    'bani': lambda regs, a, b: regs[a] & b,
    'borr': lambda regs, a, b: regs[a] | regs[b],
    'bori': lambda regs, a, b: regs[a] | b,
    'setr': lambda regs, a, b: regs[a],
    'seti': lambda regs, a, b: a,
    'gtir': lambda regs, a, b: int(a > regs[b]),
    'gtri': lambda regs, a, b: int(regs[a] > b),
    'gtrr': lambda regs, a, b: int(regs[a] > regs[b]),
    'eqir': lambda regs, a, b: int(a == regs[b]),
    'eqri': lambda regs, a, b: int(regs[a] == b),
    'eqrr': lambda regs, a, b: int(regs[a] == regs[b])
}

with open('day21.txt') as puzzle_file:
    ip = int(puzzle_file.readline().strip()[3:])
    isns = [(op, int(a), int(b), int(c)) for line in puzzle_file
            for op, a, b, c in (line.split(), )]

def cheat(regs):
    base = regs[ip]
    if base + 8 >= len(isns):
        return False
    op, a, b, t = isns[base]
    if op != 'seti' or a != 0 or t in (0, ip):
        return False
    op, a, b, u = isns[base + 1]
    if op != 'addi' or a != t or b != 1 or u in (0, ip, t):
        return False
    op, a, n, c = isns[base + 2]
    if op != 'muli' or a != u or b <= 0 or c != u:
        return False
    op, a, r, c = isns[base + 3]
    if op != 'gtrr' or a != u or r in (0, ip, t, u) or c != u:
        return False
    op, a, b, c = isns[base + 4]
    if op != 'addr' or a != u or b != ip or c != ip:
        return False
    op, a, b, c = isns[base + 5]
    if op != 'addi' or a != ip or b != 1 or c != ip:
        return False
    op, a, b, c = isns[base + 6]
    if op != 'seti' or a != base + 8 or c != ip:
        return False
    op, a, b, c = isns[base + 7]
    if op != 'addi' or a != t or b != 1 or c != t:
        return False
    op, a, b, c = isns[base + 8]
    if op != 'seti' or a != base or c != ip:
        return False
    regs[ip], regs[t], regs[u] = base + 8, max(0, regs[r]) // n, 1
    return True

def run(regs):
    while 0 <= regs[ip] < len(isns):
        op, a, b, c = isns[regs[ip]]
        if c == 0:
            raise ValueError('writing value to register 0')
        if op == 'eqrr' and a == 0 and b != 0:
            yield (regs[b])
            regs[c] = 0
            regs[ip] += 1
            continue
        if op == 'eqrr' and a != 0 and b == 0:
            yield (regs[a])
            regs[c] = 0
            regs[ip] += 1
            continue
        if op != 'seti' and a == 0:
            raise ValueError('reading from register 0')
        if op in ('addr', 'mulr', 'banr', 'borr', 'gtir', 'gtrr', 'eqir', 'eqrr') and b == 0:
            raise ValueError('reading from register 0')
        if cheat(regs):
            continue
        regs[c] = ops[op](regs, a, b)
        regs[ip] += 1

seen = set()
for reg in run(6 * [0]):
    if not seen:
        print(reg)
    elif reg in seen:
        break
    ultimate = reg
    seen.add(reg)
print(ultimate)

day22.py

from heapq import heappop, heappush

with open('day22.txt') as puzzle_file:
    depth = int(puzzle_file.readline().split()[1])
    target_x, target_y = map(int, puzzle_file.readline().split()[1].split(','))

maze = {(0, 0): 0, (target_x, target_y): 0}

def get(x, y, raw=False):
    v = maze.get((x, y))
    if v is None:
        if x == 0:
            v = 48271 * y
        elif y == 0:
            v = 16807 * x
        else:
            v = ((get(x - 1, y, True) + depth) % 20183) * ((get(x, y - 1, True) + depth) % 20183)
        maze[(x, y)] = v
    return v if raw else (v + depth) % 20183 % 3

print(sum(get(x, y) for x in range(target_x + 1) for y in range(target_y + 1)))

def estimate(w, x, y, t):
    return w + abs(x) + abs(y) + (0 if t == 1 else 7), w, x, y, t

q = [(0, 0, target_x, target_y, 1)]
ws = {}
while q:
    _, w, x, y, t = heappop(q)
    if (x, y, t) in ws and ws[(x, y, t)] <= w:
        continue
    ws[(x, y, t)] = w
    if x == 0 and y == 0 and t == 1:
        break
    heappush(q, estimate(w + 7, x, y, -(get(x, y) + t) % 3))
    for x, y in ((x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)):
        if x < 0 or y < 0 or get(x, y) == t or (x, y, t) in ws:
            continue
        e = w + 1 + abs(target_x - x) + abs(target_y - y) + (0 if t == 1 else 7)
        heappush(q, estimate(w + 1, x, y, t))
print(w)

day23.py

from collections import OrderedDict, defaultdict, namedtuple
from functools import total_ordering
from heapq import heappop, heappush
from itertools import chain
import re

Bot = namedtuple('Bot', 'x y z r')

with open('day23.txt') as puzzle_file:
    pattern = re.compile(r'pos=<(-?\d+),(-?\d+),(-?\d+)>, r=(\d+)')
    bots = [Bot(*map(int, pattern.match(line).groups())) for line in puzzle_file]

max_r = max(bot.r for bot in bots)
print(
    max(
        sum(abs(b.x - a.x) + abs(b.y - a.y) + abs(b.z - a.z) <= a.r for b in bots) for a in bots
        if a.r == max_r))

@total_ordering
class Octa_ordering(object):
    def __lt__(self, other):
        return self.min < other.min or self.min == other.min and other.max < self.max

class Octa(Octa_ordering, namedtuple('Octa', ('min', 'max'))):
    def __new__(cls, *args, **kwargs):
        if 'bot' in kwargs:
            x, y, z, r = kwargs['bot']
            t, u, v, w = x + y + z, x + y - z, x - y - z, x - y + z
            return super(Octa, cls).__new__(cls, (t - r, u - r, v - r, w - r),
                                            (t + r, u + r, v + r, w + r))
        return super(Octa, cls).__new__(cls, *args, **kwargs)

    def intersect(self, other):
        c, d, e, f = self.min
        g, h, i, j = other.min
        k, l, m, n = self.max
        o, p, q, r = other.max
        s, t, u, v = max(c, g), max(d, h), max(e, i), max(f, j)
        w, x, y, z = min(k, o), min(l, p), min(m, q), min(n, r)
        return None if s > w or t > x or u > y or v > z else Octa((s, t, u, v), (w, x, y, z))

    def distance_to_origin(self):
        o, p, q, r = self.min
        s, t, u, v = self.max
        if o < s and p < t and q < u and r < v:
            w = min(abs(o), abs(s)) if o * s >= 0 else 0
            x = min(abs(p), abs(t)) if p * t >= 0 else 0
            y = min(abs(q), abs(u)) if q * u >= 0 else 0
            z = min(abs(r), abs(v)) if r * v >= 0 else 0
            return max(w, x, y, z)
        return min(
            abs((x + z) // 2) + abs((y - z) // 2) + abs((x - y) // 2)
            for x in range(o, s + 1) for y in range(p + ((p ^ x) & 1), t + 1, 2)
            for z in range(q + ((q ^ x) & 1), u + 1, 2) if r <= x - y + z <= v)

best_count = 0
octs = defaultdict(set)
for i, bot in enumerate(bots):
    octs[Octa(bot=bot)].add(i)
queue = [(0, (), OrderedDict((k, octs[k]) for k in sorted(octs)))]
while queue:
    n, _, rest = heappop(queue)
    if -n < best_count:
        break
    octa, n = rest.popitem()
    sub = defaultdict(set)
    for octa2, m in rest.items():
        octa3 = octa.intersect(octa2)
        if octa3 is not None:
            (n if octa == octa3 else sub[octa3]).update(m)
    if len(n) > best_count:
        best_count, best_distance = len(n), [octa]
    elif len(n) == best_count:
        best_distance.append(octa)
    m = frozenset(chain.from_iterable(rest.values()))
    heappush(queue, (-len(m), m, rest))
    rest = OrderedDict((k, sub[k].union(n)) for k in sorted(sub))
    m = frozenset(chain.from_iterable(rest.values()))
    heappush(queue, (-len(m), m, rest))
print(min(octa.distance_to_origin() for octa in best_distance))

day24.py

from collections import Counter, namedtuple
from operator import attrgetter, itemgetter
import re

Group = namedtuple('Group', 'team id units hp weak immune power type initiative')

with open('day24.txt') as puzzle_file:
    pattern = re.compile(r'''
        (?P<team>\w+(?:\s+\w+)*):|
        (?P<units>\d+)[ ]units[ ]each[ ]with[ ](?P<hp>\d+)[ ]hit[ ]points[ ]
        (?:\((?:
        weak[ ]to[ ](?P<weak1>\w+(?:,[ ]\w+)*)|immune[ ]to[ ](?P<immune1>\w+(?:,[ ]\w+)*)|
        weak[ ]to[ ](?P<weak2>\w+(?:,[ ]\w+)*);[ ]immune[ ]to[ ](?P<immune2>\w+(?:,[ ]\w+)*)|
        immune[ ]to[ ](?P<immune3>\w+(?:,[ ]\w+)*);[ ]weak[ ]to[ ](?P<weak3>\w+(?:,[ ]\w+)*)
        )\)[ ])?
        with[ ]an[ ]attack[ ]that[ ]does[ ]
        (?P<power>\d+)[ ](?P<type>\w+)[ ]damage[ ]at[ ]initiative[ ](?P<initiative>\d+)
    ''', re.X)
    groups = []
    for n, line in enumerate(puzzle_file):
        if not line.strip():
            continue
        m = pattern.match(line)
        if m.group('team'):
            team = m.group('team')
            continue
        groups.append(
            Group(team, n,
                  int(m.group('units')),
                  int(m.group('hp')),
                  frozenset(
                      filter(None, (m.group('weak1') or m.group('weak2') or m.group('weak3') or ''
                                    ).split(', '))),
                  frozenset(
                      filter(None, (m.group('immune1') or m.group('immune2') or m.group('immune3')
                                    or '').split(', '))),
                  int(m.group('power')), m.group('type'), int(m.group('initiative'))))

def run(groups):
    seen = set()
    while len(set(map(attrgetter('team'), groups))) > 1:
        targets, attacks = set(groups), []
        groups.sort(key=lambda group: (group.units * group.power, group.initiative), reverse=True)
        for attacker in groups:
            if all(attacker.team == target.team or attacker.type in target.immune
                   for target in targets):
                continue
            def key(target):
                multiplier = 2 if attacker.type in target.weak else 1
                return (multiplier * attacker.units * attacker.power, target.units * target.power,
                        target.initiative)
            target = max((target for target in targets
                          if attacker.team != target.team and attacker.type not in target.immune),
                         key=key)
            targets.remove(target)
            attacks.append((attacker.initiative, attacker.id, target.id))
        attacks.sort(key=itemgetter(0), reverse=True)
        results = {group.id: group for group in groups}
        for _, attacker_id, defender_id in attacks:
            if attacker_id not in results or defender_id not in results:
                continue
            attacker = results[attacker_id]
            defender = results[defender_id]
            multiplier = 2 if attacker.type in defender.weak else 1
            kills = multiplier * attacker.units * attacker.power // defender.hp
            if defender.units <= kills:
                del results[defender_id]
            else:
                results[defender_id] = defender._replace(units=defender.units - kills)
        groups = list(results.values())
        groups.sort(key=attrgetter('id'))
        key = tuple(groups)
        if key in seen:
            break
        seen.add(key)
    ret = Counter()
    for group in groups:
        ret.update({group.team: group.units})
    return ret

results = run(groups)
print(sum(results.values()))
while len(results) > 1 or 'Immune System' not in results:
    groups = [
        group._replace(power=group.power + 1) if group.team == 'Immune System' else group
        for group in groups
    ]
    results = run(groups)
print(sum(results.values()))

day25.py

with open('day25.txt') as puzzle_file:
    puzzle_input = [tuple(int(s.strip()) for s in line.split(',')) for line in puzzle_file]

groups = {}
for p1 in puzzle_input:
    for p2 in puzzle_input:
        if sum(abs(a - b) for a, b in zip(p1, p2)) > 3:
            continue
        s1 = groups.get(p1)
        if s1 is None:
            s1 = set((p1, ))
            groups[p1] = s1
        s2 = groups.get(p2)
        if s2 is None:
            s2 = set((p2, ))
            groups[p2] = s2
        if s1 is not s2:
            s1.update(s2)
            for p in s2:
                groups[p] = s1
print(len(set(map(frozenset, groups.values()))))

day3.py

from collections import defaultdict
import re

with open('day3.txt') as puzzle_file:
    pattern = re.compile(r'\d+')
    puzzle_input = [tuple(int(m.group()) for m in pattern.finditer(line)) for line in puzzle_file]

def part1(items):
    c, n = defaultdict(int), 0
    for _, x, y, w, h in items:
        for i in range(x, x + w):
            for j in range(y, y + h):
                c[(i, j)] += 1
                if c[(i, j)] == 2:
                    n += 1
    return n

def part2(items):
    c, n = {}, {item[0] for item in items}
    for t, x, y, w, h in items:
        for i in range(x, x + w):
            for j in range(y, y + h):
                if (i, j) in c:
                    n.discard(t)
                    n.discard(c[(i, j)])
                else:
                    c[(i, j)] = t
    return next(iter(n))

print(part1(puzzle_input))
print(part2(puzzle_input))

day4.py

from collections import Counter, defaultdict

with open('day4.txt') as puzzle_file:
    puzzle_input = [(int(line[15:17]), line.split()[3].lstrip('#')) for line in sorted(puzzle_file)]

sleep_by_guard = Counter()
minutes_by_guard = defaultdict(Counter)
guards_by_minute = defaultdict(Counter)
for time, action in puzzle_input:
    try:
        guard = int(action)
    except:
        if action == 'asleep':
            start = time
        elif action == 'up':
            sleep_by_guard[guard] += time - start
            minutes_by_guard[guard].update(range(start, time))
            for minute in range(start, time):
                guards_by_minute[minute][guard] += 1
        else:
            throw
guard = sleep_by_guard.most_common(1)[0][0]
minute = minutes_by_guard[guard].most_common(1)[0][0]
print(guard * minute)
guard, minute = max(((guards.most_common(1)[0], minute)
                     for minute, guards in guards_by_minute.items()),
                    key=lambda item: item[0][1])
print(guard[0] * minute)

day5.py

with open('day5.txt') as file_input:
    puzzle_input = file_input.read().strip()

def react(string):
    stack = []
    for a in string:
        if stack and a == stack[-1].swapcase():
            stack.pop()
        else:
            stack.append(a)
    return stack

reacted = ''.join(react(puzzle_input))
print(len(reacted))
print(min(len(react(c for c in reacted if c.upper() != x)) for x in set(reacted.upper())))

day6.py

from collections import Counter, defaultdict

with open('day6.txt') as puzzle_file:
    puzzle_input = [(int(line.split()[0].rstrip(',')), int(line.split()[1].strip()))
                    for line in puzzle_file]
min_x = min(x for x, _ in puzzle_input)
min_y = min(y for _, y in puzzle_input)
max_x = max(x for x, _ in puzzle_input)
max_y = max(y for _, y in puzzle_input)

def part1():
    field = defaultdict(lambda: (None, float('inf')))
    queues = {n: {p} for n, p in enumerate(puzzle_input)}
    distance = 0
    while queues:
        for n in list(queues):
            queue = set()
            for x, y in queues[n]:
                _, d = field[(x, y)]
                if d < distance:
                    continue
                field[(x, y)] = n if d > distance else None, distance
                queue.update((x, y) for x, y in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1))
                             if min_x <= x <= max_x and min_y <= y <= max_y)
            if queue:
                queues[n] = queue
            else:
                del queues[n]
        distance += 1
    areas, exclude = Counter(), {None}
    for x, y in field:
        n, d = field[(x, y)]
        if x in (min_x, max_x) or y in (min_y, max_y):
            exclude.add(n)
        else:
            areas[n] += 1
    return next(n for i, n in areas.most_common() if i not in exclude)

def part2(limit=10000):
    radius = limit // len(puzzle_input)
    xs = Counter(x for x, _ in puzzle_input)
    ys = Counter(y for _, y in puzzle_input)
    dxs = [
        dx
        for dx in (sum(abs(x - t) * c for t, c in xs.items())
                   for x in range(min_x - radius, max_x + radius + 1)) if dx < limit
    ]
    dys = [
        dy
        for dy in (sum(abs(y - t) * c for t, c in ys.items())
                   for y in range(min_y - radius, max_y + radius + 1)) if dy < limit
    ]
    return sum(dx + dy < limit for dx in dxs for dy in dys)

print(part1())
print(part2())

day7.py

from collections import defaultdict
from heapq import heappop, heappush

deps = defaultdict(set)
with open('day7.txt') as puzzle_file:
    for line in puzzle_file:
        a, b = line[5], line[36]
        deps[a]
        deps[b].add(a)

def part1(deps):
    while deps:
        k = min(k for k, dep in deps.items() if not dep)
        yield k
        del deps[k]
        for dep in deps.values():
            dep.discard(k)

def part2(deps, workers=5, dur=lambda c: ord(c) - 4):
    t, active, jobs = 0, set(), []
    while deps or jobs:
        if jobs:
            t, k = heappop(jobs)
            active.remove(k)
            del deps[k]
            for dep in deps.values():
                dep.discard(k)
        for k, w in sorted((k, dur(k)) for k, dep in deps.items() if not dep and k not in active):
            active.add(k)
            heappush(jobs, (t + w, k))
            if len(jobs) >= workers:
                break
    return t

print(''.join(part1({k: set(v) for k, v in deps.items()})))
print(part2({k: set(v) for k, v in deps.items()}))

day8.py

with open('day8.txt') as file_input:
    puzzle_input = [int(s) for s in file_input.read().split()]

def tree(it, op):
    n, m = next(it), next(it)
    return op([tree(it, op) for _ in range(n)], [next(it) for _ in range(m)])

print(tree(iter(puzzle_input), lambda a, b: sum(a) + sum(b)))
print(
    tree(
        iter(puzzle_input),
        lambda a, b: sum(a[i - 1] for i in b if 0 < i <= len(a)) if a else sum(b)))

day9.py

from collections import Counter, deque

with open('day9.txt') as puzzle_file:
    players, marbles = (int(word) for word in puzzle_file.read().split() if word.isdigit())

def play(players, marbles):
    scores = Counter()
    ring = deque((0, ))
    for marble in range(1, marbles + 1):
        if marble % 23:
            ring.rotate(2)
            ring.append(marble)
        else:
            ring.rotate(-7)
            player = marble % players
            scores[player] += ring.pop() + marble
    return scores.most_common(1)[0][1]

print(play(players, marbles))
print(play(players, 100 * marbles))