Find the shortest path through a maze with a twist: you can knock down one wall

Question

I would like my solution to Google Foobar's prepare_the_bunnies_escape checked for readability, maintainability, extensibility, style, design. I am looking forward to reading your suggestions on any of these aspects! Feel free to comment on other aspects as well.

Problem

Link to full problem statement

Summary

You are given an HxW matrix of 0's and 1's, m, where 0's indicate traversable cells and 1's indicate nontraversable cells (i.e. walls). start denotes the cell at coordinate (0, 0) and end denotes the cell at coordinate (H-1, W-1). start and end are always traversable. Given that you can remove one wall making it traversable, find the distance of a shortest path from start to end.

Test cases

Inputs:

m = [ [0, 1, 1, 0],
      [0, 0, 0, 1], 
      [1, 1, 0, 0],
      [1, 1, 1, 0] ]

Outputs:

7

Inputs:

m = [ [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] ]

Outputs:

11

Inputs:

m = [ [0, 0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 1, 1, 0],
      [1, 1, 1, 1, 1, 0, 1, 1, 0],
      [1, 1, 1, 1, 1, 0, 1, 1, 1],
      [0, 0, 0, 0, 0, 0, 1, 1, 0],
      [0, 1, 1, 1, 1, 1, 1, 1, 0],
      [0, 1, 1, 1, 1, 1, 1, 1, 0],
      [0, 0, 0, 0, 0, 0, 0, 0, 0] ]

Outputs:

16

Inputs:

m = [ [0],
      [1],
      [0] ]

Outputs:

3

Inputs:

m = [ [0, 0, 0, 0],
      [1, 1, 1, 0],
      [1, 0, 1, 0],
      [1, 1, 1, 0],
      [1, 0, 0, 0],
      [1, 0, 1, 1],
      [1, 0, 0, 0] ]

Outputs:

10

My Algorithm

Find and store start.minDistTo, the minimum distance from start to each cell. Do likewise for end, that is, find and store end.minDistTo, the minimum distance from end to each cell. Now, for each wall in m, use start.minDistTo and end.minDistTo to see if you can get a shorter path by removing the current wall and, if so, store its distance in bestResult_soFar. Once you've done this for all walls, you'll have the distance of a shortest path in bestResult_soFar. The overall time complexity of this algorithm is O(HxW).

My solution

Link to solution on GitHub

# my_solution-refactored-before_stackexchange_code_review.py

# INDEX
# 
# - def main()
# - class Board(list)
# - class Cell(tuple)
# - def answer(m)
# - def whatIfIRemovedThis(wall, m, start, end)
# - def run_tests()

def main():
    run_tests()

class Board(list):
    ''' Useful for indexing into multidimensional lists using tuples, which imo is cleaner. '''

    traversable_value    = 0
    nontraversable_value = 1
    unvisited_value      = None
    unreachable_value    = None

    def __getitem__(self, tup):
        r, c = tup
        return super(self.__class__, self).__getitem__(r).__getitem__(c)

    def __setitem__(self, tup, val):
        r, c = tup
        super(self.__class__, self).__getitem__(r).__setitem__(c, val)

from collections import deque

class Cell(tuple):
    ''' A cell on a board is represented by the cell's coordinates. '''

    def __init__(self, minDistTo = None):
        self.minDistTo = minDistTo

    def getNeighbors(self):
        ''' Yields self's neighbors in up, down, left, right order. '''

        r, c = self

        yield self.__class__( (r-1, c) ) # up
        yield self.__class__( (r+1, c) ) # down
        yield self.__class__( (r, c-1) ) # left
        yield self.__class__( (r, c+1) ) # right

    def isInside(self, board):
        r, c = self
        num_rows, num_cols = len(board), len(list(board)[0])

        return 0 <= r < num_rows and 0 <= c < num_cols

    def isTraversableIn(self, board):
        return board[self] == board.__class__.traversable_value

    def isAWallIn(self, board):
        return board[self] == board.__class__.nontraversable_value

    def hasNotBeenVisitedIn(self, board):
        return board[self] == board.__class__.unvisited_value

    def isUnreachableFrom(self, other):
        if not isinstance(other, self.__class__):
            return False
        return other.minDistTo[self] == other.minDistTo.__class__.unreachable_value # hard to understand

    # O(h*w) time complexity
    def genMinDistTo(self, m):
        ''' A BFS Single Sourse Shortest Path algorithm
            appropriate for graphs with unweighted edges*
            *or graphs with weighted edges but where every edge has the same weight'''

        if self.isAWallIn(board = m):
            return None

        h = len(m)
        w = len(list(m)[0])

        minDistTo = Board( [ [Board.unvisited_value]*w for _ in range(h) ] )

        minDistTo[self] = 1
        cells = deque([self]) # cell queue, in the cell queue, each cell is represented by its coordinate

        while cells: # h*w iterations

            cell          = cells.popleft()
            minDistToCell = minDistTo[cell]

            for neighbor in cell.getNeighbors(): # 4 iterations

                if neighbor.isInside(board = m) and \
                   neighbor.isTraversableIn(board = m) and \
                   neighbor.hasNotBeenVisitedIn(board = minDistTo):

                    minDistToNeighbor   = minDistToCell + 1
                    minDistTo[neighbor] = minDistToNeighbor # Setting minDistsTo[.] to an int also marks it as visited.

                    cells.append(neighbor) # Each cell gets appended to the cells queue only once.

        self.minDistTo = minDistTo

# O(h*w) time complexity
def answer(m):

    num_rows = h = len(m)    # height
    num_cols = w = len(m[0]) # width

    m = Board(m)

    bestConceivableResult = h + w - 1

    start = Cell( (  0,   0) )
    end   = Cell( (h-1, w-1) )

    start.genMinDistTo(m) # O(h*w) time

    if end.isUnreachableFrom(start):
        # This happens in test case 3 where it is neccesary
        # to remove a wall to have a path from start to end.
        bestResult_soFar = 2**31 - 1
    else:
        bestResult_soFar = start.minDistTo[end]

    if bestResult_soFar == bestConceivableResult:
        # We cannot do any better than this.
        return bestConceivableResult

    end.genMinDistTo(m) # O(h*w) time

    for r in range(num_rows): # h iterations
        for c in range(num_cols): # w iterations

            cell = Cell( (r, c) )

            if cell.isAWallIn(board = m):

                wall = cell

                # See if you can get a shorter path from start to end by removing this wall.

                potentiallyBetterResult = whatIfIRemovedThis(wall, m, start, end) # O(1) time

                bestResult_soFar = min(bestResult_soFar, potentiallyBetterResult)

    bestResult = bestResult_soFar

    return bestResult

# O(1) time complexity
def whatIfIRemovedThis(wall, m, start, end):
    ''' Returns the distance of the shortest start-to-end path that goes through wall
        as if wall (and only wall) had been removed and were traversable. '''

    #   u
    # l w r
    #   d
    # 
    # w := wall
    # u, d, l, r := the wall's up, down, left, right neighbors respectively
    # 
    # In the worst case there are twelve ways to "go through" the wall and each of these must be considered.
    # I will enumerate them. However symmetric 0. and 3. may seem, they must both be considered. Same goes for all other pairs.
    # 
    #  0. u -> d := from the start, you arrived at u, then went through the wall, emerged at d, and continued on to the end
    #  1. u -> l
    #  2. u -> r
    #  3. d -> u := from the start, you arrived at d, then went through the wall, emerged at u, and continued on to the end
    #  4. d -> l
    #  5. d -> r
    #  6. l -> u
    #  7. l -> d
    #  8. l -> r
    #  9. r -> u
    # 10. r -> d
    # 11. r -> l

    bestResult_soFar = 2**31 - 1

    # [up, down, left, right] = list( wall.getNeighbors() )
    for incoming in wall.getNeighbors():
        for outgoing in wall.getNeighbors():
                                             # 16 iterations
            if incoming == outgoing:
                # Such a path does not require the removal of wall and thus has already been considered.
                continue

            if not incoming.isInside(board  = m)     or not outgoing.isInside(board  = m)    or \
                   incoming.isAWallIn(board = m)     or     outgoing.isAWallIn(board = m)    or \
                   incoming.isUnreachableFrom(start) or     outgoing.isUnreachableFrom(end):
                continue

            minDistFromStartToIncoming = start.minDistTo[incoming]
            minDistFromOutgointToEnd   = end.minDistTo[outgoing]

            potentiallyBetterResult = minDistFromStartToIncoming + 1 + minDistFromOutgointToEnd

            bestResult_soFar = min(bestResult_soFar, potentiallyBetterResult)

    bestResult = bestResult_soFar

    return bestResult

# TESTING ----------------------------------------------------------------------

def run_tests():

    # test case 0
    m = [ [0, 1, 1, 0],
          [0, 0, 0, 1], 
          [1, 1, 0, 0],
          [1, 1, 1, 0] ]

    print answer(m) == 7

    # test case 1
    m = [ [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] ]

    print answer(m) == 11

    # test case 2
    m = [ [0, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 0, 0, 1, 1, 0],
          [1, 1, 1, 1, 1, 0, 1, 1, 0],
          [1, 1, 1, 1, 1, 0, 1, 1, 1],
          [0, 0, 0, 0, 0, 0, 1, 1, 0],
          [0, 1, 1, 1, 1, 1, 1, 1, 0],
          [0, 1, 1, 1, 1, 1, 1, 1, 0],
          [0, 0, 0, 0, 0, 0, 0, 0, 0] ]

    print answer(m) == 16

    # test case 3
    m = [ [0],
          [1],
          [0] ]

    print answer(m) == 3

    # test case 4
    m = [ [0, 0, 0, 0],
          [1, 1, 1, 0],
          [1, 0, 1, 0],
          [1, 1, 1, 0],
          [1, 0, 0, 0],
          [1, 0, 1, 1],
          [1, 0, 0, 0] ] # m[(2,1)] is traversable but inaccessible

    print answer(m) == 10 # == h + w - 1 == 7 + 4 - 1 (this requires wall at (5,3) to be removed)

if __name__ == "__main__":
    main()

Answer 1

So here is my version of your code. Changes made:

1. pep8:

I changed the code to more closely conform to pep8. This is important when sharing code as the consistent style makes it much easier for other programmers to read your code. There are various tools available to assist in making the code pep8 compliant. I use PyCharm which will show pep8 violations right in the editor.

2. Refactor Board() to be be a dict instead of list of lists:

Python allows a tuple to be a dict key, and I felt the coordinates tuple made a more natural key.

3. Made the native element of the Board() a Cell():

By making the native element a Cell(), and given the previously represented value to the Cell(), I felt the ownership of these values was more natural.

4. Made width and height attributes of the board class:

Recalculating these attributes, instead of interrogating the Board() object, is a potential source of errors.

5. Refactored get_neighbors() to only return valid neighbors:

This allowed the code using the get_neighbors() iterator to not need to check if the neighbors were valid. Which allowed the removal of the Cell.isInside() method.

6. Removed all usages of __class__:

Through the various refactorings, these were no longer necessary.

7. Update: An exercise for the OP:

In looking back through this code I found I had coded this:

def is_traversable_in(self, board):
    return self.value == board.traversable_value

and it likely should be:

def is_traversable_in(self, board):
    return board[self] == board.traversable_value

yet both versions pass the test cases. Might be illuminative to investigate why either allows the test cases to pass.

Question from Comment:

In the case that we wanted to change the name of the class from Board to, say, TupleIndexedMatrix, what are the implications of not using __class__?

Answer:

The suggested changes get rid of the need for most of references to Board. This one:

    min_dist_to = Board(
        [[Board.unvisited_value] * board.width] * board.height)

would likely be best served by adding a @classmethod to Board() that takes a desired default value and a size, and returns an initialized Board() (IE, recreates the line above as a method of Board()). All of the remaining references are either in Board itself (super) or are constructors.

---

# -*- coding: utf-8 -*-
from collections import deque

# INDEX
#
# - class Board(list)
# - class Cell(tuple)
# - def answer(m)
# - def whatIfIRemovedThis(wall, m, start, end)


class Board(dict):

    traversable_value = 0
    nontraversable_value = 1
    unvisited_value = None
    unreachable_value = None

    def __init__(self, m):
        super(Board, self).__init__()
        self.default_factory = None
        self.height = len(m)
        self.width = len(m[0])
        for r, row in enumerate(m):
            assert self.width == len(row)
            for c, val in enumerate(row):
                self[r, c] = Cell(self, (r, c), val)

    def __getitem__(self, item):
        if isinstance(item, Cell):
            return self[item.coordinates].value
        return super(Board, self).__getitem__(item)

    def __setitem__(self, key, value):
        if isinstance(key, Cell):
            self[key.coordinates].value = value
        else:
            super(Board, self).__setitem__(key, value)


class Cell(object):
    """ A cell on a board is keyed by the cell's coordinates. """

    def __init__(self, board, coordinates, value):
        self.coordinates = coordinates
        self.board = board
        self.value = value
        self.min_dist_to = None

    def __repr__(self):
        return "%s @ %s" % (self.value, self.coordinates)

    def get_neighbors(self):
        """ Yields self's neighbors in up, down, left, right order. """

        r, c = self.coordinates
        for coordinates in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
            try:
                yield self.board[coordinates]
            except KeyError:
                # outside of the board
                pass

    def is_traversable_in(self, board):
        return board[self] == board.traversable_value

    def is_a_wall_in(self, board):
        return board[self] == board.nontraversable_value

    def is_unvisited_in(self, board):
        return board[self] == board.unvisited_value

    def is_unreachable_from(self, other):
        # it is a bug if passed a non-cell
        assert isinstance(other, Cell)

        # hard to understand
        return other.min_dist_to[self] == self.board.unreachable_value

    # O(h*w) time complexity
    def gen_min_dist_to(self, board):
        """ A BFS Single Source Shortest Path algorithm appropriate for
        graphs with unweighted edges or graphs with weighted edges but
        where every edge has the same weight
        """

        if self.is_a_wall_in(board):
            return None

        min_dist_to = Board(
            [[Board.unvisited_value] * board.width] * board.height)
        min_dist_to[self] = 1

        cells = deque([self])

        while cells:  # h*w iterations
            cell = cells.popleft()
            min_dist_to_cell = min_dist_to[cell]

            for neighbor in cell.get_neighbors():
                is_traversable = neighbor.is_traversable_in(board)
                is_unvisited = neighbor.is_unvisited_in(min_dist_to)

                if is_traversable and is_unvisited:
                    min_dist_to_neighbor = min_dist_to_cell + 1

                    # Setting minDistsTo[.] to an int also marks it as visited.
                    min_dist_to[neighbor] = min_dist_to_neighbor

                    # Each cell gets appended to the cells queue only once.
                    cells.append(neighbor)

        self.min_dist_to = min_dist_to


def answer(board_martrix):
    """ O(h*w) time complexity """

    board = Board(board_martrix)
    best_conceivable_result = board.height + board.width - 1

    start = board[0, 0]
    end = board[board.height-1, board.width-1]

    start.gen_min_dist_to(board)  # O(h*w) time

    if end.is_unreachable_from(start):
        # This happens in test case 3 where it is necessary
        # to remove a wall to have a path from start to end.
        best_result = 2**31 - 1
    else:
        best_result = start.min_dist_to[end.coordinates]

    if best_result == best_conceivable_result:
        # We cannot do any better than this.
        return best_conceivable_result

    end.gen_min_dist_to(board)  # O(h*w) time

    for r in range(board.height):     # h iterations
        for c in range(board.width):  # w iterations

            cell = board[r, c]

            if cell.is_a_wall_in(board):
                wall = cell

                # See if you can get a shorter path from start to end by
                # removing this wall.
                potentially_better_result = what_if_removed_this(
                    wall, board, start, end)  # O(1) time

                best_result = min(best_result, potentially_better_result)

    return best_result


def what_if_removed_this(wall, board_matrix, start, end):
    """ Returns the distance of the shortest start-to-end path that goes
    through wall as if wall (and only wall) had been removed and
    were traversable.

      u
    l w r
      d

    w := wall
    u, d, l, r := the wall's up, down, left, right neighbors respectively

    In the worst case there are twelve ways to "go through" the wall and
    each of these must be considered. I will enumerate them. However
    symmetric 0. and 3. may seem, they must both be considered. Same
    goes for all other pairs.

     0. u -> d := from the start, you arrived at u, then went through the
                  wall, emerged at d, and continued on to the end
     1. u -> l
     2. u -> r
     3. d -> u := from the start, you arrived at d, then went through the
                  wall, emerged at u, and continued on to the end
     4. d -> l
     5. d -> r
     6. l -> u
     7. l -> d
     8. l -> r
     9. r -> u
    10. r -> d
    11. r -> l

    NOTE: O(1) time complexity
    """

    best_result = 2**31 - 1

    # [up, down, left, right] = list( wall.getNeighbors() )
    for incoming in wall.get_neighbors():
        for outgoing in wall.get_neighbors():

            # 16 iterations
            if (incoming == outgoing or  # already consider
                    incoming.is_a_wall_in(board_matrix) or
                    outgoing.is_a_wall_in(board_matrix) or
                    incoming.is_unreachable_from(start) or
                    outgoing.is_unreachable_from(end)):
                continue

            min_dist_from_start_to_incoming = start.min_dist_to[incoming]
            min_dist_from_outgoing_to_end = end.min_dist_to[outgoing]

            potentially_better_result = (
                min_dist_from_start_to_incoming + 1 +
                min_dist_from_outgoing_to_end)

            best_result = min(best_result, potentially_better_result)

    return best_result

# TESTING ----------------------------------------------------------------------


def run_tests():

    # test case 0
    m = [
        [0, 1, 1, 0],
        [0, 0, 0, 1],
        [1, 1, 0, 0],
        [1, 1, 1, 0]
    ]

    assert answer(m) == 7

    # test case 1
    m = [
        [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]
    ]

    assert answer(m) == 11

    # test case 2
    m = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 1, 0],
        [1, 1, 1, 1, 1, 0, 1, 1, 0],
        [1, 1, 1, 1, 1, 0, 1, 1, 1],
        [0, 0, 0, 0, 0, 0, 1, 1, 0],
        [0, 1, 1, 1, 1, 1, 1, 1, 0],
        [0, 1, 1, 1, 1, 1, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0]
    ]

    assert answer(m) == 16

    # test case 3
    m = [[0], [1], [0]]

    assert answer(m) == 3

    # test case 4
    m = [
        [0, 0, 0, 0],
        [1, 1, 1, 0],
        [1, 0, 1, 0],
        [1, 1, 1, 0],
        [1, 0, 0, 0],
        [1, 0, 1, 1],
        [1, 0, 0, 0]
    ]  # m[(2,1)] is traversable but inaccessible

    # == h + w - 1 == 7 + 4 - 1 (this requires wall at (5,3) to be removed)
    assert answer(m) == 10

if __name__ == "__main__":
    run_tests()