Skip to content

Instantly share code, notes, and snippets.

@gfhuertac
Last active July 6, 2020 12:37
Show Gist options
  • Save gfhuertac/19e3db2ed4d639802a6eecec1e2b2b73 to your computer and use it in GitHub Desktop.
Save gfhuertac/19e3db2ed4d639802a6eecec1e2b2b73 to your computer and use it in GitHub Desktop.
Combination of coins to achieve a total
"""
From: https://breadth.substack.com/p/what-the-hell-is-a-deno
In Australia, we have the following coins:
5¢ 10¢ 20¢ 50¢ $1 and $2 coins.
One way of making up $3 is by:
$1 + 50¢ + 50¢ + 50¢ + 20¢ + 20¢ + 10¢
What is the total number of ways you can create $3 out of the 6 above listed coins?
"""
from collections import Counter
combinations = []
def ways(sorted_coins, target, frm=0, cnt=Counter()):
global combinations
if target == 0:
for c in combinations:
if c == cnt: return 0
combinations.append(cnt)
return 1
elif target < 0 or frm >= len(sorted_coins):
return 0
return ways(sorted_coins, round(target-sorted_coins[frm], 2), frm, cnt + Counter({sorted_coins[frm]:1})) + ways(sorted_coins, target, frm+1, cnt+Counter())
def main():
coins = [0.05, 0.1, 0.2, 0.5, 1, 2]
target = 3
sorted_coins = sorted(coins, reverse=True)
frm = 0
while sorted_coins[frm] > target:
frm += 1
if frm == len(sorted_coins):
raise ValueError("Amount is not possible!")
print(ways(sorted_coins, target, frm))
#print(combinations)
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment