Search path through one obstacle (Google Foobar: Prepare a rabbit escape)

Question

I'm having trouble resolving the Google Foobar question related to finding paths. My solution does not allow to run 2 test cases, the inputs and outputs of which are hidden.

Request:

You have maps of parts of the space station, each of which begins in the prison, exit and stop at the door to the rescue unit. The map is presented as a matrix of 0s and 1s, where 0s is the walkable space, and 1s is the impenetrable walls. The door from the prison is in the upper left corner (0,0) and the door to the rescue unit is at the bottom right (w-1, h-1).

Write a function response (map) that generates the shortest path from the prison door to the rescue container, where you are allowed to remove one wall as part of your remodeling plans. Path length is the total number of nodes you go through, counting the input and output nodes. The start and end positions are always passable (0). The card will always be solvable, although you may or may not need to remove the wall. The height and width of the map can be from 2 to 20. Movements can be performed only in the main directions; no diagonal movements are allowed.

Test cases

Inputs: (int) maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]

Output: (int) 7

Inputs: (int) 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: (int) 11

My code is:

 from queue import PriorityQueue # Grid class class Grid: # Initialized with dimensions to check later if all neighbor points are actually within the graph def __init__(self, width, height): self.width = width self.height = height self.walls = [] self.weights = {} self.wall_count = 0 # Find the cost of a certain destination node # Cost is reported as a tuple to account for going across a wall: (# of moves through a wall, # of normal moves) def cost(self, from_node, to_node): if to_node in self.walls: return self.weights.get(to_node, (1, 0)) else: return self.weights.get(to_node, (0, 1)) # Check if the location is actually within the graph def in_bounds(self, id): (x, y) = id return 0 <= x < self.width and 0 <= y < self.height # Find the adjacent nodes of a node (ie. the places it can go to) # Filters out any result which isn't on the graph using self.in_bounds def neighbors(self, id): (x, y) = id results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1)] if (x + y) % 2 == 0: results.reverse() # aesthetics results = filter(self.in_bounds, results) return results # Find the dimensions of the 2D list by finding the lengths of the outer and inner lists def dimensions_2d(xs): width = len(xs) height = len(xs[0]) return (width, height) # Returns all the positions of an element in a 2D list # In this case it used to find all walls (occurences of 1) to pass to the Grid object def index_2d(xs, v): results = [(x, y) for y, ls in enumerate(xs) for x, item in enumerate(ls) if item == v] return results # Djikstra search algorithm; mistakenly named "a_star" before # Returns both a dictionary of "destination" locations to "start" locations (tuples) as well as a dictionary of the calculated cost of each location on the grid def djikstra_search(graph, start, goal): # Priority Queue to select nodes from frontier = PriorityQueue() # Place our starting cost in frontier.put(start, (0, 0)) came_from = {} cost_so_far = {} came_from[start] = None cost_so_far[start] = (0, 0) while not frontier.empty(): # Get the element with the highest priority from the queue current = frontier.get() if current == goal: break # For every neighbor of the selected node for next in graph.neighbors(current): # The new cost of the neighbor node is current cost plus cost of this node - (1, 0) if it goes through a wall, (0, 1) otherwise new_cost = (cost_so_far[current][0] + graph.cost(current, next)[0], cost_so_far[current][1] + graph.cost(current, next)[1]) # If the node has not cost currently # OR if the number of walls traveled through is less than the current cost # AND if the number of normal steps taken is less than or the same as the current number if next not in cost_so_far or (new_cost[0] < cost_so_far[next][0] and sum(new_cost) <= sum(cost_so_far[next])): # Record it in both the cost and came_from dicts cost_so_far[next] = new_cost # Place the cost in the queue priority = new_cost frontier.put(next, priority) came_from[next] = current return came_from, cost_so_far # Find the length of the calculated path # Using the returned list of edges from djikstra_search, move backwards from the target end and increment the length until the start element is reached def path(grid, start, end): # Perform the search path = djikstra_search(grid, start, end) search = path[0] # If the end element cost travels through more than 1 wall return 0 if path[1].get(end)[0] > 1: return 0 # Otherwise move backwards from the end element and increment length each time # Once the start element has been reached, we have our final length length = 1 last = end while last != start: last = search.get(last) length += 1 return length # The "main" function def answer(maze): # Find all occurences of walls (1) in the 2D list walls = index_2d(maze, 1) # Find the x and y dimensions of the maze (required for the Grid object) dims = dimensions_2d(maze) # Create a new grid with our found dimensions grid = Grid(dims[0], dims[1]) # The start point will always be at (0,0) and the end will always be at the bottom-right so we define those here start = (0, 0) end = (dims[0] - 1, dims[1] - 1) # the walls variable locations are flipped, so reverse each of them to get the right wall positions grid.walls = [(y, x) for x, y in walls] # Return the length return path(grid, start, end) 

In my own testing (grids up to 7x7) this solution works without problems.

Any help (or unsuccessful cases) would be greatly appreciated!