""" coins.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 programming) on two different sets of coins, (1,5,10) and (1,6,10), both 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 output is in coins_output.txt : $ python --version Python 3.10.1 $ python coins.py > coins_output.txt This is an updated version of my python2 code from 2013, cs.bennington.college/courses/spring2021/algorithms/code/search/coins_2013_python2.py Resources: * https://en.wikipedia.org/wiki/Change-making_problem * https://en.wikipedia.org/wiki/Brute-force_search * https://en.wikipedia.org/wiki/Greedy_algorithm * https://en.wikipedia.org/wiki/Dynamic_programming * https://runestone.academy/ns/books/published/pythonds/Recursion/DynamicProgramming.html Jim Mahoney | May 2022 | cs.bennington.college | 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] + ... , i.e. dot product >>> dot([1,2,3], [2,8,3]) # 1*2 + 2*8 + 3*3 = 2+16+9 27 """ result = 0 for i in range(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 range(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(f"bruteforce on coinset={coinset} with goal={goal} ") print(f" number of solutions found = {len(results)} : ") for result in results: print(f" {result} ") print(f" fewest coins is {sum(best_result)} : {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(f" greedy debug: coinset={coinset}, goal={goal}, change={change} ") if change == None: change = empty_changepurse(coinset) remaining = goal - dot(coinset, change) if remaining == 0: if verbose: print(f"greedy coinset={coinset}, goal={goal} ") print(f"finds {sum(change)} coins : {change} ") print() return change else: for i in range(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. """ # The algorithm is based on this recursion relation : # 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 for re-use. if goal == 0: return empty_changepurse(coinset) key = (goal, coinset) if key in dynamic_save: return dynamic_save[key] else: candidates = [] # possible answers for i in range(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(f" dynamic : coinset={coinset}, goal={goal}, change={change}) ") dynamic_save[key] = change[:]; return change def main(): goal = 24 coinsets = ((1,5,10), (1,6,10)) for coins in coinsets: print('== brute force ' + '='*40) bruteforce(coins, goal, verbose=True) print('== greedy search ' + '='*40) greedy(coins, goal, verbose=True) print('== dynamic programming ' + '='*40) dynamic(coins, goal, verbose=True) print() if __name__ == '__main__': import doctest doctest.testmod() main()