Simple Python Explanation

  • 8

    We can use Dijkstra's algorithm to find the shortest distance from the ball to the hole. If you are unfamiliar with this algorithm, how it works is that we process events in priority order, where the priority is (distance, path_string). When an event is processed, it adds neighboring nodes with respective distance. To repeatedly find the highest priority node to process, we use a heap (priority queue or 'pq'), where we can add nodes with logarithmic time complexity, and maintains the invariant that pq[0] is always the smallest (highest priority.) When we reach the hole for the first time (if we do), we are guaranteed to have the right answer in terms of having the shortest distance and the lexicographically smallest path-string.

    When we look for the neighbors of a location in the matrix, we simulate walking up/left/right/down as long as we are inside the bounds of the matrix and the path is clear. If during this simulation we reach the hole prematurely, we should also stop. If after searching with our algorithm it is the case that we never reached the hole, then the task is impossible.

    def findShortestWay(self, A, ball, hole):
        ball, hole = tuple(ball), tuple(hole)
        R, C = len(A), len(A[0])
        def neighbors(r, c):
            for dr, dc, di in [(-1, 0, 'u'), (0, 1, 'r'), 
                               (0, -1, 'l'), (1, 0, 'd')]:
                cr, cc, dist = r, c, 0
                while (0 <= cr + dr < R and 
                        0 <= cc + dc < C and
                        not A[cr+dr][cc+dc]):
                    cr += dr
                    cc += dc
                    dist += 1
                    if (cr, cc) == hole:
                yield (cr, cc), di, dist
        pq = [(0, '', ball)]
        seen = set()
        while pq:
            dist, path, node = heapq.heappop(pq)
            if node in seen: continue
            if node == hole: return path
            for nei, di, nei_dist in neighbors(*node):
                heapq.heappush(pq, (dist+nei_dist, path+di, nei) )
        return "impossible"

  • 0

    Awesome solution! It'd be better if no variable renaming.

  • -1

    said in Simple Python Explanation:


    I guess you are not posting the exact answer to the problem? Otherwise the return condition is not correct? The ball can pass the hole, not necessary stop on the hole.

  • 0

    @awice Thank you. One observation is one of the short paths to the hole will have the least turns. That's why it can return as soon as a hole is hit.

  • 0

    Why are we guaranteed to have the right answer lexicographically on the first instance of reaching the hole?

  • 2

    @livelearn IIRC, the problem statement wants the lexicographically smallest among the paths with the minimum distance. When we add (distance, path, ...) to our minheap and pop nodes from it, we take the lexicographically smallest path first. Note that when we pop a node of distance D for the first time, necessarily all paths to consider of distance D must be in the heap, since they are all constructed from nodes distance less than D which have already been processed.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.