#!/usr/bin/python

from itertools import combinations



def solve_partn(partn, masses):
    if partn == 1:
        num_groups = 3
    else: # partn == 2
        num_groups = 4

    m_total = sum(masses)
    m_group = int(m_total / num_groups)

    # At first, it seems the easiest way is to generate all possible
    # grouping of packages, and then just keep the ones that are valid,
    # and find the best among the remaining configurations. However,
    # the input file has 28 packages, so there are 3^28 = 23 trillion
    # possible groupings, which is obviously too much to brute-force.

    # Instead, we find the candidates for group 1: subsets of the packages
    # whose masses add up to `m_group', with the smallest number of items.

    # Step 1: Find all combinations of packages in a certain range
    k_min = int((m_group - 1) / max(masses)) + 1
    k_max = int(len(masses) / num_groups)
    combos = []
    for k in range(k_min, k_max + 1):
        combos += combinations(masses, k)
    # Step 2: Keep only combinations whose masses add up to `m_group'
    group1 = []
    for c in combos:
        if sum(c) == m_group:
            group1.append(c)
    # Step 3: Keep only candidates with the smallest package count
    min_len = min(map(len, group1))
    smallest = {}
    for g1 in group1:
        if len(g1) == min_len:
            smallest[g1] = []

    # Verify for each group 1 candidate that the remaining packages can be
    # divided into 2 more groups of mass `m_group'. This takes time and it
    # turns out that no candidates get rejected, hence it's commented out.
    #for i, g1 in enumerate(smallest):
    #    remaining = []
    #    for m in masses:
    #        if m not in g1:
    #            remaining.append(m)
    #    k_max = int(len(remaining) / (num_groups - 1))
    #    combos = []
    #    for k in range(k_min, k_max + 1):
    #        combos += combinations(remaining, k)
    #    for c in combos:
    #        if sum(c) == m_group:
    #            smallest[g1].append(c)
    #valid = {}
    #for g1 in smallest.keys():
    #    if len(smallest[g1]) > 0:
    #        valid[g1] = smallest[g1]

    # Calculate quantum entanglement of each group 1 candidate
    qentangs = []
    for g1 in smallest.keys():
        qe = 1
        for m in g1:
            qe *= m
        qentangs.append(qe)

    return min(qentangs)



def main():
    # Read package weights from input text file
    with open("input.txt", "r") as f:
        masses = list(map(int, f.read().splitlines()))

    print("Part 1 solution:", solve_partn(1, masses)) # 10439961859 for me
    print("Part 2 solution:", solve_partn(2, masses)) #    72050269 for me



if __name__ == "__main__":
    main()