import sys
from math import sqrt
from subprocess import Popen, DEVNULL, PIPE
sin60 = sqrt(3) / 2
# To use interactively: Get 07.py and copy it to lect07.py. Then,
# >>> from lect07 import *
# >>> d = make_displayer()
# >>> make_gasket(6, d.stdin)
# >>> make_gasket(10, d.stdin)
# ...
# >>> stop_displayer(d)
def make_gasket(x, y, s, n, output):
"""Draw an nth approximation to Sierpinski's gasket, with lower-left
corner at (x,y), and size s x s. Writes Postscript commands to the
the standard output to do the drawing."""
if n == 0:
print("{0:.2f} {1:.2f} moveto "
"{2:.2f} 0 rlineto "
"-{3:.2f} {4:.2f} rlineto "
"closepath fill"
.format(x, y, s, s/2, s*sin60), file=output)
else:
make_gasket(x, y, s/2, n - 1, output)
make_gasket(x + s/2, y, s/2, n - 1, output)
make_gasket(x + s/4, y + sin60*s/2, s/2, n-1, output)
def draw_gasket(n, output=sys.stdout):
print("%!", file=output)
make_gasket(100, 100, 400, n, output=output)
print("showpage", file=output)
def make_displayer():
"""Create a Ghostscript process that displays its input (sent in through
.stdin)."""
return Popen("gs", universal_newlines=True, stdin=PIPE, stdout=DEVNULL)
def stop_displayer(d):
"""Terminate execution of displayer D (created by make_displayer)."""
d.stdin.close()
d.wait()
# 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 ends)
are unoccupied. BLOCKED is a predicate such that BLOCKED(x, y)
is true iff the grid square at (x, y) is occupied. 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 paths that run from
(X0, Y0) to some unoccupied square (x1, 0).
BLOCKED is a predicate such that BLOCKED(x, y) is
true iff the grid square at (x, y) is occupied. """
def find_path(blocked, x0, y0):
"""Return a string containing the steps in a path
from (X0, Y0) tosome 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. """
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 ends)
are unoccupied. BLOCKED is a predicate such that BLOCKED(x, y)
is true iff the grid square at (x, y) is occupied. 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 paths that run from
(X0, Y0) to some unoccupied square (x1, 0).
BLOCKED is a predicate such that BLOCKED(x, y) is
true iff the grid square at (x, y) is occupied. """
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 a 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. """
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