Advent of Code 2024: Day 05

Code for solutions available on GitHub.

Print Queue

Today’s puzzle is going to be a lesson in the power of implementing traits! But only in part 2. Part 1 I initially solved the more naïve way.

The lore involves a list of updates with page numbers and a set of page ordering rules, which each report must adhere to. The input is made up of two chunks and looks something like this:

47|53
97|13
97|61
97|47
75|29
61|13

75,47,61,53,29
97,61,53,29,13
75,29,13

In the first chunk – the page ordering rules – the syntax a|b means that page a must occur before page b for an update to be considered valid. Each update is made up of an odd number of pages, and the end goal of this part is to sum up the middle elements of all valid updates.

So we need to save the rules in some data structure that we can check against in order to determine whether each update line is valid. Each page number can have more than one other page number it must appear before (e.g. 97 has 3 different page numbers it must appear before in the example above). So each entry in the data structure should probably be a Vec<u32>. The page ordering rules could be implemented as a HashMap<u32, u32>, but in my experience the puzzles in Advent of Code tend to be designed in such a way that using a hash map is slow. I noted that all page numbers seem to be between 10 and 99, inclusive. And as such I sacrificed some memory footprint for speed to avoid hashing:

type PageOrderingRules = [Vec<u32>; 100];

That’s right, I’m not even bothering making a struct for this one. A simple type alias to a slice of size 100 will do. Then the page number is simply an index into the slice to get the page numbers it must appear before. Similarly, the type describing an update is just an alias for Vec<u32>:

type Update = Vec<u32>;

So the input parsing function will get the following signature:

fn parse_input(&str) -> (PageOrderingRules, Vec<Update>)

The parsing itself isn’t that interesting, so I’ll omit its implementation.

Now we need a function to make sure an Update adheres to the PageOrderingRules. It needs to scan the Update, keeping track of which numbers it has seen, and return false if it encounters a page number that must appear before a page number it has already seen. This can be accomplished by a slice of bools that the page number indexes into:

fn valid_update(98
    update: &Update,
    rules: &PageOrderingRules
) -> bool {

    let mut seen = [false; 100];
    for page in update {
        seen[*page as usize] = true;

        if rules[*page as usize]
            .iter()
            .any(|p| seen[*p as usize])
        {
            return false;
        }
    }
    true
}

Good! Now we can filter the Vec<Update>. Since all the updates are of odd length, getting the middle element is the same thing as integer division of the length of the Update by 2:

let result = updates
    .iter()
    .filter(|update| valid_update(update, &rules))
    .map(|update| update[update.len() / 2])
    .sum();

And that’s essentially it for part 1!

Part 2

Now, we need to process the invalid updates. And what we have to do is make them valid and then do the same middle element sum on the fixed updates. An initial thought to adapt the solution described above for part 1 might look like this:

1. Filter the invalid updates (easy, just invert the condition from part 1)
2. Find the positions of a pair of pages that violate the rules (simple enough)
3. Swap them (no problem)
4. Check if the update is valid. If not, repeat. (hmmm…)
5. Sum the middle page numbers (we already know how)

Step 4 is problematic. How many times will the swapping happen? Swapping a pair of pages might violate a different rule and so the entire update will have to be checked again. I’m not sure how to define the time complexity of this.

So this simple swapping solution can probably be thrown out. It’s not well defined enough for me to have faith it will even work. But swapping positions of elements in a list should ring a bell to any computer scientist. This sounds like a sorting problem in disguise!

We’re just in a strange world where – from the example above – 97 is less than 13, 61, and 47. The ordering of page numbers is defined differently than regular numbers. Hmmm… Ordering…

Enter the Ord trait!

If we define our own struct for page numbers, and implement the Ord trait, we can call .sort() on a Vec of page numbers and it will just work. A page number can be defined as a pair of a number, and the set of PageOrderingRules. Since all page numbers will share the same rules, it makes sense to make that member a reference. Here’s how I defined it:

struct Page<'a>(u32, &'a PageOrderingRules);

If you don’t want to deal with lifetimes, you can of course always just clone the rules into each Page you construct. But that’s gonna be a lot of cloning if you look at the inputs. For example, my input for this puzzle has around 200 lines of updates, each with around 15 page numbers. 15 * 200 = 3000 Pages that need to be constructed. And with each page number possibly having a Vec of other numbers it must appear before as a rule, it’s potentially a lot of cloning. Maybe not in absolute terms, but a lot of small clones isn’t good either.

Lifetimes rant aside, now we need to implement Ord for Page<'a>. When is a Page less than another Page? Why, when the other Page appears in the first’s list of rules, of course! If the reverse is true, the Page is greater than the other. In all other cases it doesn’t matter, so we’ll just say the pages are equal:

impl<'a> Ord for Page<'a> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        if self.1[self.0 as usize].contains(&other.0) {
            std::cmp::Ordering::Less
        } else if other.1[other.0 as usize].contains(&self.0) {
            std::cmp::Ordering::Greater
        } else {
            std::cmp::Ordering::Equal
        }
    }
}

// To impl `Ord`, you have to impl `PartialOrd`.
// Luckily you can just do that in terms of `Ord`.
impl<'a> PartialOrd for Page<'a> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

Now we can just map the Updates (Vec<u32>s) into a series of Page<'a>s and, beautifully, filter using Vec::is_sorted. Then just call Vec::sort on the resulting updates and sum up the middle elements just like before:

let result = updates
    .into_iter()
    .map(|update| update.into_iter().map(|p| Page(p, &rules)).collect_vec())
    .filter(|update| !update.is_sorted())
    .map(|mut update| {
        update.sort();
        update[update.len() / 2].0
    })
    .sum();

And I think that’s pretty neat.

Once I figured out this sorting trick, I went back to part 1, deleted the validate_update function and just solved it with the same sorting method.

I feel like this is a great demonstration of the power of implementing some of the traits in the standard library. It can unlock some really neat functionality and make solving problems a breeze.

Full code.