Google Foobar Prepare the Bunnies' Escape (BFS/A* search, Python)

Question

I've been taking the Google Foobar challenge and I'm stuck with a solution I'm pretty certain is correct, but won't pass 2 tests of the challenge.

Given a 2D Array, consisting of 0s and 1s, as an input, where 0s are passable space and 1s are walls, the task is to find the shortest path form the upper left corner to the lower right corner. There's a minor twist where you can remove a wall once in your path.

My approach was simply using BFS or A* search while mainting a boolean to keep track if the removal of a wall has already been used.

The provided test cases are solution([[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]) == 7 and solution([[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]]) == 11

Below is my code where I initiate a queue with the start node, during the queue I check if goal reached or node already visited, else check possible neighbors and add them to the queue if they are in bounds, their number is a 0 or if their number is a 1 and removal is still True, updating the steps taken and the boolean accordingly. In addition, I've used the Manhattan distance from nodes to the goal node as my heuristic.

def solution(map):
    # A* using Manhattan distance with 1 optional removal of a wall
    door = (len(map) - 1, len(map[0]) - 1)
    visited = set()
    queue = [[True, 1, (0, 0)]]
    # While queue, if current node is door, return len of path, if node already visited, continue
    # If not, mark as visited, add all possible moves to queue and sort queue by steps + Manhattan distance
    # Optionally remove a wall - single-use
    while queue:
        e = queue.pop(0)
        removal, steps, node = e[0], e[1], e[2]
        print(node)
        if node in visited:
            continue
        visited.add(node)
        for dy, dx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            ny, nx = node[0] + dy, node[1] + dx
            if 0 <= ny <= door[0] and 0 <= nx <= door[1]:
                if (ny, nx) == door:
                    return steps + 1
                if map[ny][nx] == 0:
                    queue += [[removal, steps + 1, (ny, nx)]]
                elif removal:
                    queue += [[False, steps + 1, (ny, nx)]]
        queue = sorted(queue, key=lambda x: x[1] + door[0] - x[2][0] + door[1] - x[2][1] + 1)
        print (queue)

I'd be very glad for any kind of input to what could be wrong as I've spent way too much time figuring this out already ^^' Thank you very much in advance!

Answer 1

I'm an idiot and forgot to add the removal state when adding to the visited set to allow multiple ways to get to a node with or without removing a node... Below is the correct implementation

def solution(map):
    # A* using Manhattan distance with 1 optional removal of a wall
    door = (len(map) - 1, len(map[0]) - 1)
    visited = set()
    queue = [[True, 1, (0, 0)]]
    # While queue, if neighbor node is door, return steps + 1, if node (under removal state) already visited, continue
    # If not, mark as visited, add all possible moves to queue and sort queue by steps + Manhattan distance
    while queue:
        e = queue.pop(0)
        removal, steps, node = e[0], e[1], e[2]
        if (removal, node) in visited:
            continue
        visited.add((removal, node))
        for dy, dx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            ny, nx = node[0] + dy, node[1] + dx
            if 0 <= ny <= door[0] and 0 <= nx <= door[1]:
                if (ny, nx) == door:
                    return steps + 1
                elif map[ny][nx] == 0:
                    queue += [[removal, steps + 1, (ny, nx)]]
                elif removal:
                    queue += [[False, steps + 1, (ny, nx)]]
        queue = sorted(queue, key=lambda x: x[1] + door[0] - x[2][0] + door[1] - x[2][1] + 1)