from __future__ import print_function, division
from itertools import starmap, product
import numpy as np
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
coins = [1, 2, 4]
obtainable(coins)
{1, 2, 3, 4, 5, 6, 8}
values = set(range(1, 21))
def unobtainable(coins):
"""Find values that can't be obtained with the given coins."""
return values - obtainable(coins)
unobtainable(coins)
{7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
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
set(possible_new_coin(coins, 7))
{3, 5, 6}
set(possible_new_coin(coins, 9))
{5, 7, 8}
set(possible_new_coin(coins, 10))
{5, 6, 8, 9}
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))
frozenset((1,))
frozenset({1})
values = set(range(1, 21))
combinator = Combinator(values)
combinator.consider(frozenset((1,)))
combinator.smallest
6
combinator.print_winners()
[1, 3, 5, 6, 13, 14] [1, 3, 4, 8, 9, 11] [1, 3, 5, 7, 9, 10] [1, 3, 4, 9, 11, 16] [1, 2, 5, 8, 9, 10]