Google Foobar challenge optimization

Question

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?

Readme.txt

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.

Constraints

• 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[0]):
        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[0]+offset[0], node.coord[1]+offset[1])
                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[0])-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[0]+offset[0], node.coord[1]+offset[1])
                if coord in tail_coords:
                    path_lengths.append(len(tail_nodes[tail_coords.index(coord)].path)+len(node.path)+1)

    return min(path_lengths)

Answer 1

It looks like you're trying to traverse all possible ways; this is very ineffective, something about \$O(4^{w*h})\$ time. You could try Lee's wave algorithm instead. Because you need only a length, you don't need anything after the expansion step; and then, build the same expansion map in a backward direction (from exit to entrance) and check all the neighbors of all walls for a minimal sum of neighbors from two maps to get the length of the best shortcut - total will be \$O((w*h)^2)\$.