"""
 coins_2013_python2.py

 Making change with the fewest numbers of coins.
 From an exercise in chapter 8 of Skiena's algorithms textbook.

 I'll look at three different algorithms (brute force, greedy, dynamic)
 on two different sets of coins, (1,5,10) and (1,6,10),
 with a goal of 24.

  * brute force
    good:
      - always finds the right answer
      - easily counts total solutions
      - (fairly) straightforward search
    bad: slow; O(product_over_i(goal/coinset[i])) e.g. (24)*(24/5)*(24/10)

  * greedy
    good:
      - fast O(goal)
      - (fairly) straightforward recursive search
    bad:
      - only gives correct answer for some coinsets
        (1,5,10) : yes, because each one is sum of previous
        (1,6,10) : no (e.g. 24 = 4 sixes; greedy gives 2 tens and 4 ones)

  * dynamic programming
    good:
      - fast O(goal)
      - always correct
      - can count total solutions ... but needs a 2nd recursion relation
    bad:
      - more memory than others
      - trickiest to design (need to understand sub-problems)

 The (fairly long) output is at the bottom of this file.

 Tested with Python 2.x

 Jim Mahoney | April 2013 | cs.marlboro.edu | MIT License
"""

# Variables:
#    coinset   = denominations, e.g. (1,5,10) = (pennies, nickels, dimes).
#                Must be sorted (lowest ... highest)
#    goal      = target amount, e.g. 24 cents.
#    change    = how many of each, e.g. [1,2,0] for one penny and two nickels.

def dot(seq1, seq2):
    """ Return seq1[0]*seq2[0] + seq1[1]*seq2[1] + ...
        >>> dot([1,2,3], [2,8,3])  # 1*2 + 2*8 + 3*3 = 2+16+9
        27
    """
    result = 0
    for i in xrange(len(seq1)):
        result += seq1[i] * seq2[i]
    return result

def empty_changepurse(coinset):
    """ Return [0,0,0,...] with length same as coinset.
        >>> empty_changepurse((1,5,10))
        [0, 0, 0]
    """
    return [0] * len(coinset)

def increment_with_carry(change, coinset, goal):
    """ Increment change's digits using a 'carry the one' counting scheme. """
    change[0] += 1
    for i in xrange(len(coinset) - 1):
        if change[i] * coinset[i] > goal:   # This digit over the max?
            change[i] = 0                   #  ... then 'carry the one'
            change[i+1] += 1   

def fewest_coins(solutions):
    """ Given a list of changepurses, return one with the fewest coins.
        >>> fewest_coins([[1,2,3], [0,1,2]])  # 1st has 6 coins, 2nd has 3.
        [0, 1, 2]
    """
    if len(solutions) == 0:
        return []
    coins = sum(solutions[0]) + 1   # bigger than one of the solutions
    for s in solutions:
        if sum(s) < coins:
            coins = sum(s)          # best result so far
            change = s[:]
    return change

def bruteforce(coinset, goal, verbose=False):
    """ Return change needed to reach goal using a bruteforce approach. """
    change = empty_changepurse(coinset)
    results = []
    while change[-1] * coinset[-1] <= goal:
        increment_with_carry(change, coinset, goal)
        if dot(change, coinset) == goal:
            results.append(change[:])
    best_result = fewest_coins(results)
    if verbose:
        print "bruteforce on coinset=%s with goal=%i : " % (str(coinset), goal)
        print " number of solutions found = %i : " % len(results)
        for result in results:
            print "   %s " % str(result)
        print " fewest coins is %i : %s " % (sum(best_result),str(best_result))
        print
    return best_result

def greedy(coinset, goal, change=None, verbose=False):
    """ Return change needed to reach goal using a greedy approach. """
    if verbose:
        print " greedy debug: coinset=%s, goal=%i, change=%s " % \
            (str(coinset), goal, str(change))
    if change == None:
        change = empty_changepurse(coinset)
    remaining = goal - dot(coinset, change)
    if remaining == 0:
        if verbose:
            print "greedy coinset=%s, goal=%i " % (str(coinset), goal),
            print "finds %i coins : %s " % (sum(change), str(change))
            print
        return change
    else:
        for i in xrange(len(coinset)-1, -1, -1):
            if coinset[i] <= remaining:
                new_change = change[:]
                new_change[i] += 1
                return greedy(coinset, goal, new_change, verbose)
        # Oops - none of the denominations worked.
        return empty_changepurse(coinset)   # Error return

dynamic_save = {}  # (key,value) = ((goal,coinset), change_min_coins)

def dynamic(coinset, goal, verbose=False):
    """ Return change needed to reach goal using a dyn. prog. approach. """
    # This is very similar to the knapsack problem we did in class last week.
    #     dynamic(coinset, goal) =
    #        min number of coins over all denominations that work (
    #           n_coins(dynamic(coinset, goal-coin)) + 1
    #        )
    # We consider every possible way to have one few coin, recursively.
    # The previously computed answers are saved.
    if goal == 0:
        return empty_changepurse(coinset)
    key = (goal, coinset)
    if dynamic_save.has_key(key):
        return dynamic_save[key]
    else:
        candidates = []      # possible answers 
        for i in xrange(len(coinset)):
            if coinset[i] <= goal:
                subgoal = goal - coinset[i]
                change_without_coin = dynamic(coinset, subgoal, verbose)
                change_with = change_without_coin[:] # one more of this coin
                change_with[i] += 1                  # 
                candidates.append(change_with[:])
        # Now that we've constructed the possible answers,
        # pick the one with the smallest number of coins,
        # save & return it.
        change = fewest_coins(candidates)
        if verbose:
            print " dynamic : coinset=%s, goal=%i, change=%s " % \
                (str(coinset), goal, str(change))
        dynamic_save[key] = change[:];
        return change

def main():
    goal = 24
    coinsets = ((1,5,10), (1,6,10))
    for cs in coinsets:
        bruteforce(cs, goal, verbose=True)
        greedy(cs, goal, verbose=True)
        print
        dynamic(cs, goal, verbose=True)
        print

if __name__ == '__main__':
    import doctest
    doctest.testmod()
    main()

"""
---------- output -------------

$ python coins.py 
bruteforce on coinset=(1, 5, 10) with goal=24 : 
 number of solutions found = 9 : 
   [24, 0, 0] 
   [19, 1, 0] 
   [14, 2, 0] 
   [9, 3, 0] 
   [4, 4, 0] 
   [14, 0, 1] 
   [9, 1, 1] 
   [4, 2, 1] 
   [4, 0, 2] 
 fewest coins is 6 : [4, 0, 2] 

 greedy debug: coinset=(1, 5, 10), goal=24, change=None 
 greedy debug: coinset=(1, 5, 10), goal=24, change=[0, 0, 1] 
 greedy debug: coinset=(1, 5, 10), goal=24, change=[0, 0, 2] 
 greedy debug: coinset=(1, 5, 10), goal=24, change=[1, 0, 2] 
 greedy debug: coinset=(1, 5, 10), goal=24, change=[2, 0, 2] 
 greedy debug: coinset=(1, 5, 10), goal=24, change=[3, 0, 2] 
 greedy debug: coinset=(1, 5, 10), goal=24, change=[4, 0, 2] 
greedy coinset=(1, 5, 10), goal=24  finds 6 coins : [4, 0, 2] 


 dynamic : coinset=(1, 5, 10), goal=1, change=[1, 0, 0] 
 dynamic : coinset=(1, 5, 10), goal=2, change=[2, 0, 0] 
 dynamic : coinset=(1, 5, 10), goal=3, change=[3, 0, 0] 
 dynamic : coinset=(1, 5, 10), goal=4, change=[4, 0, 0] 
 dynamic : coinset=(1, 5, 10), goal=5, change=[0, 1, 0] 
 dynamic : coinset=(1, 5, 10), goal=6, change=[1, 1, 0] 
 dynamic : coinset=(1, 5, 10), goal=7, change=[2, 1, 0] 
 dynamic : coinset=(1, 5, 10), goal=8, change=[3, 1, 0] 
 dynamic : coinset=(1, 5, 10), goal=9, change=[4, 1, 0] 
 dynamic : coinset=(1, 5, 10), goal=10, change=[0, 0, 1] 
 dynamic : coinset=(1, 5, 10), goal=11, change=[1, 0, 1] 
 dynamic : coinset=(1, 5, 10), goal=12, change=[2, 0, 1] 
 dynamic : coinset=(1, 5, 10), goal=13, change=[3, 0, 1] 
 dynamic : coinset=(1, 5, 10), goal=14, change=[4, 0, 1] 
 dynamic : coinset=(1, 5, 10), goal=15, change=[0, 1, 1] 
 dynamic : coinset=(1, 5, 10), goal=16, change=[1, 1, 1] 
 dynamic : coinset=(1, 5, 10), goal=17, change=[2, 1, 1] 
 dynamic : coinset=(1, 5, 10), goal=18, change=[3, 1, 1] 
 dynamic : coinset=(1, 5, 10), goal=19, change=[4, 1, 1] 
 dynamic : coinset=(1, 5, 10), goal=20, change=[0, 0, 2] 
 dynamic : coinset=(1, 5, 10), goal=21, change=[1, 0, 2] 
 dynamic : coinset=(1, 5, 10), goal=22, change=[2, 0, 2] 
 dynamic : coinset=(1, 5, 10), goal=23, change=[3, 0, 2] 
 dynamic : coinset=(1, 5, 10), goal=24, change=[4, 0, 2] 

bruteforce on coinset=(1, 6, 10) with goal=24 : 
 number of solutions found = 9 : 
   [24, 0, 0] 
   [18, 1, 0] 
   [12, 2, 0] 
   [6, 3, 0] 
   [0, 4, 0] 
   [14, 0, 1] 
   [8, 1, 1] 
   [2, 2, 1] 
   [4, 0, 2] 
 fewest coins is 4 : [0, 4, 0] 

 greedy debug: coinset=(1, 6, 10), goal=24, change=None 
 greedy debug: coinset=(1, 6, 10), goal=24, change=[0, 0, 1] 
 greedy debug: coinset=(1, 6, 10), goal=24, change=[0, 0, 2] 
 greedy debug: coinset=(1, 6, 10), goal=24, change=[1, 0, 2] 
 greedy debug: coinset=(1, 6, 10), goal=24, change=[2, 0, 2] 
 greedy debug: coinset=(1, 6, 10), goal=24, change=[3, 0, 2] 
 greedy debug: coinset=(1, 6, 10), goal=24, change=[4, 0, 2] 
greedy coinset=(1, 6, 10), goal=24  finds 6 coins : [4, 0, 2] 


 dynamic : coinset=(1, 6, 10), goal=1, change=[1, 0, 0] 
 dynamic : coinset=(1, 6, 10), goal=2, change=[2, 0, 0] 
 dynamic : coinset=(1, 6, 10), goal=3, change=[3, 0, 0] 
 dynamic : coinset=(1, 6, 10), goal=4, change=[4, 0, 0] 
 dynamic : coinset=(1, 6, 10), goal=5, change=[5, 0, 0] 
 dynamic : coinset=(1, 6, 10), goal=6, change=[0, 1, 0] 
 dynamic : coinset=(1, 6, 10), goal=7, change=[1, 1, 0] 
 dynamic : coinset=(1, 6, 10), goal=8, change=[2, 1, 0] 
 dynamic : coinset=(1, 6, 10), goal=9, change=[3, 1, 0] 
 dynamic : coinset=(1, 6, 10), goal=10, change=[0, 0, 1] 
 dynamic : coinset=(1, 6, 10), goal=11, change=[1, 0, 1] 
 dynamic : coinset=(1, 6, 10), goal=12, change=[0, 2, 0] 
 dynamic : coinset=(1, 6, 10), goal=13, change=[1, 2, 0] 
 dynamic : coinset=(1, 6, 10), goal=14, change=[2, 2, 0] 
 dynamic : coinset=(1, 6, 10), goal=15, change=[3, 2, 0] 
 dynamic : coinset=(1, 6, 10), goal=16, change=[0, 1, 1] 
 dynamic : coinset=(1, 6, 10), goal=17, change=[1, 1, 1] 
 dynamic : coinset=(1, 6, 10), goal=18, change=[0, 3, 0] 
 dynamic : coinset=(1, 6, 10), goal=19, change=[1, 3, 0] 
 dynamic : coinset=(1, 6, 10), goal=20, change=[0, 0, 2] 
 dynamic : coinset=(1, 6, 10), goal=21, change=[1, 0, 2] 
 dynamic : coinset=(1, 6, 10), goal=22, change=[0, 2, 1] 
 dynamic : coinset=(1, 6, 10), goal=23, change=[1, 2, 1] 
 dynamic : coinset=(1, 6, 10), goal=24, change=[0, 4, 0] 


"""