#!/usr/bin/env python3
''' What proportion of decimal coin systems with 5 denominations are NOT greedy soluble?
use multi-core, which on my quad-core box yields a 30 pct reduction in runtime '''
import math, itertools, multiprocessing

def greedy(coins, target, cnt=0):
    for c in sorted(coins, reverse=True):
        while c <= target:
            target -= c
            cnt += 1
    return cnt

assert greedy( {1,5,10}, 11 ) == 2
assert greedy( {1,10,15}, 20 ) == 6

cache = {}
def dynamic(coins, target):
    if target == 0:
        return 0
    e = cache.get( (frozenset(coins), target), None )
    if e is not None:
        return e
    subcoins = { c for c in coins if c <= target }
    m = min([ target//c + dynamic(subcoins - {c}, target%c) for c in subcoins ])
    if len(coins) <= 3:
        cache[ (frozenset(coins), target) ] = m
    return m

assert dynamic( {1,5,10}, 11 ) == 2
assert dynamic( {1,10,15}, 20 ) == 2

def is_greedy(coins):
    for target in range(99, 0, -1):
        if greedy(coins, target) != dynamic(coins, target):
            return False
    return True

def run(combo):
    return 1 if not is_greedy(set(combo) | {1}) else 0


p = multiprocessing.Pool( multiprocessing.cpu_count() - 1 )
it = p.map(run, itertools.combinations( range(2,100), 4 ))
inequals = sum( it )
total    = len( it )
print('{:5.2} of {}'.format( inequals / total, total) )