In [1]:
from __future__ import print_function, division
from itertools import starmap, product
import numpy as np
In [2]:
def obtainable(coins):
"""Find the set of values obtainable with the given coins."""
combos = set(coins)
combos.update(map(sum, product(coins, coins)))
return combos
In [3]:
coins = [1, 2, 4]
In [4]:
obtainable(coins)
Out[4]:
In [5]:
values = set(range(1, 21))
def unobtainable(coins):
"""Find values that can't be obtained with the given coins."""
return values - obtainable(coins)
In [6]:
unobtainable(coins)
Out[6]:
In [7]:
def possible_new_coin(coins, value):
"""Generate new coins that would make the given value obtainable."""
if value % 2 == 0:
yield value // 2
for coin in coins:
if value > coin:
yield value - coin
In [8]:
set(possible_new_coin(coins, 7))
Out[8]:
In [9]:
set(possible_new_coin(coins, 9))
Out[9]:
In [10]:
set(possible_new_coin(coins, 10))
Out[10]:
In [11]:
class Combinator:
def __init__(self, values):
self.values = values
combo = frozenset({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90})
self.combos = {combo}
self.smallest = len(combo)
def add_combo(self, coins):
"""Add a combo to the cache and update `smallest`."""
self.combos.add(coins)
n = len(coins)
if n < self.smallest:
self.smallest = n
def unobtainable(self, coins):
"""Find values that can't be obtained with the given coins."""
return self.values - obtainable(coins)
def consider(self, coins):
"""Starting with `coins`, search for a minimal combo."""
# if we've already seen better, don't bother
if len(coins) > self.smallest:
return
# find unobtainable values
bad_values = unobtainable(coins)
# if all values are obtainable, we're set
if len(bad_values) == 0:
self.add_combo(coins)
return
# otherwise, consider possible coins we could add
for value in bad_values:
for new_coin in possible_new_coin(coins, value):
self.consider(coins | {new_coin})
def print_winners(self):
"""Print the best combinations."""
for combo in self.combos:
if len(combo) == self.smallest:
print(sorted(combo))
In [14]:
frozenset((1,))
Out[14]:
In [16]:
values = set(range(1, 21))
combinator = Combinator(values)
combinator.consider(frozenset((1,)))
In [17]:
combinator.smallest
Out[17]:
In [18]:
combinator.print_winners()
In [ ]: