Shortest Path For Google Foobar (Prepare The Bunnies Escape)

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:

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

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
s

Basically you need a breadth-first search with a minor tweak:

• each node represents a cell in the grid (x- and y-coordinates),

• each node knows its "saldo" (how many walls it may penetrate).

What comes to that saldo, if a node has zero saldo, it may not generate those its neighbors that are occupied by wall. If saldo is \$s > 0\$, and the node has a wall neighbor node \$u\$, \$u\$ is generated with saldo \$s - 1\$.

The rest is breadth-first search: as soon you remove the exit node from the queue, just print its distance from the starting node:

```
import time
from collections import deque

class Node:

def __init__(self, x, y, saldo, grid):
self.x = x
self.y = y;
self.saldo = saldo
self.grid = grid

def __hash__(self):
return self.x ^ self.y

def __eq__(self, other):
return self.x == other.x and self.y == other.y

def get_neighbors(self):
neighbors = []
x = self.x
y = self.y
saldo = self.saldo
grid = self.grid
rows = len(grid)
columns = len(grid[0])

if x > 0:
wall = grid[y][x - 1] == 1
if wall:
if saldo > 0:
neighbors.append(Node(x - 1, y, saldo - 1, grid))
else:
neighbors.append(Node(x - 1, y, saldo, grid))

if x 0:
neighbors.append(Node(x + 1, y, saldo - 1, grid))
else:
neighbors.append(Node(x + 1, y, saldo, grid))

if y > 0:
wall = grid[y - 1][x] == 1
if wall:
if saldo > 0:
neighbors.append(Node(x, y - 1, saldo - 1, grid))
else:
neighbors.append(Node(x, y - 1, saldo, grid))

if y 0:
neighbors.append(Node(x, y + 1, saldo - 1, grid))
else:
neighbors.append(Node(x, y + 1, saldo, grid))

return neighbors

class GridEscapeRouter:

def __init__(self, grid, saldo):
self.grid = grid
self.rows = len(grid)
self.columns = len(grid[0])
self.saldo = saldo

def get_escape_route_length(self):
source = Node(0, 0, self.saldo, self.grid)
queue = deque([source])
distance_map = {source: 1}

while queue:
current_node = queue.popleft()

if current_node.x == self.columns - 1 and\
current_node.y == self.rows - 1:
return distance_map[current_node]

for child_node in current_node.get_neighbors():
if child_node not in distance_map.keys():
distance_map[child_node] = distance_map[current_node] + 1
queue.append(child_node)

return 1000 1000 1000 # Cannot escape

def milliseconds():
return int(round(time.time() * 1000))

start_time = milliseconds()
router = GridEscapeRouter(
[[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]],
1)

route_length = router.get_escape_route_length();
end_time = milliseconds()

print "Route length", route_length, "in", end_time - start_time, "milliseconds."

router = GridEscapeRouter([[0, 1, 1, 0],
[0, 0, 0, 1],
[1, 1, 0, 0],
[1, 1, 1, 0]],
1)
print router.get_escape_route_length()

router = GridEscapeRouter([[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]],
1)

print router.get_escape

StackExchange Code Review Q#153242, answer score: 13