Generators Will Free Your Mind

James Powell

http://gist.github.com/dutc

A Conference "for Python Quants"

forpythonquants.com

I used to be addicted to the Hokey Pokey, but I turned myself around.

Themes

  • generators are a very useful way of modelling problems in Python
  • the ways we model problems using generators is fundamentally different

Not Covered

  • what is a generator; see my previous talks
  • efficiencies
In [1]:
from __future__ import print_function
from __future__ import division
from __future__ import unicode_literals

Functional Programming Has Already Freed Your Mind

In [2]:
from random import randrange

markets = {
    'US':              randrange(-4000000, 4000000),
    'UK':              randrange(-4000000, 4000000),
    'EU':              randrange(-4000000, 4000000),
    'CEMEA':           randrange(-4000000, 4000000),    
    'Central America': randrange(-4000000, 4000000),
    'Asia':            randrange(-4000000, 4000000),
    'Antarctica':      0,
}
In [3]:
def output(markets):
    for region, profit in markets.items():
        print(region, profit)
        
output(markets)
Central America -675140
Asia -3614396
Antarctica 0
US -2724620
UK -2380001
EU 771665
CEMEA 3480172
In [4]:
def output(markets):
    align = max(map(len,markets))
    for region, profit in markets.items():
        print('{region:<{align}}   {profit:>10,}'.format(region=region, profit=profit, align=align))
        
output(markets)
Central America     -675,140
Asia              -3,614,396
Antarctica                 0
US                -2,724,620
UK                -2,380,001
EU                   771,665
CEMEA              3,480,172
In [5]:
def output(markets, filename=None):
    align = max(map(len,markets))
    for region, profit in markets.items():
        line = '{region:<{align}}   {profit:>10,}'.format(region=region,
                                                          profit=profit,
                                                          align=align)
        if filename:
            with open(filename) as f:
                f.write(line)
                
        print(line)
        
output(markets)
Central America     -675,140
Asia              -3,614,396
Antarctica                 0
US                -2,724,620
UK                -2,380,001
EU                   771,665
CEMEA              3,480,172
In [6]:
from logging import info

def output(markets, filename=None, to_log=False):
    align = max(map(len,markets))
    for region, profit in markets.items():
        line = '{region:<{align}}   {profit:>10,}'.format(region=region,
                                                          profit=profit,
                                                          align=align)
        if filename:
            with open(filename) as f:
                f.write(line)
            
        if to_log:
            info(line)
                
        print(line)
        
output(markets, to_log=True)
Central America     -675,140
Asia              -3,614,396
Antarctica                 0
US                -2,724,620
UK                -2,380,001
EU                   771,665
CEMEA              3,480,172
In [7]:
def output(markets, filename=None, to_log=False, to_email=False, accounting=False):
    align = max(map(len,markets))
    
    for region, profit in markets.items():
        if accounting:
            if profit < 0:
                profit = '({:>10,})'.format(-profit)
            else:
                profit = ' {:>10,}'.format(profit)
            
            line = '{region:<{align}}   {profit}'.format(region=region,
                                                         profit=profit,
                                                         align=align)
        if filename:
            with open(filename) as f:
                f.write(line)
            
        if to_log:
            info(line)
                
        print(line)
        
output(markets, accounting=True)
Central America   (   675,140)
Asia              ( 3,614,396)
Antarctica                  0
US                ( 2,724,620)
UK                ( 2,380,001)
EU                    771,665
CEMEA               3,480,172
In [8]:
def output(markets, filename=None, to_log=False, to_email=False, accounting=False):
    align = max(map(len,markets))
    
    if to_email:
        lines = []
        
    for region, profit in markets.items():
        if accounting:
            if profit < 0:
                profit = '({:>10,})'.format(-profit)
            else:
                profit = ' {:>10,}'.format(profit)
            
            line = '{region:<{align}}   {profit}'.format(region=region,
                                                         profit=profit,
                                                         align=align)
        if filename:
            with open(filename) as f:
                f.write(line)
            
        if to_email:
            lines.append(line)
            
        if to_log:
            info(line)
                
        print(line)
    
    if to_email:
        email('\n'.join(lines))
        
output(markets, accounting=True)
Central America   (   675,140)
Asia              ( 3,614,396)
Antarctica                  0
US                ( 2,724,620)
UK                ( 2,380,001)
EU                    771,665
CEMEA               3,480,172
In [9]:
from numbers import Real
class Accounting(Real, float):
    def __metaclass__(name, bases, body):
        for method in Real.__abstractmethods__:
            if method not in body:
                body[method] = (lambda meth: lambda *args, **kwargs: Accounting(getattr(float,meth)(*args, **kwargs)))(method)
        for method in ('__ne__','__nonzero__',):
            if method not in body:
                body[method] = (lambda meth: lambda *args, **kwargs: getattr(float,meth)(*args, **kwargs))(method)
        return Real.__metaclass__(name, bases, body)
    __new__ = float.__new__
    def __format__(self, fmt):        
        return { 1: ' %s'%float.__format__(self, fmt),
                 0: ' %s'%float.__format__(self, fmt).replace('0', '-'),
                -1: '(%s)'%float.__format__(self, fmt) }[cmp(self,0)]
In [10]:
template = '{region:<{align}}   {profit:>14,.0f}'.format
def output(markets, write=print, template=template):
    align = max(map(len,markets))
    for region, profit in markets.items():
        line = template(region=region, profit=profit, align=align)
        write(line)

output({region:Accounting(profit) for region, profit in markets.items()})
Central America   (      -675,140)
US                (    -2,724,620)
Antarctica                      -
Asia              (    -3,614,396)
UK                (    -2,380,001)
EU                        771,665
CEMEA                   3,480,172

Functional Programming Frees Your Mind From Presuming Modalities

Functional Programming Simplified your Internal API

Functional Programming Empowered Your Users

(Pure Functional Programming Has Further Freed Your Mind)

What is a Generator & What is a Coroutine?

In [11]:
def fib(a=1, b=1, n=10):
    rv = []
    for _ in xrange(n):
        rv.append(a)
        a, b = b, a + b
    return rv

fib()
Out[11]:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
In [12]:
def ratio(xs):
    xs = iter(xs)
    x1 = next(xs) # raises StopIteration
    x2 = next(xs)
    rv = [x2/x1]
    x1 = x2
    for x2 in xs:
        rv.append(x2/x1)
        x1 = x2    
    return rv

from math import sqrt
ratio(fib(n=5))
Out[12]:
[1.0, 2.0, 1.5, 1.6666666666666667]
In [13]:
phi = (1+sqrt(5))/2
[abs(x - phi) for x in ratio(fib(n=5))]
Out[13]:
[0.6180339887498949,
 0.3819660112501051,
 0.1180339887498949,
 0.04863267791677184]
In [14]:
# 1.609 km per mi
In [15]:
def fib(a=1, b=1):
    while True:
        yield a
        a, b = b, a + b

from itertools import islice
list(islice(fib(),10))
Out[15]:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
In [16]:
from itertools import islice, izip, tee
nwise = lambda g,n: izip(*(islice(g,i,None) for i,g in enumerate(tee(g,n))))
ratio = lambda g: (y/x for x,y in nwise(g,2))

list(islice(ratio(fib()),5))
Out[16]:
[1.0, 2.0, 1.5, 1.6666666666666667, 1.6]
In [17]:
phi = (1+sqrt(5))/2
[abs(x - phi) for x in islice(ratio(fib()),5)]
Out[17]:
[0.6180339887498949,
 0.3819660112501051,
 0.1180339887498949,
 0.04863267791677184,
 0.018033988749894814]

Generators Free You From Presumptions About Use

In [18]:
def fib(a=1, b=1, n=10):
    rv = []
    for _ in xrange(10):
        rv.append(a)
        a, b = b, a + b
    return rv

print(fib())

def fib(a=1, b=1, n=10):
    rv = []
    while True:
        if a > n: break
        rv.append(a)
        a, b = b, a + b
    return rv

print(fib())
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
[1, 1, 2, 3, 5, 8]
In [19]:
def fib(a=1, b=1):
    while True:
        yield a
        a, b = b, a+b
        
from itertools import islice
print(list(islice(fib(),10)))

from itertools import takewhile
print(list(takewhile(lambda x: x < 10, fib())))

from itertools import dropwhile
print(list(dropwhile(lambda x: x < 5, 
           takewhile(lambda x: x < 100,
           islice(fib(),15)))))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
[1, 1, 2, 3, 5, 8]
[5, 8, 13, 21, 34, 55, 89]
In [20]:
from time import sleep 

def query():
    for x in xrange(10):
        sleep(.1)
        yield x
    
% time list(islice(query(),1))
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 100 ms
Out[20]:
[0]

Generators Free You From Presumptions About Return Type

In [21]:
def process(xs):
    rv = []
    for x in xs:
        rv.append(x)
    return rv
    
def process(xs):
    rv = set()
    for x in xs:
        rv.add(x)
    return rv

def process(xs):
    rv = ()
    for x in xs:
        rv += (x,)
    return rv
In [24]:
def fib(a=1, b=1, n=100):
    rv = []
    for _ in xrange(n):
        rv.append(a)
        a, b = b, a+b
    return rv

% timeit -r 5 fib()

% timeit -r 5 tuple(fib())
% timeit -r 5 set(fib())
100000 loops, best of 5: 13.1 µs per loop
100000 loops, best of 5: 13.5 µs per loop
100000 loops, best of 5: 17.8 µs per loop
In [25]:
def fib(a=1, b=1):
    while True:
        yield a
        a, b = b, a+b  
    
from itertools import islice
% timeit -r 5 list(islice(fib(),100))
% timeit -r 5 tuple(islice(fib(),100))
% timeit -r 5 set(islice(fib(),100))
100000 loops, best of 5: 13.6 µs per loop
100000 loops, best of 5: 13.7 µs per loop
100000 loops, best of 5: 16.5 µs per loop
In [27]:
def average(xs):
    if not isinstance(xs, list):
        raise TypeError('xs must strictly be a list')
    return sum(xs) / len(xs)

average([1,2,4,8,16])
Out[27]:
6.2
In [28]:
average((1,2,4,8,16))
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-28-4a82f84bdc7a> in <module>()
----> 1 average((1,2,4,8,16))

<ipython-input-27-c010f9029beb> in average(xs)
      1 def average(xs):
      2     if not isinstance(xs, list):
----> 3         raise TypeError('xs must strictly be a list')
      4     return sum(xs) / len(xs)
      5 

TypeError: xs must strictly be a list
In [29]:
from collections import Sized

def average(xs):
    if not isinstance(xs, Sized):
        raise TypeError('xs must be Sized')
    return sum(xs) / len(xs)

average((1,2,4,8,16))
Out[29]:
6.2
In [31]:
from collections import Iterable

def average(xs):
    if not isinstance(xs, Iterable):
        raise TypeError('xs must be Iterable')
    total, count = reduce(lambda x,acc: map(sum,zip(x,acc)), ((x,1) for x in xs))
    return total / count

average(2**x for x in xrange(5))
Out[31]:
6.2

Generators Simplify Your APIs & Remove Presumptions About Modes

In [32]:
from time import sleep
from random import randrange

def source():
    for _ in xrange(randrange(10,20)):
        yield randrange(-100, 100)
        sleep(randrange(5,10)/50)

def load_data(source):
    rv = []
    for datum in source:
        average = sum(x for x,_ in rv)/len(rv) if rv else datum
        rv.append((datum, average))
    return rv

load_data(source())
Out[32]:
[(-35, -35),
 (-45, -35.0),
 (88, -40.0),
 (-32, 2.6666666666666665),
 (-67, -6.0),
 (-57, -18.2),
 (83, -24.666666666666668),
 (98, -9.285714285714286),
 (-74, 4.125),
 (-71, -4.555555555555555),
 (-95, -11.2),
 (93, -18.818181818181817)]
In [33]:
def source(n):
    for _ in xrange(n):
        yield randrange(-100, 100)
        sleep(randrange(5,10)/50)

def load_data(source, size):
    rv = []
    for i, datum in enumerate(source):
        average = sum(x for x,_ in rv)/len(rv) if rv else datum
        rv.append((datum, average))
        print('loading {:.2%}'.format(i/size))
    return rv

load_data(source(5), 5)
loading 0.00%
loading 20.00%
loading 40.00%
loading 60.00%
loading 80.00%
Out[33]:
[(-18, -18), (-24, -18.0), (23, -21.0), (22, -6.333333333333333), (35, 0.75)]
In [34]:
def load_data(source, size):
    rv = []
    print('loading', end=' ')
    for i, datum in enumerate(source):
        average = sum(x for x,_ in rv)/len(rv) if rv else datum
        rv.append((datum, average))
        print('{:.2%}'.format(i/size), end=' ')
    print('done loading!')
    return rv

load_data(source(5), 5)
loading 0.00% 20.00% 40.00% 60.00% 80.00% done loading!
Out[34]:
[(22, 22), (-26, 22.0), (19, -2.0), (-19, 5.0), (68, -1.0)]
In [35]:
def load_data(source, size, before, during, after):
    rv = []
    before()
    for i, datum in enumerate(source):
        average = sum(x for x,_ in rv)/len(rv) if rv else datum
        rv.append((datum, average))
        during(i, size)
    after()
    return rv

def before():
    print('loading', end=' ')
def during(i, size):
    print('{:.2%}'.format(i/size), end=' ')
def after():
    print('done loading!')

load_data(source(5), 5, before=after, during=during, after=before)
done loading!
0.00% 20.00% 40.00% 60.00% 80.00% loading 
Out[35]:
[(-26, -26), (-78, -26.0), (86, -52.0), (15, -6.0), (-12, -0.75)]
In [36]:
def load_data(source, update):
    rv = []
    next(update)
    for i, datum in enumerate(source):
        average = sum(x for x,_ in rv)/len(rv) if rv else datum
        rv.append((datum, average))
        update.send(datum)
    next(update)
    update.close()    
    return rv

def update(n):
    print('loading', end=' ')
    count, datum = 0, (yield)
    while datum is not None:        
        print('{:.2%}'.format(count/n), end=' ')        
        count, datum = count+1, (yield)
    print('done loading!')
    while True: yield 

load_data(source(5), update(5))
loading 0.00% 20.00% 40.00% 60.00% 80.00% done loading!
Out[36]:
[(35, 35), (15, 35.0), (91, 25.0), (91, 47.0), (81, 58.0)]
In [37]:
# http://www.sifma.org/services/holiday-schedule/
# "All SIFMA holiday recommendations apply to the trading of U.S. dollar-denominated 
#  government securities, mortgage- and asset-backed securities, over-the-counter 
#  investment-grade and high-yield corporate bonds, municipal bonds and secondary 
#  money market trading in bankers' acceptances, commercial paper and Yankee and 
#  Euro certificates of deposit."
 
from datetime import date 

holidays = {                       # early               # full
    'Bank Holiday #1':               (None,                date(2014,  1,  2)),
    'Bank Holiday #2':               (None,                date(2014,  1,  3)),
    'Coming of Age Day':             (None,                date(2014,  1, 13)),
    'U.S. Martin Luther King Day':   (None,                date(2014,  1, 20)),
    'National Foundation Day':       (None,                date(2014,  2, 11)),
    "U.S. Presidents' Day":          (None,                date(2014,  2, 17)),
    'Spring Equinox':                (None,                date(2014,  3, 21)),
    'Good Friday':                   (None,                date(2014,  4, 18)),
    'U.K Easter Monday':             (date(2014, 4, 21),   None),
    'Showa Day':                     (None,                date(2014,  4, 29)),
    'Constitutional Day':            (None,                None),
    "Children's Day":                (None,                date(2014,  5,  5)),
    'U.K. May Day':                  (None,                date(2014,  5,  5)),
    'Greenery Day':                  (None,                date(2014,  5,  6)),
    'U.S. Memorial Day':             (None,                date(2014,  5, 26)),
    'U.K. Spring Bank Holiday':      (None,                date(2014,  5, 26)),
    "U.K. Queen's Diamond Jubilee":  (None,                None),
    'U.S. Independence Day':         (None,                date(2014,  7,  4)),
    'Marine Day':                    (None,                date(2014,  7, 21)),
    'U.K. Summer Bank Holiday':      (date(2014, 8, 25),   None),
    'U.S. Labor Day':                (None,                date(2014,  9,  1)),
    'Respect for the Aged Day':      (None,                date(2014,  9, 15)),
    'Autumn Equinox':                (None,                date(2014,  9, 23)),
    'Sports Day/U.S. Columbus Day':  (None,                date(2014, 10, 13)),
    'Culture Day':                   (None,                date(2014, 11,  3)),
    'U.S. Veterans Day':             (None,                date(2014, 11, 11)),
    'Labor Thanksgiving Day':        (None,                date(2014, 11, 24)),
    'U.S. Thanksgiving Day':         (None,                date(2014, 11, 27)),
    "Emperor's Birthday":            (None,                date(2014, 12, 23)),
    'Christmas Day':                 (None,                date(2014, 12, 25)),
    'U.K. Boxing Day':               (date(2014, 12, 26),  None),
    'Bank Holiday #3':               (None,                date(2014, 12, 31)), }
In [38]:
from datetime import timedelta
def nthbusinessdate(refdate, n, holidays={full for early,full in holidays.values()}):    
    while n > 0:
        refdate += timedelta(days=1)
        while refdate.weekday() in {5,6} or refdate in holidays:
            refdate += timedelta(days=1)
        n -= 1
    return refdate
    
#       July 2014        
#  Su  Mo  Tu  We  Th  Fr  Sa
#           1   2   3   4*  5  
#   6   7   8   9  10  11  12  
#  13  14  15  16  17  18  19  
#  20  21* 22  23  24  25  26  
#  27  28  29  30  31      

nthbusinessdate(date(2014,7,2), 2)
Out[38]:
datetime.date(2014, 7, 7)
In [39]:
nthbusinessdate(date(2014,7,2), 1), nthbusinessdate(date(2014,7,2), 2), nthbusinessdate(date(2014,7,2), 3)
Out[39]:
(datetime.date(2014, 7, 3),
 datetime.date(2014, 7, 7),
 datetime.date(2014, 7, 8))
In [40]:
def businessdays(refdate, holidays={full for early,full in holidays.values()}):    
    while True:
        refdate += timedelta(days=1)
        while refdate.weekday() in {5,6} or refdate in holidays:
            refdate += timedelta(days=1)
        yield refdate

g = businessdays(date(2014,7,2))
next(g), next(g), next(g)
Out[40]:
(datetime.date(2014, 7, 3),
 datetime.date(2014, 7, 7),
 datetime.date(2014, 7, 8))
In [41]:
from operator import add, sub
NBD, PBD = add, sub
def businessdays(refdate, direction=NBD, holidays={full for early,full in holidays.values()}):    
    while True:
        refdate = direction(refdate, timedelta(days=1))
        while refdate.weekday() in {5,6} or refdate in holidays:
            refdate = direction(refdate, timedelta(days=1))
        yield refdate

g = businessdays(date(2014,7,2), direction=PBD)
next(g), next(g), next(g)
Out[41]:
(datetime.date(2014, 7, 1),
 datetime.date(2014, 6, 30),
 datetime.date(2014, 6, 27))
In [42]:
NBD, PBD = lambda d: d+timedelta(days=1), lambda d: d-timedelta(days=1)

def datecount(refdate, direction=NBD):
    while True:
        yield refdate
        refdate = direction(refdate)
        
def businessdays(refdate, direction=NBD, holidays={full for early,full in holidays.values()}):    
    return (d for d in datecount(refdate, direction) if d.weekday() not in {5,6} and d not in holidays)

g = businessdays(date(2014,7,2), direction=PBD)
next(g), next(g), next(g)
Out[42]:
(datetime.date(2014, 7, 2),
 datetime.date(2014, 7, 1),
 datetime.date(2014, 6, 30))
In [43]:
g = businessdays(date(2014,7,2), direction=NBD)
next(g), next(g), next(g)
Out[43]:
(datetime.date(2014, 7, 2),
 datetime.date(2014, 7, 3),
 datetime.date(2014, 7, 7))
In [44]:
from functools import wraps

def pumped(gen):
    @wraps(gen)
    def inner(*args, **kwargs):
        g = gen(*args, **kwargs)
        next(g)
        return g.send
    return inner
In [46]:
@pumped
def jp_holidays(): # Jurassic Park    
    
    @apply
    def calendar(): # simulate lookup
        for d in sorted(full for early,full in holidays.values() if full is not None):
            sleep(.2)
            yield d
    
    refdate, next_holiday = None, next(calendar)
    while True:
        refdate = yield (refdate == next_holiday)
        while refdate > next_holiday:
            next_holiday = next(calendar)
        
def businessdays(refdate, direction=NBD, holidays=lambda _: False):
    return (d for d in datecount(refdate, direction) if d.weekday() not in {5,6} and not holidays(d))

g = businessdays(date(2014,7,2), direction=NBD, holidays=jp_holidays())
% time list(islice(g,3))
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 3 s
Out[46]:
[datetime.date(2014, 7, 2),
 datetime.date(2014, 7, 3),
 datetime.date(2014, 7, 7)]
In [47]:
% time list(islice(g,11,12))
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 200 ms
Out[47]:
[datetime.date(2014, 7, 24)]
In [48]:
from decimal import Decimal

def change(amount, denominations = map(Decimal,('1.00', '0.50', '0.25', '0.10', '0.05', '0.01'))):
    coins = []       
    while any(amount >= d for d in denominations):        
        coins.append(next((d for d in denominations if amount >= d)))
        amount -= coins[-1]
    return coins
                
change(Decimal('1.72'))
Out[48]:
[Decimal('1.00'),
 Decimal('0.50'),
 Decimal('0.10'),
 Decimal('0.10'),
 Decimal('0.01'),
 Decimal('0.01')]
In [49]:
from decimal import Decimal

def change(amount, denominations = {Decimal(d):5 for d in ('1.00', '0.50', '0.25', '0.10', '0.05', '0.01')}):
    coins = []       
    while any(amount >= d for d in sorted(denominations,reverse=True) if denominations[d] > 0):        
        coins.append(next(d for d in sorted(denominations,reverse=True) if amount >= d and denominations[d] > 0))
        denominations[coins[-1]] -= 1
        amount -= coins[-1]
    return coins
                
print(change(Decimal('1.72')))
[Decimal('1.00'), Decimal('0.50'), Decimal('0.10'), Decimal('0.10'), Decimal('0.01'), Decimal('0.01')]
In [50]:
print(change(Decimal('1.72'), denominations={Decimal('0.50'): 3, Decimal('0.10'): 10, Decimal('0.01'): 20}))
[Decimal('0.50'), Decimal('0.50'), Decimal('0.50'), Decimal('0.10'), Decimal('0.10'), Decimal('0.01'), Decimal('0.01')]
In [51]:
print(change(Decimal('1.72'), denominations={Decimal('0.50'): 2, Decimal('0.10'): 10, Decimal('0.01'): 20}))
[Decimal('0.50'), Decimal('0.50'), Decimal('0.10'), Decimal('0.10'), Decimal('0.10'), Decimal('0.10'), Decimal('0.10'), Decimal('0.10'), Decimal('0.10'), Decimal('0.01'), Decimal('0.01')]
In [52]:
from itertools import repeat, chain, takewhile
greedy = lambda items, predicate: chain.from_iterable(takewhile(predicate,repeat(x)) for x in items)
In [53]:
@pumped
def predicate(x, state=0):
    value = yield
    while True:
        if state+value <= x: # take values until you exceed the maximum
            state += value
            value = yield True 
        else:
            value = yield False
In [58]:
amounts = [randrange(0,1000) for _ in xrange(5)] # randomly pick dollar amounts
In [59]:
from itertools import groupby

denominations = [1,5,10,25,100,500,1000,2000]

for amount in amounts:
    pred = predicate(amount) # create the predicate

    coins = greedy(reversed(denominations), pred) # greedy algorithm

    # pretty print
    print('your change for {:>5.2f}$ = {}'.format(amount/100, 
          ' + '.join('{:>2d}×{:<3}'.format(sum(1 for _ in cs),
          (('{:d}¢' if c < 100 else '{:.0f}$').format(c if c < 100 else c/100))) for c,cs in groupby(coins))))
your change for  7.44$ =  1×5$  +  2×1$  +  1×25¢ +  1×10¢ +  1×5¢  +  4×1¢ 
your change for  9.09$ =  1×5$  +  4×1$  +  1×5¢  +  4×1¢ 
your change for  8.60$ =  1×5$  +  3×1$  +  2×25¢ +  1×10¢
your change for  0.96$ =  3×25¢ +  2×10¢ +  1×1¢ 
your change for  7.41$ =  1×5$  +  2×1$  +  1×25¢ +  1×10¢ +  1×5¢  +  1×1¢ 
In [60]:
@pumped
def predicate(x, state=0, constraint=lambda _, __: True):
    values = []
    value = yield
    while True:
        if state+value <= x and constraint(values, value): # take values until you exceed the maximum
            state += value
            value = yield True
            values.append(value)
        else:
            value = yield False
In [70]:
from collections import Counter
three_coins = lambda coins, coin: Counter(coins)[coin] < 2

for amount in amounts:
    pred = predicate(amount, constraint=three_coins) # create the predicate

    coins = list(greedy(reversed(denominations), pred)) # greedy algorithm

    # pretty print
    print('your change for {:>5.2f}$ -{:>5.2f}$ = {}'.format(amount/100, (amount - sum(coins))/100,
          ' + '.join('{:>2d}×{:<3}'.format(sum(1 for _ in cs),
          (('{:d}¢' if c < 100 else '{:.0f}$').format(c if c < 100 else c/100))) for c,cs in groupby(coins))))
your change for  7.44$ - 0.02$ =  1×5$  +  2×1$  +  1×25¢ +  1×10¢ +  1×5¢  +  2×1¢ 
your change for  9.09$ - 1.27$ =  1×5$  +  2×1$  +  2×25¢ +  2×10¢ +  2×5¢  +  2×1¢ 
your change for  8.60$ - 0.78$ =  1×5$  +  2×1$  +  2×25¢ +  2×10¢ +  2×5¢  +  2×1¢ 
your change for  0.96$ - 0.14$ =  2×25¢ +  2×10¢ +  2×5¢  +  2×1¢ 
your change for  7.41$ - 0.00$ =  1×5$  +  2×1$  +  1×25¢ +  1×10¢ +  1×5¢  +  1×1¢ 
In [62]:
roman = {  1:  'i',   4: 'iv',    5:  'v',   9: 'ix',  10: 'x',
          40: 'ix',  50:  'x',   90: 'xc', 100:  'c', 400: 'cd',
         500:  'd', 900: 'cm', 1000:  'm',}
In [63]:
years = [randint(1900,2200) for _ in xrange(5)] # randomly pick a year
In [64]:
@pumped
def predicate(x, state=0, constraint=lambda _, __: True):
    values = []
    value = yield
    while True:
        if state+value <= x and constraint(values, value): # take values until you exceed the maximum
            state += value
            value = yield True
            values.append(value)
        else:
            value = yield False
In [65]:
for year in years:    
    pred = predicate(year) # create the predicate
    
    numerals = greedy(reversed(sorted(roman)), pred) # greedy algorithm
    
    print('the year {} is written {}'.format( year,''.join(roman[x].upper() for x in list(numerals))))
the year 1903 is written MCMIII
the year 2052 is written MMXII
the year 2029 is written MMXXIX
the year 1975 is written MCMXXXV
the year 1945 is written MCMIXV

Generators Have Freed Your Mind

Go In Peace

James Powell

[email protected]

@dontusethiscode

seriously.dontusethiscode.com

dutc on irc.freenode.net