93 lines
2.3 KiB
Python
93 lines
2.3 KiB
Python
|
#!/usr/bin/env python
|
||
|
|
# -*- encoding: utf-8; py-indent-offset: 4 -*-
|
||
|
|
|
||
|
|
# Author: Sebastian Mark
|
||
|
|
# CC-BY-SA (https://creativecommons.org/licenses/by-sa/4.0/deed.de)
|
||
|
|
|
||
|
|
# pylint: disable=missing-module-docstring,missing-function-docstring,consider-using-f-string
|
||
|
|
|
||
|
|
|
||
|
|
from collections import defaultdict
|
||
|
|
|
||
|
|
|
||
|
|
def readinput() -> list:
|
||
|
|
with open("input", "r", encoding="utf-8") as file:
|
||
|
|
lines = file.readlines()
|
||
|
|
return lines
|
||
|
|
|
||
|
|
|
||
|
|
def get_orders_and_updates() -> tuple[list, list]:
|
||
|
|
lines = readinput()
|
||
|
|
|
||
|
|
sep = lines.index("\n") # newline in input
|
||
|
|
|
||
|
|
rules = defaultdict(set)
|
||
|
|
for line in lines[:sep]:
|
||
|
|
a, b = map(int, line.split("|"))
|
||
|
|
rules[a].add(b)
|
||
|
|
|
||
|
|
updates = []
|
||
|
|
for line in lines[sep + 1 :]:
|
||
|
|
updates.append(list(map(int, line.split(","))))
|
||
|
|
|
||
|
|
return (rules, updates)
|
||
|
|
|
||
|
|
|
||
|
|
def validate_rules(update: list, rules: list) -> bool:
|
||
|
|
for i in range(len(update) - 1):
|
||
|
|
next_page = update[i + 1]
|
||
|
|
page = update[i]
|
||
|
|
if next_page not in rules[page]:
|
||
|
|
return False
|
||
|
|
return True
|
||
|
|
|
||
|
|
|
||
|
|
def get_middle_number(update: list) -> int:
|
||
|
|
return update[int(len(update) / 2)]
|
||
|
|
|
||
|
|
|
||
|
|
def fix_with_rules(update: list, rules: list) -> list:
|
||
|
|
# this block is inspired by:
|
||
|
|
# https://github.com/nitekat1124/advent-of-code-2024/blob/main/solutions/day05.py
|
||
|
|
|
||
|
|
# filter only the rules for the pages in the current update
|
||
|
|
filtered_rules = defaultdict(set)
|
||
|
|
for i in update:
|
||
|
|
new_rules = []
|
||
|
|
for x in rules[i]:
|
||
|
|
if x in update:
|
||
|
|
new_rules.append(x)
|
||
|
|
filtered_rules[i] = new_rules
|
||
|
|
|
||
|
|
# the more filtered rules for the value exist,
|
||
|
|
# the further to the end is has to be placed,
|
||
|
|
# then reverse this
|
||
|
|
ordered_keys = sorted(
|
||
|
|
filtered_rules, key=lambda val: len(filtered_rules[val]), reverse=True
|
||
|
|
)
|
||
|
|
|
||
|
|
return ordered_keys
|
||
|
|
|
||
|
|
|
||
|
|
def main():
|
||
|
|
rules, updates = get_orders_and_updates()
|
||
|
|
|
||
|
|
# part 1
|
||
|
|
count = 0
|
||
|
|
for update in updates:
|
||
|
|
if validate_rules(update, rules):
|
||
|
|
count += get_middle_number(update)
|
||
|
|
print("Summed updates: %d" % count)
|
||
|
|
|
||
|
|
# part 2
|
||
|
|
count = 0
|
||
|
|
for update in updates:
|
||
|
|
if not validate_rules(update, rules):
|
||
|
|
new_update = fix_with_rules(update, rules)
|
||
|
|
count += get_middle_number(new_update)
|
||
|
|
print("Summ fixed updates: %d" % count)
|
||
|
|
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
main()
|