# File: coin_changing.py
# John Longley
# January 2021 (for IADS Q+A session)

# COIN CHANGING PROBLEMS.

import sys
sys.setrecursionlimit(10000)

# Some coin systems:

lecture_coins = [1,5,7]    

sterling_coins = [1,2,5,10,20,50,100,200]


# Problem (1): Minimum number of coins (as in Lecture 16).

# Plain recursive implementation.

c_list = lecture_coins  # global variable, can set as desired

# Version returning just smallest number of coins:

def fewest_coins(v):
    if v==0:
        return 0
    else:
        return 1 + min([fewest_coins(v-c) for c in c_list if c <= v])

# Version returning the actual list of coins:

def fewest_coins_list(v):
    if v==0:
        return []
    else:
        c_list1 = [c for c in c_list if c <= v]
        sub_sols = [fewest_coins_list(v-c) for c in c_list1]
        sub_sol_sizes = [len(s) for s in sub_sols]
        i = sub_sol_sizes.index(min(sub_sol_sizes))
        return sub_sols[i] + [c_list1[i]]

# Memoization operation, exactly as in lecture:

def memoize(f):
    memo = {}
    def check(v):
        if v not in memo:
            memo[v] = f(v)
        return memo[v]
    return check

# memoize : (int->int) -> (int->int)
# f : int->int,  check : int->int

# To get the optimization:

#   fewest_coins = memoize(fewest_coins)
#   fewest_coins_list = memoize(fewest_coins_list)

# NB. Mustn't change c_list after doing this!
# Should reload file to use with new c_list.


def fewest_coins_dp(v):
   k = len(c_list)
   C = [w for w in range(v+1)]
   if v > 0:
      C[1] = 1
      for w in range(2,v+1):
          for i in range(k):
              if (c_list[i] <= w) and (C[w-c_list[i]]+1 < C[w]):
                  C[w] = C[w-c_list[i]] +1
   return C[v]


def fewest_coins_list_dp(v):
   k = len(c_list)
   C = [w for w in range(v+1)]
   P = [0 for w in range(v+1)] 
   P[0] = None
   S = [0 for i in range(k)]
   coins=[]
   if v > 0:
      C[1] = 1
      for w in range(2,v+1):
          for i in range(k):
              if (c_list[i] <= w) and (C[w-c_list[i]]+1 < C[w]):
                  C[w] = C[w-c_list[i]] +1
                  P[w] = i
   while (v> 0):
      i = P[v]
      S[i]=S[i]+1
      v = v - c_list[i]
   while (k>0):
      while S[k-1]>0:
         coins.append(c_list[k-1])
         S[k-1] -= 1
      k -= 1
   return coins