############################################################
# knapsack helper functions
############################################################


def group_item_info(names, values, weights):
    n = len(names)
    return [(names[i], values[i], weights[i]) for i in range(n)]


def item_names(items):
    return [item[0] for item in items]


def total_value(items):
    return sum([item[1] for item in items])


def total_weight(items):
    return sum([item[2] for item in items])


def test_knapsack(knapsack_func, make_problem):
    print("=" * 40)
    print(f"Test {knapsack_func.__name__}()")
    print("=" * 40)
    print()

    names, values, weights, capacity = make_problem()
    items = group_item_info(names, values, weights)
    print(knapsack_func(items, capacity))
    print()


############################################################
# solving the normal knapsack problem
############################################################


def make_hiking():
    names = ["water bottle", "sandwich", "camera", "jacket", "book"]
    weights = [3, 2, 5, 4, 3]
    values = [9, 7, 4, 6, 3]
    capacity = 10
    return names, values, weights, capacity


def knapsack(items, capacity):
    memo = {}
    return knapsack_helper(items, 0, capacity, memo)


def knapsack_helper(items, index, capacity, memo):
    # bypass if already in memo
    if (index, capacity) in memo:
        return memo[index, capacity]

    # base case: no more items, empty solution
    if index == len(items):
        return [], 0

    # recursion: decide whether to take first item, solve for remaining items
    name, value, weight = items[index]

    sol_without, val_without = knapsack_helper(items, index + 1, capacity, memo)

    if weight <= capacity:
        sol_with, val_with = knapsack_helper(items, index + 1, capacity - weight, memo)
        sol_with = sol_with + [name]  # need to make new list, due to memoization
        val_with += value
    else:
        sol_with = None
        val_with = 0

    # memoize answer before returning
    if val_with > val_without:
        answer = sol_with, val_with
    else:
        answer = sol_without, val_without
    memo[index, capacity] = answer
    return answer


# test_knapsack(knapsack, make_hiking)


############################################################
# complementary knapsack
# mirrors original knapsack solution
############################################################

# original problem statement:
# pick items to maximize value without exceeding a weight capacity

# complementary problem statement:
# pick items to minimize value without going under a weight threshold


def make_hiking_complementary():
    names = ["water bottle", "sandwich", "camera", "jacket", "book"]
    weights = [3, 2, 5, 4, 3]
    values = [9, 7, 4, 6, 3]
    threshold = 7
    return names, values, weights, threshold


def knapsack_complementary(items, threshold):
    memo = {}
    return knapsack_complementary_helper(items, 0, threshold, memo)


def knapsack_complementary_helper(items, index, threshold, memo):
    # check memo
    if (index, threshold) in memo:
        return memo[index, threshold]

    # base case
    if index == len(items):
        return [], 0

    # recursive case
    name, value, weight = items[index]

    if total_weight(items[index + 1:]) >= threshold:
        sol_without, val_without = knapsack_complementary_helper(items, index + 1, threshold, memo)
    else:
        sol_without = None
        val_without = float("inf")

    sol_with, val_with = knapsack_complementary_helper(items, index + 1, threshold - weight, memo)
    sol_with = sol_with + [name]
    val_with += value

    # memoize before returning
    if val_with < val_without:
        answer = sol_with, val_with
    else:
        answer = sol_without, val_without
    memo[index, threshold] = answer
    return answer


# test_knapsack(knapsack_complementary, make_hiking_complementary)


############################################################
# complementary knapsack
# uses original knapsack solution
############################################################


def knapsack_complementary(items, threshold):
    # map problem to a "normal" knapsack problem
    # threshold = total weight - capacity
    capacity = total_weight(items) - threshold

    # solve transformed problem
    answer, value = knapsack(items, capacity)

    # transform output back into the original complementary problem
    items_names = [name for name, _, _ in items]
    compl_answer = list(set(items_names) - set(answer))
    compl_value = total_value(items) - value
    return compl_answer, compl_value


# test_knapsack(knapsack_complementary, make_hiking_complementary)


# another example: given the following potential classes, which ones
# should we NOT put in our schedule given the credit limit?


def make_schedule_complementary():
    names = [
        "6.100",
        "6.100A",
        "7.012",
        "18.02",
        "9.00",
        "3.000",
        "24.900"
    ]
    units = [12, 6, 12, 12, 12, 3, 12]
    credit_limit = 54
    future_impact = [6, 9, 10, 10, 7, 3, 7]

    weights = ...  # TODO
    threshold = ...  # TODO
    values = ...  # TODO

    return names, values, weights, threshold


# test_knapsack(knapsack_complementary, make_schedule_complementary)