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

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 search 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)

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

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

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]
# ]

• @gareth-rees, thank you for your edits. However, I intentionally left out its connection to Google Foobar problem and I believe it should be kept that way. I didn't want to post the direct solution for a problem that's supposed to be solved individually. I posted this after I had already posted my solution to foobar and simply was looking for ways to improve it as a general problem. So in my opinion, it would make sense to keep it a none Google-specific one, so searching problem name wouldn't return this. However, I would like to hear your argument before reverting it to its previous form. Jan 9 '17 at 22:46
• It's general practice here at Code Review to quote relevant parts of the text of programming challenges (see this answer on meta). There are several reasons: (i) it's helpful, when writing answers, to be able to consult the exact text of the programming challenge, not just the asker's summary; (ii) programming challenge websites often disappear (or in the case of the Google Foobar challenges, are not visible to the general public); (iii) credit where it's due. Jan 9 '17 at 22:50
• As for your problem, this answer might help. Jan 9 '17 at 22:52
• Thank you. As for your points, I agree with them all in general. However, just to give you more context, if I'm not mistaken, I remember foobar asking people not posting their solutions online. Since I was trying to get a general programming help independent of the problem, I tried to honor their request by skipping the connection. This way we are dealing with a maze algorithm problem and ways to improve the solution. So I think this covers all three of your points. p.s. starting BFS from two ends of the maze is very clever! :) Jan 9 '17 at 23:12
• FYI, this question is being discussed on meta. Jan 10 '17 at 22:19

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
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

...
while q:
...
...


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):

• Looks great. Thanks! This is very helpful. I used the profiler too and was aware of the first two points that you made. But using a caching mechanism and also replacing the list for passable_walls with a set is a great idea. Oct 4 '16 at 15:41