Inlägg

lines = open('input20.txt', 'rt').read().split('\n')

module_kind = {}
module_targets = {}

for l in lines:
    a, b = l.split(' -> ')
    targets = b.split(', ')
    if a == 'broadcaster':
        kind, name = 'b', a
    else:
        kind, name = a[0], a[1:]
    module_kind[name] = kind
    module_targets[name] = targets

def get_initial_memory():
    memory = {}

    for name, kind in module_kind.items():
        if kind == '%':
            memory[name] = 0
        elif kind == '&':
            memory[name] = {}

    for name, targets in module_targets.items():
        for target in targets:
            kind = module_kind.get(target)
            if kind == '&':
                memory[target][name] = 0

    return memory

def process_pulses(pulses, memory):
    while pulses:
        sender, level, name = pulses.pop(0)
        kind = module_kind.get(name)
        targets = module_targets.get(name)
        if kind == 'b':
            for target in targets:
                pulses.append((name, level, target))
        elif kind == '%':
            if level == 0:
                level = memory.get(name, 0) ^ 1
                memory[name] = level
                for target in targets:
                    pulses.append((name, level, target))
        elif kind == '&':
            if level == 1 and 'rx' in targets:
                return True
            mem = memory.get(name, {})
            mem[sender] = level
            level = 0 if all(x == 1 for x in mem.values()) else 1
            for target in targets:
                pulses.append((name, level, target))
    return False

prod = 1

for n in module_targets['broadcaster']:
    memory = get_initial_memory()
    steps = 0
    while True:
        steps += 1
        pulses = [('broadcaster', 0, n)]
        if process_pulses(pulses, memory):
            prod *= steps
            break

print(prod)

lines = open('input19.txt', 'rt').read().split('\n')

def parse_rules_parts(lines):
    LETTER_TO_INDEX = {'x': 0, 'm': 1, 'a': 2, 's': 3}
    rules = {}
    parts = []
    for line in lines:
        if line == '':
            pass
        elif line[0] != '{':
            pos = line.find('{')
            name = line[:pos]
            xs = line[pos+1:-1].split(',')
            rule = []
            for x in xs:
                pos = x.find(':')
                if pos != -1:
                    clause = (LETTER_TO_INDEX[x[0]], x[1], int(x[2:pos]), x[pos+1:])
                else:
                    clause = (0, '', 0, x)
                rule.append(clause)
            rules[name] = rule
        else:
            xs = line[1:-1].split(',')
            xs = tuple(int(x.split('=')[1]) for x in xs)
            parts.append(xs)
    return rules, parts

def evaluate(rule, limits, queues_to_evaluate, accepted):
    for clause in rule:
        index, comparison, value, target = clause
        limit_min, limit_max = limits[index]
        if comparison == '<':
            match_min, match_max = limit_min, value-1
            keep_min, keep_max = value, limit_max
        elif comparison == '>':
            match_min, match_max = value+1, limit_max
            keep_min, keep_max = limit_min, value
        else:
            match_min, match_max = limit_min, limit_max
            keep_min, keep_max = 1, 0

        if match_min <= match_max:
            match_limits = tuple(((match_min, match_max) if i == index else p for i, p in enumerate(limits)))
            if target == 'A':
                accepted.append(match_limits)
            elif target != 'R':
                queues_to_evaluate.append((target, match_limits))

        if keep_min <= keep_max:
            limits = tuple(((keep_min, keep_max) if i == index else p for i, p in enumerate(limits)))
        else:
            break

rules, _ = parse_rules_parts(lines)
queues_to_evaluate = [('in', ((1, 4000), (1, 4000), (1, 4000), (1, 4000)))]
accepted = []

while queues_to_evaluate:
    queue_name, limits = queues_to_evaluate.pop()
    rule = rules[queue_name]
    evaluate(rule, limits, queues_to_evaluate, accepted)

res = 0
for limits in accepted:
    elements = 1
    for limit_min, limit_max in limits:
        elements *= limit_max - limit_min + 1
    res += elements
print(res)

lines = open('input18.txt', 'rt').read().split('\n')

def get_instructions_part1(lines):
    directions = {'R': 0, 'D': 1, 'L': 2, 'U': 3}
    instructions = []
    for l in lines:
        dir, length, _ = l.split()
        dir = directions[dir]
        length = int(length)
        instructions.append((dir, length))
    return instructions

def get_instructions_part2(lines):
    instructions = []
    for l in lines:
        _, _, instr = l.split()
        length = int(instr[2:-2], 16)
        dir = int(instr[-2])
        instructions.append((dir, length))
    return instructions

def generate_vectors(instructions):
    offsets = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    vectors = []

    x, y = 0, 0
    prev_dir_outline = (instructions[-1][0] + 3) & 3

    for dir, length in instructions:
        dir_outline = (dir + 3) & 3

        dx1, dy1 = offsets[prev_dir_outline]
        dx2, dy2 = offsets[dir_outline]
        outline_x = x + (dx1 + dx2) * 0.5
        outline_y = y + (dy1 + dy2) * 0.5

        vectors.append((outline_x, outline_y))

        dx, dy = offsets[dir]
        x += dx * length
        y += dy * length

        prev_dir_outline = dir_outline

    return vectors

def inside_triangle(v0, v1, v2, v):
    tr = [v0, v1, v2]
    for i in range(3):
        vo = tr[i]
        vn = tr[(i + 1) % 3]
        e = (vn[0] - vo[0], vn[1] - vo[1])
        w = (v[0] - vo[0], v[1] - vo[1])
        cross = e[0] * w[1] - e[1] * w[0]
        if cross < 0:
            return False
    return True

def correctly_winded_triangle(v0, v1, v2):
    e1 = (v1[0] - v0[0], v1[1] - v0[1])
    e2 = (v2[0] - v1[0], v2[1] - v1[1])
    cross = e1[0] * e2[1] - e1[1] * e2[0]
    return cross >= 0

def triangulize(vectors):
    triangles = []

    while len(vectors) > 3:
        n = len(vectors)
        for i in range(n):
            vm1 = vectors[(i - 1) % n]
            v0 = vectors[i]
            v1 = vectors[(i + 1) % n]

            if not correctly_winded_triangle(vm1, v0, v1):
                continue

            is_ear = True
            for j in range(n - 3):
                v = vectors[(i + 2 + j) % n]
                if inside_triangle(vm1, v0, v1, v):
                    is_ear = False
                    break

            if is_ear:
                triangles.append((vm1, v0, v1))
                del vectors[i]
                break

    triangles.append(tuple(vectors))
    return triangles

def calculate_total_area(triangles):
    total_area = 0
    for v0, v1, v2 in triangles:
        x0, y0 = v0
        x1, y1 = v1
        x2, y2 = v2
        area = abs(x0 * (y1 - y2) + x1 * (y2 - y0) + x2 * (y0 - y1)) / 2
        total_area += area
    return total_area

instructions = get_instructions_part2(lines)
vectors = generate_vectors(instructions)
triangles = triangulize(vectors)
total_area = calculate_total_area(triangles)
print(total_area)

lines = open('input17.txt', 'rt').read().split('\n')

H = len(lines)
W = len(lines[0])

RIGHT = 0
DOWN = 1
LEFT = 2
UP = 3

x_offs = [1, 0, -1, 0]
y_offs = [0, 1, 0, -1]

start = (0, 0, RIGHT, 0)

import heapq

dist_heap = [(0, start)]
dist_dict = {start: 0}

found = {}

part_no = 2

def allowed_dir(dir, dir_count, next_dir):
    if part_no == 1:
        if next_dir == dir:
            if dir_count == 3:
                return False
        elif next_dir == ((dir + 2) & 3):
            return False
        return True
    else:
        if next_dir == dir:
            if dir_count == 10:
                return False
        elif next_dir == ((dir + 2) & 3):
            return False
        elif dir_count < 4:
            return False
        return True

while dist_heap:
    d, state = heapq.heappop(dist_heap)
    del dist_dict[state]

    found[state] = d

    y, x, dir, dir_count = state
    if y == H-1 and x == W-1:
        if part_no == 1 or dir_count >= 4:
            print(d)
            break

    for next_dir in range(4):
        next_y = y + y_offs[next_dir]
        next_x = x + x_offs[next_dir]
        if next_y < 0 or next_y >= H or next_x < 0 or next_x >= W:
            continue

        if not allowed_dir(dir, dir_count, next_dir):
            continue

        next_dir_count = 1 + (dir_count if next_dir == dir else 0)

        next_state = (next_y, next_x, next_dir, next_dir_count)
        if next_state in found:
            continue

        cost = int(lines[next_y][next_x])
        next_d = d + cost

        prev_d = dist_dict.get(next_state)

        add_state = prev_d is None or next_d < prev_d

        if prev_d is not None and add_state:
            dist_heap.remove((prev_d, next_state))
            heapq.heapify(dist_heap)

        if add_state:
            heapq.heappush(dist_heap, (next_d, next_state))
            dist_dict[next_state] = next_d

lines = open('input16.txt', 'rt').read().split('\n')

H = len(lines)
W = len(lines[0])

L2R = 1
T2B = 2
R2L = 4
B2T = 8

TURN_SLASH = {L2R: B2T, T2B: R2L, R2L: T2B, B2T: L2R}
TURN_BACKSLASH = {L2R: T2B, T2B: L2R, R2L: B2T, B2T: R2L}

def follow_beam(y, x, dir):
    while True:
        if y < 0 or y >= H or x < 0 or x >= W:
            return

        if energized[y][x] & dir:
            return

        energized[y][x] |= dir

        c = lines[y][x]

        if c == '/':
            dir = TURN_SLASH[dir]
        elif c == '\\':
            dir = TURN_BACKSLASH[dir]
        elif c == '|' and dir in (L2R, R2L):
            stack.append((y-1, x, B2T))
            dir = T2B
        elif c == '-' and dir in (T2B, B2T):
            stack.append((y, x-1, R2L))
            dir = L2R

        if dir == L2R:
            x += 1
        elif dir == T2B:
            y += 1
        elif dir == R2L:
            x -= 1
        elif dir == B2T:
            y -= 1

energized = [[0] * W for _ in range(H)]
stack = []

max_tiles_energized = 0

for start_dir in [L2R, T2B, R2L, B2T]:
    n = H if start_dir in (L2R, R2L) else W
    for i in range(n):
        energized = [[0] * W for _ in range(H)]

        if start_dir == L2R:
            stack = [(i, 0, start_dir)]
        elif start_dir == T2B:
            stack = [(0, i, start_dir)]
        elif start_dir == R2L:
            stack = [(i, W-1, start_dir)]
        elif start_dir == B2T:
            stack = [(H-1, i, start_dir)]

        while stack:
            y, x, dir = stack.pop(0)
            follow_beam(y, x, dir)

        tiles_energized = sum(1 if x else 0 for row in energized for x in row)

        if max_tiles_energized < tiles_energized:
            max_tiles_energized = tiles_energized

print(max_tiles_energized)

commands = open('input15.txt', 'rt').read().split(',')

def hash_algo(s):
    v = 0
    for c in s:
        v = ((v + ord(c)) * 17) & 255
    return v

boxes = [[] for _ in range(256)]

for command in commands:
    pos = command.find('=')
    if pos != -1:
        label, power = command[:pos], int(command[pos+1:])
        box = boxes[hash_algo(label)]
        in_box = False
        for i, (lab, _) in enumerate(box):
            if lab == label:
                box[i] = (label, power)
                in_box = True
                break
        if not in_box:
            box.append((label, power))
    else:
        label = command[:-1]
        box = boxes[hash_algo(label)]
        for i, (lab, _) in enumerate(box):
            if lab == label:
                del box[i]
                break

res = 0
for i, box in enumerate(boxes):
    for j, (_, power) in enumerate(box):
        res += (i+1) * (j+1) * power
print(res)

lines = open('input14.txt', 'rt').read().split('\n')

pattern0 = tuple(tuple(l) for l in lines)

H = len(pattern0)
W = len(pattern0[0])

def tilt_north(pattern):
    mutable_pattern = [list(l) for l in pattern]
    for y in range(1, H):
        for x in range(W):
            if mutable_pattern[y][x] == 'O':
                new_y = y
                for y2 in range(y-1, -1, -1):
                    if mutable_pattern[y2][x] == '.':
                        new_y = y2
                    else:
                        break
                if new_y != y:
                    mutable_pattern[y][x] = '.'
                    mutable_pattern[new_y][x] = 'O'
    return tuple(tuple(l) for l in mutable_pattern)

def rotate_90(pattern):
    return tuple(tuple(pattern[H - 1 - x][y] for x in range(W)) for y in range(H))

period = 0
offset = 0
patterns = {}
pattern = pattern0

N = 1000000000

for spins in range(1, N):
    for _ in range(4):
        pattern = tilt_north(pattern)
        pattern = rotate_90(pattern)

    last_occurrence = patterns.get(pattern)
    if last_occurrence is not None:
        period = spins - last_occurrence
        offset = spins
        break
    patterns[pattern] = spins

patterns = ((i, t) for t, i in patterns.items())
patterns = [t for _, t in sorted(patterns)]
patterns = patterns[-period:]

def calculate_load(pattern):
    return sum(sum(c == 'O' for c in row) * (H - y) for y, row in enumerate(pattern))

pattern_index = (N - offset) % period
pattern = patterns[pattern_index]
print(calculate_load(pattern))

lines = open('input12.txt', 'rt').read().split('\n')

combinations_cache = {}

def combinations_cache_lookup(pos, group_index, group_len):
    v = combinations_cache.get((pos, group_index, group_len))
    if v is None:
        v = combinations(pos, group_index, group_len)
        combinations_cache[(pos, group_index, group_len)] = v
    return v

def combinations(pos, group_index, group_len):
    if pos == len(row):
        if group_len == 0:
            return 1 if group_index == len(groups) else 0
        else:
            return 1 if group_index == len(groups) - 1 and groups[group_index] == group_len else 0

    valid = 0

    if row[pos] == '.' or row[pos] == '?':
        if group_len == 0:
            valid += combinations_cache_lookup(pos+1, group_index, 0)
        elif groups[group_index] == group_len:
            valid += combinations_cache_lookup(pos+1, group_index+1, 0)

    if row[pos] == '#' or row[pos] == '?':
        if group_index < len(groups) and group_len < groups[group_index]:
            valid += combinations_cache_lookup(pos+1, group_index, group_len+1)

    return valid

res = 0

for l in lines:
    row, groups = l.split()
    groups = [int(x) for x in groups.split(',')]

    row = '?'.join([row] * 5)
    groups = groups * 5

    combinations_cache.clear()
    valid = combinations(0, 0, 0)
    res += valid

print(res)