day05/solution_gpt-4o.py

from collections import defaultdict, deque

def parse_input(file):
    with open(file, 'r') as f:
        lines = f.read().strip().split('\n')
    
    # Separate rules and updates
    rules = []
    updates = []
    is_update_section = False
    
    for line in lines:
        if '|' in line:
            rules.append(tuple(map(int, line.split('|'))))
        else:
            updates.append(list(map(int, line.split(','))))
    
    return rules, updates

def is_correct_order(update, rules):
    # Create a map of page to its index in the update
    index_map = {page: i for i, page in enumerate(update)}
    
    for x, y in rules:
        if x in index_map and y in index_map:
            if index_map[x] > index_map[y]:
                return False
    return True

def find_middle_page(update):
    n = len(update)
    return update[n // 2]

def reorder_update(update, rules):
    # Create a graph and in-degree count for topological sorting
    graph = defaultdict(list)
    in_degree = defaultdict(int)
    
    # Only consider rules that involve pages in the current update
    update_set = set(update)
    for x, y in rules:
        if x in update_set and y in update_set:
            graph[x].append(y)
            in_degree[y] += 1
    
    # Initialize queue with nodes having zero in-degree
    queue = deque([page for page in update if in_degree[page] == 0])
    sorted_update = []
    
    while queue:
        node = queue.popleft()
        sorted_update.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return sorted_update

def main():
    file = "input.txt"
    rules, updates = parse_input(file)
    
    correct_order_sum = 0
    incorrect_order_sum = 0
    
    for update in updates:
        if is_correct_order(update, rules):
            correct_order_sum += find_middle_page(update)
        else:
            reordered_update = reorder_update(update, rules)
            incorrect_order_sum += find_middle_page(reordered_update)
    
    print(correct_order_sum)
    print(incorrect_order_sum)

main()