4 ms·
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?
by n4r9 5y ago
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.
- rullelito 5y ago
- jacquesm 5y ago
- eutectic 5y agoThe 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.
- OskarS 5y agoThat 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.
- n4r9 5y agoAh, I see what you mean. The shortest path could snake around a lot. Not quite as easy as I thought!
- jacobmischka 5y agoYep, I wasted a few hours trying to force the DP solution to work as well before giving up and just using Dijkstra.
- Kwantuum 5y agoAnd in fact, there were detours in pretty much all the solutions I've seen posted online for part 2
- smcl 5y agoI 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.
- EnderShadow8 5y agoIf 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.
- smcl 5y agooh yeah it goes without saying that Python dicts and sets are my AOC bread and butter :D
- deleted 5y ago[deleted]
- vitus 5y agoYeah. 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.
- taneq 5y agoYeah, 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.