I found myself in the North Pole's printing department today, helping an elf with their safety manual updates. The printer had strict rules about page ordering - certain pages had to be printed before others. As I stared at the long list of rules like "47|53", I couldn't help but smile. This wasn't just about printing pages - this was a dependency resolution puzzle in disguise.

The Challenge: A Printer's Dependency Graph

The problem gave me two things: rules like "47|53" (meaning page 47 must be printed before page 53), and sequences of page numbers to validate. Part 1 asked me to identify sequences that already followed all the rules. Part 2 got more interesting - I needed to sort the invalid sequences according to the rules.

Four Languages, Four Approaches

Rust: Bidirectional Maps for Efficient Ordering

In Rust, I modeled the rules using two HashMaps - one for forward dependencies and one for reverse:

#[derive(Debug, Default)]
struct RuleMaps {
    forward: HashMap<i32, HashSet<i32>>,
    reverse: HashMap<i32, HashSet<i32>>,
}

impl RuleMaps {
    fn compare(&self, a: i32, b: i32) -> std::cmp::Ordering {
        if self.forward.get(&a)
            .map_or(false, |targets| targets.contains(&b)) {
            Ordering::Less
        } else if self.forward.get(&b)
            .map_or(false, |targets| targets.contains(&a)) {
            Ordering::Greater
        } else {
            a.cmp(&b)
        }
    }
}

This bidirectional approach made both validation and sorting efficient. The compare function integrates seamlessly with Rust's sorting mechanisms while respecting our dependency rules.

Elixir: Pattern Matching for Clear Logic

Elixir's pattern matching made the rule checking particularly elegant:

def should_come_before?(rules, a, b) do
  case Enum.find(rules, fn {source, target} ->
         (source == a and target == b) or (source == b and target == a)
       end) do
    {^a, ^b} -> true   # Direct rule a|b exists
    {^b, ^a} -> false  # Direct rule b|a exists
    nil -> false       # No direct rule exists
  end
end

The pin operator (^) creates a beautiful declarative way to express our ordering rules. The code reads almost like the problem description itself.

Go: Pragmatic Sorting

Go's approach shows its strength in straightforward, efficient code:

func shouldComeBefore(rules []rule, a, b int) bool {
    for _, r := range rules {
        if r.source == a && r.target == b {
            return true
        }
        if r.source == b && r.target == a {
            return false
        }
    }
    return false
}

func (s sequence) sort(rules []rule) sequence {
    sorted := make(sequence, len(s))
    copy(sorted, s)
    sort.Slice(sorted, func(i, j int) bool {
        return shouldComeBefore(rules, sorted[i], sorted[j])
    })
    return sorted
}

The explicit handling of comparisons and sorting reflects Go's preference for clarity over cleverness.

Haskell: Pure Functional Dependencies

Haskell's solution leverages efficient data structures from the containers package:

buildRuleMaps :: [Rule] -> (IntMap IntSet, IntMap IntSet)
buildRuleMaps rules = foldl' insertRule (IM.empty, IM.empty) rules
  where
    insertRule (!fwd, !rev) (src, tgt) =
        ( IM.insertWith IS.union src (IS.singleton tgt) fwd
        , IM.insertWith IS.union tgt (IS.singleton src) rev
        )

The use of IntMap and IntSet isn't just about performance - it's about expressing relationships between numbers in a purely functional way. The strict annotations (!) ensure our dependency maps are evaluated eagerly.

Performance Through Data Structures

Each language brought its own insights about efficient dependency handling. Rust's bidirectional maps made lookups O(1). Elixir's pattern matching compiler optimized our rule checks. Go's sort package provided an efficient implementation of our custom comparator. Haskell's specialized data structures gave us both performance and correctness guarantees.

Reflections on Dependencies

You know what's funny? I spend my days working with package managers and build systems, dealing with complex dependency trees. Yet here I was, getting excited about a printer queue doing essentially the same thing. Each of my languages handled it differently - Rust with its efficient maps, Elixir with elegant pattern matching, Go keeping it pragmatic, and Haskell showing off its pure functional approach. But they all had to solve the same core problem: making sure page 47 prints before page 53, just like making sure libssl installs before nginx.