I keep thinking I'll wake up in time to compete for an #AdventOfCode leaderboard spot (at least in the few private leaderboards I'm in) and I keep ... sleeping. 🤷
Oh well, #AdventOfCode2024 Day 5 is done regardless.
I’ll leave it to the reader to decide if all the Big Tech interview leetcoding I've done allowing me to rattle off a topological sort from memory is a good thing or a bad thing. 🤣
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
John