The fifth day of Advent of Code was yesterday 12/05/2024! If you’re here for the first time today, don’t forget to read the posts about Day 1, Day 2, Day 3, and Day 4!

I classified the fifth problem as easy (part 1) and medium (part 2).

Tips#

The problem has two inputs, a list of rules and a list of updates.
The pages present in the rules list (X) must be printed before pages (Y). Since the same page X can have multiple Y’s, the rules are a dictionary with integer keys and lists of integers as values.
The updates are simple integer lists.
To verify if the rules were followed, check if every page present in the update follows the rules.
One way to check the validation is to verify if the list before the page being checked has any other page listed in the rules of the same page. You can use list slicing rules to create a sublist with the previous elements of the list.

For example:

>>> L = [7, 8, 9]
>>> L[1:]
[8, 9]
>>> L[:2]
[7, 8]
>>> L[:1] + L[2:]
[7, 9]
>>>

Reread the list slicing section in chapter 7 if needed.

Reordering can be done the same way. When an out-of-order element is found, remove it from the list, swapping the order of the wrong element with the element from the rulebook that should appear before.

Example with a small list:

>>> RULE = {8: [7]}
>>> update = [7, 8, 9]
# Since p is the second element, index 1, we can swap the order:
>>> REORDERED = update[:0] + [8] + [update[0]] + update[2:]
[8, 7, 9]

This type of problem can be confusing because ascending order prevails, and even while following the rules, you might get the impression that it’s incorrect.
You can use a recursive function to reorder the list since when changing an element, the rules must be checked again.
Part 1: Easy - requires some creativity to combine lists and dictionaries.
Part 2: Medium - the recursive reordering isn’t so obvious.

How much Python do you need to know?#

The chapters refer to my book Introduction to Programming with Python.

Lists, Dictionaries - Chapter 6
Recursive Functions - Chapter 8

Answer#

from auxiliares import string_to_int_matrix, list_per_line

ORDER = """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"""

TEST = """
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 build_rules(restrictions: list[list[int]]) -> dict[int, list[int]]:
    rules = {}
    for x, y in restrictions:
        rules[x] = rules.get(x, []) + [y]
    return rules


def build_restrictions(order: str) -> list[list[int]]:
    return string_to_int_matrix(order, separator="|")


def check_order(rules: dict[int, list[int]], update: list[int]) -> bool:
    for p, page in enumerate(update):
        if page in rules:
            previous = update[:p]
            for prev in previous:
                if prev in rules[page]:
                    return False
    return True


def reorder(rules: dict[int, list[int]], update: list[int]) -> bool:
    for p, page in enumerate(update):
        if page in rules:
            previous = update[:p]
            for i, prev in enumerate(previous):
                if prev in rules[page]:
                    return reorder(
                        rules,
                        previous[:i]
                        + [page]
                        + previous[i:]
                        + update[p + 1 :],
                    )
    return update


def sum_middle_pages(rules, updates):
    s = 0
    for update in updates:
        if check_order(rules, update):
            middle = (len(update)) // 2
            s += update[middle]
    return s


# Part 1
test_rules_part_1 = build_rules(build_restrictions(ORDER))
m_test = string_to_int_matrix(TEST, ",")

test_part_1 = sum_middle_pages(test_rules_part_1, m_test)
print("Test part 1:", test_part_1)
assert test_part_1 == 143

rules_part_1 = build_rules(list_per_line("05/regras.txt", separator="|"))
updates_part_1 = list_per_line("05/atualizacoes.txt", separator=",")

part_1 = sum_middle_pages(rules_part_1, updates_part_1)
print("Part 1:", part_1)
assert part_1 == 5268

# Part 2

sum_test_part_1 = sum_middle_pages(
    test_rules_part_1,
    [
        reorder(test_rules_part_1, update)
        for update in m_test
        if not check_order(test_rules_part_1, update)
    ],
)
print("Sum of middle elements, part 2 test vector:", sum_test_part_1)
assert sum_test_part_1 == 123

sum_part_2 = sum_middle_pages(
    rules_part_1,
    [
        reorder(rules_part_1, update)
        for update in updates_part_1
        if not check_order(rules_part_1, update)
    ],
)
print("Sum of middle elements, part 2:", sum_part_2)
assert sum_part_2 == 5799

# Output
# Test part 1: 143
# Part 1: 5268
# Sum of middle elements, part 2 test vector: 123
# Sum of middle elements, part 2: 5799

Advent of Code 2024 - Day 05 of 25

Table of Contents

Tips#

How much Python do you need to know?#

Answer#