Spaces:
Running
Running
File size: 2,757 Bytes
a4da721 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
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)) |