aoc2024day5.py

# === Parsing ===

from collections import defaultdict

illegal_before = defaultdict(set)
print_orders = []
with open("input.txt", "r") as f:
    for line in iter(f.readline, "\n"):
        key, value = line.split("|")
        illegal_before[int(key)].add(int(value))

    for line in f:
        print_orders.append([int(num) for num in line.split(",")])

print(illegal_before)
print(print_orders)


# === Part 1 ===


def is_valid(order):
    prefix_set = set()
    for num in order:
        if illegal_before[num] & prefix_set:
            return False
        prefix_set.add(num)
    return True


accumulator = 0
for order in print_orders:
    if is_valid(order):
        accumulator += order[len(order) // 2]

print(accumulator)


# === Part 2 ===

invalid_orders = [order for order in print_orders if not is_valid(order)]

accumulator = 0
for order in invalid_orders:
    ptr = 0
    prefix_set = set()
    while ptr < len(order):
        to_move = order[ptr]
        invalid_values = illegal_before[to_move] & prefix_set
        if invalid_values:
            first_invalid_idx = min(order.index(value) for value in invalid_values)
            order.pop(ptr)
            order.insert(first_invalid_idx, to_move)

        prefix_set.add(to_move)
        ptr += 1

    accumulator += order[len(order) // 2]

print(accumulator)