How to code a Sorting Algorithm for Advent of Code 2024

In the previous post, I briefly mentioned that I am participating in this year’s Advent of Code. Co-incidentally, in one of the puzzles, specifically the one published on day 5, involves fixing the order of pages in a list. This came not long after I posted about implementing a sorting algorithm, so I figure I should write about it.

A cute image depicting some sorting algorithm

For those who have not heard about Advent of Code, it is an annual event hosted by Eric Wastl. Each year, it tells a story that sets in the holiday season, this year it is about looking for the Chief Historian, possibly an important figure in every big Christmas sleigh launch. The challenge will run from the first of December each year, till the 25th. Every day, the plot progresses, and it contains a programming puzzle (and it comes with an input).

Within the story narration, the puzzle is usually defined clearly, and includes test cases. Every puzzle is split into two parts, and the second part shows up only after submitting the first answer.

Participants can implement any algorithm, in any language, or even skipping programming altogether, as long as the derived answer matches. This year I am attempting to code the solutions in Python, and after 9 days, I feel like I learned quite a fair bit throughout the journey.

On day 5, the story asked to help with the printing of safety manuals. The input contained both the page rules, and the lists of pages the elf was trying to print.

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

Let’s start by parsing the input:

def parse(
    input: str,
) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
    def inner(
        current, incoming
    ) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
        rules, pages = current

        if "|" in incoming:
            return rules + (
                tuple(int(item) for item in incoming.strip().split("|")),
            ), pages

        else:
            return rules, pages + (
                tuple(int(item) for item in incoming.strip().split(",")),
            )

    return reduce(
        inner, filter(lambda line: line.strip(), input.strip().splitlines()), ((), ())
    )

The function receives the input as a string named input, breaks it into lines with .splitlines(), to be sent into the inner function to produce two tuples, one for page rules, and another for page sequence. The code differentiates the two types of definitions through the separator, | for page rules, and , for pages.

In the first part of the puzzle, the story asked to check if the pages were in order. Let’s start by implementing a function that does the job:

def check_pair(rules: tuple[tuple[int, int], ...], alpha: int, beta: int) -> bool:
    return (beta, alpha) not in rules

And then another function that sends all combinations of pages (combinations((1,2,3), 2) returns 1,2, 1,3 and 2,3):

from itertools import combinations

def check_pages(rules: tuple[tuple[int, int], ...], pages: tuple[int, ...]) -> bool:
    return all(
        check_pair(rules, alpha, beta)
        for alpha, beta in combinations(pages, 2)
    )

The main reason I separated these two into individual functions is that I want to keep each part as small as possible. From my experience, keeping things small enough not only makes it testable, it usually also helps with debugging the final input (which is usually unreasonably large).

A lot of times, part 2 comes as a surprise, and it is not uncommon to find it calls for a revision in code design for part 1. It could be a small variation to something you have implemented, or require different function invocation order for different goal, etc. I do maintain a habit of writing short functions at work (as an alternative to comments).

Small functions like this only work if the names are good, so you need to pay good attention to naming. This takes practice, but once you get good at it, this approach can make code remarkably self-documenting. Larger scale functions can read like a story, and the reader can choose which functions to dive into for more detail as she needs it.
quoted from the article titled Function Length, authored by Martin Fowler

Back to the puzzle.

At the end, the puzzle asked for the sum of the middle page number for all cases where the pages were properly ordered.

def get_middle(pages: tuple[int, ...]) -> int:
    return pages[len(pages) // 2]

def part1(input: str) -> int:
    rules, pages_list = parse(input)

    return sum(
        get_middle(pages)
        for pages in pages_list
        if check_pages(rules, pages)
    )

Pretty straight forward, if you have done everything right, it is just a list comprehension away (because Python devs prefer this over map / filter).

Next, is the sorting algorithm:

Continuing from part 1, the second part wanted the sum of middle pages, but for cases where the pages were not ordered properly. The instruction also asked to fix the order before retrieving the middle page number.

While my peers managed to fix it without a full-fledged sorting algorithm, I decided to just do it the exact way the puzzle described earlier, in the section explaining the page rules. I already had the comparison part done (check_pair), now I need a function that would move elements around.

def move(items: tuple[int, ...], current: int, incoming: int) -> tuple[int, ...]:
    assert incoming > current

    return (
        *items[:current],
        items[incoming],
        *tuple(
            item
            for idx, item in enumerate(items)
            if (idx >= current) and not (idx == incoming)
        ),
    )

Suppose I have 1,2,3,4,5 and the function moves the incoming number, to right before the current number. Assuming current = 2, and incoming = 4, then I will get 1,4,2,3,5 in return (assuming we are arranging according to the increasing numerical value).

My unsuccessful attempt to explain the algorithm to a friend

Next is turning the algorithm, shown in my handwritten draft, into actual code.

def sort_pages(
    rules: tuple[tuple[int, int], ...],
    pages: tuple[int, ...],
    pointer: int = 0,
    subpointer: int = 0,
) -> tuple[int, ...]:
    return (
        sort_pages(
            rules,
            *next(
                (
                    (move(pages, pointer, incoming), pointer, pointer + 2)
                    for incoming in range(subpointer, len(pages))
                    if check_pair(rules, pages[pointer], pages[incoming]) is False
                ),
                (pages, pointer + 1, pointer + 2),
            ),
        )
        if pointer < (len(pages) - 1)
        else pages
    )

Yeah, unfortunately it is in a recursion. I should post the first version, that could be friendlier to read:

def sort_pages(
    rules: tuple[tuple[int, int], ...], pages: tuple[int, ...]
) -> tuple[int, ...]:
    result, pointer = pages, 0

    while True:
        if pointer == (len(pages) - 1):
            break

        changed = False

        for incoming in range(pointer + 1, len(pages)):
            if check_pair(rules, result[pointer], result[incoming]) is False:
                result = move(result, pointer, incoming)
                changed = True
                break

        pointer = 0 if changed else pointer + 1

    return result

Both are essentially the same, with the final functional version is slightly optimized. By referring to the draft screenshot, I have two pointers, the yellow underline is named pointer in the code, and incoming the blue underline.

The algorithm works as follows:

1. It begins by setting the pointer to the first element.
2. Initially incoming is always the element next to it.
3. The incoming pointer will step through one element at a time, and would move the value to right before current if it violates the rule.
4. Once that happens, incoming pointer resets, and move back to the next of current.
5. The current pointer does not change position, but it is now pointing at the new element that was inserted in the earlier step.

If the incoming pointer manages to step through the remaining of the list without introducing a change, we advance the current pointer (and incomingpointer re-initialized to the position next to it), and repeat the process again.

The process ends after the algorithm is done comparing the last 2 elements, and then returns the sorted pages as the result. Then, we can proceed to assemble whatever we have for part 2:

def part2(input: str) -> int:
    rules, pages_list = parse(input)

    return sum(
        get_middle(sort_pages(rules, pages))
        for pages in pages_list
        if check_pages(rules, pages) is False
    )

The code for both parts are similar. It is just a slight modification to part1, just some variation in the filter clause, and get_middle receives a sorted list instead. Essentially, if is as if I am assembling an answer out of building blocks in the shape of functions, in a slightly different combination.

While this is still not exactly an efficient algorithm, as the time complexity is close to O(n^2). According to the cascade AI-companion in windsurf, the algorithm resembles the insertion sort in some ways (yeah, this is when the AI tool is useful, providing explanation to algorithms).

That’s it for today, I am glad that the algorithm works fine, though my life is currently a mess (just pulled out from a project due to funding issues). Hopefully things get better as time passes, and I shall write again, next week.