4
\$\begingroup\$

This code is a bidirectional BFS search. Given any two points in a matrix having 0's and 1's, I would like to find if there exists a path between them. Also note that it is forbidden to enter a cell that has a value of 0.

One note I would like to make about the code is that I have maintained a duplicate matrix to check if a particular cell has been visited by the source/destination.

Can someone please let me know if there are any discrepancies in what I have implemented and how I can improve the time efficiency of this? I am new to Python.

import copy



def path_exists(grid, queries):
    #iterate through queries.
    result=[]
    for (x1,y1,x2,y2) in queries:
        print "query",x1,y1,x2,y2
        if isValidIndex((x1,y1),(x2,y2),grid) != 0:
            result.append(findPath(x1,y1,x2,y2,grid))
        else:
            result.append(0)

    return result


def isValidIndex(startIndex,endIndex,grid):
    if startIndex[0] >= len(grid) or startIndex[0] < 0 or startIndex[1] >= len(grid[0]) or startIndex[1] < 0 or endIndex[0] >= len(grid) or endIndex[0] < 0 or endIndex[1] >= len(grid[0]) or endIndex[1] < 0 :
        return 0
    return 1

def findPath(x1,y1,x2,y2,grid):
    queue1=[[x1,y1]]
    queue2=[[x2,y2]]

    bool_grid = copy.deepcopy(grid)

    source_path = 0
    dest_path = 0

    while(1):
       if len(queue1) > 0:
           if find_path_from_source(queue1,grid,bool_grid,3) == 1:
               return 1

       if len(queue2) > 0:
           if find_path_from_source(queue2,grid,bool_grid,4) == 1:
               return 1

       if len(queue1) == 0 and len(queue2) == 0:
           return 0


def find_path_from_source(queue,grid,bool_grid,val):
    x=queue[0][0]
    y=queue[0][1]
    other_val = val

    if val == 3:
        other_val = 4
    else:
        other_val = 3


    if x + 1 < len(grid):
        if bool_grid[x+1][y] == other_val:
            return 1
        elif bool_grid[x+1][y] == 1:
            bool_grid[x+1][y] = val
            queue.append([x+1,y])

    if y + 1 < len(grid[0]):
        if bool_grid[x][y+1] == other_val:
            return 1
        elif bool_grid[x][y+1] == 1:
            bool_grid[x][y+1] = val
            queue.append([x,y+1])

    if x - 1 >= 0:
        if bool_grid[x - 1][y] == other_val:
            return 1
        elif bool_grid[x - 1][y] == 1:
            bool_grid[x - 1][y] = val
            queue.append([x - 1 , y])

    if y - 1 >= 0:
        if bool_grid[x][y - 1] == other_val:
            return 1
        elif bool_grid[x][y - 1] == 1:
            bool_grid[x][y - 1] = val
            queue.append([x, y - 1])

    queue.pop(0)


grid =  [[1,0,0,1,1],
         [0,1,1,1,1],
         [1,1,0,1,1],
         [0,1,1,0,1],
         [1,1,1,0,1]]

queries=((1,2,2,3),(0,0,1,1),(2,0,0,4),(5,0,2,5),(4,4,0,0),(0,4,4,4))


x = path_exists(grid,queries)

print x
\$\endgroup\$
2
\$\begingroup\$
  • isValidIndex handling two "indices" seems wrong. At least the condition you spell becomes too long. Besides, the condition looks somewhat inside-out. Consider

    def isValidIndex(index, grid):
        return 0 <= index[0] < len(grid) and 0 <= index[1] < len(grid[0])
    

    That said, AFNP principle tells that you don't really need this function at all:

        for (x1,y1,x2,y2) in queries:
            try:
                result.append(findPath(x1,y1,x2,y2,grid))
            except IndexError:
                results.append(0)
    
  • find_path_from_source has an execution path which returns nothing. Here you can get away with it, but the practice is in generally dangerous and indicates sloppy coding.

  • The repetitive code in find_path_from_source should be wrapped in the loop:

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            try:
                if bool_grid[x + dx][y + dy] == other_val:
                    return 1
                if bool_grid[x + dx][y + dy] == 1:
                    bool_grid[x + dx][y + dy] = val
                    queue.append([x + dx, y + dy])
            except IndexError:
                    pass
    
  • The bool_grid name is misleading. What is bool about it?

  • Copying a large grid may hurt the performance. An alternative is to compare visited cells: once they have a common element, the path is found. Implementing them as sets may make it quite fast. Of course, when in doubt, profile.

\$\endgroup\$
  • \$\begingroup\$ wouldnt the exception handling be slower than prechecking for conditions ? \$\endgroup\$ – Sujith Apr 18 '18 at 19:11
  • \$\begingroup\$ @Sujith In languages like C++ and Java exceptions are heavy, and are only used as the last resort. Not in Python. Python is designed around lightweight exceptions (in fact, even the simple things like for loop use them under the hood). \$\endgroup\$ – vnp Apr 18 '18 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.