# 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

### 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

# my_solution-refactored-before_stackexchange_code_review.py

# INDEX
#
# - def main()
# - class Board(list)
# - class Cell(tuple)
# - 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

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] ]

# 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] ]

# 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] ]

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

# 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()

• Can you provide the main function? – coderodde Feb 5 '17 at 9:09
• @coderodde Thanks for the heads up. I added the main function. – josfervi Feb 5 '17 at 22:14

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__?

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

""" 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]
]

# 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]
]

# 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]
]

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

# 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)

• Regarding point 6 (removing all usages of __class__), I was thinking that having self.__class__ instead of Board would make the class more maintanable, for example in the case that we wanted to change the name of the class from Board to, say, TupleIndexedMatrix. What are your thoughts on this? – josfervi Feb 6 '17 at 4:28
• Regarding point 2 (making Board() a dict instead of a list of lists, I am trying to see the benefit. From outside, the Board() looks the same right or did the Board() interface change? – josfervi Feb 6 '17 at 4:38
• Regarding point 7 (excercise for OP), I think both snippets are equivalent. Say c == Cell(c_board, c_coordinates, c_value), then board[c] calls board.__getitem__(c), which returns board[c.coordinates].value == board[c_coordinates].value and if board == c_board, then board[c_coordinates].value == c_board[c_coordinates].value == c.value == board[c]. So that kind of 'proofs' that self.value == board[self] by taking c == self. It's kind of circular though. Please have a look at this and let me know if I made any mistakes. – josfervi Feb 6 '17 at 4:53
• so the dict approach is useful for bypassingisInside() altogether and you can also make sure every row is the same length? (the latter thing you also do with the list of lists approach, I believe.) – josfervi Feb 6 '17 at 5:00