BFS shortest path for Google Foobar "Prepare the Bunnies' Escape"

Question

This is the Google Foobar puzzle "Prepare the Bunnies' Escape":

You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left \$(0,0)\$ and the door into an escape pod is at the bottom right \$(w-1,h-1)\$.

Write a function answer(map) that generates the length of the shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed.

Test cases

Input:

maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]

Output:

7

Input:

maze = [[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]]

Output:

11

My approach is to make a list of removable walls and then by removing them one at a time in a loop, do a BFS for the shortest path. At the end, I return the shortest path overall.

I have the following code that works. However, when I deal with larger matrices, it becomes very slow and I can't get past the test code due to exceeding the time limit.

I was wondering if there is a problem in my algorithm or there would be a better approach to this problem.

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)


def adjacent_to(maze_dim, point):
    neighbors = (
        (point[0]-1, point[1]),
        (point[0], point[1]-1),
        (point[0], point[1]+1),
        (point[0]+1, point[1]))

    for p in neighbors:
        if 0 <= p[0] < maze_dim[0] and 0 <= p[1] < maze_dim[1]:
            yield p


def removable(maz, ii, jj):
    counter = 0
    for p in adjacent_to((len(maz),len(maz[0])), (ii, jj)):
        if maz[p[0]][p[1]] == 0:
            counter += 1
        
    if counter >= 2:
        return True
    else:
        return False


def answer(maze):

    path_length = 0

    if not maze:
        return

    dims = (len(maze), len(maze[0]))
    end_point = (dims[0]-1, dims[1]-1)

    # list of walls that can be removed
    passable_walls = [0]
    for i in xrange(dims[0]):
        for j in xrange(dims[1]):
            if maze[i][j] == 1 and removable(maze, i, j):
                passable_walls.append((i, j))

    shortest_path = 0
    best_possible = dims[0] + dims[1] - 1

    path_mat = [[None] * dims[1] for _ in xrange(dims[0])]  # tracker matrix for shortest path
    path_mat[dims[0]-1][dims[1]-1] = 0  # set the starting point to destination (lower right corner)

    for i in xrange(len(passable_walls)):
        
        temp_maze = maze
        if passable_walls[i] != 0:
            temp_maze[passable_walls[i][0]][passable_walls[i][1]] = 0 

        stat_mat = [['-'] * dims[1] for _ in xrange(dims[0])]  # status of visited and non visited cells

        q = Queue()
        q.enqueue(end_point)

        while not q.isEmpty():
            curr = q.dequeue()

            if curr == (0,0):
                break
            
            for next in adjacent_to(dims, curr):
                if temp_maze[next[0]][next[1]] == 0:  # Not a wall
                    temp = path_mat[curr[0]][curr[1]] + 1
                    if temp < path_mat[next[0]][next[1]] or path_mat[next[0]][next[1]] == None:  # there is a shorter path to this cell
                        path_mat[next[0]][next[1]] = temp
                    if stat_mat[next[0]][next[1]] != '+':  # Not visited yet
                        q.enqueue(next)

            stat_mat[curr[0]][curr[1]] = '+'  # mark it as visited
        
        if path_mat[0][0]+1 <= best_possible:
            break        

    if shortest_path == 0 or path_mat[0][0]+1 < shortest_path:
        shortest_path = path_mat[0][0]+1

    return shortest_path


maze = [
[0, 0, 0, 0, 0, 0], 
[1, 1, 1, 1, 1, 0], 
[0, 0, 0, 0, 0, 0], 
[0, 1, 1, 1, 1, 1], 
[0, 1, 1, 1, 1, 1], 
[0, 0, 0, 0, 0, 0]
]

# maze = [
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
# [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], 
# [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], 
# [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], 
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# ]

# maze = [
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
# [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], 
# [0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], 
# [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], 
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], 
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
# [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# ]
print answer(maze)

Answer 1

One problem might be your custom Queue class. The list you use as underlying data structure has O(n) behaviour for list.insert(0, item).

It would be better to use a collections.deque, for which insertion and poping from both sides is O(1).

You would use it like this:

q = collections.deque()
for value in range(10):
    q.append(value)
...
while q:
    next_value = q.popleft()
    # Do something with `next_value`

---

In removable your return logic can be short-circuited:

def removable(maze, ii, jj):
    zeros = 0
    for y, x in adjacent_to((len(maze),len(maze[0])), (ii, jj)):
        if not maze[y][x]:
            if zeros:
                return True
            zeros += 1
    return False

This way you exit early after finding the second 0 already.

I also used the more readable name maze, split up p into an x and y coordinate and used the fact that 0 == False in Python.

---

When looping over passable_walls you should directly loop over the elements, not the indices:

for wall in passable_walls:
    temp_maze = maze
    if wall:
        temp_maze[wall[0]][wall[1]] = 0 
    ...

Here I also used the fact that 0 == False in Python.

---

Implementing these first two changes, the running time changes for the medium size maze from 89492 function calls in 0.042 seconds to 61763 function calls in 0.035 seconds, so not really a lot of improvement. The large maze takes about 30s.

Profiling the code (run it with python -m cProfile maze.py) yields that 42761 of those calls are a call to adjacent_to. So it might make sense to speed that function up. One possibility for this is caching the results of the function, because with 40k calls for less than 300 cells for the large maze there are bound to be repeated calls.

The fastest cache for a single valued function I know is this one:

def memodict(f):
    """ Memoization decorator for a function taking a single argument """
    class memodict(dict):

        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return memodict().__getitem__

This could be modified to allow for multiple values, or we could just always supply the arguments as a tuple:

@memodict
def adjacent_to((maze_dim, (i, j))):
    neighbors = (
        (i - 1, j),
        (i, j - 1),
        (i, j + 1),
        (i + 1, j))

    return [p for p in neighbors if 0 <= p[0] < maze_dim[0] and 0 <= p[1] < maze_dim[1]]


def removable(maze, i, j):
    counter = 0
    for x, y in adjacent_to(((len(maze), len(maze[0])), (i, j))):
        if not maze[x][y]:
            if counter:
                return True
            counter += 1
    return False


def answer(maze):
    ...
    while q:
        ...
        for next in adjacent_to((dims, curr)):
            ...

Here I had to remove the generator from adjacent_to as well, because it messes with the caching.

This solves the medium maze with 28616 function calls in 0.020 seconds and the large maze with 22233918 function calls in 14.493 seconds. So it is a speed-up of about a factor 2.

At this time most of the time spent is in the logic of answer (12 out of the 14s). The rest is equally shared by dict.__getitem__, deque.append and deque.popleft.

---

For further speed improvement, consider again passable_walls. Currently it is a list. But it might as well be a set, because it is enough to note that a wall is removable, having a pair (i,j) in there twice does not add any information:

def answer(maze):
    ...
    passable_walls = set()
    for i in xrange(dims[0]):
        for j in xrange(dims[1]):
            if maze[i][j] == 1 and removable(maze, i, j):
                passable_walls.add((i, j))
    ...
    for wall in passable_walls:
        temp_maze = maze
        if wall:
            temp_maze[wall[0]][wall[1]] = 0
        ...

This, finally, executes with 5470021 function calls in 3.590 seconds for the large maze.

Answer 2

The approach followed by the question poster and also in the other answers use BFS in a loop to find the answer. If there're a lot of walls that cannot be passed, the time complexity can get quite high. To be precise, the time complexity would be \$O(n * m * j)\$ where \$n\$ and \$m\$ are the number of rows and columns respectively and \$j\$ is the number of walls.

The solution that I propose solves the problem in single BFS loop, so it is much faster than other suggested solutions.

Logic:

The question can be solved using BFS with the following modifications:

1. Each path that'd otherwise have all 0s in a standard BFS algo can have a single 1.

2. In the BFS queue, each node, in addition to keeping a track of the x and y coordinates, will also store the number of steps (path length) taken to reach there and if the path for that node has already traversed over a 1 or not. So, each node in the queue will have the format - [[row, col], num_steps, one_traversed].

   So while it may look like we need to store the whole paths in the BFS traversal, what we actually need to store is if a 1 has been traversed in the path or not. So, every node will store that info for itself.

3. We will maintain a visited grid that will keep a track of all nodes that have been visited (to avoid loops) but here's the tricky part - instead of having only 1s and 0s to represent visited or not, this grid will have 4 possible values:

   • -1 is the initial value
   • 0 means visited by a path having NO 1s (all 0s)
   • 1 means visited by a path having a 1
   • 2 means visited by both types of paths

   Reason:

   While in usual BFS questions, we avoid visiting a node after it has been visited once, in this problem every node in the maze can be visited twice before being marked for not visiting again. This is because:

   • If a node is being visited for the first time by a path consisting of only 0s, it should not be visited again by any another path consisting of only 0s as that other path would either be of the same length (in which case it doesn't matter) or longer (in which case we anyway wouldn't want to consider it as that path is reaching a node which has already been traversed by a shorter path consisting of all 0s).

     Same logic goes for a node that has been visited by a path which had traversed a 1 and is now again being visited by a path having a 1 (we will reject the later path as it is either same or longer than the first path).

   • However if a node that was earlier visited by a path having a 1 is now being visited by a path having only 0s, we want to consider this later path too. Why? Because it is possible that the earlier path which reached this node after traversing a 1 may not be able to reach the destination as it may reach a point where it needs to traverse an additional 1 for reaching the destination but as it has already traversed a 1, it cannot proceed further. So, this new path which may be longer than the earlier one, but hasn't traversed a 1 yet, may be able to traverse the additional 1.

     Example

     

     In this example while the red path reaches the node [2, 0] first, it is not the correct path as it gets blocked at [3, 0]. Therefore, we have to also consider the green path to pass through [2, 0] even if it is longer than the red one.

And finally, the base case is to stop when you reach the bottom right node in the maze. (The question states that there will always be a solution, so no check for the no solution case.)

Code:

grid = [[0, 0, 0, 0],
[1, 1, 1, 0],
[0, 0, 0, 0],
[1, 1, 1, 1],
[0, 1, 1, 1],
[0, 0, 0, 0]]  # using the name grid instead of maze

num_rows = len(grid)
num_cols = len(grid[0])

def is_valid(r, c):
    return True if (0 <= r < num_rows and 0 <= c < num_cols) else False

def get_neighbours(r, c):
    up = [r - 1, c]
    down = [r + 1, c]
    left = [r, c - 1]
    right = [r, c + 1]

    neighbours = [down, right, up, left]
    valid_neighbour = list()

    for neighbour in neighbours:
        if is_valid(*neighbour):
            valid_neighbour.append(neighbour)

    return valid_neighbour

# queue format is [[row, col], num_steps, one_traversed]
queue = [[[0, 0], 1, 0]]

cols = list()
visited = list()

# visited matrix is used to keep track of visited nodes:
# -1 is default
# 0 means visited by a path having no 1s
# 1 means visited by a path having a 1
# 2 means visited by both paths - having 1 and 0s
for j in range(num_rows):
    visited.append([-1] * num_cols)

visited[0][0] = 0

# BFS
while queue:
    current_node = queue.pop(0)

    r, c, num_steps, one_traversed = current_node[0][0], current_node[0][
        1], current_node[1], current_node[2]

    # Base Case
    if r == num_rows - 1 and c == num_cols - 1:
        print(num_steps)

    neighbours = get_neighbours(r, c)

    for neighbour in neighbours:
        if visited[neighbour[0]][neighbour[1]] in [0, 1]:
            # the current node was previously visited with opposite one_traversed value, so consider it
            if visited[neighbour[0]][neighbour[1]] != one_traversed:
                one_traversed_now = 1 if grid[neighbour[0]][neighbour[1]] == 1 else one_traversed
                visited[neighbour[0]][neighbour[1]] = 2

                queue.append([[neighbour[0], neighbour[1]], num_steps + 1, one_traversed_now])
        elif visited[neighbour[0]][neighbour[1]] == -1:
            if grid[neighbour[0]][neighbour[1]] == 1 and one_traversed == 1:
                continue

            one_traversed_now = 1 if grid[neighbour[0]][neighbour[1]] == 1 else one_traversed

            visited[neighbour[0]][neighbour[1]] = one_traversed_now
            queue.append([[neighbour[0], neighbour[1]], num_steps + 1, one_traversed_now])

Example test cases: