Hacker News Reader

Comment by n4r9 | Hacker News Reader

Nice to see an implementation of priority queues in Haskell, although I think most people would say this is already an integral part of the dijsktra algorithm?

I haven't yet attempted this year's AOC but I suspect this is one where working backwards from the bottom right and dynamically storing the best value at each cell would work much better than dijsktra.

View on HN

That assumes that the path only ever goes right and down. There’s no basis for that assumption in the general case, it’s entirely possible that the shortest path has to take a “detour” to avoid some high cost sections. This is a shortest-path problem, not a DP problem.

And in fact, there were detours in pretty much all the solutions I've seen posted online for part 2

Ah, I see what you mean. The shortest path could snake around a lot. Not quite as easy as I thought!

Yep, I wasted a few hours trying to force the DP solution to work as well before giving up and just using Dijkstra.

Yeah. Priority queue backing is the most common way of introducing the algorithm, although fib heap achieves better asymptotic performance in the general case.

Here the number of edges is linear in the number of vertices (at most 4x) so it doesn't make a difference (relative simplicity of priority queue probably wins out here in practice) but it's even more efficient to solve via memoized recursion as briefly mentioned in the article, assuming that you don't blow your stack.

The naive dynamic programming solution doesn't work because it's possible to 'backtrack'. But I used Bellman-Ford which is almost as simple and very fast.

I worked on a lot of previous AoC problems in November and then did AoC 2021 in December. I should do a little write-up because there are definitely patterns that repeat, but one thing I noticed was that if you're doing them in Python then the "heapq" module is sometimes so useful it feels like cheating. There are many problems where as long as you have a simple brute force algorithm and a way to rank potential solutions, you're mostly done.

If it works, it works. Priority queues are an extremely powerful data structure if you leverage them right.

I find C++'s set and map and related data structures are also very useful for solving cp problems.

oh yeah it goes without saying that Python dicts and sets are my AOC bread and butter :D

Yeah, that's how we were taught it anyway. Nodes are added to a priority queue as they're discovered while being popped off the queue in order. From the title I was expecting something like going from naive Dijkstra via A* to an optimized jump point search or something.

That said, the title aside, it's still a worthwhile post. It's sometimes easy to accidentally nuke your algorithm's performance with an innocent-looking function call or operation that's secretly turning it quadratic or worse.

Reply on news.ycombinator.com