Print Queue

Part 1

We’re doing several printing jobs where certain page numbers must be printed before others. The job of correctly ordering the pages to fit this requirement is called topological sorting. But for now, we don’t need to do any topological sorting; we just want to check which lists of pages are topologically sorted.

First, let’s parse the page ordering rules and the updates. The whole input is in the form of two blocks separated by \n\n (my solution template allows me to do this automatically, but you’ll want to call str.split on your input explicitly). Each of these blocks has multiple lines, which can be split with str.splitlines.

class Solution(StrSplitSolution):
    separator = "\n\n"

    def part_1(self) -> int:
        raw_rules, raw_updates = (part.splitlines() for part in self.input)
        ...

The list of updates is a list of lists of integers, and is simple to parse.

For the page ordering rules, I decided to represent them as a dict mapping each page to a set of its predecessors; for example, if 47|53 were a rule, then 47 in predecessors[53] would be true, because page 47 must go before page 53. This way, checking whether any given rule exists involving two pages can be done quickly.

from collections import defaultdict

class Solution(StrSplitSolution):
    ...
    def part_1(self) -> int:
        ...
        # updates will hold updates as lists of page numbers
        updates = [
            [int(u) for u in raw_update.split(",")]
            for raw_update in raw_updates
        ]
        # predecessors will map pages to pages that must go before them
        predecessors: dict[int, set[int]] = defaultdict(set)
        for raw_rule in raw_rules:
            before, after = map(int, raw_rule.split("|"))
            predecessors[after].add(before)
        ...

We can then use this predecessor dict to make a function that checks whether a given update follows the rules. An update follows the rules if and only if no pair of pages is in an invalid order; in other words, if a page before comes before a page after in the update, there can’t be a rule that says after must be a predecessor of before.

from itertools import combinations

def follows_rules(
        update: list[int],
        predecessors: dict[int, set[int]],
) -> bool:
    return not any(
        after in predecessors[before]
        for before, after in combinations(update, 2)
    )

And now, we can total the middle items of every update that follows the page ordering rules!

...

def middle_item(lst: list[int]) -> int:
    return lst[len(lst) // 2]

class Solution(StrSplitSolution):
    ...
    def part_1(self) -> int:
        ...
        total = 0
        for update in updates:
            if follows_rules(update, predecessors):
                total += middle_item(update)

        return total

(I also went ahead and created a middle_item function to grab the middle element of the update, for ease of readability.)

Part 2

Now that the correctly ordered updates have been processed, we want to process the incorrectly ordered updates by ordering them correctly. In other words, we must now do some topological sorting.

As Tim Peters wrote in The Zen of Python, “there should be one— and preferably only one —obvious way to do it”¹ — though which way is most obvious can depend on how much you know about the language and the relevant algorithms.

• In my initial solution, I used the fact that the input overspecified the order to write a single sorted expression (even though how it works requires a bit of explanation).
• Those who knew a bit more about topological sorting used Kahn’s algorithm, a standard algorithm for topological sorting.
• And those who knew deeply about Python’s standard library used graphlib.TopologicalSorter, a class made to assist in topological sorting. (In my opinion, this is the “obvious” solution.)²

However, I saw one approach taken by a few people (including the ever-clever u/4HbQ on Reddit) which I found interesting, and which I probably would’ve used myself if I knew about it back in 2024. So I’ll be explaining that approach instead — especially because I will likely never have an excuse to explain it again.

Because this problem involves a type of “sorting”, it would be nice if we could directly use the list.sort method or sorted function in the solution. These functions have a key parameter which can be used to sort by a custom rule, and items are compared by calling that key function on them and comparing their results.

In this scenario, we can’t seem to directly apply a key function. Given two pages, we can only figure out the relative order of those two pages. This is more conducive to a comparison function, which takes two items and returns a negative value for “less than”, zero for “equal”, and a positive value for “greater than”. (Comparison functions were the only way to sort by a custom rule before Python 2.4, and they’re still commonly used in low-level languages like C or C++.)

...

class Solution(StrSplitSolution):
    ...
    def solve(self) -> tuple[int, int]:
        ...
        def cmp_pages(a: int, b: int) -> int:
            """Old-style comparison function for page numbers."""
            # If page A comes before page B, A goes first
            if a in predecessors[b]:
                return -1
            # If page B comes before page A, B goes first
            if b in predecessors[a]:
                return 1
            # Otherwise, it doesn't matter which page goes first
            return 0
        ...

Sometimes, this is the best you can do. And the team behind Python not only recognizes this, but accommodates for it with functools.cmp_to_key. This function allows a comparison function to be converted to a key function — which, especially for cases like this, is occasionally useful.

For this solution, we can sort each update that doesn’t follow the rules by converting our custom cmp_pages comparison function to a key function. Then it’s only a matter of adding the middle pages of those sorted updates to a separate total.

from functools import cmp_to_key
...

class Solution(StrSplitSolution):
    ...
    def solve(self) -> tuple[int, int]:
        ...
        part_1, part_2 = 0, 0
        for update in updates:
            if follows_rules(update, predecessors):
                part_1 += middle_item(update)
            else:
                sorted_update = sorted(update, key=cmp_to_key(cmp_pages))
                part_2 += middle_item(sorted_update)

        return part_1, part_2

The thing I like most about this approach is the fact that you don’t have to know what topological sorting is, or how to do it, to come up with it. It’s a neat example of a clever use of the Python standard library.