Spaces:
Running
Running
File size: 2,157 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 |
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() |