# 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
def adjacent_to((maze_dim, point)):
neighbors = (
(point - 1, point),
(point, point - 1),
(point, point + 1),
(point + 1, point))

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

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

def answer(maze):

path_length = 0

if not maze:
return

dims = (len(maze), len(maze))
end_point = (dims-1, dims-1)

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

shortest_path = 0
best_possible = dims + dims - 1

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

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

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

q = deque()
q.append(end_point)

while q:
curr = q.popleft()

if curr == (0,0):
break

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

stat_mat[curr][curr] = '+'  # mark it as visited

if path_mat+1 <= best_possible:
break

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

return shortest_path


## 1 Answer

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.

Instead, consider the following approach:

1. Run a breadth-first search starting at the prison door, to find the distance of each passable space from the prison door.

2. Run another breadth-first search starting at the escape pod, to find the distance of each passable space from the escape pod.

3. Now iterate over the walls, and consider removing each wall in turn. You know the distance of each passable space from the prison door and the escape pod, so you can immediately work out the length of the shortest route that passes through the space left by the wall you just removed.

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

• Hi Gareth. What is the intuition behind this approach. Please advise. – Pbd Jun 11 '19 at 20:17