Sign up at app.codecrafters.io/join?via=hyper-neutrino and try out Codecrafters today! You can get a taste of their many learning streams and try out their beta courses all completely for free (no credit card needed), and when you go to sign up, you'll get 40% off at checkout and support the channel! Thank you for watching :) (Codecrafters has not sponsored this video directly and they did not have the opportunity to review any of this video, including the promotional segment.)
i spent all day trying to do this with dijkstra but i couldn’t figure it out. thanks for confirming i wasn’t too far off! i think what i missed is that direction *and* number of steps have to be saved in the state
Thanks so much for this video! Today is the first day where I've REALLY got no idea. Never done a Dijkstra before! After watching your video multiple times, copying your entire code into my project and rewriting it into my language and writing my own version of heappush, it finally runs to completion! I mean, I get an answer of 12 for the sample data, but it runs 😅
Found an "optimization" for your solution - you can remove "dr, dc != 0, 0" checks if you start with two tuples already in queue for two directions: right and down 🙂It worked for my copy of your algorithm written in TS, I also added "1" as "n" and "0" for "hl" for both
Also your solution has saved me from eternal pain - I got stuck looking at existing implementations of A* and Dijkstra for JS where they weren't using a separate "seen" set but worked with pre-made node grid which then get marked with boolean keys "visited" and "closed", and I just couldn't comprehend how could I ever use it for counting steps and tracking directions... Definitely learning a lot from your videos!
Thanks for this video. It realy helped me. But I seem to do something wrong, because my program (used Rust to implement it) took very long (some minutes for part 2). How long is your run time (and of others here in comments)?
In all the Dijkstra tutorials I've looked at, we have to have a data structure that stores the path distances from the source to every other node where the start vertex is initialized to 0 and all the other ones are initialized to infinity. Is there a reason why we don't do that here and somehow the Dijkstra works?
It's useful as an optimization. I forgot here so technically my solution isn't perfectly efficient but it doesn't matter too much in a context like this. It also allows you to get the minimum path length to any vertex from the fixed starting point, but again, we only care about a predetermined point in this problem.
@@hyper-neutrino Gotcha, thanks for responding. I don't have a good grasp on Dijkstra so I thought that data structure was required for the algorithm to work but clearly I'm mistaken.
@@noblerare At its core Dijkstras is basically breadth first search with a min heap to determine which node to explore next based on current distance estimates from the source (an unseen node in a connected graph will never be that node, since some node will always have a value less than infinity in the min heap). Instead of pre-calculating the distances as you mention, you can just check if a distance entry exists at all the first time you encounter a node, if it doesn’t you add the new distance. This would be the same mechanically if you had encountered an infinity entry as well (eg any infinity entry means we haven’t encountered the node yet in our exploration)
@@noblerare the optimization that hyper refers to I believe is that if you add all nodes up front, you can create your min heap in O(n) time basically by heapifying an array. If you add them as you go, each insertion is O(log n) and you do this n times so your total cost would be O(nlogn) instead for creating the min heap.
Why is there not a need to "relax" estimates in this implementation? You add the distances to the heap one time, but there is no update happening to these distance estimates like in typical Dijkstras
You don't strictly need to do distance updates; if a more efficient distance is found, it will just be added to the priority queue as well. In my day 11 to 17 stream, I do add a distance map and only add new items to the priority queue when a more optimal distance is found, but that's a constant-time optimization (theoretically speaking) and not necessary for the algorithm.
@hyper-neutrino thank you for the response. It makes sense now. Because the "seen" set does not store distances, when we pop the node from the priority queue, although we might have repeat states with different distances, only the lowest distance will get processed and the rest get ignored (popped from queue and discarded eventually). Per the original Dijkstras algorithm this is still correct in theory, because it's as if we still "relaxed" the state as much as possible by placing all of the candidate distances in queue, and once popped we are guaranteed the min distance is returned.
I don't quite understand how the lowest value ends up always being at the start of the heap, especially given that the values in the item could be anything, and you're only ever calling "push" - how does it know which is the lowest value? For example, if you'd chosen to put the location coordinates first, would this still work?
If you put the coordinates first, it wouldn't work, because the priority queue maintains order based on python sort order. the priority queue data structure allows you to insert elements and then remove the smallest one first every time; I may do a video in the future covering this ADT and how the heap implementation works
Isn't A* traversal >= Dykstra? I tried implementing an A* and not spotting an error in my code, but not working. At a high level, could I use A* instead of Dykstra and solve problem you think?
Dijkstra is a subset of A* where the potential from your heuristic is always zero. It will help improve the performance of just Dijkstra because your heap sort will favor paths that are closer to the end.
Hi @hyper-neutrino, why checking for distance minimization won't work here? I tried to keep track of the shortest distance / path like in normal dijkstra: new_hl = hl+ grid[nr, nc] if new_hl < distances[nr, nc]: distances[nr, nc] = new_hl heappush(...) For both going straight and turning left and right, but it gives me the wrong result. Any ideas?
Correct me if I'm wrong but I think it'd create infinite loops all over the place. Each loop will slowly rise in HL and will get pushed further down the heap, but they'll still be there unnecessarily being checked and re-added.
@@mihaimanole2643 Good point, but I guess they're only finite by a technicality 🤣, I think you'd be creating up to 9 unnecessary recurring loops for every single node
@@hyper-neutrino well, afaik you can't say x < y < z because x < y will return boolean which will then be type co-erced to int to check y < z. Unless they implemented chained comparision operators in python which, given it's python they probably could have...
Part 2 annoyingly breaks some optimizations. Without the minimum steps, you can make the checks more aggressive. If you saw a tile entering from one direction, you don't care about the opposite direction anymore. In the same way, if you saw it with a lower step count, you don't have to bother. For part 1 that brought it from 17ms to 4ms. You can't do either in part 2, unfortunately.
Sign up at app.codecrafters.io/join?via=hyper-neutrino and try out Codecrafters today! You can get a taste of their many learning streams and try out their beta courses all completely for free (no credit card needed), and when you go to sign up, you'll get 40% off at checkout and support the channel! Thank you for watching :)
(Codecrafters has not sponsored this video directly and they did not have the opportunity to review any of this video, including the promotional segment.)
i spent all day trying to do this with dijkstra but i couldn’t figure it out. thanks for confirming i wasn’t too far off!
i think what i missed is that direction *and* number of steps have to be saved in the state
Thanks so much for this video! Today is the first day where I've REALLY got no idea. Never done a Dijkstra before! After watching your video multiple times, copying your entire code into my project and rewriting it into my language and writing my own version of heappush, it finally runs to completion! I mean, I get an answer of 12 for the sample data, but it runs 😅
same, less go
thank you for this 1-10, 2-4 node graph. It helped my with my code!
Found an "optimization" for your solution - you can remove "dr, dc != 0, 0" checks if you start with two tuples already in queue for two directions: right and down 🙂It worked for my copy of your algorithm written in TS, I also added "1" as "n" and "0" for "hl" for both
Also your solution has saved me from eternal pain - I got stuck looking at existing implementations of A* and Dijkstra for JS where they weren't using a separate "seen" set but worked with pre-made node grid which then get marked with boolean keys "visited" and "closed", and I just couldn't comprehend how could I ever use it for counting steps and tracking directions...
Definitely learning a lot from your videos!
nice
I would compute once
R = len(grid)
C = len(grid[0])
Thanks for this video. It realy helped me. But I seem to do something wrong, because my program (used Rust to implement it) took very long (some minutes for part 2). How long is your run time (and of others here in comments)?
In all the Dijkstra tutorials I've looked at, we have to have a data structure that stores the path distances from the source to every other node where the start vertex is initialized to 0 and all the other ones are initialized to infinity. Is there a reason why we don't do that here and somehow the Dijkstra works?
It's useful as an optimization. I forgot here so technically my solution isn't perfectly efficient but it doesn't matter too much in a context like this. It also allows you to get the minimum path length to any vertex from the fixed starting point, but again, we only care about a predetermined point in this problem.
@@hyper-neutrino Gotcha, thanks for responding. I don't have a good grasp on Dijkstra so I thought that data structure was required for the algorithm to work but clearly I'm mistaken.
@@noblerare At its core Dijkstras is basically breadth first search with a min heap to determine which node to explore next based on current distance estimates from the source (an unseen node in a connected graph will never be that node, since some node will always have a value less than infinity in the min heap). Instead of pre-calculating the distances as you mention, you can just check if a distance entry exists at all the first time you encounter a node, if it doesn’t you add the new distance. This would be the same mechanically if you had encountered an infinity entry as well (eg any infinity entry means we haven’t encountered the node yet in our exploration)
@@noblerare the optimization that hyper refers to I believe is that if you add all nodes up front, you can create your min heap in O(n) time basically by heapifying an array. If you add them as you go, each insertion is O(log n) and you do this n times so your total cost would be O(nlogn) instead for creating the min heap.
Why is there not a need to "relax" estimates in this implementation? You add the distances to the heap one time, but there is no update happening to these distance estimates like in typical Dijkstras
You don't strictly need to do distance updates; if a more efficient distance is found, it will just be added to the priority queue as well. In my day 11 to 17 stream, I do add a distance map and only add new items to the priority queue when a more optimal distance is found, but that's a constant-time optimization (theoretically speaking) and not necessary for the algorithm.
@hyper-neutrino thank you for the response. It makes sense now. Because the "seen" set does not store distances, when we pop the node from the priority queue, although we might have repeat states with different distances, only the lowest distance will get processed and the rest get ignored (popped from queue and discarded eventually). Per the original Dijkstras algorithm this is still correct in theory, because it's as if we still "relaxed" the state as much as possible by placing all of the candidate distances in queue, and once popped we are guaranteed the min distance is returned.
I don't quite understand how the lowest value ends up always being at the start of the heap, especially given that the values in the item could be anything, and you're only ever calling "push" - how does it know which is the lowest value? For example, if you'd chosen to put the location coordinates first, would this still work?
If you put the coordinates first, it wouldn't work, because the priority queue maintains order based on python sort order. the priority queue data structure allows you to insert elements and then remove the smallest one first every time; I may do a video in the future covering this ADT and how the heap implementation works
@@hyper-neutrino Thanks. I'd missed the implementation detail that if `item` is a tuple, it'll sort by each property in turn.
Isn't A* traversal >= Dykstra? I tried implementing an A* and not spotting an error in my code, but not working. At a high level, could I use A* instead of Dykstra and solve problem you think?
Dijkstra is a subset of A* where the potential from your heuristic is always zero. It will help improve the performance of just Dijkstra because your heap sort will favor paths that are closer to the end.
Hi @hyper-neutrino, why checking for distance minimization won't work here? I tried to keep track of the shortest distance / path like in normal dijkstra:
new_hl = hl+ grid[nr, nc]
if new_hl < distances[nr, nc]:
distances[nr, nc] = new_hl
heappush(...)
For both going straight and turning left and right, but it gives me the wrong result. Any ideas?
You need to also keep track of dr, dc, and n
What if I skip the seen set! I think it’s working without it. I may insert some loops in the heap queue but is not a big deal.
It may work, but it will be slower and in some cases it will become unacceptably slow if you don't do this
Correct me if I'm wrong but I think it'd create infinite loops all over the place. Each loop will slowly rise in HL and will get pushed further down the heap, but they'll still be there unnecessarily being checked and re-added.
@@BlazzaBlu I agree with all but the loops will not be infinite, they will stop when the bottom right corner is met.
@@mihaimanole2643 Good point, but I guess they're only finite by a technicality 🤣, I think you'd be creating up to 9 unnecessary recurring loops for every single node
Isn't 0
It isn't, but I am curious why you think it is, as it may help me explain why this is correct.
@@hyper-neutrino well, afaik you can't say x < y < z because x < y will return boolean which will then be type co-erced to int to check y < z. Unless they implemented chained comparision operators in python which, given it's python they probably could have...
@@professornumbskull5555 Yup, comparison ops do chain in python (see docs 6.10)
in python 0
Part 2 annoyingly breaks some optimizations. Without the minimum steps, you can make the checks more aggressive. If you saw a tile entering from one direction, you don't care about the opposite direction anymore. In the same way, if you saw it with a lower step count, you don't have to bother. For part 1 that brought it from 17ms to 4ms. You can't do either in part 2, unfortunately.