This document explains the solution to the Day 5 puzzle, which involves verifying and fixing ordered lists of pages based on specific ordering rules.
The problem presents:
Let’s clarify the ordering concept with a simple example. If we have a rule “47|53”, it means:
If we have multiple rules like:
47|53
53|29
This creates a transitive relationship: 47 must come before 53, and 53 must come before 29, so 47 must also come before 29.
This naturally maps to a directed graph:
In the above example, valid orderings would be:
The OrderRules structure captures this directed graph:
pub struct OrderRules {
// Key: Page, Value: Set of Pages that MUST follow
rules: HashMap<Page, PageSet>
}
For each page (node), we store a set of pages (nodes) that must come after it. This is an adjacency list representation of the directed graph.
| When parsing the input, each rule “X | Y” adds Y to the set of pages that must follow X: |
rules
.entry(x)
.and_modify(|s: &mut PageSet| {s.insert(y);})
.or_insert(HashSet::new())
.insert(y);
The ManualUpdates structure represents a list of pages that needs to be verified or fixed:
pub(crate) struct ManualUpdates {
list: Vec<Page>,
}
To verify if a manual update follows the rules, we need to check if it respects all directed edges in our graph. This is different from checking if it’s a valid topological sort, because:
The validation logic uses Rust’s is_sorted_by to check if pages maintain required ordering:
pub fn make_validator(rules: &OrderRules) -> impl Fn(&ManualUpdates) -> bool {
|updates: &ManualUpdates| {
updates
.entries()
.is_sorted_by(|&a,b|
rules
.followed_by(*a)
.map(|set| set.contains(b))
.unwrap_or(false)
)
}
}
This works because:
is_sorted_by looks at consecutive pairs of elements (a, b)Consider this example with rules “47|53” and “53|29”:
The logic correctly handles cases where pages aren’t directly connected in our graph.
Fixing an invalid ordering is more complex than just verifying it. We need to rearrange the list to respect all rules.
The solution uses a topological sort via Rust’s standard sorting function:
pub fn sort_update(rules: &OrderRules) -> impl Fn(&ManualUpdates) -> ManualUpdates {
use std::cmp;
|updates: &ManualUpdates| {
let mut list = updates.entries().cloned().collect::<Vec<_>>();
list.sort_by(|&a,b| {
rules
.followed_by(a)
.map(|set|
if set.contains(b) { cmp::Ordering::Less } else { cmp::Ordering::Greater }
)
.unwrap_or(cmp::Ordering::Equal)
});
ManualUpdates { list }
}
}
This works because:
The sorting algorithm uses this comparator to rearrange all pages to satisfy the ordering rules.
The custom comparator creates a partial ordering based on our directed graph:
The standard sorting algorithm extends this partial ordering to a total ordering that respects all our rules.
Let’s trace through a simple example with these rules:
47|53
53|29
And this manual update: [29, 47, 53]
When checking if this update is valid:
However, the original ordering is [29, 47, 53], but 29 must come after 53 according to the rules, so this update is invalid.
When fixing this update:
The main function combines these components:
fn main() {
// [parsing code omitted]
// Part 1: Find valid updates
let is_valid_order = ManualUpdates::make_validator(&rules);
let score = manual_updates
.iter()
.filter(|&update| is_valid_order(update))
.map(|update| update.middle())
.sum::<usize>();
// Part 2: Fix invalid updates
let reorder_update = ManualUpdates::sort_update(&rules);
let score = manual_updates
.iter()
.filter(|update| !is_valid_order(update))
.map(reorder_update)
.map(|update| update.middle())
.sum::<usize>();
}
Graph-Based Reasoning: The ordering rules form a directed graph that defines the allowed orderings.
Partial vs Total Ordering: The rules define a partial ordering (some elements are comparable, others aren’t), but we need a total ordering (all elements are comparable) for our final list.
Custom Comparator Logic: The custom comparator for sorting translates the graph-based constraints into a format that standard sorting algorithms can use.
Efficient Validation: Checking if a list respects the ordering can be done in linear time using the is_sorted_by function, which avoids quadratic comparisons.
This solution demonstrates how to efficiently encode ordering constraints as a graph and leverage Rust’s standard library to implement the verification and sorting algorithms.