AoC 2017 Advent of Code (Python)

lines = open('input').read().splitlines()
state = lines[0][15]
steps = int(lines[1].split()[5])
program = {}
curs = 0
tape = {}
 
def parse_op(stmt):
    val = int(stmt[0][22])
    dir = 1 if 'right' in stmt[1] else -1
    nxt = stmt[2][26]
    return (val, dir, nxt)
 
 
for blk in range(len(lines) // 10):
    label = lines[blk*10+3][9]
    program[label] = [ parse_op(lines[blk*10+5:blk*10+8]), parse_op(lines[blk*10+9:blk*10+12]) ]
 
for s in range(steps):
    value = tape[curs] if curs in tape else 0
    (value, dir, state) = program[state][value]
    tape[curs] = value
    curs += dir
 
print(list(tape.values()).count(1))

from collections import defaultdict, deque
 
connections = defaultdict(set)
 
lines = open('input').read().splitlines()
for line in lines:
    a, b = map(int, line.split('/'))
    connections[a].add((a, b))
    connections[b].add((a, b))
 
start = ({(0, 0)}, 0, 0)
que = deque([start])
 
max_score = 0
longest_strongest = (0, 0)
 
while que:
    path, score, conn = que.popleft()
    if score > max_score:
        max_score = score
    if (len(path), score) > longest_strongest:
        longest_strongest = (len(path), score)
    for candidate in connections[conn]:
        if candidate not in path:
            new_connection = candidate[candidate.index(conn) - 1]
            new_score = score + sum(candidate)
            new_path = path | {candidate}
            que.append((new_path, new_score, new_connection))
 
print(max_score)
print(longest_strongest[-1])

import math
 
lines = open('input').read().splitlines()
d = [x.strip().split() for x in lines]
 
 
def v(mem, x):
    try:
        return int(x)
    except ValueError:
        return mem.get(x, 0)
 
 
def is_prime(n):
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n))+1, 2):
        if n % i == 0:
            return False
    return True
 
 
def tick(i):
    ins, a, b = d[i]
    b = v(m, b)
    if ins == 'set':
        m[a] = b
    elif ins == 'sub':
        m[a] = v(m, a) - b
    elif ins == 'mul':
        m[a] = v(m, a) * b
    elif ins == 'jnp':
        if not is_prime(v(m, a)):
            i += b - 1
    elif v(m, a):
        i += b - 1
    return i + 1
 
 
d[8] = 'jnp b 17'.split()
d[9] = 'jnz 1 17'.split()
m, i = {'a': 1}, 0
while 0 <= i < len(d):
    i = tick(i)
print(m['h'])

import math
 
lines = open('input').read().splitlines()
d = [x.strip().split() for x in lines]
 
 
def v(mem, x):
    try:
        return int(x)
    except ValueError:
        return mem.get(x, 0)
 
 
def is_prime(n):
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n))+1, 2):
        if n % i == 0:
            return False
    return True
 
 
def tick(i):
    ins, a, b = d[i]
    b = v(m, b)
    if ins == 'set':
        m[a] = b
    elif ins == 'sub':
        m[a] = v(m, a) - b
    elif ins == 'mul':
        m[a] = v(m, a) * b
    elif ins == 'jnp':
        if not is_prime(v(m, a)):
            i += b - 1
    elif v(m, a):
        i += b - 1
    return i + 1
 
 
m, i, mul = {}, 0, 0
while 0 <= i < len(d):
    if d[i][0] == 'mul':
        mul += 1
    i = tick(i)
print(mul)

def tick(m, cx, cy, dx, dy, dc):
    c = m.get((cx, cy), 0)
    s = c % 4
    dx, dy = (dy, -dx) if s == 0 else (-dy, dx) \
        if s == 2 else (-dx, -dy) if s == 3 else (dx, dy)
    m[(cx, cy)] = c + dc
    return cx + dx, cy + dy, dx, dy
 
 
m, w, h = {}, 0, 0
lines = open('input').read().splitlines()
for y, line in enumerate(lines):
    for x, c in enumerate(line.strip()):
        m[(x, y)] = int(c == '#')*2
        w, h = max(w, x), max(h, y)
 
start = sum(c // 4 + (c % 4) // 2 for c in m.values())
 
ma = dict(m)
dx, dy, cx, cy = 0, -1, w // 2, h // 2
for _ in range(10000000):
    cx, cy, dx, dy = tick(m, cx, cy, dx, dy, 1)
print(sum((c // 4) + ((c % 4) // 2) for c in m.values()) - start)

def tick(m, cx, cy, dx, dy, dc):
    c = m.get((cx, cy), 0)
    s = c % 4
    dx, dy = (dy, -dx) if s == 0 else (-dy, dx) \
        if s == 2 else (-dx, -dy) if s == 3 else (dx, dy)
    m[(cx, cy)] = c + dc
    return cx + dx, cy + dy, dx, dy
 
 
m, w, h = {}, 0, 0
lines = open('input').read().splitlines()
for y, line in enumerate(lines):
    for x, c in enumerate(line.strip()):
        m[(x, y)] = int(c == '#')*2
        w, h = max(w, x), max(h, y)
 
start = sum(c // 4 + (c % 4) // 2 for c in m.values())
 
ma = dict(m)
dx, dy, cx, cy = 0, -1, w // 2, h // 2
for _ in range(10000):
    cx, cy, dx, dy = tick(ma, cx, cy, dx, dy, 2)
print(sum((c // 4) + ((c % 4) // 2) for c in ma.values()) - start)

def parse(x):
    return [[int(c == '#') for c in l] for l in x.split('/')]
 
 
def rot(g):
    for _ in range(4):
        g = list(zip(*g[::-1]))
        yield g
 
 
def key(g):
    return str(min(min(x, x[::-1]) for x in rot(g)))
 
 
def iterate(g):
    s = 2 + len(g) % 2
    return sum([list(zip(*sum(r, [])))
                for r in [[m[key([[c for c in l[x:x+s]]
                                  for l in g[y:y+s]])]
                           for x in range(0, len(g), s)]
                          for y in range(0, len(g), s)]], [])
 
 
m = {}
lines = open('input').read().splitlines()
for line in lines:
    k, r = [parse(x) for x in line.strip().split(' => ')]
    m[key(k)] = r
 
s = parse('.#./..#/###')
 
for _ in range(5):
    s = iterate(s)
print(sum(1 for r in s for c in r if c))
 
for _ in range(18-5):
    s = iterate(s)
print(sum(1 for r in s for c in r if c))

lines = open('input').read().splitlines()
lines = [x.strip() for x in lines]
 
 
def tick(ps):
    for p in ps:
        p['v'] = [sum(x) for x in zip(p['v'], p['a'])]
        p['p'] = [sum(x) for x in zip(p['p'], p['v'])]
 
 
ps = [dict([(y[0], [int(z) for z in y[3:-1].split(',')])
            for y in x.split(', ')]) for x in lines]
r = 0
while r < 50:
    r += 1
    i = 0
    while i < len(ps) - 1:
        for j in range(len(ps)-1, i, -1):
            if ps[i]['p'] == ps[j]['p']:
                r = 0
                del ps[j]
        if r:
            i += 1
        else:
            del ps[i]
            r += 1
    tick(ps)
print(len(ps))

lines = open('input').read().splitlines()
lines = [x.strip() for x in lines]
 
 
def tick(ps):
    for p in ps:
        p['v'] = [sum(x) for x in zip(p['v'], p['a'])]
        p['p'] = [sum(x) for x in zip(p['p'], p['v'])]
 
 
ps = [dict([(y[0], [int(z) for z in y[3:-1].split(',')])
            for y in x.split(', ')]) for x in lines]
val = 0
r = 0
while r < 300:
    r += 1
    tick(ps)
    x = min((sum(abs(x) for x in p['p']), i) for i, p in enumerate(ps))[1]
    if val != x:
        val = x
        r = 0
print(val)

instructions = open('input').read().splitlines()
 
pos = instructions[0].find('|') + 0j
direction = 1j
letters = []
steps = 0
 
 
get_char = lambda pos: instructions[int(pos.imag)][int(pos.real)]
 
def change_direction(direction):
    candidate = direction * 1j
    return candidate if get_char(pos + candidate) != ' ' else direction * -1j
 
 
char = get_char(pos)
while char != ' ':
    steps += 1
    if char.isalpha():
        letters.append(char)
    elif char == '+':
        direction = change_direction(direction)
    pos += direction
    char = get_char(pos)
 
print(''.join(letters))
print(steps)

from collections import defaultdict, deque
 
instructions = open('input').read().splitlines()
interpret = lambda val, reg: reg[val] if val.isalpha() else int(val)
sent_counter = 0
 
 
def solve(registers, which, i=0, first_part=False):
    played = 0
    while i < len(instructions):
        c = instructions[i].split()
        v = interpret(c[-1], registers)
        if c[0] == 'set':
            registers[c[1]] = v
        elif c[0] == 'add':
            registers[c[1]] += v
        elif c[0] == 'mul':
            registers[c[1]] *= v
        elif c[0] == 'mod':
            registers[c[1]] %= v
        elif c[0] == 'jgz':
            w = interpret(c[1], registers)
            if w > 0:
                i += v
                continue
        elif c[0] == 'snd':
            if first_part:
                played = v
 
            elif which == 'x':
                y.append(v)
            else:
                global sent_counter
                sent_counter += 1
                x.append(v)
        elif c[0] == 'rcv':
            if first_part:
                if v != 0:
                    return played
 
            elif which == 'x' and x:
                registers[c[-1]] = x.popleft()
            elif which == 'y' and y:
                registers[c[-1]] = y.popleft()
            else:
                return i
        i += 1
 
 
print(solve(defaultdict(int), 'x', first_part=True))
 
registers_x = defaultdict(int)
registers_y = defaultdict(int)
registers_y['p'] = 1
 
x = deque([])
y = deque([])
 
x_i = solve(registers_x, 'x')
y_i = solve(registers_y, 'y')
while x or y:
    x_i = solve(registers_x, 'x', x_i)
    y_i = solve(registers_y, 'y', y_i)
 
print(sent_counter)

from collections import deque
 
def spin(insertions):
    spinlock = deque([0])
    for i in range(1, insertions+1):
        spinlock.rotate(-puzzle)
        spinlock.append(i)
    return spinlock
 
 
puzzle = 337
ans = spin(2017)
print(ans[0])
 
ans = spin(50_000_000)
print(ans[ans.index(0) + 1])

from collections import deque
 
programs = 'abcdefghijklmnop'
 
with open('input') as f:
    instructions = f.readline().split(',')
 
 
def clean_up(instructions):
    result = []
    for instr in instructions:
        first = instr[0]
        if first == 's':
            result.append((first, int(instr[1:])))
        elif first == 'x':
            a, b = map(int, instr[1:].split('/'))
            result.append((first, a, b))
        else:
            result.append((first, instr[1], instr[-1]))
    return result
 
 
def dance(dancers):
    dancers = deque(dancers)
    for first, *rest in cleaned:
        if first == 's':
            dancers.rotate(rest[0])
        elif first == 'x':
            a, b = rest
            dancers[a], dancers[b] = dancers[b], dancers[a]
        elif first == 'p':
            x, y = rest
            a = dancers.index(x)
            b = dancers.index(y)
            dancers[a], dancers[b] = y, x
    return ''.join(dancers)
 
 
def long_dance(dancers, iterations=1_000_000_000):
    seen = [dancers]
    for i in range(1, iterations):
        dancers = dance(dancers)
        if dancers == programs:
            return seen[iterations % i]
        seen.append(dancers)
 
 
cleaned = clean_up(instructions)
print(dance(programs))
print(long_dance(programs))

data = open('input').read().splitlines()
data = [line.split(' ') for line in data]
a = int(data[0][4])
b = int(data[1][4])
 
factors = {'a': 16807, 'b': 48271}
divisor = 2147483647
 
def generator(value, factor, multi=1):
    while True:
        value = value * factor % divisor
        if value % multi == 0:
            yield value & 0xFFFF
 
 
gen_a = generator(a, factors['a'])
gen_b = generator(b, factors['b'])
ans = sum(next(gen_a) == next(gen_b) for _ in range(40000000))
print(ans)
 
gen_a = generator(a, factors['a'], 4)
gen_b = generator(b, factors['b'], 8)
ans = sum(next(gen_a) == next(gen_b) for _ in range(5000000))
print(ans)

from collections import deque
from functools import reduce
from operator import xor
 
def knot_logic(sizes, iterations=64):
    circle = deque(range(256))
    skip = 0
    for _ in range(iterations):
        for group_size in sizes:
            knot = [circle.popleft() for _ in range(group_size)]
            circle += reversed(knot)
            circle.rotate(-skip)
            skip += 1
    unwind = iterations * sum(sizes) + skip * (skip-1) // 2
    circle.rotate(unwind)
    return list(circle)
 
 
def knot_hashing(word):
    ascii_sizes = [ord(c) for c in word] + [17, 31, 73, 47, 23]
    numbers = knot_logic(ascii_sizes)
    SIZE = 256
    BLOCK_SIZE = 16
    block = lambda i: numbers[i*BLOCK_SIZE : (i+1)*BLOCK_SIZE]
    dense = [reduce(xor, block(i)) for i in range(SIZE // BLOCK_SIZE)]
    return ''.join(f'{n:02x}' for n in dense)
 
 
instructions = 'stpzcrnm'
maze = set()
for row in range(128):
    word = f'{instructions}-{row}'
    hex_hash = knot_hashing(word)
    bin_hash = f'{int(hex_hash, 16):0128b}'
    for i, n in enumerate(bin_hash):
        if n == '1':
            maze.add((row, i))
print(len(maze))
 
def dfs(start):
    stack = [start]
    while stack:
        (x, y) = stack.pop()
        for dx, dy in DELTAS:
            candidate = x+dx, y+dy
            if candidate in maze:
                stack.append(candidate)
                maze.remove(candidate)
 
 
DELTAS = ((1, 0), (-1, 0), (0, 1), (0, -1))
regions = 0
while maze:
    dfs(maze.pop())
    regions += 1
print(regions)

import itertools
 
data = open('input').read().splitlines()
lines = [line.split(': ') for line in data]
heights = {int(pos): int(height) for pos, height in lines}
 
def scanner(height, time):
    offset = time % ((height - 1) * 2)
 
    return 2 * (height - 1) - offset if offset > height - 1 else offset
 
print(sum(pos * heights[pos] for pos in heights if scanner(heights[pos], pos) == 0))
 
print(next(wait for wait in itertools.count() if not any(scanner(heights[pos], wait + pos) == 0 for pos in heights)))

from collections import deque
 
data = open('input').readlines()
 
graph = {}
 
for line in data:
    pipe, neighbours = line.split(' <-> ')
    pipe = int(pipe)
    neighbours = [int(n) for n in neighbours.split(', ')]
    graph[pipe] = neighbours
 
 
def bfs(starting_point):
    connections = set()
    que = deque([starting_point])
    while que:
        current = que.popleft()
        connections.add(current)
        for node in graph[current]:
            if node not in connections:
                que.append(node)
    return connections
 
 
seen = bfs(0)
islands = 1
first_island_size = len(seen)
 
for pipe in graph:
    if pipe not in seen:
        pipe_island = bfs(pipe)
        islands += 1
        seen |= pipe_island
 
print(first_island_size)
print(islands)

data = open('input').read().split(',')
 
to_cube = {
    'n':  (0, 1, -1),
    'nw': (-1, 1, 0),
    'sw': (-1, 0, 1),
    's':  (0, -1, 1),
    'se': (1, -1, 0),
    'ne': (1, 0, -1),
}
position = (0, 0, 0)
 
 
def move(a, b):
    b = to_cube[b]
    return (a[0]+b[0], a[1]+b[1], a[2]+b[2])
 
def distance_to_origin(a):
    return sum(map(abs, a)) // 2
 
 
distances = set()
 
for direction in data:
    position = move(position, direction)
    dist = distance_to_origin(position)
    distances.add(dist)
 
print(distance_to_origin(position))
print(max(distances))

from collections import deque
from functools import reduce
from operator import xor
 
 
def knot_logic(sizes, iterations=64):
    circle = deque(range(256))
    skip = 0
    for _ in range(iterations):
        for group_size in sizes:
            knot = [circle.popleft() for _ in range(group_size)]
            circle += reversed(knot)
            circle.rotate(-skip)
            skip += 1
    unwind = iterations * sum(sizes) + skip * (skip-1) // 2
    circle.rotate(unwind)
    return list(circle)
 
 
def knot_hashing(word):
    ascii_sizes = [ord(c) for c in word] + [17, 31, 73, 47, 23]
    numbers = knot_logic(ascii_sizes)
    SIZE = 256
    BLOCK_SIZE = 16
    block = lambda i: numbers[i*BLOCK_SIZE : (i+1)*BLOCK_SIZE]
    dense = [reduce(xor, block(i)) for i in range(SIZE // BLOCK_SIZE)]
    return ''.join(f'{n:02x}' for n in dense)
 
 
data = open('input').read().strip()
int_sizes = [int(n) for n in data.split(',')]
 
first_hash = knot_logic(int_sizes, iterations=1)
first = first_hash[0] * first_hash[1]
print(first)
 
second = knot_hashing(data)
print(second)

data = open('input').read().strip()
garbage_cleaned = 0
nesting_level = 0
score = 0
i = 0
while i < len(data):
    if data[i] == '<':
        i += 1
        while data[i] != '>':
            if data[i] == '!':
                i += 1
            else:
                garbage_cleaned += 1
            i += 1
    elif data[i] == '{':
        nesting_level += 1
    elif data[i] == '}':
        score += nesting_level
        nesting_level -= 1
    i += 1
print(score)
print(garbage_cleaned)

# dict and defaultdict are almost the same except for the fact that defaultdict never raises a KeyError.
# defaultdict provides a default value for keys that do not exist.
# even when just calling a key in an empty defaultdict, the key will be added and a default value is generated.
# when the int class is passed as the default_factory argument, a defaultdict is created with default value as zero.
 
from collections import defaultdict
from operator import lt, gt, eq, ne, le, ge
 
data = open('input').read().splitlines()
 
registers = defaultdict(int)
operators = {
    '<': lt,
    '>': gt,
    '==': eq,
    '!=': ne,
    '<=': le,
    '>=': ge,
}
maximum = 0
 
for line in data:
    register, instruction, amount, _, cond_reg, operator, value = line.split()
    directon = 1 if instruction == 'inc' else -1
    if operators[operator](registers[cond_reg], int(value)):   # example: if gt(hx,-10):
        registers[register] += directon * int(amount)
        maximum = max(registers[register], maximum)
 
print(max(registers.values()))
print(maximum)

from collections import Counter
import re
data = open('input').read().splitlines()
weights = {}
children = {}
for line in data:
    node, weight, *kids = re.findall(r"(\w+)", line)
    weights[node] = int(weight)
    children[node] = kids
#print(weights)
#print(children)
 
all_nodes = set(weights)
all_kids = {kid for kids in children.values() for kid in kids}
root = (all_nodes - all_kids).pop()
print(root)
 
def find_offsprings_weights(node):
    kids_weights = [find_offsprings_weights(kid) for kid in children[node]]
    unique_weights = Counter(kids_weights).most_common()
    if len(unique_weights) == 2:
        (correct_total, _), (wrong_total, _) = unique_weights
        difference = correct_total - wrong_total
        wrong_node = children[node][kids_weights.index(wrong_total)]
        wrong_weight = weights[wrong_node]
        print(wrong_weight + difference)
        return weights[node] + sum(kids_weights) + difference
    return weights[node] + sum(kids_weights)
 
find_offsprings_weights(root)

from collections import OrderedDict
 
data = open('input').read().split()
data = list(map(int, data))
 
size = len(data) # = 16 registers
seen = OrderedDict()
 
# A tuple is a collection which is ordered (not to be confused with sorted) and unchangeable.
# A set is a collection which is sorted (order is not preserved) and contains only unique elements.
 
# Does Python have an ordered set?
# No, but you can use collections.OrderedDict with just keys (and values as None)
 
# Using while ... not in ... we can check if/when a collection pattern reoccurs.
 
while tuple(data) not in seen:
    seen[tuple(data)] = None
    max_value = max(data)
    max_index = data.index(max_value)
    data[max_index] = 0
    to_every, to_some = divmod(max_value, size)
    data = [d + to_every for d in data]
    for i in range(to_some):
        data[(max_index + i+1) % size] += 1
print(len(seen))
# Lookup in the OrderedDict keys, the index of when we first encountered the duplicate value.
loop_start = list(seen.keys()).index(tuple(data))
print(len(seen) - loop_start)

data = open('input').read().splitlines()
data = list(map(int, data))
ptr = 0
steps = 0
while ptr < len(data):
    offset = data[ptr]
    if offset >= 3:
        data[ptr] -= 1
    else:
        data[ptr] += 1
    ptr += offset
    steps += 1
print(steps)

data = open('input').read().splitlines()
data = list(map(int, data))
ptr = 0
steps = 0
while ptr < len(data):
    offset = data[ptr]
    data[ptr] += 1
    ptr += offset
    steps += 1
print(steps)

data = open('input').read().splitlines()
valid = 0
words = []
for d in data:
    words = d.split()
    words = [''.join(sorted(word)) for word in words]
    uniq = set(words)
    if len(words) == len(uniq):
        valid+=1
print(valid)

data = open('input').read().splitlines()
valid = 0
words = []
for d in data:
    words = d.split()
    uniq = set(words)
    if len(words) == len(uniq):
        valid+=1
print(valid)

data = open('input').read().split()
number = int(data[0])
 
grid = {(0, 0): 1}
neighbours = lambda x, y: [(x+1, y), (x, y+1), (x+1, y+1), (x-1, y-1),
                           (x-1, y), (x, y-1), (x+1, y-1), (x-1, y+1)]
 
 
def set_value(point):
    grid[point] = sum(grid.get(neighbour, 0) for neighbour in neighbours(*point))
    return grid[point]
 
 
def iterate_through_spiral(ring=0):
    while True:
        ring += 1
        for y in range(-ring + 1, ring): yield set_value((ring,  y))
        for x in range(ring, -ring, -1): yield set_value((x,  ring))
        for y in range(ring, -ring, -1): yield set_value((-ring, y))
        for x in range(-ring, ring + 1): yield set_value((x, -ring))
 
 
for value in iterate_through_spiral():
    if value > number:
        print(value)
        break

data = open('input').read().split()
number = int(data[0])
# double-asterisks (**) in Python is a 
# 'to the power of' exponentiation operator
# example: 2 ** 6 = 64
spiral_corner = int(number ** 0.5)
remaining_steps = number % spiral_corner ** 2
side_length = spiral_corner + 1
towards_middle = remaining_steps % (side_length // 2)
print(side_length - towards_middle)

data = open('input').read().splitlines()
delta = 0
nums = []
for line in data:
    nums = line.split('\t')
    nums = list(map(int, nums))
    for a in nums:
        for b in nums:
            if a % b == 0 and a != b:
                delta += a // b
print(delta)

data = open('input').read().splitlines()
delta = 0
nums = []
for line in data:
    nums = line.split('\t')
    nums = list(map(int, nums))
    delta += max(nums) - min(nums)
print(delta)

data = open('input').read().strip()
data = list(map(int, data))
 
def solve(digits, second_part=False):
    jump = 1 if not second_part else len(digits)//2
    return sum(n for i, n in enumerate(digits) if n == digits[i-jump])
 
print(solve(data))
print(solve(data, 'part 2'))

data = open('input').read().strip()
data = list(map(int, data))
count = 0
offset = len(data)//2
for i, n in enumerate(data):
    if n == data[i - offset]:
        count += data[i]
print(count)
# Single slash(/) in python is used to perform classic division
# whereas double slash in python (//) is used to perform floor division.
# Floor division means rounding down to the nearest whole number.

data = open('input').read().strip()
data = list(map(int, data))
count = 0
for i, n in enumerate(data):
    if n == data[i-1]:
        count += data[i]
print(count)