../aoc24day5

Advent of Code Day 5: Topological Sort!

As before with Day 3, I won’t be redescribing the puzzles in full; please check out Advent of Code for more.

This problem was fun to solve, and allows me to do a quick explainer on topological sorting (see part 2), hope you enjoy!

Part 1: OSHA would be very mad

The pages of the safety manuals are out of order, oh fie! Whatever shall we do to verify their validity???

(Tragic, I know.)

Histrionics aside, the basis of this problem is simple; we have lines that give us a before|after relation between pages, and then we have lines of pages as a list, and we have to verify that they work. A sample input is as follows:

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

Our end goal for part 1 is to sum up the middle pages of all of the “correctly ordered” lines, but I will mostly be focusing on how we can check for that, rather than the overall solution.

To begin, I create a rule_map that contains, for every before page, a HashSet of all of the pages that must come after it! For example, in the above input, notice that 13 must come after 29, so that gets placed in our rule_map. This is populated as follows:

rule_map.entry(before)
    .and_modify(|after_pages| { 
        after_pages.insert(after); 
    }).or_insert(HashSet::from([after]));
rule_map.entry(after).or_insert(HashSet::new());

We add an entry for after to make it easier to handle cases later.

Then, the real checking begins when we encounter the lines, and the logic here is that since we have a mapping (for a given page number) of all of the pages that should come after it, if we have seen a page that should come after our current page, we know we’ve found an incorrect list.

'outer: for line in read_to_string(file).unwrap().lines() {
    // Do some stuff here that isn't relevant to this code block
    // ...

    let mut seen = HashSet::<u32>::with_capacity(nums.len());
    for num in &nums {
        let after_pages = rule_map.get(&num).unwrap();
        // checks for the bad thing
        let found = after_pages.iter().any(|val| seen.contains(val));
        if found {
            continue 'outer // skip this entire line, basically
        }
        seen.insert(*num);
    }
}

A small nifty thing here is the continue 'outer syntax; if we are in a for loop that is nested, but we want to break out of the outer for loop, we can tag the outer for loop with 'outer: for ... in ..., and then use the continue 'outer syntax! This also works with break as well.

After this, if we haven’t found an error, then we just add the middle page values up with sum += nums[nums.len()/2] (simple as).

Part 2: Topo-sort is inevitable

There are 100% other ways to do part 2.

However.

I could not find them.

It was 2 AM again.










Anywho.

So the basis of this problem is that for all of the incorrect rows we marked previously, we now want to fix them and find the sum of their middle pages, a la part 1. Originally I was thinking of some sort of bubble sort esque swapping solution, but I couldn’t intuit it nicely, so I went with topological sorting instead since it felt somewhat natural.

As a brief aside, it felt natural primarily because we’ve been dealing with what is essentially a dependency graph this entire time, and it’d be a shame not to leverage that structure with a nicely made DAG just sitting there, yknow?

So the rest of this section is going to basically just be an introduction to topological sorting because you can probably fill in the gaps as to how the rest of part 2 is done.

Topological Sorting, for dummies

Topological Sort

Simply put, given a directed acyclic graph (DAG), a topological sort is a linear ordering of vertices such that for all edges from u to v, u is “before” v in the linear ordering.

A good example is in this image which is for this original list [97,13,75,29,47] (thank you to Ved for the graph).

There are a few ways to implement toposort, but the most intuitive to me is Kahn’s Algorithm, which goes as follows:

  1. (Prior to doing much of anything) For the list you are trying to sort, calculate the “in degree” of each vertex; this is just the number of nodes that have edges flowing into the current node.
let mut in_degree: HashMap<u32, u32> = HashMap::new();
for &node in &input {
    in_degree.insert(node, 0);
}
for from in &input {
    if let Some(neighbors) = rule_map.get(&from) {
        for &to in neighbors {
            if input.contains(&to) {
                *in_degree.entry(to).or_insert(0) += 1;
            }
        }
    }
}

Note that we have to be careful to do our in degree calculation locally, and not over the whole list, since the whole list may not have a valid topological sort (may not be an acyclic graph).

  1. Now that we have our in degree calculated for all relevant nodes, we can create a queue of zero in degree nodes. Intuitively, we want to start at the nodes that have no other nodes as dependencies. This can be done easily with:
let mut zero_in_degree: VecDeque<u32> = in_degree
    .iter()
    .filter(|&(_, &deg)| deg == 0)
    .map(|(&node, _)| node)
    .collect();
  1. Do the actual topological sort. This is arguably best explained with the code itself, so take a look below and I’ll explain in bits and pieces after:
let mut sorted = Vec::new();
while let Some(node) = zero_in_degree.pop_front() {
    sorted.push(node);

    if let Some(neighbors) = rule_map.get(&node) {
        for neighbor in neighbors {
            if let Some(count) = in_degree.get_mut(neighbor) {
                *count -= 1;
                if *count == 0 {
                    zero_in_degree.push_back(*neighbor);
                }
            }
        }
    }
}

Life’s sorted again

And there you have it, done with day 5! This was a pretty fun problem to solve, and I’m somewhat happy with how my solution turned out. See you next time :D

/aoc2024/ /rust/