Is your path finding algorithm the dijkstra one? Thanks, it was very clear how it works, maybe because it in javascript :), I used it for my solution for part one.
But I didn't understand how you choose the next step exactly. It works, but I can't see where you break the ties in reading order. Anyhow, nicely done, learned how to find shortest route with your code.
Hi @askeroff
, thanks!! Yes, I'm using Dijkstra's algorithm (even though I didn't explicitly mention it in the code), but it's implemented on getMinimumDistance function, where I basically do the following steps to get the minimum step between "start" and "end" squares:
create a map for the distances of all squares and set each one of them as Number.POSITIVE_INFINITY
create a set to mark unvisited squares and add every square to it
set "current" as the unvisited square with the lowest distance (or the "start" square in the beginning)
for each unvisited unblocked neighbors of "current", update the distance to the minimum between distance(current)+1 and the neighbor's current distance.
mark "current" as visited (by removing it from the unvisited squares set)
go back to step 3 and repeat until there are no more unvisited squares
The final distance between "start" and "end" is the smallest distance of all "end"'s unblocked neighbors.
Also, to break the ties in the reading order, it's all in getAdjacents function, where I look for the following neighbor squares and return in their reading order.
Considering we're getting adjacents for position X,Y, N=max(X) and M=max(Y)
Is your path finding algorithm the dijkstra one? Thanks, it was very clear how it works, maybe because it in javascript :), I used it for my solution for part one.
But I didn't understand how you choose the next step exactly. It works, but I can't see where you break the ties in reading order. Anyhow, nicely done, learned how to find shortest route with your code.
Hi @askeroff , thanks!! Yes, I'm using Dijkstra's algorithm (even though I didn't explicitly mention it in the code), but it's implemented on
getMinimumDistance
function, where I basically do the following steps to get the minimum step between "start" and "end" squares:Number.POSITIVE_INFINITY
The final distance between "start" and "end" is the smallest distance of all "end"'s unblocked neighbors.
Also, to break the ties in the reading order, it's all in
getAdjacents
function, where I look for the following neighbor squares and return in their reading order.Considering we're getting adjacents for position X,Y, N=max(X) and M=max(Y)
In other words,
Oh, awesome. I got it. I want to come back after I've done others and revisit this problem with breadth-first-search. Maybe it'll be faster.