Solution for Advent of Code 2015 - Day 24: It Hangs in the Balance

Link to the puzzle text

Part 1

In this puzzle we are asked to divide a list of numbers into 3 parts with equal sums. For all possible divisions, we are trying to find the one that a) has the fewest elements in the first group and b) the product of the first group is minimal.

This can again be solved by brute force. Since all parts have the same sum, it has to be the sum of the whole list divided by 3. We are iterating over all subsets of a fixed size and checking if it has the correct sum until there are subsets matching. For all matching subsets, we minimize the product and return it as the answer.

def minimize_subsets(goal):
    accepted_subsets = []
    for i in range(len(weights)):
        for subset in itertools.combinations(weights, i):
            if sum(subset) == goal:
                accepted_subsets.append(subset)
        if len(accepted_subsets) > 0:
            break
    
    min_qe = math.inf
    for subset in accepted_subsets:
        qe = functools.reduce(lambda x, y: x * y, subset, 1)
        min_qe = min(min_qe, qe)
    return min_qe

While we may have to check if the remaining parts can be divided into two equal sets, this worked out fine.

Part 2

For part 2, we are asked to divide into four equal parts, so we just change the goal for the function above and get the correct answer.

Link to my solutions