I am trying to solve Google Foobar challenge
prepare-the-bunnies-escape using my own approach, instead of BFS. I attempt to solve two ends of the maze and try to connect them together. It works, but it exceeds Google's time limits. How can I optimize the program/algorithm to meet google standards?
You have maps of parts of the space station, each starting at a work area 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 station 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 solution(map) that generates the length of the shortest path from the station 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.
- Your code will run inside a Python 2.7.13 sandbox. All tests will be run by calling the solution() function.
- Standard libraries are supported except for bz2, crypt, fcntl, mmap, pwd, pyexpat, select, signal, termios, thread, time, unicodedata, zipimport, zlib.
- Input/output operations are not allowed.
- Your solution must be under 32000 characters in length including new lines and and other non-printing characters.
"""Google foobar challenge attempt foobar:~/prepare-the-bunnies-escape """ r1 = ((1, 0), (-1, 0), (0, 1), (0, -1)) r2 = ((2, 0), (-2, 0), (0, 2), (0, -2)) class Out(Exception): pass class Node(object): def __init__(self, coord, parent=None): self.coord = coord self.parent = parent self.index = 0 if self.parent is None: self.depth = 0 self.path =  else: self.depth = self.parent.depth+1 self.path = self.parent.path*1 # copy self.path.append(coord) self.children =  def add_child(self, coord): if coord not in self.path: self.children.append(self.__class__(coord, parent=self)) def next(self): if self.index+1 > len(self.children): if self.parent is None: raise Out else: return self.parent.next() else: self.index += 1 return self.children[self.index-1] def get_top(self): return self if self.parent is None else self.parent.get_top() def get(arr, coord): y, x = coord if 0 <= y < len(arr) and 0 <= x < len(arr): return arr[y][x] else: return -1 def walkthru(arr, node, dest): """Solve maze.""" try: while True: if node.coord == dest: break for offset in r1: coord = (node.coord+offset, node.coord+offset) if get(arr, coord) == 0: if coord not in node.path: node.add_child(coord) node = node.next() except Out: return node def traverse(node): """Get all child nodes of node.""" result =  result.append(node) if node.children: for child in node.children: result.extend(traverse(child)) return result def solution(m): """Return minimum path (always solvable).""" head_coord, tail_coord = ((0, 0)), ((len(m)-1, len(m)-1)) head, tail = Node(head_coord), Node(tail_coord) walkthru(m, head, tail) walkthru(m, tail, head) head_nodes, tail_nodes = (traverse(_) for _ in (head, tail)) tail_coords = [node.coord for node in tail_nodes] path_lengths =  for node in head_nodes: if node.coord == tail_coords: path_lengths.append(len(node.path)) else: for offset in r2: coord = (node.coord+offset, node.coord+offset) if coord in tail_coords: path_lengths.append(len(tail_nodes[tail_coords.index(coord)].path)+len(node.path)+1) return min(path_lengths)