Spaces:
Running
Running
| from collections import defaultdict | |
| import copy | |
| def parse_input(filename): | |
| rules = [] | |
| updates = [] | |
| with open(filename) as f: | |
| lines = f.read().strip().split('\n') | |
| # Find the empty line that separates rules and updates | |
| separator = lines.index('') | |
| # Parse rules | |
| for line in lines[:separator]: | |
| x, y = map(int, line.split('|')) | |
| rules.append((x, y)) | |
| # Parse updates | |
| for line in lines[separator+1:]: | |
| update = list(map(int, line.split(','))) | |
| updates.append(update) | |
| return rules, updates | |
| def build_graph(rules): | |
| # Build adjacency list representation | |
| graph = defaultdict(list) | |
| for x, y in rules: | |
| graph[x].append(y) | |
| return graph | |
| def is_valid_order(nums, graph): | |
| # Check if current order satisfies all rules | |
| num_set = set(nums) | |
| for i, num in enumerate(nums): | |
| for next_num in graph[num]: | |
| if next_num in num_set: | |
| # If there's a rule num->next_num, check if next_num appears after num | |
| next_pos = nums.index(next_num) | |
| if next_pos < i: | |
| return False | |
| return True | |
| def topological_sort(nums, graph): | |
| # Create a graph only with the numbers in the update | |
| num_set = set(nums) | |
| local_graph = defaultdict(list) | |
| in_degree = defaultdict(int) | |
| # Initialize in-degree for all numbers | |
| for num in nums: | |
| in_degree[num] = 0 | |
| # Build local graph and calculate in-degrees | |
| for num in nums: | |
| for next_num in graph[num]: | |
| if next_num in num_set: | |
| local_graph[num].append(next_num) | |
| in_degree[next_num] += 1 | |
| # Find all nodes with in-degree 0 | |
| queue = [num for num in nums if in_degree[num] == 0] | |
| result = [] | |
| while queue: | |
| current = queue.pop(0) | |
| result.append(current) | |
| for next_num in local_graph[current]: | |
| in_degree[next_num] -= 1 | |
| if in_degree[next_num] == 0: | |
| queue.append(next_num) | |
| return result | |
| def get_middle_number(nums): | |
| return nums[len(nums)//2] | |
| # Read and parse input | |
| rules, updates = parse_input("input.txt") | |
| graph = build_graph(rules) | |
| # Part 1: Sum middle numbers of correctly ordered updates | |
| valid_sum = 0 | |
| invalid_updates = [] | |
| for update in updates: | |
| if is_valid_order(update, graph): | |
| valid_sum += get_middle_number(update) | |
| else: | |
| invalid_updates.append(update) | |
| print(str(valid_sum)) | |
| # Part 2: Sum middle numbers of corrected invalid updates | |
| invalid_sum = 0 | |
| for update in invalid_updates: | |
| sorted_update = topological_sort(update, graph) | |
| invalid_sum += get_middle_number(sorted_update) | |
| print(str(invalid_sum)) |