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