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

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 b

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.

1. 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.

1. 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.

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

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

1. 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.

1. Removed all usages of __class__:

Through the various refactorings, these were no longer necessary.

1. 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] * b

StackExchange Code Review Q#154482, answer score: 5