Advent of Code: Day 5
Link to problem: https://adventofcode.com/2024/day/5 When I first looked at this, my first instinct was to treat it like a partial order, and make the DAG to represent it. But then I thought on it a bit more-- The way the question is stated doesn't actually make the input a partial ordering, it doesn't have to be transitive-- so I wasn't sure whether it'd be possible to properly represent this as a DAG. I decided not to think too hard, and just use a simple approach that I knew would work. I'll probably implement it as a DAG later on though, when I'm doing this in another language. I decided to read the "rules" into a dict -- for each number on the left, I'd keep a set of numbers that appear in its right in the rules -- i.e. a set of numbers that should never precede it. Let's call N the number of rules, M the number of updates, and L the length of the longest update list. Then the maximum number of keys and values in the rules dict would be N...