AOC 2017 solutions

.gitignore

private.py
*.pyc
.cache

day1.py

import util


def char_sum(s):
    return sum(int(x) for x, y in zip(s, s[1:] + s[:1]) if x == y)


def test():
    assert char_sum("1122") == 3
    assert char_sum("1111") == 4
    assert char_sum("1234") == 0
    assert char_sum("91212129") == 9


if __name__ == "__main__":
    print(char_sum(util.get_input(1).strip()))

day10.py

import util


def swap(l, start, length):
    end = start + length

    end_slice = slice(start, min(len(l), end))
    start_slice = slice(0, max(end - len(l), 0))

    end_len = end_slice.stop - end_slice.start

    section = l[end_slice] + l[start_slice]

    section.reverse()

    l[end_slice] = section[:end_len]
    l[start_slice] = section[end_len:]


def knot_hash(lengths, size=256):
    l = list(range(size))

    start = 0
    skip = 0

    for length in lengths:
        swap(l, start, length)

        start = (start + length + skip) % size
        skip += 1

    return l[0] * l[1]


def test_knot_hash():
    assert knot_hash([3, 4, 1, 5], 5) == 12


def parse(s):
    return [int(x.strip()) for x in s.strip().split(",")]


if __name__ == "__main__":
    print(knot_hash(parse(util.get_input(10))))

day10_2.py

import util
from day10 import swap
import operator
from functools import reduce


def knot_hash(s, size=256):
    lengths = [ord(c) for c in s] + [17, 31, 73, 47, 23]

    l = list(range(size))

    start = 0
    skip = 0

    for round in range(64):
        for length in lengths:
            swap(l, start, length)

            start = (start + length + skip) % size
            skip += 1

    dense = [reduce(operator.xor, l[i: i + 16], 0) for i in range(0, size, 16)]

    return ''.join("{:02x}".format(x) for x in dense)


def test():
    assert knot_hash("") == "a2582a3a0e66e6e86e3812dcb672a272"
    assert knot_hash("AoC 2017") == "33efeb34ea91902bb2f59c9920caa6cd"
    assert knot_hash("1,2,3") == "3efbe78a8d82f29979031a4aa0b16a9d"
    assert knot_hash("1,2,4") == "63960835bcdc130f0b66d7ff4f6a5a8e"


if __name__ == "__main__":
    print(knot_hash(util.get_input(10).strip()))

day11.py

import util
import numpy as np

directions = dict(
    n=np.array([0, 2]),
    s=np.array([0, -2]),
    ne=np.array([2, 1]),
    se=np.array([2, -1]),
    nw=np.array([-2, 1]),
    sw=np.array([-2, -1]),
)


def position_after(steps):
    position = np.array([0, 0])
    for step in steps:
        position += directions[step]
    return position


def dist_from_origin(target):
    # split into a number of horizontal steps followed by a number of vertical
    # steps

    # we always need this many horizontal steps to get us into the right column
    steps_h = np.abs(target[0]) // 2

    # these horizontal steps can put us into the range y=+-steps_h, depending
    # on whether each horizontal step goes up or down; calculate the number of
    # extra vertical steps needed
    steps_v = max(np.abs(target[1]) - steps_h, 0) // 2

    return steps_h + steps_v


def test():
    assert dist_from_origin(position_after("ne,ne,ne".split(","))) == 3
    assert dist_from_origin(position_after("ne,ne,sw,sw".split(","))) == 0
    assert dist_from_origin(position_after("ne,ne,s,s".split(","))) == 2
    assert dist_from_origin(position_after("se,sw,se,sw,sw".split(","))) == 3


if __name__ == "__main__":
    steps = util.get_input(11).strip().split(",")
    position = position_after(steps)
    print(dist_from_origin(position))

day11_2.py

import util
import numpy as np
from day11 import directions, dist_from_origin


def solve(steps):
    max_dist = 0

    position = np.array([0, 0])
    for step in steps:
        position += directions[step]
        max_dist = max(max_dist, dist_from_origin(position))

    return max_dist


if __name__ == "__main__":
    steps = util.get_input(11).strip().split(",")
    print(solve(steps))

day12.py

import networkx as nx
import util
import re

LINE_RE = re.compile("(.*) <-> (.*)$")


def parse_line(line):
    m = LINE_RE.match(line)
    node_str, node_connected_str = m.groups()

    return int(node_str), [int(c.strip()) for c in node_connected_str.split(",")]


def test_parse_line():
    assert parse_line("2 <-> 0, 3, 4") == (2, [0, 3, 4])


def parse(s):
    return [parse_line(l.strip()) for l in s.strip().split("\n")]


def load(s):
    G = nx.Graph()
    for node, connected in parse(s):
        for other in connected:
            G.add_edge(node, other)
    return G


# is using networkx cheating? implementing regular graph algorithms is boring
# and useless, knowing how to use networkx might come in handy
def solve(s):
    G = load(s)
    return len(nx.node_connected_component(G, 0))


def test():
    example = """
0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5
"""
    assert solve(example) == 6


if __name__ == "__main__":
    print(solve(util.get_input(12)))

day12_2.py

import networkx as nx
import util
from day12 import load


def solve(s):
    G = load(s)
    return len(list(nx.connected_components(G)))


def test():
    example = """
0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5
"""
    assert solve(example) == 2


if __name__ == "__main__":
    print(solve(util.get_input(12)))

day13.py

import util


def parse_line(line):
    depth_s, range_s = line.split(":")
    return int(depth_s.strip()), int(range_s.strip())


def parse(s):
    return [parse_line(line) for line in s.strip().split("\n")]


def get_pos(range_, t):
    scanner_state = t % ((range_ - 1) * 2)
    return min(scanner_state, 2 * range_ - 2 - scanner_state)


def get_severity(s):
    scanners = dict(parse(s))

    severity = 0
    for t in range(max(scanners.keys()) + 1):
        if t in scanners:
            pos = get_pos(scanners[t], t)
            if pos == 0:
                severity += t * scanners[t]

    return severity


def test():
    sample = """
0: 3
1: 2
4: 4
6: 4
"""
    assert get_severity(sample) == 24


if __name__ == "__main__":
    print(get_severity(util.get_input(13)))

day13_2.py

import util
from day13 import parse, get_pos
from itertools import count

# a bit slow again


def is_caught(scanners, delay):
    for t in range(delay, delay + max(scanners.keys()) + 1):
        depth = t - delay
        if depth in scanners:
            pos = get_pos(scanners[depth], t)
            if pos == 0:
                return True
    return False


def min_delay_not_caught(s):
    scanners = dict(parse(s))

    for delay in count():
        if not is_caught(scanners, delay):
            return delay


def test():
    sample = """
0: 3
1: 2
4: 4
6: 4
"""
    assert min_delay_not_caught(sample) == 10


if __name__ == "__main__":
    print(min_delay_not_caught(util.get_input(13)))

day14.py

from day10 import swap
import operator
from functools import reduce


def knot_hash_dense(s, size=256):
    lengths = [ord(c) for c in s] + [17, 31, 73, 47, 23]

    l = list(range(size))

    start = 0
    skip = 0

    for round in range(64):
        for length in lengths:
            swap(l, start, length)

            start = (start + length + skip) % size
            skip += 1

    dense = [reduce(operator.xor, l[i: i + 16], 0) for i in range(0, size, 16)]

    return dense


def grid(key):
    return [knot_hash_dense("{key}-{i}".format(key=key, i=i)) for i in range(128)]


def count_used(grid):
    return sum((x >> ofs) & 1 for row in grid for x in row for ofs in range(8))


def test():
    assert count_used(grid("flqrgnkx")) == 8108


if __name__ == "__main__":
    print(count_used(grid("jxqlasbh")))

day14_2.py

from day14 import grid
import numpy as np


def grid_arr(key):
    return np.unpackbits(np.array(grid(key), dtype=np.uint8), axis=1)


offsets = np.array([
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
])


def fill(used, regions, start):
    to_visit = [start]
    regions[start] = 1

    while to_visit:
        pos = to_visit.pop()

        for offset in offsets:
            next_pos = tuple(offset + pos)

            if (next_pos[0] >= 0 and next_pos[1] >= 0 and
                    next_pos[0] < used.shape[0] and next_pos[1] < used.shape[1] and
                    used[next_pos] and not regions[next_pos]):
                regions[next_pos] = 1
                to_visit.append(next_pos)


def num_regions(used):
    regions = np.zeros_like(used)
    count = 0
    for pos in np.ndindex(*used.shape):
        if used[pos] and not regions[pos]:
            fill(used, regions, pos)
            count += 1

    return count


def test():
    assert num_regions(grid_arr("flqrgnkx")) == 1242


if __name__ == "__main__":
    print(num_regions(grid_arr("jxqlasbh")))

day15.py

from itertools import islice


def generator(factor, start):
    value = start
    while True:
        value = (value * factor) % 2147483647
        yield value


factors = 16807, 48271


def test_generator():
    assert list(islice(generator(16807, 65), 5)) == [1092455,
                                                     1181022009,
                                                     245556042,
                                                     1744312007,
                                                     1352636452]


def solve(a, b):
    return sum(
        a_val & 0xffff == b_val & 0xffff
        for a_val, b_val
        in islice(zip(generator(factors[0], a),
                      generator(factors[1], b)),
                  40000000))


def test():
    assert solve(65, 8921) == 588


if __name__ == "__main__":
    print(solve(289, 629))

day15_2.py

from itertools import islice
from functools import partial
from day15 import factors


def generator(factor, multiple, start):
    value = start
    while True:
        value = (value * factor) % 2147483647
        if value % multiple == 0:
            yield value


multiples = 4, 8
generators = [partial(generator, factor, multiple)
              for factor, multiple in zip(factors, multiples)]


def test_generator():
    assert list(islice(generators[0](65), 5)) == [1352636452,
                                                  1992081072,
                                                  530830436,
                                                  1980017072,
                                                  740335192]


def solve(a, b):
    return sum(
        a_val & 0xffff == b_val & 0xffff
        for a_val, b_val
        in islice(zip(generators[0](a), generators[1](b)),
                  5000000))


def test():
    assert solve(65, 8921) == 309


if __name__ == "__main__":
    print(solve(289, 629))

day16.py

import util
import string


def solve(n, moves):
    p = list(string.ascii_letters[:n])

    for move in moves:
        if move[0] == "s":
            x = int(move[1:])
            assert x
            p = p[-x:] + p[:-x]
        elif move[0] == "x":
            a, b = move[1:].split("/")
            a, b = int(a), int(b)
            p[a], p[b] = p[b], p[a]
        elif move[0] == "p":
            a, b = move[1:].split("/")
            a, b = p.index(a), p.index(b)
            p[a], p[b] = p[b], p[a]
        else:
            assert False

    return ''.join(p)


def test():
    assert solve(5, ["s1", "x3/4", "pe/b"]) == "baedc"


def parse(s):
    return s.strip().split(",")


if __name__ == "__main__":
    print(solve(16, parse(util.get_input(16))))

day16_2.py

import util
import string
from itertools import count


def parse_move(move):
    if move[0] == "s":
        x = int(move[1:])
        assert x

        def f(p):
            p[:] = p[-x:] + p[:-x]
    elif move[0] == "x":
        a, b = move[1:].split("/")
        a, b = int(a), int(b)

        def f(p):
            p[a], p[b] = p[b], p[a]
    elif move[0] == "p":
        a, b = move[1:].split("/")

        def f(p):
            a_i, b_i = p.index(a), p.index(b)
            p[a_i], p[b_i] = p[b_i], p[a_i]
    else:
        assert False

    return f


def find_loop(n, moves_f):
    p = list(string.ascii_letters[:n])
    seen = {}

    for i in count():
        p_str = ''.join(p)
        if p_str in seen:
            return seen[p_str], i
        seen[p_str] = i

        for move_f in moves_f:
            move_f(p)


def state_after(n, moves_f, loops):
    p = list(string.ascii_letters[:n])

    for i in range(loops):
        for move_f in moves_f:
            move_f(p)

    return ''.join(p)


def solve(n, moves):
    moves_f = list(map(parse_move, moves))

    loop_a, loop_b = find_loop(n, moves_f)

    target = 1000000000
    loops = loop_a + (target - loop_b) % (loop_b - loop_a)

    return state_after(n, moves_f, loops)


def parse(s):
    return s.strip().split(",")


if __name__ == "__main__":
    print(solve(16, parse(util.get_input(16))))

day17.py

def solve(step):
    b = [0]
    pos = 0

    for i in range(1, 2017 + 1):
        pos = (pos + step) % len(b) + 1
        b.insert(pos, i)

    return b[(pos + 1) % len(b)]


def test():
    assert solve(3) == 638


if __name__ == "__main__":
    print(solve(316))

day17_2.py

def solve_slow(step, n):
    b = [0]
    pos = 0

    for i in range(1, n + 1):
        pos = (pos + step) % len(b) + 1
        b.insert(pos, i)

    print(b, pos)
    return b[(b.index(0) + 1) % len(b)]


def solve(step, n):
    pos = 0
    zero_pos = 0
    after_zero = None

    for i in range(1, n + 1):
        buf_len = i
        pos = (pos + step + 1) % buf_len

        if pos <= zero_pos:
            zero_pos += 1

        if pos == (zero_pos + 1) % (buf_len + 1):
            after_zero = i
        # print(pos, zero_pos, buf_len, after_zero)

    return after_zero


def test():
    assert solve_slow(3, 1) == 1
    assert solve(3, 1) == 1

    assert solve_slow(3, 2017) == solve(3, 2017)


if __name__ == "__main__":
    print(solve(316, 50000000))

day18.py

import util
import string
import operator
from attr import attrs, attrib, Factory


def regnum(r):
    return ord(r) - ord('a')


def const(X):
    X = int(X)
    return lambda state: X


def reg(X):
    X = regnum(X)
    return lambda state: state.regs[X]


def reg_or_const(X):
    if X in string.ascii_lowercase:
        return reg(X)
    else:
        return const(X)


def i_snd(X):
    X = reg_or_const(X)

    def f(state):
        rv = state.snd_cb(X(state))
        state.pc += 1
        return rv
    return f


def i_rcv(X):
    X = reg_or_const(X)

    def f(state):
        rv = True
        if X(state):
            rv = state.rcv_cb(X(state))
        state.pc += 1
        return rv
    return f


def bin_op(op):
    def instr(X, Y):
        X = regnum(X)
        Y = reg_or_const(Y)

        def f(state):
            state.regs[X] = op(state.regs[X], Y(state))
            state.pc += 1
            return True
        return f
    return instr


i_set = bin_op(lambda x, y: y)
i_add = bin_op(operator.add)
i_mul = bin_op(operator.mul)
i_mod = bin_op(operator.mod)


def i_jgz(X, Y):
    X = reg_or_const(X)
    Y = reg_or_const(Y)

    def f(state):
        if X(state) > 0:
            state.pc += Y(state)
        else:
            state.pc += 1
        return True
    return f


i_types = dict(
    snd=i_snd,
    set=i_set,
    add=i_add,
    mul=i_mul,
    mod=i_mod,
    rcv=i_rcv,
    jgz=i_jgz,
)


def parse_inst(i_types, instr):
    op, *rest = instr.strip().split(" ")
    return i_types[op](*rest)


def parse(i_types, s):
    return [parse_inst(i_types, i) for i in s.strip().split("\n")]


TEST = """
set a 1
add a 2
mul a a
mod a 5
snd a
set a 0
rcv a
jgz a -1
set a 1
jgz a -2
"""


@attrs(slots=True)
class State(object):
    instrs = attrib()
    pc = attrib(default=0)
    regs = attrib(default=Factory(lambda: [0] * 26))

    def snd_cb(self, x):
        return True

    def rcv_cb(self, x):
        return True


@attrs(slots=True)
class StateSolve(State):
    last_freq = attrib(default=None)

    def snd_cb(self, x):
        self.last_freq = x
        return True

    def rcv_cb(self, x):
        return False


def run(state):
    while 0 <= state.pc < len(state.instrs) and state.instrs[state.pc](state):
        pass


def test():
    state = StateSolve(parse(i_types, TEST))
    run(state)
    assert state.last_freq == 4


if __name__ == "__main__":
    state = StateSolve(parse(i_types, util.get_input(18)))
    run(state)
    print(state.last_freq)

day18_2.py

import util
from attr import attrs, attrib
from day18 import State, regnum, parse, reg_or_const
from day18 import i_types as old_i_types


def i_snd(X):
    X = reg_or_const(X)

    def f(state):
        state.other_queue.append(X(state))
        state.num_sent += 1
        state.pc += 1

        return True
    return f


def i_rcv(X):
    X = regnum(X)

    def f(state):
        if state.queue:
            state.regs[X] = state.queue.pop(0)
            state.waiting = False
            state.pc += 1
        else:
            state.waiting = True
        return True

    return f


i_types = old_i_types
i_types["snd"] = i_snd
i_types["rcv"] = i_rcv


@attrs(slots=True)
class StateSolve(State):
    queue = attrib(default=None)
    other_queue = attrib(default=None)
    waiting = attrib(default=False)
    num_sent = attrib(default=0)

    @property
    def running(self):
        return 0 <= self.pc < len(self.instrs)


def run(state_a, state_b):
    state_a.regs[regnum("p")] = 0
    state_b.regs[regnum("p")] = 1

    while (state_a.running or state_b.running) and not (state_a.waiting and state_b.waiting):
        if state_a.running:
            state_a.instrs[state_a.pc](state_a)
        if state_b.running:
            state_b.instrs[state_b.pc](state_b)


def build_states(instrs):
    queue_a, queue_b = [], []

    state_a = StateSolve(instrs=instrs,
                         queue=queue_a,
                         other_queue=queue_b)
    state_b = StateSolve(instrs=instrs,
                         queue=queue_b,
                         other_queue=queue_a)

    return state_a, state_b


TEST = """
snd 1
snd 2
snd p
rcv a
rcv b
rcv c
rcv d
"""


def test():
    instrs = parse(i_types, TEST)
    state_a, state_b = build_states(instrs)
    run(state_a, state_b)
    assert state_a.waiting and state_b.waiting
    assert state_b.num_sent == 3


if __name__ == "__main__":
    instrs = parse(i_types, util.get_input(18))
    state_a, state_b = build_states(instrs)
    run(state_a, state_b)
    print(state_b.num_sent)

day19.py

import util
import numpy as np


def parse(s):
    lines = [l for l in s.split("\n") if l.strip()]
    return np.array([list(line) for line in lines])


def start_pos(g):
    return np.where(g[0] == "|")[0][0]


directions = np.array([
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
])


def next_direction(g, pos, direction):
    for new_direction in directions:
        if np.all(-direction == new_direction):
            continue

        new_pos = pos + new_direction

        if 0 <= new_pos[0] < g.shape[0] and 0 <= new_pos[1] < g.shape[1] and g[tuple(new_pos)] != ' ':
            return new_direction

    assert False


def test_next_dir():
    g = parse(TEST)
    assert g[5, 5] == "+"
    direction = next_direction(g, np.array([5, 5]), np.array([1, 0]))
    assert list(direction) == [0, 1]


def chars_on_path(g):
    pos = np.array([0, start_pos(g)])
    direction = np.array([1, 0])
    seen = []

    while True:
        c = g[tuple(pos)]
        if c == "-" or c == "|":
            pass
        elif c == "+":
            direction = next_direction(g, pos, direction)
        elif c == " ":
            break
        else:
            seen.append(c)

        pos += direction

        if not (0 <= pos[0] < g.shape[0] and 0 <= pos[1] < g.shape[1]):
            break

    return ''.join(seen)


# noqa
TEST = """
     |          
     |  +--+    
     A  |  C    
 F---|----E|--+ 
     |  |  |  D 
     +B-+  +--+ 
"""


def test():
    assert chars_on_path(parse(TEST)) == "ABCDEF"


if __name__ == "__main__":
    print(chars_on_path(parse(util.get_input(19))))

day19_2.py

import util
import numpy as np
from day19 import TEST, start_pos, next_direction, parse


def path_len(g):
    pos = np.array([0, start_pos(g)])
    direction = np.array([1, 0])
    steps = 0

    while True:
        c = g[tuple(pos)]
        if c == "+":
            direction = next_direction(g, pos, direction)
        elif c == " ":
            break

        pos += direction

        if not (0 <= pos[0] < g.shape[0] and 0 <= pos[1] < g.shape[1]):
            break

        steps += 1

    return steps


def test():
    assert path_len(parse(TEST)) == 38


if __name__ == "__main__":
    print(path_len(parse(util.get_input(19))))

day1_2.py

import util


def char_sum(s):
    offset = len(s) // 2
    return sum(int(x) for x, y in zip(s, s[offset:] + s[:offset]) if x == y)


def test():
    assert char_sum("1212") == 6
    assert char_sum("1221") == 0
    assert char_sum("123425") == 4
    assert char_sum("123123") == 12
    assert char_sum("12131415") == 4


if __name__ == "__main__":
    print(char_sum(util.get_input(1).strip()))

day2.py

import util
import numpy as np
from io import StringIO


def load_sheet(s):
    return np.loadtxt(StringIO(s), dtype=int)


def checksum(s):
    return np.sum(np.max(s, axis=1) - np.min(s, axis=1))


def test():
    sheet = "5 1 9 5\n7 5 3 4\n2 4 6 8"
    assert checksum(load_sheet(sheet)) == 18


if __name__ == "__main__":
    print(checksum(load_sheet(util.get_input(2).strip())))

day20.py

import util
import numpy as np
import re


LINE_RE = re.compile("p=<(.*),(.*),(.*)>, v=<(.*),(.*),(.*)>, a=<(.*),(.*),(.*)>$")


def parse_line(line):
    m = LINE_RE.match(line.strip())
    x = [int(g) for g in m.groups()]
    return (x[0:3], x[3:6], x[6:9])


def parse(s):
    lines = s.strip().split("\n")
    return np.array([parse_line(line) for line in lines]).swapaxes(0, 1)


TEST = """
p=< 3,0,0>, v=< 2,0,0>, a=<-1,0,0>
p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>
"""


def solve(s):
    p, v, a = parse(s)
    return np.argmin(np.sum(np.abs(a), axis=1))


def test():
    assert solve(TEST) == 0


if __name__ == "__main__":
    print(solve(util.get_input(20)))

day20_2.py

from day20 import parse
import numpy as np
from collections import defaultdict
import util


# This is a bit of a mess -- the particle positions are represented as
# polynomials, which intersect when the particles collide. This allows us to be
# sure that we haven't missed a future collision, but:
#
# - it's slow. Using the quadratic formula directly would be faster than using
#   np.roots though.
# - in my input, the last collision is at t=39, which could have easily been
#   simulated
# - the code assumes that only a single collision happens in a given time step
#   -- there's a possibility that this would give incorrect results if multiple
#   colisions happened at once and some of the particles had already collided.
#   This would be easy to fix, but it gives the right result for my input.
#
# A direct simulation would have been much easier, see day20_direct.py


def positions(p, v, a):
    while True:
        yield p
        v += a
        p += v


def to_poly(p, v, a):
    return p, v + a / 2, a / 2


def all_to_polys(p, v, a):
    # particle, axis, poly
    return np.array(to_poly(p, v, a)[::-1]).swapaxes(0, 1).swapaxes(1, 2)


# True: axes are identical
# False: axes never collide
# set: integer intersection times
def axis_intersections(a, b):
    if np.all(a == b):
        return True

    roots = np.roots(a - b)
    real_roots = roots[np.isreal(roots)]
    real_roots_round = np.round(real_roots)

    real_int_roots = real_roots_round[np.abs(real_roots - real_roots_round) < 1e-2]
    real_int_roots_pos = real_int_roots[real_int_roots >= 0]

    if len(real_int_roots_pos):
        return set(real_int_roots_pos)
    else:
        return False


def intersection_times(a, b):
    intersections = [axis_intersections(a_axis, b_axis) for a_axis, b_axis in zip(a, b)]

    if False in intersections:
        return set()
    elif all(t is True for t in intersections):
        return {0}
    else:
        future_colisions = [t for t in intersections if t is not True]
        if future_colisions:
            return set.intersection(*future_colisions)
        else:
            return set()


TEST = """
p=<-6,0,0>, v=< 3,0,0>, a=< 0,0,0>
p=<-4,0,0>, v=< 2,0,0>, a=< 0,0,0>
p=<-2,0,0>, v=< 1,0,0>, a=< 0,0,0>
p=< 3,0,0>, v=<-1,0,0>, a=< 0,0,0>
"""


def test_colides():
    p = all_to_polys(*parse(TEST))
    assert intersection_times(p[0], p[1]) == {2.0}
    assert intersection_times(p[1], p[2]) == {2.0}

    assert intersection_times(p[0], p[0]) == {0.0}


def all_intersections(p, v, a):
    p = all_to_polys(p, v, a)

    intersections = defaultdict(set)

    for i in range(len(p)):
        for j in range(i + 1, len(p)):
            i_j_times = intersection_times(p[i], p[j])
            for t in i_j_times:
                intersections[int(t)].add(i)
                intersections[int(t)].add(j)

    return intersections


def solve(p, v, a):
    intersections = all_intersections(p, v, a)
    active = np.ones(len(p), dtype=bool)

    for t in sorted(intersections):
        if sum(active[i] for i in intersections[t]) >= 2:
            for i in intersections[t]:
                active[i] = False

    print("last collision: {}".format(max(intersections)))

    return sum(active)


def test():
    assert solve(*parse(TEST)) == 1


if __name__ == "__main__":
    input_mod = "\n".join(util.get_input(20).strip().split("\n")[:])
    print(solve(*parse(input_mod)))

day20_2_direct.py

import numpy as np
import util
from day20 import parse
from itertools import count
from collections import defaultdict


def solve(p, v, a):
    p, v = p.copy(), v.copy()
    active = np.ones(len(p), dtype=bool)

    for i in count():
        print(i, sum(active))

        active_by_position = defaultdict(list)

        for i, pos in enumerate(p):
            if active[i]:
                active_by_position[tuple(pos)].append(i)

        for particles in active_by_position.values():
            if len(particles) >= 2:
                active[particles] = False

        v += a
        p += v


if __name__ == "__main__":
    solve(*parse(util.get_input(20)))

day21.py

import util
import numpy as np


def parse_grid(s):
    return np.array([
        [c == "#" for c in row]
        for row in s.split("/")
    ], dtype=bool)


def parse_rule(rule):
    from_s, to_s = rule.strip().split(" => ")
    return parse_grid(from_s), parse_grid(to_s)


def parse(s):
    return [parse_rule(line) for line in s.strip().split("\n")]


def to_tuple(grid):
    return tuple(tuple(row) for row in grid)


def permutations(grid):
    for grid_t in [grid, grid.T]:
        for x in [slice(None), slice(None, None, -1)]:
            for y in [slice(None), slice(None, None, -1)]:
                yield grid_t[x, y]


def make_table(rules):
    table = {}
    for from_grid, to_grid in rules:
        for permutation in permutations(from_grid):
            table[to_tuple(permutation)] = to_grid
    return table


start_pattern = parse_grid(".#./..#/###")


def grid_after(table, n):
    pattern = start_pattern

    for i in range(n):
        size = len(pattern)
        if size % 2 == 0:
            step = 2
        elif size % 3 == 0:
            step = 3
        else:
            assert False

        new_size = size + size // step
        new_pattern = np.zeros((new_size, new_size), dtype=bool)

        for y in range(size // step):
            for x in range(size // step):
                new_x, new_y = x * (step + 1), y * (step + 1)
                old_x, old_y = x * step, y * step

                new_block = table[to_tuple(pattern[old_y: old_y + step,
                                                   old_x: old_x + step])]

                new_pattern[new_y:new_y + step + 1,
                            new_x:new_x + step + 1] = new_block

        pattern = new_pattern

    return pattern


def test():
    TEST = "../.# => ##./#../...\n.#./..#/### => #..#/..../..../#..#"
    table = make_table(parse(TEST))
    assert np.sum(grid_after(table, 0)) == 5
    assert np.sum(grid_after(table, 1)) == 4
    assert np.sum(grid_after(table, 2)) == 12


if __name__ == "__main__":
    table = make_table(parse(util.get_input(21)))
    print(np.sum(grid_after(table, 5)))

day21_2.py

import util
from day21 import parse, make_table, grid_after
import numpy as np


if __name__ == "__main__":
    table = make_table(parse(util.get_input(21)))
    print(np.sum(grid_after(table, 18)))

day22.py

import util
import numpy as np


def load(s):
    lines = s.strip().split("\n")

    ofs_x = len(lines[0]) // 2
    ofs_y = len(lines) // 2

    return set((x - ofs_x, y - ofs_y)
               for y, line in enumerate(lines)
               for x, c in enumerate(line)
               if c == "#")


directions = np.array([
    [0, -1],
    [1, 0],
    [0, 1],
    [-1, 0],
])


def solve(infected, n):
    pos = (0, 0)
    direction = 0
    num_infected = 0

    for i in range(n):
        if pos in infected:
            direction = (direction + 1) % len(directions)
            infected.remove(pos)
        else:
            direction = (direction - 1) % len(directions)
            infected.add(pos)
            num_infected += 1

        pos = tuple(np.add(pos, directions[direction]))

    return num_infected


TEST = """
..#
#..
...
"""


def test():
    assert solve(load(TEST), 70) == 41
    assert solve(load(TEST), 10000) == 5587


if __name__ == "__main__":
    print(solve(load(util.get_input(22)), 10000))

day22_2.py

import util
import numpy as np
from day22 import directions, TEST
from enum import Enum, auto


class NodeState(Enum):
    CLEAN = auto()
    WEAKENED = auto()
    INFECTED = auto()
    FLAGGED = auto()


next_state = {
    NodeState.CLEAN: NodeState.WEAKENED,
    NodeState.WEAKENED: NodeState.INFECTED,
    NodeState.INFECTED: NodeState.FLAGGED,
    NodeState.FLAGGED: NodeState.CLEAN,
}


def load(s):
    lines = s.strip().split("\n")

    ofs_x = len(lines[0]) // 2
    ofs_y = len(lines) // 2

    return {(x - ofs_x, y - ofs_y): NodeState.INFECTED
            for y, line in enumerate(lines)
            for x, c in enumerate(line)
            if c == "#"}


def solve(state, n):
    pos = (0, 0)
    direction = 0
    num_infected = 0

    for i in range(n):
        curr_state = state.get(pos, NodeState.CLEAN)

        if curr_state == NodeState.CLEAN:
            direction = (direction - 1) % len(directions)
        elif curr_state == NodeState.WEAKENED:
            pass
        elif curr_state == NodeState.INFECTED:
            direction = (direction + 1) % len(directions)
        elif curr_state == NodeState.FLAGGED:
            direction = (direction + 2) % len(directions)
        else:
            assert False

        curr_state = next_state[curr_state]

        if curr_state == NodeState.INFECTED:
            num_infected += 1

        if curr_state == NodeState.CLEAN:
            del state[pos]
        else:
            state[pos] = curr_state

        pos = tuple(np.add(pos, directions[direction]))

    return num_infected


def test():
    assert solve(load(TEST), 100) == 26
    assert solve(load(TEST), 10000000) == 2511944


if __name__ == "__main__":
    print(solve(load(util.get_input(22)), 10000000))

day2_2.py

import util
import numpy as np
from day2 import load_sheet


def checksum(s):
    i, j, k = np.where((s[:, :, np.newaxis] % s[:, np.newaxis, :]) == 0)
    ii, jj, kk = i[j != k], j[j != k], k[j != k]
    return np.sum(s[ii, jj] // s[ii, kk])


def test():
    sheet = "5 9 2 8\n9 4 7 3\n3 8 6 5"
    assert checksum(load_sheet(sheet)) == 9


if __name__ == "__main__":
    print(checksum(load_sheet(util.get_input(2).strip())))

day3.py

import numpy as np


def ring_start(n):
    return 4 * n ** 2 - 4 * n + 2


def ring_of(n):
    return int((np.sqrt(n - 1) + 1) / 2)


def coord(n):
    if n == 1:
        return np.array([0, 0])

    ring = ring_of(n)
    start = ring_start(ring)
    ofs = n - start

    edge_len = np.array([2 * ring - 1, 2 * ring, 2 * ring, 2 * ring])
    edge_start = np.cumsum(np.concatenate(([0], edge_len[:-1])))
    directions = np.array([
        [0, 1],
        [-1, 0],
        [0, -1],
        [1, 0],
    ])

    return (np.array([ring, 1 - ring]) +
            np.dot(np.clip(ofs - edge_start, 0, edge_len), directions))


def dist(n):
    return np.sum(np.abs(coord(n)))


def test():
    assert ring_start(1) == 2
    assert ring_start(2) == 10
    assert ring_start(3) == 26

    assert ring_of(2) == 1
    assert ring_of(9) == 1

    assert ring_of(10) == 2
    assert ring_of(25) == 2

    assert ring_of(26) == 3
    assert ring_of(27) == 3

    assert list(coord(1)) == [0, 0]
    assert list(coord(2)) == [1, 0]
    assert list(coord(3)) == [1, 1]
    assert list(coord(4)) == [0, 1]
    assert list(coord(5)) == [-1, 1]
    assert list(coord(6)) == [-1, 0]
    assert list(coord(7)) == [-1, -1]
    assert list(coord(8)) == [0, -1]
    assert list(coord(9)) == [1, -1]
    assert list(coord(10)) == [2, -1]
    assert list(coord(11)) == [2, 0]
    assert list(coord(12)) == [2, 1]
    assert list(coord(13)) == [2, 2]

    assert dist(1) == 0
    assert dist(12) == 3
    assert dist(23) == 2
    assert dist(1024) == 31


if __name__ == "__main__":
    print(dist(265149))

day3_2.py

import numpy as np
from itertools import islice
from day3 import coord


def values_written():
    mem = {}

    mem[tuple(coord(1))] = 1
    yield 1

    offsets = np.array([
        [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1],
    ])

    i = 2
    while True:
        next_coord = coord(i)
        next_value = sum(mem.get(tuple(next_coord + offset), 0) for offset in offsets)
        mem[tuple(next_coord)] = next_value
        yield next_value
        i += 1


def solve(n):
    for val in values_written():
        if val > n:
            return val


def test():
    seq = [1, 1, 2, 4, 5, 10, 11, 23, 25, 26, 54, 57, 59]
    assert list(islice(values_written(), len(seq))) == seq

    assert solve(30) == 54


if __name__ == "__main__":
    print(solve(265149))

day4.py

from collections import Counter
import util


def valid(pp):
    words = pp.split()
    assert len(words) > 1
    return Counter(words).most_common()[0][1] == 1


def test():
    assert valid("aa bb cc dd ee")
    assert not valid("aa bb cc dd aa")
    assert valid("aa bb cc dd aaa")


if __name__ == "__main__":
    pps = util.get_input(4).strip().split("\n")
    print(sum(valid(pp) for pp in pps))

day4_2.py

from collections import Counter
import util


def sort_word(word):
    return ''.join(sorted(word))


def valid(pp):
    words = pp.split()
    assert len(words) > 1
    return Counter(map(sort_word, words)).most_common()[0][1] == 1


def test():
    assert valid("abcde fghij")
    assert not valid("abcde xyz ecdab")
    assert valid("a ab abc abd abf abj")
    assert valid("iiii oiii ooii oooi oooo")
    assert not valid("oiii ioii iioi iiio")


if __name__ == "__main__":
    pps = util.get_input(4).strip().split("\n")
    print(sum(valid(pp) for pp in pps))

day5.py

import util
import itertools
from attr import attrs, attrib


@attrs
class Simulator(object):
    code = attrib()
    pc = attrib(default=0)

    def step(self):
        instr = self.code[self.pc]
        self.code[self.pc] += 1
        self.pc += instr

    def steps_until_exit(self):
        for i in itertools.count(0):
            if self.pc >= len(self.code):
                return i
            self.step()


def parse_code(s):
    return list(map(int, s.strip().split()))


def test():
    assert Simulator(parse_code("0\n3\n0\n1\n-3")).steps_until_exit() == 5


if __name__ == "__main__":
    print(Simulator(parse_code(util.get_input(5))).steps_until_exit())

day5_2.py

import util
import itertools
from attr import attrs, attrib
from day5 import parse_code


@attrs(slots=True)
class Simulator(object):
    code = attrib()
    pc = attrib(default=0)

    def step(self):
        instr = self.code[self.pc]
        self.code[self.pc] += -1 if instr >= 3 else 1
        self.pc += instr

    def steps_until_exit(self):
        code_len = len(self.code)
        for i in itertools.count(0):
            if self.pc >= code_len:
                return i
            self.step()


def steps_until_exit_faster(code):
    code_len = len(code)

    pc = 0
    for i in itertools.count(0):
        if pc >= code_len:
            return i

        instr = code[pc]
        code[pc] += -1 if instr >= 3 else 1
        pc += instr


def test():
    assert Simulator(parse_code("0\n3\n0\n1\n-3")).steps_until_exit() == 10
    assert steps_until_exit_faster(parse_code("0\n3\n0\n1\n-3")) == 10


if __name__ == "__main__":
    # 17s
    # print(Simulator(parse_code(util.get_input(5))).steps_until_exit())

    # 7s
    print(steps_until_exit_faster(parse_code(util.get_input(5))))

    # both are ~1.5s in pypy

day6.py

import util
import numpy as np
from itertools import count


def redistribute(a):
    bank = np.argmax(a)
    to_redistribute = a[bank]
    a[bank] = 0

    idx = (np.arange(len(a)) - (bank + 1)) % len(a)

    to_all, remaining = np.divmod(to_redistribute, len(a))

    a += to_all
    a[idx < remaining] += 1

    return a


def test_redistribute():
    a = np.array([0, 2, 7, 0], dtype=int)
    redistribute(a)
    assert list(a) == [2, 4, 1, 2]
    redistribute(a)
    assert list(a) == [3, 1, 2, 3]
    redistribute(a)
    assert list(a) == [0, 2, 3, 4]
    redistribute(a)
    assert list(a) == [1, 3, 4, 1]
    redistribute(a)
    assert list(a) == [2, 4, 1, 2]


def solve(a):
    seen = set()

    for i in count():
        a_tpl = tuple(a)
        if a_tpl in seen:
            return i
        seen.add(a_tpl)
        redistribute(a)


def test_solve():
    assert solve(np.array([0, 2, 7, 0])) == 5


def parse(s):
    return np.array([int(i) for i in s.strip().split("\t")])


if __name__ == "__main__":
    print(solve(parse(util.get_input(6))))

day6_2.py

import util
import numpy as np
from itertools import count
from day6 import redistribute


def solve(a):
    seen = {}

    for i in count():
        a_tpl = tuple(a)
        if a_tpl in seen:
            return i - seen[a_tpl]
        seen[a_tpl] = i
        redistribute(a)


def test_solve():
    assert solve(np.array([0, 2, 7, 0])) == 4


def parse(s):
    return np.array([int(i) for i in s.strip().split("\t")])


if __name__ == "__main__":
    print(solve(parse(util.get_input(6))))

day7.py

import util
import re
from attr import attrs, attrib, Factory

LINE_RE = re.compile(r"""(?P<name>\S+)             # name
                         \                         # space
                         \( (?P<weight>[0-9]+) \)  # weight
                         (?:
                            \ -> \                 # sep
                            (?P<children>.*)       # children
                         )?$""", re.VERBOSE)


def parse_line(line):
    m = LINE_RE.match(line)
    assert m is not None
    children = m.group("children")
    return (
        m.group("name"),
        int(m.group("weight")),
        [] if children is None else [child.strip() for child in children.split(",")],
    )


def test_parse_line():
    assert parse_line("fwft (72)") == ("fwft", 72, [])
    assert parse_line("fwft (72) -> ktlj, cntj, xhth") == ("fwft", 72, ["ktlj", "cntj", "xhth"])


def parse(s):
    return [parse_line(l) for l in s.strip().split("\n")]


@attrs(slots=True)
class Tree(object):
    name = attrib()
    weight = attrib()
    children = attrib(default=Factory(list))


def lines_to_tree(lines):
    tree_by_name = {}

    # dict from child names to their parent
    needs_child = {}

    for name, weight, children in lines:
        tree = Tree(name, weight)

        if name in needs_child:
            needs_child[name].children.append(tree)
            del needs_child[name]
        else:
            tree_by_name[name] = tree

        for child in children:
            if child in tree_by_name:
                tree.children.append(tree_by_name[child])
                del tree_by_name[child]
            else:
                needs_child[child] = tree

    assert len(needs_child) == 0
    assert len(tree_by_name) == 1

    tree, = tree_by_name.values()
    return tree


def test_lines_to_tree():
    in_str = """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)"""
    tree = lines_to_tree(parse(in_str))
    assert tree == (
        Tree(name='tknk', weight=41, children=[
            Tree(name='padx', weight=45, children=[
                Tree(name='pbga', weight=66, children=[]),
                Tree(name='havc', weight=66, children=[]),
                Tree(name='qoyq', weight=66, children=[])]),
            Tree(name='fwft', weight=72, children=[
                Tree(name='ktlj', weight=57, children=[]),
                Tree(name='xhth', weight=57, children=[]),
                Tree(name='cntj', weight=57, children=[])]),
            Tree(name='ugml', weight=68, children=[
                Tree(name='ebii', weight=61, children=[]),
                Tree(name='jptl', weight=61, children=[]),
                Tree(name='gyxo', weight=61, children=[])])]))


if __name__ == "__main__":
    print(lines_to_tree(parse(util.get_input(7))).name)

day7_2.py

import util
from day7 import parse, lines_to_tree
from collections import Counter

# use an exception to return -- a bit of a hack to avoid double recursion or
# odd return values


class InvalidWeight(Exception):
    pass


def check(tree):
    child_weights = [check(child) for child in tree.children]

    if tree.children:
        ctr = Counter(child_weights)
        if len(ctr) > 1:
            target_weight = ctr.most_common()[0][0]

            for child, weight in zip(tree.children, child_weights):
                if weight != target_weight:
                    raise InvalidWeight((target_weight - weight) + child.weight)

    return sum(child_weights) + tree.weight


def solve(tree):
    try:
        check(tree)
    except InvalidWeight as e:
        return e.args[0]


def test_solve():
    in_str = """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)"""
    tree = lines_to_tree(parse(in_str))

    assert solve(tree) == 60


if __name__ == "__main__":
    print(solve(lines_to_tree(parse(util.get_input(7)))))

day8.py

import util
import re
# from attr import attrs, attrib, Factory
import operator
from collections import defaultdict


INSTR_RE = re.compile(r"""(?P<target>\w+)
                          \   # space
                          (?P<type>inc|dec)
                          \   # space
                          (?P<value>[-0-9]+)
                          \ if\  # ' if '
                          (?P<cond_reg>\w+)
                          \   # space
                          (?P<cond>>|<|<=|>=|==|!=)
                          \   # space
                          (?P<cond_value>[-0-9]+)
                          $
                          """, re.VERBOSE)

operators = {
    "<": operator.lt,
    ">": operator.gt,
    "<=": operator.le,
    ">=": operator.ge,
    "==": operator.eq,
    "!=": operator.ne,
}


# who needs an AST anyway?


def const(x):
    return lambda state: x


def reg(r):
    return lambda state: state[r]


def bin_op(op, lhs, rhs):
    f = operators[op]
    return lambda state: f(lhs(state), rhs(state))


def incr(reg, value, cond):
    def f(state):
        if cond(state):
            state[reg] += value
    return f


def decr(reg, value, cond):
    return incr(reg, -value, cond)


def parse(l):
    m = INSTR_RE.match(l)

    inst = dict(inc=incr, dec=decr)[m.group("type")]

    return inst(m.group("target"),
                int(m.group("value")),
                bin_op(
                    m.group("cond"),
                    reg(m.group("cond_reg")),
                    const(int(m.group("cond_value")))))


def parse_all(s):
    return [parse(l) for l in s.strip().split("\n")]


def eval_instrs(instrs):
    state = defaultdict(lambda: 0)

    for inst in instrs:
        inst(state)

    return state


def solve(instrs):
    state = eval_instrs(instrs)
    return max(state.values())


def test():
    s = """
b inc 5 if a > 1
a inc 1 if b < 5
c dec -10 if a >= 1
c inc -20 if c == 10
"""
    instrs = parse_all(s)
    # an AST would be nice for testing :(
    assert solve(instrs) == 1


if __name__ == "__main__":
    print(solve(parse_all(util.get_input(8))))

day8_2.py

import util
from day8 import parse_all
from collections import defaultdict


def solve(instrs):
    state = defaultdict(lambda: 0)

    max_ever = 0

    for instr in instrs:
        instr(state)
        max_ever = max(max_ever, max(state.values()))

    return max_ever


def test():
    s = """
b inc 5 if a > 1
a inc 1 if b < 5
c dec -10 if a >= 1
c inc -20 if c == 10
"""
    instrs = parse_all(s)
    assert solve(instrs) == 10


if __name__ == "__main__":
    print(solve(parse_all(util.get_input(8))))

day9.py

import util
from enum import Enum, auto


class State(Enum):
    IN_STREAM = auto()
    IN_GARBAGE = auto()
    IGNORE_NEXT = auto()


class Event(Enum):
    OPEN_BRACE = auto()
    CLOSE_BRACE = auto()
    GARBAGE_CHAR = auto()


def scan(s):
    state = State.IN_STREAM

    for c in s:
        if state == State.IN_STREAM:
            if c == '{':
                yield Event.OPEN_BRACE
            elif c == '}':
                yield Event.CLOSE_BRACE
            elif c == '<':
                state = State.IN_GARBAGE
            elif c == ",":
                pass
            else:
                assert False
        elif state == State.IN_GARBAGE:
            if c == '>':
                state = State.IN_STREAM
            elif c == '!':
                state = State.IGNORE_NEXT
            else:
                yield Event.GARBAGE_CHAR
        elif state == State.IGNORE_NEXT:
            state = State.IN_GARBAGE
        else:
            assert False


def parse(s):
    stack = [[]]
    for ev in scan(s):
        if ev == Event.OPEN_BRACE:
            new = []
            stack[-1].append(new)
            stack.append(new)
        elif ev == Event.CLOSE_BRACE:
            stack.pop()

    assert len(stack) == 1

    return stack[0][0]


def test_parse():
    assert parse("{}") == []
    assert parse("{{{}}}") == [[[]]]
    assert parse("{{},{}}") == [[], []]
    assert parse("{<a>,<a>,<a>,<a>}") == []
    assert parse("{{<!>},{<!>},{<!>},{<a>}}") == [[]]


def score(group, outer=1):
    return outer + sum(score(g, outer + 1) for g in group)


def test_score():
    assert score(parse("{}")) == 1
    assert score(parse("{{{}}}")) == 6
    assert score(parse("{{},{}}")) == 5
    assert score(parse("{{{},{},{{}}}}")) == 16
    assert score(parse("{<a>,<a>,<a>,<a>}")) == 1
    assert score(parse("{{<ab>},{<ab>},{<ab>},{<ab>}}")) == 9
    assert score(parse("{{<!!>},{<!!>},{<!!>},{<!!>}}")) == 9
    assert score(parse("{{<a!>},{<a!>},{<a!>},{<ab>}}")) == 3


if __name__ == "__main__":
    print(score(parse(util.get_input(9).strip())))

day9_2.py

import util
from day9 import scan, Event


def solve(s):
    return sum(ev == Event.GARBAGE_CHAR for ev in scan(s))


def test():
    assert solve("{<{o\"i!a,<{i<a>}") == 10


if __name__ == "__main__":
    print(solve(util.get_input(9).strip()))

util.py

def get_input(i):
    import requests
    from private import cookies

    req = requests.get("http://adventofcode.com/2017/day/{i}/input".format(i=i),
                       cookies=cookies)
    return req.text