2024-12-05 - Print Queue
(original .ipynb)
Day 5 puzzle input is a list of rules that determine the correct order of things (first|second implies first has to appear before second for an "update" to be valid), mine is here). Part 1 involves using these rules to identify the valid updates then sum their middle elements. Part 2 involves taking the invalid updates and reordering them according to the rules so that they're valid and then summing their middle elements.
from collections import defaultdict
from copy import deepcopy
puzzle_input_str = open("./puzzle_input/day5.txt").read()
test_input_str = """47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13
75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47"""
def parse_rules(rules_str):
rules_tree = defaultdict(lambda:[])
for rule_str in rules_str.splitlines():
from_page, to_page = rule_str.split("|")
rules_tree[from_page].append(to_page)
return rules_tree
def parse_updates(updates_str):
return [update.split(",") for update in updates_str.splitlines()]
def parse_input(input_str):
rules_str, updates_str = input_str.split("\n\n")
return parse_rules(rules_str), parse_updates(updates_str)
def pairwise(iterable):
# need to upgrade Python on server, no pairwise in 3.9 :-O
iterator = iter(iterable)
a = next(iterator, None)
for b in iterator:
yield a, b
a = b
def correctly_ordered(page_a, page_b, rules):
return page_b in rules[page_a]
# for fuck's sake
# def correctly_ordered(page_a, page_b, rules):
# queue = deepcopy(rules[page_a])
# while len(queue) > 0:
# other_page = queue.pop(0)
# if other_page == page_b:
# return True
# queue += deepcopy(rules[other_page])
# return False
def valid_update(rules, update):
return all(
correctly_ordered(page_a, page_b, rules)
for page_a, page_b
in pairwise(update)
)
def part_one(input_str):
rules, updates = parse_input(input_str)
valid_updates = [update for update in updates if valid_update(rules, update)]
return sum(
int(update[len(update)//2])
for update
in valid_updates
)
assert 143 == part_one(test_input_str)
print("part one:", part_one(puzzle_input_str))
part one: 5087
from itertools import chain
from functools import cmp_to_key
def any_incoming_edges(node, rules):
return node in set(chain.from_iterable(rules.values()))
def order_rules(update, rules):
rules_copy = {}
for page, child_pages in rules.items():
if page in update:
rules_copy[page] = [p for p in child_pages if p in update]
l = []
s = set(key for key in rules_copy.keys() if not any_incoming_edges(key, rules_copy))
while s:
n = s.pop()
l.append(n)
ms = rules_copy[n]
del rules_copy[n]
for m in ms:
if not any_incoming_edges(m, rules_copy):
s.add(m)
return {page:i for i, page in enumerate(l)}
def sort_update(update, rules):
page_order = order_rules(update, rules)
return sorted(update, key=lambda u: page_order[u])
def part_two(input_str):
rules, updates = parse_input(input_str)
invalid_updates = [
sort_update(update, rules) for update in updates if not valid_update(rules, update)
]
return sum(
int(update[len(update)//2])
for update
in invalid_updates
)
assert 123 == part_two(test_input_str)
print("part two:", part_two(puzzle_input_str))
part two: 4971