Skip to content

Instantly share code, notes, and snippets.

@9seconds
Created December 28, 2018 12:17
Show Gist options
  • Save 9seconds/419a0eaedbfea937dcd7ea7aa9f3f72e to your computer and use it in GitHub Desktop.
Save 9seconds/419a0eaedbfea937dcd7ea7aa9f3f72e to your computer and use it in GitHub Desktop.
Coins task solution
#!/usr/bin/env python3
import sys
import itertools
COINS = [1, 5, 10, 50, 100, 200, 500, 1000, 2500]
CACHE = {}
def change_number(money):
number = 0
for current in range(1, money + 1):
number = change_number_rec(current, 1)
return number
def change_number_rec(money, min_coin):
key = f"{money}-{min_coin}"
if key in CACHE:
return CACHE[key]
if money == 0:
return 1
result = sum(
change_number_rec(money - coin, coin)
for coin in itertools.dropwhile(lambda x: x < min_coin, COINS)
if money - coin >= 0
)
CACHE[key] = result
return result
def main(num):
print(change_number(int(num)))
if __name__ == "__main__":
main(sys.argv[1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment