I have been working on Google Foobar since a few days ago. I am currently in the third level but is stuck in the second challenge of "Prepare the Bunnies' Escape."
I have checked this post but it did not fully resolve my problem in Google Foobar as it is still giving me Time limit exceeded errors.
For reference, here is the 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:
7Input:
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
What I have done is create a graph based on the matrix and apply the shortest path algorithm (I am not sure what the algorithm is exactly called).
The code I have below runs and gives me the proper length of the shortest path.
class Node(object):
def __init__(self, identity, x, y):
self.neighbours = []
self.identity = identity
self.coordinates = (x, y)
def addNeighbour(self, node_key):
self.neighbours.append(node_key)
class Graph(object):
def __init__(self, matrix):
self.matrix = matrix
self.passable_walls = set()
self.nodes = {}
def create(self):
length = len(self.matrix)
for row in range(length):
for col in range(length):
identity = 0
if self.matrix[row][col] == 1:
identity = 1
node = Node(identity, row, col)
# Get the neighbours
if self._hasNeighbour(row - 1, col): # Is the top cell there?
node.addNeighbour((row - 1, col))
if self._hasNeighbour(row + 1, col): # Is the bottom cell there?
node.addNeighbour((row + 1, col))
if self._hasNeighbour(row, col - 1): # Is the left cell there?
node.addNeighbour((row, col - 1))
if self._hasNeighbour(row, col + 1): # Is the right cell there?
node.addNeighbour((row, col + 1))
self.nodes[(row, col)] = node
def getWalls(self):
length = len(self.matrix)
traversed_walls = 0
for row in range(length):
for col in range(length):
if self.matrix[row][col] == 1:
self.passable_walls.add((row, col))
def findShortestPath(self, start, end, passable_wall, path=set()):
path.add(start)
if start == end:
return path
if start not in self.nodes:
return None
shortest = None
for node in self.nodes[start].neighbours:
if node not in path and (self.nodes[node].identity == 0 or self.nodes[node].coordinates == passable_wall):
curr_path = set(path)
new_path = self.findShortestPath(self.nodes[node].coordinates, end, passable_wall, curr_path)
if new_path:
if not shortest or len(new_path) < len(shortest):
shortest = new_path
return shortest
def _hasNeighbour(self, row, col):
length = len(self.matrix)
if row < 0 or col < 0 or row >= length or col >= length:
return False
return True
def answer(matrix):
graph = Graph(matrix)
shortest = None
matrix_length = len(matrix)
start_node = (0, 0)
exit_node = (matrix_length - 1, matrix_length - 1)
graph.create()
graph.getWalls()
for wall in graph.passable_walls:
curr_path = graph.findShortestPath(start_node, exit_node, wall, path=set())
if curr_path is not None:
if shortest is None:
shortest = len(curr_path)
else:
if len(curr_path) < shortest:
shortest = len(curr_path)
return shortest
When I run it using this line
print(answer([[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 0, 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, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 0, 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, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 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],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 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],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 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, 1, 1, 1, 1, 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]]))
It takes 0.992 seconds to get the shortest path length according to cProfile. Using cProfile reveals that the bottleneck is the shortest path algorithm (def findShortestPath(...)).
Is there a problem with my algorithm? How could I improve it? What would be a better approach?
