Programming Garbage Distance

January 01, 2017 | 3 Minute Read

There is a robot that collects garbage from a 2-D map of size m x n, where m is number of rows and n is number of columns. A robot starts at top-left (0,0) cell of the map and tries to find the shortest distance to a garbage. A cell with garbage has a value 9. There are obstacles on the map that is marked as 0, meaning robot cant visit or pass through that cell. For all other values the cell is accesible. Find the shortest distance to the garbage, in terms of moves needed to get to the garbage.

Conditions

• You cant modify the original map.
• The program must not create an array to track the entire map.
• The robot can add a new entry to a data structure for a cell it visits. On the fly is allowed.
• The garbage is guaranteed to be in the map.

Hints

• Use raster scan to build cell unique ids as you go.
• Keep track of the unique ids traversed with a data structure that has O(1) expected insert and search time.
• Start from 0,0 and use BFS to add the neighbors that are not visited.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def minimumGarbageDistance(lot):
    nodes = [[0, 0, -1]] #x,y, distance
    checked = set()
    m = len(lot)
    n = len(lot[0])

    while nodes:
        node = nodes.pop(0)
        x, y, d = node
        
        if 0<=x<m and 0<=y<n:
            uid = n*x + y
            if uid not in checked:
                checked.add(uid)
                newd = d + 1
                if lot[x][y] == 9: #garbage
                    return newd
                elif lot[x][y] == 1:  #flat landscape
                    nodes.append([x, y+1, newd])
                    nodes.append([x, y-1, newd])
                    nodes.append([x+1, y, newd])
                    nodes.append([x-1, y, newd])
                #else obstacle or 0
    return -1

if __name__=="__main__":   #test driver program 
   lot = [
            [1,1,1,1],
            [1,1,1,1],
            [0,0,0,1],
            [1,1,9,1]
         ]
   print minimumGarbageDistance(lot)

Problem: If you have multiple such robots or 1 robot and multiple ghosts, find who gets to the garbage first. You are given with a player coordinate and multiple ghosts coordinate inside the map.

Implement: findWinner (lot, player, ghosts)
Output: returns True if player gets to the garbage or False when ghost gets to the garbage first.
Do it in O(mn)

Cheers!