DEV Community

Discussion on: AoC Day 15: Beverage Bandits

Collapse
themindfuldev profile image
Tiago Romero Garcia • Edited on

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:

  1. create a map for the distances of all squares and set each one of them as Number.POSITIVE_INFINITY
  2. create a set to mark unvisited squares and add every square to it
  3. set "current" as the unvisited square with the lowest distance (or the "start" square in the beginning)
  4. for each unvisited unblocked neighbors of "current", update the distance to the minimum between distance(current)+1 and the neighbor's current distance.
  5. mark "current" as visited (by removing it from the unvisited squares set)
  6. 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.

Thread Thread
themindfuldev profile image
Tiago Romero Garcia

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)

  1. if X > 0, adjacent on X-1,Y
  2. if Y > 0, adjacent on X,Y-1
  3. if Y < M-1, adjacent on X,Y+1
  4. if X < N-1, adjacent on X+1,Y

In other words,

  1. Neighbor on the line above
  2. Neighbor on the same line, to the left
  3. Neighbor on the same line, to the right
  4. Neighbor on the line below
Thread Thread
askeroff profile image
Javid Askerov • Edited on

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.