"""
Created on June 10, 2020

@author: Hayk Stepanyan
"""


# ================================
# 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 memorization (you may not need to use this parameter depending on your implementation)
    
    Returns: int, smallest number of eggs needed to make target weight
    """

    if target_weight == 0:
        egg_count = 0
        for key in memo.keys():
            egg_count += memo[key]
        return egg_count
    for weight in reversed(egg_weights):
        if weight <= target_weight:
            target_weight -= weight
            if weight in memo.keys():
                memo[weight] += 1
            else:
                memo.update({weight: 1})
            return dp_make_weight(egg_weights, target_weight, memo)


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