AoC 2018 Advent of Code (Python)

import numpy as np
 
lines = open('input').read().splitlines()
pts = [np.array(list(map(int, line.split(',')))) for line in lines]
groups = []
for pt in pts:
    matches = []
    not_matches = []
    for group in groups:
        ds = np.abs(group - pt).sum(axis=1)
        if np.sum(ds <= 3):
            matches.append(group)
        else:
            not_matches.append(group)
 
    if matches:
        supergroup = [p for group in matches for p in group] + [pt]
        matches = [np.array(supergroup)]
    else:
        matches = [np.array([pt])]
    groups = matches + not_matches
print(len(groups))

import itertools
import logging
import re
 
class Group(object):
    def __init__(self, immune, n, units, hitpoints, weaknesses, immunity, initiative, attack, attack_type):
        self.immune = immune
        self.n = n
        self.units = units
        self.hitpoints = hitpoints
        self.weaknesses = weaknesses
        self.immunity = immunity
        self.initiative = initiative
        self.attack = attack
        self.attack_type = attack_type
 
    @property
    def effective_power(self):
        return self.units * self.attack
 
    def damage(self, b):
        if self.attack_type in b.immunity:
            return 0
        elif self.attack_type in b.weaknesses:
            return 2 * self.effective_power
        return self.effective_power
 
    @property
    def name(self):
        if self.immune:
            return 'Immune System group %d' % self.n
        return 'Infection group %d' % self.n
 
    @classmethod
    def parse(cls, immune, n, line):
        m = re.match(r'(\d+) units each with (\d+) hit points (\(.+\) )?with an attack that does (\d+) (\S+) damage at initiative (\d+)', line)
        units, hitpoints, details, attack, attack_type, initiative = m.groups()
        weak_to = re.findall(r'weak to ([^;)]+)', details or '')
        weaknesses = weak_to[0].split(', ') if weak_to else []
        immune_to = re.findall(r'immune to ([^;)]+)', details or '')
        immunity = immune_to[0].split(', ') if immune_to else []
 
        return Group(
            immune,
            n,
            int(units), 
            int(hitpoints),
            set(weaknesses),
            set(immunity),
            int(initiative),
            int(attack),
            attack_type)
 
    def __repr__(self):
        return str(self.__dict__)
 
def parse(filename):
    pairs = (list(lines) for _, lines in itertools.groupby(open(filename), lambda s: s.endswith(':\n')))
    pairs = zip(pairs, pairs)
 
    for header, lines in pairs:
        if header[0].startswith('Immune'):
            immune = [Group.parse(True, i+1, line) for i, line in enumerate(lines) if line != '\n']
        elif header[0].startswith('Infection'):
            infection = [Group.parse(False, i+1, line) for i, line in enumerate(lines) if line != '\n']
 
    return immune + infection
 
def select_targets(ga, gb):
    gb = gb[:]
    res = []
    for a in sorted(ga, key=lambda a: (-a.effective_power, -a.initiative)):
        if not gb:
            break
        for b in sorted(gb, key=lambda u: u.n):
            d = a.damage(b)
            logging.debug('%s would deal defending group %s %d damage' % (a.name, b.n, d))
        gb.sort(key=lambda b: (-a.damage(b), -b.effective_power, -b.initiative))
        if a.damage(gb[0]) == 0:
            # "If it cannot deal any defending groups damage, it does not choose a target"
            continue
        pick = gb.pop(0)
        # logging.debug('%s picked %s' % (a.name, pick.name))
        res.append((a, pick))
    return res
 
def run(filename, boost):
    units = parse(filename)
    for unit in units:
        if unit.immune:
            unit.attack += boost
 
    drawn = False
    while not drawn:
        drawn = True
        immune = [t for t in units if t.immune]
        logging.debug('Immune System:')
        for g in sorted(immune, key=lambda u: u.n):
            logging.debug('Group %d contains %d units' % (g.n, g.units))
        infection = [t for t in units if not t.immune]
        logging.debug('Infection:')
        for g in sorted(infection, key=lambda u: u.n):
            logging.debug('Group %d contains %d units' % (g.n, g.units))
        logging.debug('')
 
        if not immune or not infection:
            break
 
        # target selection
        targets = dict()
        t = select_targets(infection, immune)
        targets.update(t)
        t = select_targets(immune, infection)
        targets.update(t)
        logging.debug('')
 
        # attacking in increasing order of initiative
        units.sort(key=lambda u: -u.initiative)
        for unit in units:
            if unit.units == 0:
                continue
            target = targets.get(unit)
            if not target:
                continue
 
            killed = min(unit.damage(target) // target.hitpoints, target.units)
            if killed:
                drawn = False
            logging.debug('%s attacks defending group %d, killing %d units' % (unit.name, target.n, killed))
            target.units -= killed
 
        units = [u for u in units if u.units > 0]
        logging.debug('')
 
    return sum(u.units for u in infection), sum(u.units for u in immune)
 
def part1(filename):
    score, _ = run(filename, 0)
    return score
 
def part2(filename):
    for boost in itertools.count(1):
        infection, immune = run(filename, boost)
        if infection == 0:
            break
    return immune
 
 
logging.basicConfig(level=logging.INFO, format='%(message)s')
print(part1('input'))
print(part2('input'))

import re
import numpy as np
from itertools import product
 
def manhattanDist(a,b): # this can be found in scipy.spatial.distance.cityblock
    return sum(abs(np.array(a)-np.array(b)))
 
def calc_InRange_DistTo0_metric(pos, nanobots, ranges=None):
    dist = np.array([manhattanDist(pos, n2["pos"]) for n2 in nanobots])
    if not ranges: # if ranges is not set, calculate bot-to-pos ranges, else calculate pos-with-range-to-bots distance
        ranges = np.array([bot["range"] for bot in nanobots])
    in_range = sum(dist <= ranges)
    dist_to_0 = manhattanDist(pos, (0,0,0))
    # as we try to maximize this function, the dist_to_0 (where we want a small one) should be negative
    return in_range, - dist_to_0
 
 
# Read and parse data
a = open('input').read()
b = a.split("\n")
c = [re.findall(r"(-?\d+)", bb) for bb in b]
nanobots = [{"id":id, "pos":(int(a), int(b), int(c)), "range":int(d)} for id, (a,b,c,d) in enumerate(c)]
 
 
# Part 1: Find how many drones are in range of master (drone with max range)
master = max(nanobots, key=lambda bot: bot["range"])
master_dist = calc_InRange_DistTo0_metric(master["pos"], nanobots, master["range"])
print(master, "\n", master_dist, "\n", "number of drones in range of master:",master_dist[0])
 
 
# Part 2: Binary search the best position
best_pos, bs = (0,0,0), (0,0)
for _ in range(5): # start from new best_pos 5 times
    for bexp in range(30, -1, -1):
        for xyz in product(range(-1,2), repeat=3):
            expo = 2**bexp
            pos = best_pos + np.array(xyz) * expo
            score = calc_InRange_DistTo0_metric(pos, nanobots)
            if score > bs:
                bs, bp = score, pos
                #print("new best distance", bs, bp)
        best_pos = bp #start searching from bp now, and repeat binary search
print(" manhattan distance from 0,0,0 to best pos:",-bs[1])

import networkx as nx
 
rocky, wet, narrow = 0, 1, 2
torch, gear, neither = 0, 1, 2
valid_items = {rocky: (torch, gear), wet: (gear, neither), neither: (torch, neither)}
valid_regions = {torch: (rocky, narrow), gear: (rocky, wet), neither: (wet, narrow)}
 
 
def get_cave(file):
    with open(file) as f:
        lines = iter([line.strip() for line in f.read().strip().splitlines()])
        depth = int(next(lines)[len("depth: "):])
        target = tuple([int(n) for n in next(lines)[len("target: "):].split(",")])
    return depth, target
 
 
def generate_grid(depth, corner):
    # (x, y) -> geologic index, erosion level, risk
    grid = {}
 
    for y in range(0, corner[1] + 1):
        for x in range(0, corner[0] + 1):
            if (x, y) in [(0, 0), target]:
                geo = 0
            elif x == 0:
                geo = y * 48271
            elif y == 0:
                geo = x * 16807
            else:
                geo = grid[(x-1, y)][1] * grid[(x, y-1)][1]
            ero = (geo + depth) % 20183
            risk = ero % 3
            grid[(x, y)] = (geo, ero, risk)
 
    return grid
 
 
def dijkstra(grid, corner, target):
    graph = nx.Graph()
    for y in range(0, corner[1] + 1):
        for x in range(0, corner[0] + 1):
            items = valid_items[grid[(x, y)]]
            graph.add_edge((x, y, items[0]), (x, y, items[1]), weight=7)
            for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                new_x, new_y = x+dx, y+dy
                if 0 <= new_x <= corner[0] and 0 <= new_y <= corner[1]:
                    new_items = valid_items[grid[(new_x, new_y)]]
                    for item in set(items).intersection(set(new_items)):
                        graph.add_edge((x, y, item), (new_x, new_y, item), weight=1)
 
    return nx.dijkstra_path_length(graph, (0, 0, torch), (target[0], target[1], torch))
 
 
depth, target = get_cave("input")
grid = generate_grid(depth, target)
print("Answer 1:", sum([v[2] for v in grid.values()]))
 
corner = (target[0] + 100, target[1] + 100)
grid = {c: v[2] for c, v in (generate_grid(depth, corner)).items()}
print("Answer 2:", dijkstra(grid, corner, target))

def run_activation_system(magic_number, is_part_1):
    seen = set()
    c = 0
    last_unique_c = -1
 
    while True:
        a = c | 65536
        c = magic_number
 
        while True:
            c = (((c + (a & 255)) & 16777215) * 65899) & 16777215
 
            if 256 > a:
                if is_part_1:
                    return c
                else:
                    if c not in seen:
                        seen.add(c)
                        last_unique_c = c
                        break
                    else:
                        return last_unique_c
            else:
                a //= 256
 
 
magic_number = int(open("input").readlines()[8].split()[1])
print(run_activation_system(magic_number, True))
print(run_activation_system(magic_number, False))

from collections import defaultdict
from heapq import *
 
 
def new_node(d, p=None):
    return {"d": d, "p": p, "c": []}
 
 
def move(pos, dir):
    if dir == "S":
        return (pos[0], pos[1] + 1)
    elif dir == "E":
        return (pos[0] + 1, pos[1])
    elif dir == "W":
        return (pos[0] - 1, pos[1])
    elif dir == "N":
        return (pos[0], pos[1] - 1)
 
 
def build_graph(regex):
    regex = regex[1:-1]
    pos = (0, 0)
    graph = defaultdict(list)
    stack = [pos]
 
    for v in regex:
        if v == "(":
            stack += [pos]
        elif v == ")":
            pos = stack.pop()
        elif v == "|":
            pos = stack[-1]
        else:
            graph[pos] += [move(pos, v)]
            graph[move(pos, v)] += [pos]
            pos = move(pos, v)
 
    return graph
 
 
def dij(graph):
    scores = {(0, 0): 0}
    queue = [(0, (0, 0))]
    best = 100000
    while len(queue):
        score, pos = heappop(queue)
        for nb in graph[pos]:
            new = score + 1
            if new > best:
                break
            if new < scores.get(nb, 100000):
                scores[nb] = new
                heappush(queue, (new, nb))
    return scores
 
 
regex = open('input').read().splitlines()[0]
graph = build_graph(regex)
scores = dij(graph)
 
 
print(max(scores.values()))
print(len([x for x in scores.values() if x >= 1000]))

ADDR, ADDI, MULR, MULI, BANR, BANI, BORR, BORI, SETR, SETI, GTIR, GTRI, GTRR, EQIR, EQRI, EQRR = range(16)
 
OPERATIONS = ['addr', 'addi', 'mulr', 'muli', 'banr', 'bani', 'borr', 'bori',
              'setr', 'seti', 'gtir', 'gtri', 'gtrr', 'eqir', 'eqri', 'eqrr']
 
 
def solve(instructions, ip, optimize_for_part2=False):
    # set register 0 to 1 in part 2
    reg = [1] + [0] * 5 if optimize_for_part2 else [0] * 6
 
    # execute the program as long as the ip is valid
    while 0 <= reg[ip] < len(instructions):
        ins = instructions[reg[ip]]
 
        # initialization for part 2 is done at instruction 35
        if optimize_for_part2 and reg[ip] == 35:
            return optimized_loop(reg)
 
        execute(*ins, reg)
        reg[ip] += 1
 
    # undo last increment operation
    reg[ip] -= 1
 
    return reg[0]
 
 
def optimized_loop(reg):
    a, b, c, d, ip, f = reg
 
    # manually disassembled code ... (too slow)
 
    # f = 1  # 1
    # while f <= d:  # 13 - 15
    #     b = 1  # 2
    #     while b <= d:  # 9 - 11
    #         if (f * b) == d:  # 3 - 6
    #             a += f  # 7
    #         b += 1  # 8
    #     f += 1  # 12
 
    # optimized inner loop, that checks for factors faster
 
    f = 1  # 1
    while f <= d:  # 13 - 15
        if d % f == 0:
            a += f
        f += 1  # 12
 
    return a
 
 
def execute(op, a, b, c, reg):
    if op == ADDR:
        reg[c] = reg[a] + reg[b]
    elif op == ADDI:
        reg[c] = reg[a] + b
    elif op == MULR:
        reg[c] = reg[a] * reg[b]
    elif op == MULI:
        reg[c] = reg[a] * b
    elif op == BANR:
        reg[c] = reg[a] & reg[b]
    elif op == BANI:
        reg[c] = reg[a] & b
    elif op == BORR:
        reg[c] = reg[a] | reg[b]
    elif op == BORI:
        reg[c] = reg[a] | b
    elif op == SETR:
        reg[c] = reg[a]
    elif op == SETI:
        reg[c] = a
    elif op == GTIR:
        reg[c] = 1 if a > reg[b] else 0
    elif op == GTRI:
        reg[c] = 1 if reg[a] > b else 0
    elif op == GTRR:
        reg[c] = 1 if reg[a] > reg[b] else 0
    elif op == EQIR:
        reg[c] = 1 if a == reg[b] else 0
    elif op == EQRI:
        reg[c] = 1 if reg[a] == b else 0
    elif op == EQRR:
        reg[c] = 1 if reg[a] == reg[b] else 0
 
 
def explain_program(instructions, ip):
    print()
    for i, ins in enumerate(instructions):
        print("{:>2} {:<5} {}".format(i, OPERATIONS[ins[0]], explain(*ins, ip)))
 
 
def explain(op, a, b, c, ip):
    names = {0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f', ip: 'IP'}
 
    if op == ADDR:
        return "{} = {} + {}".format(names[c], names[a], names[b])
    elif op == ADDI:
        return "{} = {} + {}".format(names[c], names[a], b)
    elif op == MULR:
        return "{} = {} * {}".format(names[c], names[a], names[b])
    elif op == MULI:
        return "{} = {} * {}".format(names[c], names[a], b)
    elif op == BANR:
        return "{} = {} & {}".format(names[c], names[a], names[b])
    elif op == BANI:
        return "{} = {} & {}".format(names[c], names[a], b)
    elif op == BORR:
        return "{} = {} | {}".format(names[c], names[a], names[b])
    elif op == BORI:
        return "{} = {} | {}".format(names[c], names[a], b)
    elif op == SETR:
        return "{} = {}".format(names[c], names[a])
    elif op == SETI:
        return "{} = {}".format(names[c], a)
    elif op == GTIR:
        return "{} = {} > {} ?".format(names[c], a, names[b])
    elif op == GTRI:
        return "{} = {} > {} ?".format(names[c], names[a], b)
    elif op == GTRR:
        return "{} = {} > {} ?".format(names[c], names[a], names[b])
    elif op == EQIR:
        return "{} = {} == {} ?".format(names[c], a, names[b])
    elif op == EQRI:
        return "{} = {} == {} ?".format(names[c], names[a], b)
    elif op == EQRR:
        return "{} = {} == {} ?".format(names[c], names[a], names[b])
 
 
def parse(lines):
    instructions, ip = [], int(lines[0].split()[1])
 
    for line in lines[1:]:
        parts = line.split()
        instructions.append((OPERATIONS.index(parts[0]), *map(int, parts[1:])))
 
    return instructions, ip
 
 
print(solve(*parse(open(r"input").readlines())))
print(solve(*parse(open(r"input").readlines()), optimize_for_part2=True))
# print the entire program for better understanding
#explain_program(*parse(open(r"input").readlines()))

import re
import collections
 
lines=open('input').read().splitlines()
 
a,b = map(int, [re.findall('\d+', lines[i])[1] for i in [22, 24]])
number_to_factorize = 10551236 + a * 22 + b
 
factors = collections.defaultdict(lambda: 0)
possible_prime_divisor = 2
while possible_prime_divisor ** 2 <= number_to_factorize:
  while number_to_factorize % possible_prime_divisor == 0:
    number_to_factorize /= possible_prime_divisor
    factors[possible_prime_divisor] += 1 
  possible_prime_divisor += 1
if number_to_factorize > 1:
  factors[number_to_factorize] += 1
 
sum_of_divisors = 1
for prime_factor in factors:
  sum_of_divisors *= (prime_factor ** (factors[prime_factor] + 1) - 1) / (prime_factor - 1)
 
print (sum_of_divisors)

import re
 
def functions():
    return {
        "addr": (lambda reg, a, b: reg[a] + reg[b]),
        "addi": (lambda reg, a, b: reg[a] + b),
        "mulr": (lambda reg, a, b: reg[a] * reg[b]),
        "muli": (lambda reg, a, b: reg[a] * b),
        "banr": (lambda reg, a, b: reg[a] & reg[b]),
        "bani": (lambda reg, a, b: reg[a] & b),
        "borr": (lambda reg, a, b: reg[a] | reg[b]),
        "bori": (lambda reg, a, b: reg[a] | b),
        "setr": (lambda reg, a, b: reg[a]),
        "seti": (lambda reg, a, b: a),
        "gtir": (lambda reg, a, b: 1 if a > reg[b] else 0),
        "gtri": (lambda reg, a, b: 1 if reg[a] > b else 0),
        "gtrr": (lambda reg, a, b: 1 if reg[a] > reg[b] else 0),
        "eqir": (lambda reg, a, b: 1 if a == reg[b] else 0),
        "eqri": (lambda reg, a, b: 1 if reg[a] == b else 0),
        "eqrr": (lambda reg, a, b: 1 if reg[a] == reg[b] else 0),
    }
 
 
def ints(x):
    return list(map(int, re.findall("\\d+", x)))
 
 
def parse_line(line):
    fn, *codes = line.split(" ")
    codes = list(map(int, codes))
    return {"fn": fn, "a": codes[0], "b": codes[1], "c": codes[2]}
 
 
def parse_program(file):
    program = open(file).read().splitlines()
    ip = program[0]
    program = program[1:]
    program = [parse_line(line) for line in program]
    ip = ints(ip)[0]
    reg = [0] * 6
    return program, ip, reg
 
 
#part 01
program, ip, reg = parse_program('input')
fns = functions()
while reg[ip] < len(program):
    inst = program[reg[ip]]
    reg[inst["c"]] = fns[inst["fn"]](reg, inst["a"], inst["b"])
    reg[ip] += 1
print(reg[0])
 
#part 02
program, ip, reg = parse_program('input')
fns = functions()
reg[0] = 1
while reg[ip] < len(program):
    inst = program[reg[ip]]
    print(f"ip={reg[ip]}, {reg}", end=" ")
    reg[inst["c"]] = fns[inst["fn"]](reg, inst["a"], inst["b"])
    print(f"{reg}")
    reg[ip] += 1
    if reg[ip] == 1:
        break
#it seems that this calculates the sum of the factors
#of the big number in address 4!
print(sum(i for i in range(1, reg[4] + 1) if reg[4] % i == 0))
#to be continued...

from collections import defaultdict
 
 
def neighbours(i, j):
    return [
        (i - 1, j - 1),
        (i, j - 1),
        (i + 1, j - 1),
        (i - 1, j),
        (i + 1, j),
        (i - 1, j + 1),
        (i, j + 1),
        (i + 1, j + 1),
    ]
 
 
def print_board(b, r, c):
    for i in range(r):
        print(*[b[i, j] for j in range(c)], sep="")
 
 
def update(board):
    new_board = defaultdict(lambda: ".")
    for pos in list(board.keys()):
        new_board[pos] = board[pos]
        vals = [board[x] for x in neighbours(*pos)]
        if board[pos] == ".":
            if vals.count("|") >= 3:
                new_board[pos] = "|"
        if board[pos] == "|":
            if vals.count("#") >= 3:
                new_board[pos] = "#"
            else:
                new_board[pos] = "|"
        if board[pos] == "#":
            if vals.count("#") >= 1 and vals.count("|") >= 1:
                new_board[pos] = "#"
            else:
                new_board[pos] = "."
    return new_board
 
 
def dat():
    dat = open('input').read().splitlines()
    board = defaultdict(lambda: ".")
    for i in range(len(dat)):
        line = list(dat[i])
        for j in range(len(line)):
            board[i, j] = line[j]
    return board
 
#part 1
board = dat()
for i in range(10):
    board = update(board)
 
vals = list(board.values())
print(vals.count("#") * vals.count("|"))
 
#part 2
values = list()
board = dat()
for i in range(1000):
    board = update(board)
    vals = list(board.values())
    values.append(vals.count("#") * vals.count("|"))
# There is a burn in of 470, then repeating sections 471:526 inclusive
# Therefore after n the value will be the same as (n-470) % 56 + 470
# e.g.
# n = 890
# values[(n - 470) % 56 + 470] == values[n]
n = 1000000000 - 1
print(values[(n - 470) % 56 + 470])

import re
from collections import defaultdict, deque
from itertools import count
from typing import Tuple
 
 
min_y = 99999999
max_y = -1
min_x = 99999999
max_x = -1
 
ground = defaultdict(lambda: defaultdict(lambda: '.'))
 
lines = open('input').readlines()
for line in lines:
    at, start, end = map(int, re.findall(r'\d+', line))
    if line[0] == 'x':
        xs = [at]
        ys = range(start, end + 1)
    else:
        xs = range(start, end + 1)
        ys = [at]
 
    min_x = min(min_x, *xs)
    max_x = max(max_x, *xs)
    min_y = min(min_y, *ys)
    max_y = max(max_y, *ys)
 
    for x in xs:
        for y in ys:
            ground[y][x] = '#'
min_x -= 1
max_x += 1
heads = deque([(min_y, 500)])
 
def visualize():
    with open('visualize.txt', 'w+') as f:
        for i in range(1, max_y + 1):
            for j in range(min_x, max_x + 1):
                f.write(ground[i][j])
            f.write('\n')
 
def bounds(i: int, j: int) -> Tuple[int, int]:
    start = 999999
    end = 0
    for step in (-1, 1):
        for k in count(j, step):
            if ground[i][k] == '#' or k > max_x or k < min_x:
                break
            start = min(start, k)
            end = max(end, k)
    return start, end + 1
 
def can_settle(i: int, j: int) -> bool:
    start, end = bounds(i, j)
    for j in range(start, end):
        if ground[i + 1][j] == '.':
            return False
    return True
 
while heads:
    (i, j) = heads.popleft()
    ground[i][j] = '|'
 
    if ground[i + 1][j] not in ('#', '~'):  # if there is space to drop, drop
        if i != max_y:  # if not at bottom of map
            heads.append((i + 1, j))
    else:
        if can_settle(i, j):  # if the water can settle
            start, end = bounds(i, j)
            for k in range(start, end):  # convert | to ~
                ground[i][k] = '~'
            if (i - 1, j) not in heads:  # weird optimization that somehow works
                heads.append((i - 1, j))
        else:  # spill over
            for step in (-1, 1):
                for k in count(j, step):
                    if ground[i][k] == '#':  # if hit a wall, stop expanding
                        break
                    elif ground[i + 1][k] == '.':  # if space, stop dropping from there
                        heads.append((i, k))
                        break
                    elif ground[i + 1][k] == '|':  # if already traversed, don't traverse
                        break
                    else:  # else expand
                        ground[i][k] = '|'
 
visualize()  # write visualization to file for debug
print(len([i for row in ground.values() for i in row.values() if i in ('~', '|')]))  # count all water tiles
print(len([i for row in ground.values() for i in row.values() if i == '~']))  # count stationary water tiles

import re
 
opcodes = (
    'addr',
    'addi',
    'mulr',
    'muli',
    'banr',
    'bani',
    'borr',
    'bori',
    'setr',
    'seti',
    'gtir',
    'gtri',
    'gtrr',
    'eqir',
    'eqri',
    'eqrr',
)
 
 
def process(opcode, args, registers):
    def set_register(index, value):
        return tuple(
            value if i == index else r for i, r in enumerate(registers)
        )
 
    a, b, c = args
    if opcode == 'addr':
        return set_register(c, registers[a] + registers[b])
    if opcode == 'addi':
        return set_register(c, registers[a] + b)
    if opcode == 'mulr':
        return set_register(c, registers[a] * registers[b])
    if opcode == 'muli':
        return set_register(c, registers[a] * b)
    if opcode == 'banr':
        return set_register(c, registers[a] & registers[b])
    if opcode == 'bani':
        return set_register(c, registers[a] & b)
    if opcode == 'borr':
        return set_register(c, registers[a] | registers[b])
    if opcode == 'bori':
        return set_register(c, registers[a] | b)
    if opcode == 'setr':
        return set_register(c, registers[a])
    if opcode == 'seti':
        return set_register(c, a)
    if opcode == 'gtir':
        return set_register(c, int(a > registers[b]))
    if opcode == 'gtri':
        return set_register(c, int(registers[a] > b))
    if opcode == 'gtrr':
        return set_register(c, int(registers[a] > registers[b]))
    if opcode == 'eqir':
        return set_register(c, int(a == registers[b]))
    if opcode == 'eqri':
        return set_register(c, int(registers[a] == b))
    if opcode == 'eqrr':
        return set_register(c, int(registers[a] == registers[b]))
 
 
def read_ints(s):
    return tuple(map(int, re.findall(r'\d+', s)))
 
 
def read_samples(lines):
    lines_iter = iter(lines)
    while True:
        before = next(lines_iter)
        args = next(lines_iter)
        after = next(lines_iter)
        if before == '' and args == '':
            return
        yield read_ints(before), read_ints(args), read_ints(after)
        next(lines_iter)
 
 
def read_program(lines):
    lines_iter = iter(lines)
    previous = None
    for line in lines_iter:
        if line == '' and previous == '':
            break
        previous = line
    next(lines_iter)
    yield from map(read_ints, lines_iter)
 
 
lines = open('input').readlines()
lines = [line.strip() for line in lines]
 
# part 1
print(
    sum(
        sum(process(opcode, args[1:], before) == after for opcode in opcodes)
        >= 3
        for before, args, after in read_samples(lines)
    )
)
 
# part 2
opcode_table = [None] * 16
for before, args, after in read_samples(lines):
    if opcode_table[args[0]]:
        continue
    candidates = [
        opcode
        for opcode in opcodes
        if opcode not in opcode_table
        and process(opcode, args[1:], before) == after
    ]
    if len(candidates) == 1:
        opcode, = candidates
        opcode_table[args[0]] = opcode
registers = (0, 0, 0, 0)
for line in read_program(lines):
    registers = process(opcode_table[line[0]], line[1:], registers)
print(registers[0])

directions = (0, 1), (0, -1), (1, 0), (-1, 0)
 
 
def adjacent(x, y):
    return ((x + move_x, y + move_y) for move_x, move_y in directions)
 
 
class Game:
    def __init__(self, data, elf_attack=3):
        self.free = []
        self.units = []
        for y, line in enumerate(data.splitlines()):
            self.free.append([])
            for x, char in enumerate(line.rstrip()):
                self.free[-1].append(char == '.')
                if char == 'E' or char == 'G':
                    attack = elf_attack if char == 'E' else 3
                    self.units.append(Unit(self, char, x, y, attack))
 
    def visualize(self):
        for y in range(len(self.free)):
            line = (
                next(
                    (
                        unit.team
                        for unit in self.units
                        if unit.x == x and unit.y == y
                    ),
                    '#.'[self.free[y][x]],
                )
                for x in range(len(self.free[y]))
            )
            print(''.join(line))
 
    def team_size(self, team):
        return sum(unit.team == team for unit in self.units)
 
    def team_health(self, team):
        return sum(unit.health for unit in self.units if unit.team == team)
 
 
class Unit:
    __slots__ = ('game', 'team', 'x', 'y', 'health', 'attack')
 
    def __init__(self, game, team, x, y, attack):
        self.game = game
        self.team = team
        self.x = x
        self.y = y
        self.health = 200
        self.attack = attack
 
    def __lt__(self, other):
        return (self.y, self.x) < (other.y, other.x)
 
    def can_attack(self, other):
        return (
            self.team != other.team
            and abs(self.x - other.x) + abs(self.y - other.y) == 1
        )
 
    def attack_priority(self):
        return self.health, self.y, self.x
 
    def get_attack_target(self):
        return min(
            filter(self.can_attack, self.game.units),
            key=Unit.attack_priority,
            default=None,
        )
 
    def tick(self):
        attack_target = self.get_attack_target()
        if not attack_target:
            paths = []
            for move_x, move_y in adjacent(self.x, self.y):
                if not self.game.free[move_y][move_x]:
                    continue
                visited = set(((self.x, self.y),))
                edges = [(move_x, move_y)]
                distance = 1
                best_distance = None
                while edges:
                    new_edges = []
                    for edge_x, edge_y in edges:
                        for x, y in adjacent(edge_x, edge_y):
                            if any(
                                unit.x == x and unit.y == y
                                for unit in self.game.units
                                if unit.team != self.team
                            ):
                                paths.append(
                                    (distance, edge_y, edge_x, move_y, move_x)
                                )
                                best_distance = distance
                            if self.game.free[y][x] and (x, y) not in visited:
                                visited.add((x, y))
                                new_edges.append((x, y))
                    edges = new_edges
                    distance += 1
                    if best_distance and distance > best_distance:
                        break
            if paths:
                _, _, _, move_y, move_x = min(paths)
                self.game.free[self.y][self.x] = True
                self.x = move_x
                self.y = move_y
                self.game.free[self.y][self.x] = False
                attack_target = self.get_attack_target()
 
        if attack_target:
            attack_target.health -= self.attack
            if attack_target.health <= 0:
                self.game.units.remove(attack_target)
                self.game.free[attack_target.y][attack_target.x] = True
 
 
def solve_part_1(data):
    game = Game(data)
    time = 0
    while True:
        for unit in sorted(game.units):
            if unit.health > 0:
                if game.team_size('E') == 0:
                    return time * game.team_health('G')
                if game.team_size('G') == 0:
                    return time * game.team_health('E')
                unit.tick()
        time += 1
 
 
def solve_part_2(data):
    for elf_attack in range(3, 999):
        game = Game(data, elf_attack)
        time = 0
        start_elves = game.team_size('E')
        while True:
            goblins = game.team_size('G')
            if goblins > 0:
                elves = game.team_size('E')
                if elves < start_elves:
                    break
                elf_dps = elves * elf_attack
                elf_health = game.team_health('E')
                goblin_dps = goblins * 3
                goblin_health = game.team_health('G')
                # 2* is just to make one of the tests pass, remove for much faster solution
                if 2 * elf_dps / goblin_health < goblin_dps / elf_health:
                    break
            for unit in sorted(game.units):
                if unit.health > 0:
                    if game.team_size('G') == 0:
                        return time * game.team_health('E')
                    unit.tick()
            time += 1
 
 
data = open('input').read()
print(solve_part_1(data))
print(solve_part_2(data))

n = open('input').readline()
digits = [*map(int, n)]
n_digits = len(digits)
recipes = [3, 7]
index1 = 0
index2 = 1
 
while True:
    new = recipes[index1] + recipes[index2]
    if new >= 10:
        recipes.append(1)
    recipes.append(new % 10)
    index1 = (index1 + 1 + recipes[index1]) % len(recipes)
    index2 = (index2 + 1 + recipes[index2]) % len(recipes)
    if recipes[-n_digits:] == digits:
        print(len(recipes) - n_digits)
        exit()
    if recipes[-n_digits - 1 : -1] == digits:
        print(len(recipes) - n_digits - 1)
        exit()

n = int(open('input').readline())
recipes = [3, 7]
index1 = 0
index2 = 1
 
while len(recipes) < n + 10:
    new = recipes[index1] + recipes[index2]
    if new >= 10:
        recipes.append(1)
    recipes.append(new % 10)
    index1 = (index1 + 1 + recipes[index1]) % len(recipes)
    index2 = (index2 + 1 + recipes[index2]) % len(recipes)
print(''.join(map(str, recipes[n : n + 10])))

import re
 
def draw(track, carts):
    out = [list(row) for row in track]
    for cart in carts:
        out[cart.y][cart.x] = cart.d
    return '\n'.join(''.join(row) for row in out)
 
dirs = {
    '^': (0, -1),
    'v': (0, 1),
    '<': (-1, 0),
    '>': (1, 0),
}
 
turn_forward = {
    '^': '>',
    '>': '^',
    '<': 'v',
    'v': '<',
}
 
turn_backward = {
    '^': '<',
    '<': '^',
    '>': 'v',
    'v': '>',
}
 
turn_intersect = {
    '^': '<^>',
    'v': '>v<',
    '<': 'v<^',
    '>': '^>v',
}
 
class Cart(object):
    def __init__(self, x, y, d):
        self.x = x
        self.y = y
        self.d = d
        self.intersects = 0
 
    def next(self):
        dx, dy = dirs[self.d]
        return self.x+dx, self.y+dy
 
    def move(self):
        self.x, self.y = self.next()
 
    def turn_forward(self):
        self.d = turn_forward[self.d]
 
    def turn_backward(self):
        self.d = turn_backward[self.d]
 
    def intersection(self):
        self.d = turn_intersect[self.d][self.intersects]
        self.intersects = (self.intersects + 1) % 3
 
    def __str__(self):
        return '(%d, %d, %s)' % (self.x, self.y, self.d)
 
 
def run(stop):
    track = [line.strip('\n') for line in open('input')]
    mx = max(map(len, track))
    my = len(track)
 
    carts = []
    for y, row in enumerate(track):
        for x, d in enumerate(row):
            if d not in '^v<>':
                continue
            carts.append(Cart(x, y, d))
    track = [row.replace('>', '-').replace('v', '|').replace('^', '|').replace('<', '-') for row in track]
    # print()
    # print(draw(track, carts))
 
    while True:
        carts.sort(key=lambda cart: (cart.y, cart.x))
        positions = set((cart.x, cart.y) for cart in carts)
        dead = []
        for cart in carts:
            if cart in dead:
                continue
 
            positions.remove((cart.x, cart.y))
            nx, ny = cart.next()
            if (nx, ny) in positions:
                if stop:
                    return '%d,%d' % (nx, ny) # crash!
                else:
                    # eliminate and continue
                    other = next(cart for cart in carts if cart.x == nx and cart.y == ny)
                    dead.extend([cart, other])
                    positions.remove((nx, ny))
                    continue
 
            # move
            cart.move()
            positions.add((cart.x, cart.y))
 
            # calculate new direction
            t = track[ny][nx]
            if t == '/':
                cart.turn_forward()
            elif t == '\\':
                cart.turn_backward()
            elif t == '+':
                cart.intersection()
 
        if not stop and dead:
            carts = [cart for cart in carts if cart not in dead]
            if len(carts) == 1:
                return '%d,%d' % (carts[0].x, carts[0].y)
 
        # print()
        # print(draw(track, carts))
 
print(run(stop=True))
print(run(stop=False))

from itertools import count
 
def str_to_bits(s):
    return sum(2**i for i, v in enumerate(s) if v == '#')
 
def bits_to_str(b):
    return ''.join('#' if c & 1 else '.' for c in bit_iter(b))
 
def bit_iter(b, mask=1):
    while b:
        yield b & mask
        b >>= 1
 
def bit_sum(state, offset):
    return sum(b * i for b, i in zip(bit_iter(state), count(-offset)))
 
def bit_count(b):
    return sum(bit_iter(b))
 
lines = open('input')
initial = next(lines).strip().replace('initial state: ', '')
initial = str_to_bits(initial)
offset = 10
initial <<= offset
next(lines)     # blank line
n = 20          # part 1
n = 50000000000 # part 2
masks = [0]*32
for line in lines:
    rule, result = line.strip().split(' => ')
    masks[str_to_bits(rule)] = 1 if result == '#' else 0
 
state = initial
for i in range(n):
    previous = state
    state = sum(
        masks[p] << (j+2)
        for j, p in enumerate(bit_iter(previous, 31))
    )
    if state == previous*2:
        # doubling cycle detected - shortcut
        print(bit_sum(state, offset) + bit_count(state) * (n-i-1))
        exit()
 
print(bit_sum(state, offset))

import numpy as np
 
def power_grid(serial):
    gr = np.zeros((300, 300), dtype=np.int8)
    mx, my = np.mgrid[1:301, 1:301]
    rack_id = mx + 10
    power = (rack_id * my + serial) * rack_id
    gr = power // 100 % 10 - 5
    return gr
 
serial = int(open('input').read())
gr = power_grid(serial)
cs = gr.cumsum(0).cumsum(1)
 
answer = None
max_total = 0
for size in range(1, 300):
    totals = cs[size:,size:] + cs[:-size,:-size] - cs[size:,:-size] - cs[:-size,size:]
    if totals.max() > max_total:
        x, y = np.unravel_index(totals.argmax(), totals.shape)
        answer = (int(x + 2), int(y + 2), size)
        max_total = totals.max()
print(answer)

import numpy as np
 
def power_grid(serial):
    gr = np.zeros((300, 300), dtype=np.int8)
    mx, my = np.mgrid[1:301, 1:301]
    rack_id = mx + 10
    power = (rack_id * my + serial) * rack_id
    gr = power // 100 % 10 - 5
    return gr
 
serial = int(open('input').read())
gr = power_grid(serial)
cs = gr.cumsum(0).cumsum(1)
size = 3
totals = cs[size:,size:] + cs[:-size,:-size] - cs[size:,:-size] - cs[:-size,size:]
x, y = np.unravel_index(totals.argmax(), totals.shape)
print(f"{x + 2},{y + 2}")

import re
from itertools import count
 
lines = open('input').read().splitlines()
lines = [re.findall(r'-?\d+', line) for line in lines]
lines = [list(map(int, line)) for line in lines]
stars = lines
 
min_width = 10000000000000000000000
 
for i in count():
    new_stars = []
    for px, py, vx, vy in stars:
        px += vx
        py += vy
        new_stars.append((px, py, vx, vy))
 
    max_y = max(k[1] for k in new_stars)
    min_y = min(k[1] for k in new_stars)
    width = max_y - min_y
 
    if width < min_width:
        min_width = width
    if width > min_width:
        max_x = max(k[0] for k in stars)
        min_x = min(k[0] for k in stars)
        max_y = max(k[1] for k in stars)
        min_y = min(k[1] for k in stars)
        star_map = set((px, py) for px, py, *_ in stars)
        for y in range(min_y, max_y + 1):
            row = []
            for x in range(min_x, max_x + 1):
                if (x, y) in star_map:
                    row.append('#')
                else:
                    row.append(' ')
            print(''.join(row))
        print(i)
        break
 
    stars = new_stars

from collections import deque
 
def play(players, marbles):
    circle = deque()
    circle.append(0)
    scores = [0] * players
    for marble in range(1, marbles+1):
        if marble % 23 == 0:
            circle.rotate(-7)
            scores[marble % players] += marble + circle.pop()
        else:
            circle.rotate(2)
            circle.append(marble)
 
    return max(scores)
 
 
data = open('input').read().split()
players = int(data[0])
value = int(data[6])
print(play(players, value))
print(play(players, value * 100))

import itertools
 
class Node(object):
    def __init__(self, children, metadata):
        self.children = children
        self.metadata = metadata
 
    def __repr__(self):
        return '[%s %s]' % (self.metadata, self.children)
 
    def all_meta(self):
        return self.metadata + [x for c in self.children for x in c.all_meta()]
 
    def value(self):
        if not self.children:
            return sum(self.metadata)
        return sum(
            self.children[m-1].value()
            for m in self.metadata
            if m >= 1 and m <= len(self.children))
 
def parse(it):
    nc = next(it)
    nm = next(it)
    children = [parse(it) for c in range(nc)]
    metadata = list(itertools.islice(it, nm))
    return Node(children, metadata)
 
def parse_file(filename):
    ins = map(int, open(filename).read().split())
    return parse(ins)
 
tree = parse_file('input')
print(sum(tree.all_meta()))
print(tree.value())

import re
 
def cost(c):
    return ord(c)-ord('A')+61
 
data = open('input').read().splitlines()
data = [re.findall(' ([A-Z]) ', line) for line in data]
 
t = 0
max_workers = 5
work = []
started = set()
 
remain = set(a for p in data for a in p)
 
while remain:
    done = set(c for c, td in work if t == td)
    if done:
        remain -= done
        data = [(a, b) for a, b in data if a not in done]
        work = [(c, td) for c, td in work if c not in done]
 
    ready = set(remain) - set(b for _, b in data) - started
    idle = max_workers - len(work)
    for _, start in zip(range(idle), ready):
        started.update(start)
        work.append((start, t + cost(start)))
 
    if remain:
        t += 1
 
print(t)

import re
 
data = open('input').read().splitlines()
data = [re.findall(' ([A-Z]) ', line) for line in data]
 
remain = set(a for p in data for a in p)
order = ''
 
while remain:
    ready = set(remain) - set(b for _, b in data)
    now = sorted(ready)[0]
    order += now
    remain.remove(now)
    data = [(a, b) for a, b in data if a != now]
 
print(order)

from collections import defaultdict
 
data = open('input').read().splitlines()
data = [list(map(int, x.split(", "))) for x in data]
 
x0 = min(x for x, y in data)
x1 = max(x for x, y in data)
y0 = min(y for x, y in data)
y1 = max(y for x, y in data)
 
 
def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
 
 
def closest(pad=0):
    r = defaultdict(int)
    for x in range(x0 - pad, x1 + pad):
        for y in range(y0 - pad, y1 + pad):
            d = [dist([x, y], p) for p in data]
            m = min(d)
            if d.count(m) == 1:
                i = d.index(min(d))
                r[i] += 1
    return r
 
 
a = closest()
b = closest(1)
stable = [k for k in a.keys() if a[k] == b[k]]
print(max(a[k] for k in stable))
 
count = 0
for x in range(x0, x1):
    for y in range(y0, y1):
        if sum(dist([x, y], p) for p in data) < 10000:
            count += 1
print(count)

import re
from string import ascii_lowercase as lc
from string import ascii_uppercase as uc
 
polymer = open('input').read().rstrip()
 
def react(polymer):
    pairs = list(zip(lc, uc)) + list(zip(uc, lc))
    patterns = ["".join(x) for x in pairs]
    l2 = len(polymer)
    l1 = l2 + 1
    while l1 != l2:
        l1 = l2
        for p in patterns:
            polymer = re.sub(p, "", polymer)
        l2 = len(polymer)
    return polymer
 
print(len(react(polymer)))
 
 
def fix_and_react(polymer, l):
    fixed = re.sub(l, "", polymer, flags=re.IGNORECASE)
    return react(fixed)
 
print(min(len(fix_and_react(polymer, l)) for l in lc))

from collections import defaultdict, Counter
 
lines = open('input').read().splitlines()
lines.sort()
 
sleep=[]
 
for line in lines:
    words = line.split()
    minute = int(words[1][3:5])
    if words[2] == 'falls':
        start = minute
    elif words[2] == 'wakes':
        end = minute
        sleep.append([guard, start, end])
    else:
        guard = int(words[3][1:])
 
#print(sleep)
 
total_sleep = Counter()
by_minute = defaultdict(Counter)
 
for guard_id, fell_asleep, wake_up in sleep:
    total_sleep[guard_id] += wake_up - fell_asleep
    by_minute[guard_id].update(range(fell_asleep, wake_up))
 
sleepiest, _ = total_sleep.most_common(1)[0]
best_minute = by_minute[sleepiest].most_common(1)[0][0]
print(sleepiest * best_minute)
 
 
guard_minute = Counter()
 
for guard_id, fell_asleep, wake_up in sleep:
    guard_minute.update((guard_id, m) for m in range(fell_asleep, wake_up))
 
a, b = guard_minute.most_common(1)[0][0]
print(a * b)

import re
from collections import defaultdict
 
claims = []
lines = open('input').read().splitlines()
for line in lines:
    claims.append (re.findall(r'\d+',line))
claims = [list(map(int, c)) for c in claims]
 
fabric = defaultdict(list)
for id_, dx, dy, x, y in claims:
    for i in range(dx, dx + x):
        for j in range(dy, dy + y):
            fabric[(i, j)].append(id_)
 
print(len([i for i in fabric.values() if len(i) > 1]))
 
ids_all = set(map(lambda x: x[0], claims))
ids_overlapped = set(id_ for ids in fabric.values() if len(ids) > 1
                        for id_ in ids)
 
print(ids_all - ids_overlapped)

from collections import Counter
from itertools import combinations
 
c2 = 0
c3 = 0
 
lines = open('input').read().splitlines()
for line in lines:
    c = Counter(line)
    if 2 in c.values():
        c2 += 1
    if 3 in c.values():
        c3 += 1
print(c2 * c3)
 
for a, b in combinations(lines, 2):
    count_diff = sum(i != j for i, j in zip(a, b))
    if count_diff == 1:
        print(''.join(i for i, j in zip(a, b) if i == j))

def countDups(string):
  c2 = 0 # 'doubles' (count_2)
  c3 = 0 # 'triples' (count_3)
  for c in string:
    n = string.count(c)
    if not c2 and n == 2:
      c2 = 1
    if not c3 and n == 3:
      c3 = 1
    if c2 and c3:
      break
  return c2, c3
 
c2 = 0
c3 = 0
lines = open('input').read().splitlines()
for line in lines:
    c = countDups(line)
    c2 += c[0]
    c3 += c[1]
print(c2 * c3)

lines = open('input').read().splitlines()
f = 0
prev = set()
 
while True:
    for line in lines:
        f += (int(line))
        if f in prev:
            print(f)
            exit()
        else:
            prev.add(f)

lines = open('input').read().splitlines()
f = 0
for line in lines:
    f += (int(line))
print(f)