Instantly share code, notes, and snippets.

# dblume/first_attempt.py

Last active August 29, 2015 14:22
Show Gist options
• Save dblume/c30fbbe408fb03b644ad to your computer and use it in GitHub Desktop.
Ways to Break a Dollar into Change
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 def ways_to_break(amount, coins): """ :param amount: the monetary value to break into some number of coins :param coins: a container of descending coin denominations :return: the number of different ways to break amount into coins """ this_coin = coins[0] # If this is the only coin, there's one way to break it. if len(coins) == 1: return 1 # Note range is never empty, we always want to try with 0 of this coin. total = 0 for coin_value in range(0, amount+1, this_coin): total += ways_to_break(amount - coin_value, coins[1:]) return total print ways_to_break(100, (100, 50, 25, 10, 5, 1))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 def ways_to_break(amount, coins): """ :param amount: the monetary value to break into some number of coins :param coins: a mutable container of coin denominations :return: the number of different ways to break amount into coins """ this_coin = coins.pop() # If that was the only coin, see if it can break amount. if not coins: if amount % this_coin: return 0 else: return 1 # For every time this coin denomination could be used (including zero), # get the number of ways to break the remaining amount with only the # remaining coins. return sum([ways_to_break(amount - coin_value, coins[:]) for coin_value in range(0, amount+1, this_coin)]) # The list of coins doesn't have to be ordered now, but there'll # be fewer calls if the biggest denominations are processed first. print ways_to_break(100, [1, 5, 10, 25, 50, 100])