Part 2 ended up falling out of Part 1 so they're mushed together. Part 1 was essentially, "given this graph (the overall dependency set) and this subset of nodes we care about (the pages in the current order), is the current order topologically sorted?

Part 2 is then, ok, since they're not, sort them.

There was nothing particularly tricky if you already know how directed acyclic graphs work. If you didn’t, hopefully now you do? :-)

The "we only care about pages in the current order, not the entire dependency graph” part added a bit of complication, but between Python dict comprehensions and set operations it was pretty easy to create an order-specific graph, which we could use non-destructively to answer Part 1 by keeping a `seen` set and checking the disunion of the current page's deps and the seen set each time, and then if it wasn't in order we could use it destructively in Part 2.

#AdventOfCode #AdventOfCode2024 #graphs #algorithms #topologicalsort #python