amb.py

# compute pythagorean triples using nondeterministic choice
# skip ahead to the 'pythag' function

import time
c0 = time.clock()
def nondet (fn):
  def replacement (*args):
    c = []
    def Return (x):
      c.append(x)
      raise StopIteration()
    nondet_pump(lambda:fn(Return, *args))
    return c

  replacement.__name__ = fn.__name__ + "_unyield"
  return replacement

def nondet_pump (initiator, prefix=[]):
  it = initiator()
  xs = it.next()
  try:
    for p in prefix:
      xs = it.send(p)
    for x in xs:
      nondet_pump(initiator, prefix+[x])
  except StopIteration:
    pass

@nondet
def pythag(Return, amax, bmax,cmax):
  """finds pythagorean triples such that a<=amax, 
  b<=bmax, c<=cmax, and a<=b<=c"""

  # yield picks a value from the range
  a = yield range(1,amax+1)
  b = yield range(a,bmax+1)
  c = yield range(b,cmax+1)
  if a*a + b*b == c*c:
    Return((a,b,c))

for triple in pythag(20,20,20):
  print triple
c1 = time.clock()
print "elapsed time: %s seconds"%(c1-c0)