#!/usr/bin/env python
# coding: utf-8

# ## Problem statement
# 
# Q: Given pennies, nickels, dimes, and quarters, and a certain money value $v$, make the total value $v$ with the fewest total coins possible.
# 
# This is a famous introductory exercise.
# 
# The brute force solution is to iterate over every possible combination of coins whose total is smaller than the value $v$, appending coins of each type to the prior total and checking if the result is equal in value to $v$.

# ## Test suite

# In[6]:


import unittest

class TestCC(unittest.TestCase):
    """Example of how to use unittest in Jupyter."""
    
    def testZeroLength(self):
        self.assertEqual(cc(0, []), [])
        
    def testTrivial(self):
        self.assertEqual(cc(1, [1]), [1])

    def testDouble(self):
        self.assertEqual(cc(1, [1, 1]), [1])

    def testNonTrivial(self):
        self.assertEqual(sorted(cc(5, [1, 2, 3])), [2, 3])
        
    def testNonTrivialMore(self):
        self.assertEqual(sorted(cc(6, [1, 2, 3, 4])), [2, 4])
        
    def testImpossible(self):
        self.assertEqual(sorted(cc(1, [10])), [])
        

        
if __name__ == '__main__':
    unittest.main(argv=[''], exit=False)


# ## Brute force psuedocode implementation
# 
# ```
# function cc(v, coins):
#     known_solutions = []
#     rcc(known_solutions)
#     return argmin(known_solutions)
# 
# 
# function rcc(v, coins, known_solutions, prior_coins):
#     for coin in coins:
#         next_v = prior.value + coin.value
#         if next_v = v:
#             known_solutions.append(next_v)
#             break
#         else if next_v > v:
#             break
#         else:
#             new_prior = prior_coins.push(coin)
#             rcc(v, coins, known_solutions, new_prior)
# ```

# In[2]:


def cc(v, coins):
    known_solutions = []
    start_prior = {'value': 0, 'coins': []}
    rcc(v, coins, known_solutions, start_prior)
    
    if known_solutions == []:
        return []
    
    best_solution = known_solutions[0]
    for solution in known_solutions:
        if len(solution) < len(best_solution):
            best_solution = solution
    return best_solution

def rcc(v, coins, known_solutions, prior_coins):
    for coin in coins:
        next_v = prior_coins['value'] + coin
        if next_v == v:
            known_solutions.append(prior_coins['coins'] + [coin])
            break
        elif next_v > v:
            break
        else:
            new_prior = {'value': next_v, 'coins': prior_coins['coins'] + [coin]}
            rcc(v, coins, known_solutions, new_prior)


# ### Greedy solution psuedocode
# 
# It turns out that an optimal solution to the coin change problem is to just take as many of the largest donomination of coin as possible, and working up the list. There is a recursive proof you can do to show that this is true.

# ```
# function cc(v, coins):
#     sol = []
#     sol_tot = 0
#     for coin in coins:
#         while (sol_tot + coin <= v):
#             sol.append(coin)
#             sol_tot += coin
#         if sol_tot == v:
#             return sol_tot
#     return None
# ```

# ### Greedy solution implementation

# In[3]:


def cc(v, coins):
    sol = []
    sol_tot = 0
    for coin in coins:
        while (sol_tot + coin <= v):
            sol.append(coin)
            sol_tot += coin
        if sol_tot == v:
            return sol
    return None


# In[4]:


cc(5, [3, 2, 1])


# ### Dynamic analysis
# 
# The other solution is to recognize that the optimal solution for value $x$ is the best (smallest) solution amongst $x - 1$, $x - 5$, $x - 10$, and $x - 25$, plus one (the one additional coin required). In other words:
# 
# $$\text{cc}(x) = \min{\{\text{cc}(x-10), \text{cc}(x-5), \text{cc}(x-25), \text{cc}(x-1)\}} + 1$$
# 
# We can use this relation to forward solve the problem.

# ### Dynamic pseudocode

# ```
# function cc(v, coins):
#     memo = {coin: [coin] for coin in coins}
#     for n in range(2, v + 1):
#         priors = [n - coin for coin in coins if n - coin >= 1]
#         priors = [memo[prior] for prior in priors]
#         selected_prior_idx = argmin([prior for prior in priors])
#         selected_prior = priors[selected_prior_idx]
#         selected_prior_missing_coin = coins[selected_prior_idx]
#         memo[n] = selected_prior + [selected_prior_missing_coin]
#         
#     return memo[v]
# ```

# In[9]:


def cc(v, coins):
    if coins == [] or v < min(coins): return []
    
    coins = sorted(coins)
    memo = {coin: [coin] for coin in coins}
    for n in range(2, v + 1):
        # Skip keys already included. Missed this in the initial pseudocode!
        if n in memo.keys():
            continue
            
        priors = [n - coin for coin in coins if n - coin >= 1]
        priors = {prior: memo[prior] for prior in priors}
        
        def argmin(d):
            if len(d.keys()) == 0: return
            best, best_idx = d[list(d.keys())[0]], 0
            for (idx, d_k) in enumerate(d.keys()):
                if len(d[d_k]) < len(best):
                    best, best_idx = d[d_k], idx
            return best, best_idx
        
        selected_prior, selected_prior_idx = argmin(priors)
        
        print(n, priors, selected_prior)        
        
        selected_prior_missing_coin = coins[selected_prior_idx]
        memo[n] = selected_prior + [selected_prior_missing_coin]
    
    return memo[v]


# After a long derivation looking at the recursion tree, I think the brute-force solution is perhaps $O(n!v!)$, where $n$ is the number of different coins possible and $v$ is the the value we are looking for, but it's hard to be sure from a time-constrained look at the numbers.
# 
# The greedy solution is $O(n)$, where $n$ is the number of coins.
# 
# The dynamic solution is $O(v)$, where $v$ is the value.