#!/usr/bin/env python3
###########################
# 6.0002 Problem Set 1b: Space Change
# Name: <John-L-Jones-IV>
# Collaborators: tuthang102
# Time:
# Author: charz, cdenise

#================================
# Part B: Golden Eggs
#================================

# Problem 1
def dp_make_weight(egg_weights, target_weight, memo = {}):
    """
    Find number of eggs to bring back, using the smallest number of eggs. Assumes there is
    an infinite supply of eggs of each weight, and there is always a egg of value 1.
    
    Parameters:
    egg_weights - tuple of integers, available egg weights sorted from smallest to largest value (1 = d1 < d2 < ... < dk)
    target_weight - int, amount of weight we want to find eggs to fit
    memo - dictionary, OPTIONAL parameter for memoization (you may not need to use this parameter depending on your implementation)

    NOTE: memo will keep memory of how it was built the first time it was used. It is possible to use the wrong memo on the set of
    egg_weights. Or build a completly invalid memo when called again with a new set of egg_weights.
    
    Returns: int, smallest number of eggs needed to make target weight
    """
    if target_weight not in memo:
      if target_weight in egg_weights:
        memo[target_weight] = 1
      else:
        memo[target_weight] = min(
            1 + dp_make_weight(egg_weights, target_weight - egg_weight, memo)
            for egg_weight in egg_weights if target_weight > egg_weight
          )

    return memo.get(target_weight)

# EXAMPLE TESTING CODE, feel free to add more if you'd like
if __name__ == '__main__':
    egg_weights = (1, 5, 10, 25)
    n = 26
    print("Egg weights = (1, 5, 10, 25)")
    print("n = 26")
    print("Expected ouput: 2 (25 + 1 = 26)")
    print("Actual output:", dp_make_weight(egg_weights, n))
    print()

    n = 99
    print("Egg weights = (1, 5, 10, 25)")
    print("n = 99")
    print("Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
    print("Actual output:", dp_make_weight(egg_weights, n))
    print()

    n = 100
    print("Egg weights = (1, 5, 10, 25)")
    print("n = 100")
    print("Expected ouput: 4 (4 * 25 = 100)")
    print("Actual output:", dp_make_weight(egg_weights, n))
    print()

    n = 7
    print("Egg weights = (1, 5, 10, 25)")
    print("n = 7")
    print("Expected ouput: 3 (1 * 5 + 2 * 1 = 100)")
    print("Actual output:", dp_make_weight(egg_weights, n))
    print()

    n = 101
    print("Egg weights = (1, 5, 10, 25)")
    print("n = 101")
    print("Expected ouput: 5 (4 * 25 + 1 * 1 = 100)")
    print("Actual output:", dp_make_weight(egg_weights, n))
    print()

    egg_weights = (1, 5, 10, 20)
    n = 99
    print("Egg weights = ", egg_weights)
    print("n = ", n)
    print("Expected ouput: 10 (4 * 20 + 1 * 10 + 1 * 5 + 4 * 1 = 99)")
    print("Actual output:", dp_make_weight(egg_weights, n, {}))
    print()
    
    n = 100
    print("Egg weights = ", egg_weights)
    print("n = ", n)
    print("Expected ouput: 5 (5 * 20 = 100)")
    print("Actual output:", dp_make_weight(egg_weights, n, {}))
    print()
