# BFS shortest path for Google Foobar challenge “Prepare the Bunnies' Escape”

This is the Google Foobar challenge "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


I found a couple solutions but none seem to be optimal enough.

Solution in Python: BFS shortest path for Google Foobar "Prepare the Bunnies' Escape"

I tried the recommendations in this answer but I am still getting a "time-limit-exceeded" error and I did not have any means to confirm whether the optimisations happened and to what extent they worked. I am fairly new to Python so I might have missed some basic details. Is there any more room for optimisation?

My code after following the instructions is as follows:

from collections import deque

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__

@memodict
neighbors = (
(point[0] - 1, point[1]),
(point[0], point[1] - 1),
(point[0], point[1] + 1),
(point[0] + 1, point[1]))

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

def removable(maz, ii, jj):
counter = 0
for p in adjacent_to(((len(maz), len(maz[0])), (ii, jj))):
if not maz[p[0]][p[1]]:
if counter:
return True
counter += 1
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 = set()
for i in xrange(dims[0]):
for j in xrange(dims[1]):
if maze[i][j] == 1 and removable(maze, 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 wall in passable_walls:
temp_maze = maze
if wall:
temp_maze[wall[0]][wall[1]] = 0

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

q = deque()
q.append(end_point)

while q:
curr = q.popleft()

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.append(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

• You can always use timeit or cProfile on both version to check if improvements happened. – Mathias Ettinger Jan 6 '17 at 9:43
• the changes do improve performance but for my test case it seems to be not enough. – Tanzeel Jan 6 '17 at 22:30

The algorithm in the post is to iterate over the walls, and for each wall, to remove that wall from the maze, and then solve the maze using breadth-first-search.

If the maze is $n×n$, then there are $Θ(n^2)$ walls, and it takes $Θ(n^2)$ to do a breadth-first search on the resulting maze, for $Θ(n^4)$ overall runtime. No wonder you are exceeding the time limit.

This would have runtime $Θ(n^2)$.