# Maze configuration from lecture
BLOCKS1 = { (0, 0), (0, 3), (0, 4), (0, 5), (0, 6), (1, 0), (1, 2), (1, 3),
(1, 4), (1, 5), (2, 0), (2, 1), (2, 3), (2, 4), (2, 6), (3, 0),
(3, 1), (3, 3), (3, 5), (3, 6), (4, 0), (4, 1), (4, 2), (4, 3),
(4, 4), (4, 6), (5, 0), (5, 2), (5, 3), (5, 4), (5, 5), (6, 1),
(6, 3), (6, 6), (7, 1), (7, 2), (7, 4), (7, 5), (8, 0), (8, 1),
(8, 3), (8, 4), (8, 6), (9, 0), (9, 3), (9, 6) }
def maze1(x, y):
return not 0 <= x < 10 or (x, y) in BLOCKS1
# Missing block at (7, 1)
BLOCKS2 = { (0, 0), (0, 3), (0, 4), (0, 5), (0, 6), (1, 0), (1, 2), (1, 3),
(1, 4), (1, 5), (2, 0), (2, 1), (2, 3), (2, 4), (2, 6), (3, 0),
(3, 1), (3, 3), (3, 5), (3, 6), (4, 0), (4, 1), (4, 2), (4, 3),
(4, 4), (4, 6), (5, 0), (5, 2), (5, 3), (5, 4), (5, 5), (6, 1),
(6, 3), (6, 6), (7, 2), (7, 4), (7, 5), (8, 0), (8, 1),
(8, 3), (8, 4), (8, 6), (9, 0), (9, 3), (9, 6) }
def maze2(x, y):
return not 0 <= x < 10 or (x, y) in BLOCKS2
def is_path(blocked, x0, y0):
"""True iff there is a path of squares from (X0, Y0) to some
square (x1, 0) such that all squares on the path (including first and
last) are unoccupied. BLOCKED is a predicate such that BLOCKED(x, y)
is true iff the grid square at (x, y) is occupied or off the edge.
Each step of a path goes down one row and 1 or 0 columns left or right."""
if __________________________________________________:
return __________________________________________________
elif __________________________________________________:
return __________________________________________________
else:
return __________________________________________________
def num_paths(blocked, x0, y0):
"""Return the number of unoccupied paths that run from (X0, Y0)
to some square (x1, 0). BLOCKED is a predicate such that BLOCKED(x, y)
is true iff the grid square at (x, y) is occupied or off the edge. """
def find_path(blocked, x0, y0):
"""Return a string containing the steps in an unoccupied
path from (X0, Y0) to some unoccupied square (x1, 0),
or None if not is_path(BLOCKED, X0, Y0). BLOCKED is a
predicate such that BLOCKED(x, y) is true iff the
grid square at (x, y) is occupied or off the edge. """
def is_path_solution(blocked, x0, y0):
"""True iff there is a path of squares from (X0, Y0) to some
square (x1, 0) such that all squares on the path (including first and
last) are unoccupied. BLOCKED is a predicate such that BLOCKED(x, y)
is true iff the grid square at (x, y) is occupied or off the edge.
Each step of a path goes down one row and 1 or 0 columns left or right."""
if blocked(x0, y0):
return False
elif y0 == 0:
return True
else:
return (is_path(blocked, x0-1, y0-1)
or is_path(blocked, x0, y0-1)
or is_path(blocked, x0+1, y0-1))
# Comment out to test your solution
is_path = is_path_solution
def num_paths_solution(blocked, x0, y0):
"""Return the number of unoccupied paths that run from (X0, Y0)
to some square (x1, 0). BLOCKED is a predicate such that BLOCKED(x, y)
is true iff the grid square at (x, y) is occupied or off the edge. """
if blocked(x0, y0):
return 0
elif y0 == 0:
return 1
else:
return num_paths(blocked, x0, y0-1) \
+ num_paths(blocked, x0-1, y0-1) \
+ num_paths(blocked, x0+1, y0-1)
# OR (looking ahead a bit)
# return sum( (num_paths(blocked, x0+k, y0-1)
# for k in range(-1, 2))
#b )
# Comment out to test your solution
num_paths = num_paths_solution
def find_path_solution(blocked, x0, y0):
"""Return a string containing the steps in an unoccupied
path from (X0, Y0) to some unoccupied square (x1, 0),
or None if not is_path(BLOCKED, X0, Y0). BLOCKED is a
predicate such that BLOCKED(x, y) is true iff the
grid square at (x, y) is occupied or off the edge. """
if blocked(x0, y0):
return None
elif y0 == 0:
return str( (x0, y0) )
else:
for c in x0 - 1, x0, x0 + 1:
p = find_path(blocked, c, y0-1)
if p is not None:
return str( (x0, y0) ) + " " + p
return None
# Comment out to test your solution
find_path = find_path_solution