change.py

#!/usr/bin/env python3
'''
You have notes in 3 denominations: two, five and ten.
Write a function `change` which takes in one argument which is the money amount,
and return the combination of the 3 notes using minimum number of notes
that adds up to the given amount.
Return None if it is not able to add up to the amount.
Assume you have infinite supply of notes in all 3 denominations.
Examples:
1: the function should return None
2: the function should return {'two': 1, 'five': 0, 'ten': 0}
6: the function should return {'two': 3, 'five': 0, 'ten': 0}
10: the function should return {'two': 0, 'five': 0, 'ten': 1}, 
    instead of {'two': 5, 'five': 0, 'ten': 0}
20: the function should return {'two': 0, 'five': 0, 'ten': 2}, 
    instead of {'two': 4, 'five': 0, 'ten': 0} or {'two': 2, 'five': 0, 'ten': 1}
'''

from collections import Counter

def change(cash, memo=None):
  ## memoization
  if memo is None:
    memo = {}
  # first, base conditions
  if cash == 0:
    memo[cash] = []
    return []
  if cash <=1:
    memo[cash] = None
    return None

  # 2nd, logic here.
  # remember to return the same type/form/shape as base conditions
  best_way = None
  for m in 2, 5, 10:
    way = change(cash - m, memo)
    if way is not None:
      if best_way is None or len(way) < len(best_way):
        best_way = [m, *way]

  memo[cash] = best_way
  return best_way

def format_output(ar):
  '''
  `ar` is None or a array with possible values 2, 5, or 10.
  Returns None if `ar` is None,
  Returns a dictionary counting number of distinct values:
  For example, [10, 10] returns {'two': 0, 'five': 0, 'ten': 2} 
  '''
  if ar is None:
    return None
  counter = Counter(ar)
  
  m = {
    'two': 2,
    'five': 5,
    'ten': 10,
  }
  d = {
    'two': counter.get(m['two'], 0),
    'five': counter.get(m['five'], 0),
    'ten': counter.get(m['ten'], 0),
  }
  return d

print(format_output(change(1)))
print(format_output(change(2)))
print(format_output(change(3)))
print(format_output(change(6)))
print(format_output(change(10)))
print(format_output(change(20)))
print(format_output(change(29)))
print(format_output(change(51)))
# print(format_output(change(101))) # How to optimize this??? Memoization in place now does not work.

'''
None
{'two': 1, 'five': 0, 'ten': 0}
None
{'two': 3, 'five': 0, 'ten': 0}
{'two': 0, 'five': 0, 'ten': 1}
{'two': 0, 'five': 0, 'ten': 2}
{'two': 2, 'five': 1, 'ten': 2}
{'two': 3, 'five': 1, 'ten': 4}
'''