Python breadth first shortest path for Google foo bar (prepare the bunnies escape) [closed]

Question

I am working on the following problem, and I think that I have it mostly solved, however some of the test cases are failing:

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

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

As mentioned before, I believe I have the better part of the problem figured out (although I do not think my code is optimized, and I could be wrong) but out of hidden test cases 1 through 5, case 3 and 4 are failing.

While I do not by any means expect anybody to give me the answer, I would be interested to hear if anybody could nudge me in the right direction. Maybe there is an edge case that I'm missing? Maybe I have a small mistake somewhere? Maybe my logic is just plain wrong? I've written all of this code from scratch, and tried to be as descriptive as possible with my variable names and comments.

I would also like to mention that the above 2 test cases are passing. Below, I will provide my code as well as some of my own tests cases. Thank you for taking the time to hear me out.

Also, I would like to apologize in advance if my code is unorganized or sloppy. I've been copying and pasting around a lot and have been doing my best to stay organized under pressure.

import sys
import Queue

# 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]]
# maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]
# maze = [[0, 1], [1, 0]]
# maze = [[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]]
# maze = [[0,1,1,0,0],
#       [0,1,0,1,0],
#       [0,0,0,1,0],
#       ]
# maze = [[0,0,0,0,0],
#       [1,1,1,1,1],
#       [1,1,0,0,1],
#       [0,0,1,0,0],
#       ]
# maze = [[0,1,1],
#       [1,1,1],
#       [0,0,0],
#       ]
# maze = [[0, 1, 1, 0, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0]]
# maze = [[0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0]
#       ]
# maze = [[0,0,1],
#       [0,0,1],
#       [0,0,1],
#       [0,1,1],
#       [1,0,1,1],
#       [0,0,0,0],
#       [0,1,1,0,1],
#       [1,1,1,0,0,0],
#       ]

# maze = [[0],
#       [0, 1],
#       [0, 0, 1],
#       [0, 0, 0, 1],
#       [0, 1, 0, 0, 1],
#       [0, 1, 0, 0, 0, 1],
#       [0, 0, 1, 1, 0, 0, 0],
#       ]

# maze = [[0, 0, 1, 1, 0, 0, 0],
#       [0, 1, 0, 0, 0, 1],
#       [0, 1, 0, 0, 1],
#       [1, 0, 0, 1],
#       [1, 0, 1],
#       [0, 0],
#       [0],
#       ]

# maze = [[0,1,1,1,1,0],
#       [0,0,1],
#       [0,1,0,0,0],
#       [0],
#       [0,1,0,0,0,0,0],
#       [1,0,1,0],
#       [1,0,0],
#       [0,0],
#       ]

class Graph():
    def __init__(self, m):
        #create a list of nodes
        self.maze = m
        # self.Nodes = [[None for val in xrange(len(self.maze[0]))] for val in xrange(len(self.maze))]
        self.Nodes = []
        self.visited = Queue.Queue()
        self.saldo = 1
        for rowNum, row in enumerate(m):
            newRow = []
            for colNum, col in enumerate(row):
                #create a node with infinite distance
                #corresponding to the maze index
                # n = Node(sys.maxint, self.saldo)
                n = Node('x', 0)
                n.x = rowNum
                n.y = colNum
                n.value = self.maze[rowNum][colNum]
                #append the node to the graph's list
                # of nodes
                # self.Nodes[rowNum][colNum] = n
                newRow.append(n)
                # self.Nodes.put(n)
            self.Nodes.append(newRow)
            print row

        self.Nodes[0][0].saldo = self.saldo

        print

        for rowNum, row in enumerate(self.Nodes):
            for colNum, node in enumerate(row):
                #set the neighbors of each node by looking at their adjacent
                #nodes, and making sure the list index does not go out of
                #the list bounds
                #also determine whether or not a wall can still be broken down
                #at this node,from this path
                if rowNum > 0:
                    # print rowNum, colNum, len(row) - abs(len(row) - len(self.maze[rowNum - 1]))
                    if len(row) == len(self.Nodes[rowNum - 1]) or colNum < len(row) - abs(len(row) - len(self.maze[rowNum - 1])):
                        if self.maze[rowNum - 1][colNum] == 1:
                            if node.saldo > 0:
                                saldo = node.saldo - 1
                            else:
                                saldo = 0
                            self.Nodes[rowNum - 1][colNum].saldo = saldo
                            node.neighbors.append(self.Nodes[rowNum - 1][colNum])
                        else:
                            if self.Nodes[rowNum - 1][colNum].saldo < node.saldo:
                                self.Nodes[rowNum - 1][colNum].saldo = node.saldo
                            node.neighbors.append(self.Nodes[rowNum - 1][colNum])

                if colNum > 0:
                    if self.maze[rowNum][colNum - 1] == 1:
                        if node.saldo > 0:
                            saldo = node.saldo - 1
                        else:
                            saldo = 0
                        self.Nodes[rowNum][colNum - 1].saldo = saldo
                        node.neighbors.append(self.Nodes[rowNum][colNum - 1])
                    else:
                        if self.Nodes[rowNum][colNum - 1] != None:
                            if self.Nodes[rowNum][colNum - 1].saldo < node.saldo:
                                self.Nodes[rowNum][colNum - 1].saldo = node.saldo
                            node.neighbors.append(self.Nodes[rowNum][colNum - 1])

                if rowNum < len(self.Nodes) - 1:

                    if len(row) > len(self.maze[rowNum + 1]):
                        colLimit = len(self.Nodes[rowNum + 1]) - 1
                    else:
                        colLimit = len(row) - abs(len(row) - len(self.maze[rowNum + 1]))
                        if colLimit < 0:
                            colLimit = 0

                    # print colNum, colLimit
                    # if rowNum == 1 and colNum == 0:
                    #   print len(row), len(self.maze[rowNum + 1]), colNum, colLimit
                    # if len(row) == len(self.maze[rowNum + 1]) or rowNum == 0 or colNum <= colLimit:
                    if colNum <= colLimit:
                        if rowNum == 1 and colNum == 0:
                            print "bottom neighbor"
                        if self.maze[rowNum + 1][colNum] == 1:
                            if node.saldo > 0:
                                saldo = node.saldo - 1
                            else:
                                saldo = 0
                            self.Nodes[rowNum + 1][colNum].saldo = saldo
                            node.neighbors.append(self.Nodes[rowNum + 1][colNum])
                        else:
                            if self.Nodes[rowNum + 1][colNum] != None:
                                if self.Nodes[rowNum + 1][colNum].saldo < node.saldo:
                                    self.Nodes[rowNum + 1][colNum].saldo = node.saldo
                                node.neighbors.append(self.Nodes[rowNum + 1][colNum])

                if colNum < len(row) - 1:
                    if self.maze[rowNum][colNum + 1] == 1:
                        if node.saldo > 0:
                            saldo = node.saldo - 1
                        else:
                            saldo = 0
                        self.Nodes[rowNum][colNum + 1].saldo = saldo
                        node.neighbors.append(self.Nodes[rowNum][colNum + 1])
                    else:
                        if self.Nodes[rowNum][colNum + 1] != None:
                            if self.Nodes[rowNum][colNum + 1].saldo < node.saldo:
                                self.Nodes[rowNum][colNum + 1].saldo = node.saldo
                            node.neighbors.append(self.Nodes[rowNum][colNum + 1])

        #print the saldo values for the maze
        for rowNum, row in enumerate(self.Nodes):
            for colNum, val in enumerate(row):
                print val.saldo,
            print

        #set the initial distance to 1 at the origin
        self.Nodes[0][0].distance = 1

    def shortestDistanceToNode(self):

        #add the origin to the queue
        self.visited.put(self.Nodes[0][0])

        #while there are still nodes in the queue,
        #push the current node's neighbors onto the queue
        #if they are equal to 0, or if a wall can be
        #broken down from this neighbor node
        while not self.visited.empty():
            node = self.visited.get()
            distance = node.distance
            # print "node (", node.x, ",", node.y, ") has", len(node.neighbors), "neighbors" 
            for neighbor in node.neighbors:
                if self.maze[neighbor.x][neighbor.y] == 0 or node.saldo > 0:
                    if distance + 1 < neighbor.distance:
                        # print "node (", node.x, ",", node.y, ") moves to (", neighbor.x, ",", neighbor.y, ")"
                        self.visited.put(neighbor)
                        neighbor.distance = distance + 1

        # for neighbor in self.Nodes[0][1].neighbors:
        #   print "Distance:", self.Nodes[0][1].distance, "x:", neighbor.x, "y:", neighbor.y, "Neighbor Distance:", neighbor.distance

        #print the new node graph with distances based on the
        #shortest path
        print
        for row in self.Nodes:
            for val in row:
                # print "(", val.value, ",", val.distance, ")",
                print val.distance,
            print

        return self.Nodes[len(self.Nodes) - 1][len(self.Nodes[len(self.Nodes) - 1]) - 1].distance

class Node():
    def __init__(self, distance, saldo):
        self.x = 0
        self.y = 0
        self.distance = distance
        self.neighbors = []
        self.saldo = saldo

def answer(maze):
    g = Graph(maze)
    return g.shortestDistanceToNode()

answer(maze)

Output for each test case, with debug (in comments above)

For each test case:

• First matrix is the original input
• Second matrix is the "saldo" values (whether or not the node can break down a wall)
• Third matrix is the updated object with the shortest path to each node in the corresponding position in the list
• The bottom right index of each array is (intended to be) the shortest path to the "exit"

Working Solution For Anybody Who Is Interested

import sys
import Queue

# 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]]
# maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]
# maze = [[0, 1], [1, 0]]
# maze = [[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]]
# maze = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 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, 1, 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, 0],
#         [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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, 1, 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, 0, 1],
#         [0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1],
#         [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 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, 1, 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, 0],
#         [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0],
#         [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 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, 1, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

# maze = [[0,1,1,0,0],
#       [0,1,0,1,0],
#       [0,0,0,1,0],
#       ]
# maze = [[0,0,0,0,0],
#       [1,1,1,1,1],
#       [1,1,0,0,1],
#       [0,0,1,0,0],
#       ]
# maze = [[0,1,1],
#       [1,1,1],
#       [0,0,0],
#       ]
# maze = [[0, 1, 1, 0, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0]]
# maze = [[0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0],
#       [0,0]
#       ]

maze = [
   [0, 1, 0, 1, 0, 0, 0], 
   [0, 0, 0, 1, 0, 1, 0]
]

class Graph():

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

    def shortestDistanceToEnd(self):

        visited = Queue.Queue()
        # source = Node(0, 0, self.saldo, self.maze, self.maze[0])
        source = Node(0, 0, self.saldo, self.maze)
        visited.put(source)
        distance = {source: 1}

        while not visited.empty():

            node = visited.get()

            if node.rowNum == self.rows - 1 and node.colNum == self.columns - 1:
                return distance[node]

            for neighbor in node.getNeighbors():
                if neighbor not in distance.keys():
                    distance[neighbor] = distance[node] + 1
                    visited.put(neighbor)

        return sys.maxint

class Node:
    # def __init__(self, rowNum, colNum, saldo, maze, row):
    def __init__(self, rowNum, colNum, saldo, maze):
        self.rowNum = rowNum
        self.colNum = colNum
        self.saldo = saldo
        self.maze = maze
        # self.row = row

    def __hash__(self):
        return self.colNum ^ self.rowNum

    def __eq__(self, other):
        return self.rowNum == other.rowNum and self.colNum == other.colNum and self.saldo == other.saldo

    def getNeighbors(self):
        neighbors = []
        rowNum = self.rowNum
        colNum = self.colNum
        saldo = self.saldo
        maze = self.maze
        # row = self.row
        rowLimit = len(maze)
        colLimit = len(maze[0])

        #makes sure we are not going to go passed the left boundary
        if colNum > 0:

            #checks if the node to the left of the current node
            #is a wall
            isAWall = maze[rowNum][colNum - 1] == 1
            if isAWall:
                #checks if this node has the ability to break
                #through a wall
                if saldo > 0:
                    #append a NEW node object to the array of neighbors for
                    #this node. One of my problems with my old version was 
                    #that each node was sharing a pool of references, so
                    #when a new node had the same neighbor as a previous
                    #node, it would overwrite all of its data, which was
                    #causing the algorithm to think it could break through
                    #a wall when it in fact could not
                    # neighbors.append( Node(rowNum, colNum - 1, saldo, maze, maze[rowNum]) )
                    neighbors.append( Node(rowNum, colNum - 1, saldo - 1, maze) )
            else:
                #append a NEW node object to the array of neighbors for
                #this node. One of my problems with my old version was 
                #that each node was sharing a pool of references, so
                #when a new node had the same neighbor as a previous
                #node, it would overwrite all of its data, which was
                #causing the algorithm to think it could break through
                #a wall when it in fact could not
                # neighbors.append( Node(rowNum, colNum - 1, saldo, maze, maze[rowNum]) )
                neighbors.append( Node(rowNum, colNum - 1, saldo, maze) )

        #makes sure we are not going to go passed the right boundary
        if colNum < colLimit - 1:

            #checks if the node to the right of the current node
            #is a wall
            isAWall = maze[rowNum][colNum + 1] == 1
            if isAWall:
                #checks if this node has the ability to break
                #through a wall
                if saldo > 0:
                    neighbors.append( Node(rowNum, colNum + 1, saldo - 1, maze) )
            else:
                #same deal as the above 'if'
                # neighbors.append( Node(rowNum, colNum + 1, saldo, maze, maze[rowNum]) )
                neighbors.append( Node(rowNum, colNum + 1, saldo, maze) )

        #makes sure we are not going to go passed the top boundary
        if rowNum > 0:

            #makes sure we are not checking a value that does not exist
            #in the case that the matrix is not rectangular
            # if len(row) == len(maze[rowNum - 1]) or colNum < len(row) - abs(len(row) - len(maze[rowNum - 1])):

            #checks if the node on top of the current node
            #is a wall
            isAWall = maze[rowNum - 1][colNum] == 1
            if isAWall:
                #checks if this node has the ability to break
                #through a wall
                if saldo > 0:
                    neighbors.append( Node(rowNum - 1, colNum, saldo - 1, maze) )
            else:
                #same deal as the above 'if'
                # neighbors.append( Node(rowNum - 1, colNum, saldo, maze, maze[rowNum]) )
                neighbors.append( Node(rowNum - 1, colNum, saldo, maze) )

        #makes sure we are not going to go passed the bottom boundary
        if rowNum < len(maze) - 1:

            #makes sure we are not checking a value that does not exist
            #in the case the the matrix is not rectangular
            # if len(row) > len(maze[rowNum + 1]):
            #   colLimit = len(maze[rowNum + 1]) - 1
            # else:
            #   colLimit = len(row) - abs(len(row) - len(maze[rowNum + 1]))
            #   if colLimit < 0:
            #       colLimit = 0

            # if colNum < colLimit:
            isAWall = maze[rowNum + 1][colNum] == 1
            if isAWall:
                #checks if this node has the ability to break
                #through a wall
                if saldo > 0:
                    neighbors.append( Node(rowNum + 1, colNum, saldo - 1, maze) )
            else:
                # neighbors.append( Node(rowNum + 1, colNum, saldo, maze, maze[rowNum + 1]) )
                neighbors.append( Node(rowNum + 1, colNum, saldo, maze) )

        return neighbors

def answer(maze):
    g = Graph(maze, 1)
    return g.shortestDistanceToEnd()

print answer(maze)

Answer 1

Soo, after looking into that puzzle and playing with your code for a while (I like puzzles...) I think the major Problem is not a simple bug but a plain wrong algorithm/implementation/concept.

Let me try to explain it as much as possible

1. I've found a Problem Instance which yields a wrong result:

maze = [
   [0, 1, 0, 1, 0, 0, 0], 
   [0, 0, 0, 1, 0, 1, 0]
]

This instance results in a distance of 8 thought it should be 10 since the saldo is used for breaking either wall (0,3) or (1,3) and the additional distance is needed to go around Wall (0,1) and (1,5).

2. Looking into the saldo and neighbor calculation (only one neighbor):

if rowNum > 0:
    if len(row) == len(self.Nodes[rowNum - 1]) or colNum < len(row) - abs(len(row) - len(self.maze[rowNum - 1])):
        if self.maze[rowNum - 1][colNum] == 1:
            # Position A.
            if node.saldo > 0:
                saldo = node.saldo - 1
            else:
                saldo = 0
            # Position B.
            self.Nodes[rowNum - 1][colNum].saldo = saldo
            node.neighbors.append(self.Nodes[rowNum - 1][colNum])
        else:
            # Position C.
            if self.Nodes[rowNum - 1][colNum].saldo < node.saldo:
                self.Nodes[rowNum - 1][colNum].saldo = node.saldo
            node.neighbors.append(self.Nodes[rowNum - 1][colNum])

At Position A. it is understandable that, if the neighbor is a Wall and we have saldo > 0 on the "current Path", we can break the Wall and reduce the saldo.

But if you look into Position B. and Position C., this is setting the saldo on basis of a neighbor/wall and it depends more on how the loop runs than actual pathes. You can easily (well no.. actually not so easy) see that the given failing Problem Instance comes from the resetting of saldo when wall/non-wall alternates. There is no real fix for that either. [proof needed]

The basic point and misconception (in my opinion) is that this algorithm doesn't account for the fact that any given node (cell in the grid) - except the start and some special cases - can be both on a path with and without broken wall. You do not know if either of them is shorter than the other so you basically need to calculate both cases.

3. So how to fix the calculation?

If you wan't to stick to the saldo's algorithm, then it needs to be moved into your BFS. Additionally you need to take care for the case where a node has both possibilities.

Additional note: I've stumbled upon a similar algorithm here on Stack Exchange Code Review which does the saldo calculations in BFS from the current node. Even thought the answer is accepted, the algorithm is only correct if you replace the __eq__ check return self.x == other.x and self.y == other.y and self.saldo == other.saldo (as stated in the comments). This algorithm is probably the best reference.