"""
 change.py
 
 Find the smallest number of coins to get to a specific amount.


 The greedy algorithm only works for some coinage choices.
 This one, for example, doesn't work :
   (1, 3, 4)
   how many to get to 6?
   greedy ... 4, 1, 1  which is 3 coins
   right answer is two 3's, 2 coins
 For US coins (25, 10, 5, 1), the greedy approach does work.   
 
 We worked through this in class on April 26 2021.

 Jim Mahoney | cs.bennington.college | MIT License
"""

coinage = (1, 5, 10)         # coin denomiations

sorted_coinage = (25, 10, 5, 1)  

def search1(target):
    """ brute force recursive """
    print(f"searching {target}")
    if target in coinage:
        return 1
    else:
        best_answer = target  # all pennies would work ... just not good.
        for coin in coinage:
            if coin <= target:
                answer = 1 + search1(target - coin)
                best_answer = min(best_answer, answer)
        return best_answer

memo = {}    # {target:n, }    
    
def search2(target):
    """ brute force recursive with memoization """
    if target in memo:
        return memo[target]
    print(f"searching {target}")
    if target in coinage:
        memo[target] = 1
    else:
        best_answer = target  # all pennies would work ... just not good.
        for coin in coinage:
            if coin <= target:
                answer = 1 + search2(target - coin)
                best_answer = min(best_answer, answer)
        memo[target] = best_answer
    return memo[target]

def search3(target):
    """ greedy search """
    # "greedy" head towards goal as fast as possible, biggest coin possible
    if target == 0: 
        return 0
    print(f"searching {target}")
    for coin in sorted_coinage:
        #print(" search3 : coin is ", coin)
        if coin <= target:
            #print(" search 3: in if, returning search3(target-coin) ")
            return 1 + search3(target - coin)

def main():
    target = int(input("Making change! target is ? "))
    answer = search3(target)
    print(answer)

if __name__ == '__main__':
    main()