coins



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]:
{1, 2, 3, 4, 5, 6, 8}

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]:
{7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}

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]:
{3, 5, 6}

In [9]:
set(possible_new_coin(coins, 9))


Out[9]:
{5, 7, 8}

In [10]:
set(possible_new_coin(coins, 10))


Out[10]:
{5, 6, 8, 9}

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]:
frozenset({1})

In [16]:
values = set(range(1, 21))
combinator = Combinator(values)
combinator.consider(frozenset((1,)))

In [17]:
combinator.smallest


Out[17]:
6

In [18]:
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]

In [ ]: