# Tail-recursive sum_squares
def sum_squares(N):
    """The sum of K**2 for 1 <= K <= N."""
    def part_sum(k, accum):
        if k <= N:
            return part_sum(k+1, accum + k**2)
        else:
           return accum
    part_sum(1, 0)

def find_first(start, pred):
    """Find the smallest k >= START such that PRED(START)."""
    if pred(start):
        return start
    else:
        return find_first(start+1, pred)

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("{x:.2f} {y:.2f} moveto "
              "{s:.2f} 0 rlineto "
              "-{mid:.2f} {alt:.2f} rlineto "
              "closepath fill" 
              .format(x=x, y=y, s=s, mid=s/2, alt=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)
    output.flush()
    
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()