2
\$\begingroup\$

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


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

     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

             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.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
\$\endgroup\$
  • 1
    \$\begingroup\$ You can always use timeit or cProfile on both version to check if improvements happened. \$\endgroup\$ – Mathias Ettinger Jan 6 '17 at 9:43
  • \$\begingroup\$ the changes do improve performance but for my test case it seems to be not enough. \$\endgroup\$ – Tanzeel Jan 6 '17 at 22:30
8
\$\begingroup\$

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)\$.

\$\endgroup\$
  • \$\begingroup\$ Hi Gareth. What is the intuition behind this approach. Please advise. \$\endgroup\$ – Pbd Jun 11 at 20:17

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.