Advent of Code: Day 24

2015-12-24

Source

Part 1: Split a list of integers into three groups of equal sum. Find the grouping such that the smallest group has the least items, breaking ties by the smallest product for that group.

My initial solution to this was to solve the subset sum problem (or at least a slightly modified version thereof):

def subsets_summing_to(target, items, cache = {}):
    if target == 0:
        yield set()
    else:
        for i, item in enumerate(items):
            if item <= target:
                for recur in subsets_summing_to(target - item, items - {item}):
                    yield {item} | recur

It’s elegant code, and you can use that to generate the three groups fairly easily:

packages = {int(line.strip()) for line in sys.stdin}
weight_per_package = sum(packages) // 3

for group1 in subsets_summing_to(weight_per_package, package):
    for group2 in subsets_summing_to(weight_per_package, package - group1):
        group3 = packages - group1 - group2
        ...

And then while I let that run, I made a realization. If I generate the first group to be the smallest (by generating all groups of size 1, size 2, size 3, etc), then it doesn’t actually matter what the other groups are. Furthermore, if I structure my iteration carefully so that I always return the smallest items first, I will get a minimal product1. Combining these two jumps, I get:

def subset_sum_of_n(target, items, count):
    if target == 0 and count == 0:
        yield set()
    elif count == 0:
        return
    else:
        for i, item in enumerate(sorted(items)):
            if item <= target:
                for recur in subset_sum_of_n(target - item, items - {item}, count - 1):
                    yield {item} | recur

def calculate_quantum_entanglement(group):
    product = 1
    for item in group:
        product *= item
    return product

def split_into(packages, n_groups):
    weight_per_section = sum(packages) / int(sys.argv[1])

    for n in range(1, len(packages)):
        for group in subset_sum_of_n(weight_per_section, packages, n):
            return (len(group), calculate_quantum_entanglement(group), group)

if __name__ == '__main__':
    packages = {int(line.strip()) for line in sys.stdin}
    n_groups = int(sys.argv[1])

    print(split_into(packages, n_groups))

I’m greatly amused that it doesn’t matter at all what any of the other groups are.

Part 2: Split into four groups.

I already solved this with the n_groups parameter above.

Amusingly, because this solution (at least with my input) only has 4 items in the minimal group, it runs about 60 times faster than the first part. It still doesn’t matter at all what the other groups are.

  1. I’m not actually sure if this is correct, but it worked… ¯_(ツ)_/¯ ↩︎