24 Day 24

The puzzle. Our input is a list of weights of certain packages.

24.1 What’s the score of the optimal group of packages, when divided into three groups?

We need to arrange our packages into three groups of equal weight. There are multiple ways to do this, of course. According to the puzzle, the optimal arrangement is the one that results in a group with the fewest number of packages. If multiple arrangements yield an equally small group, then the winner is the one with the lowest “quantum entanglement” score, which is defined as the product of the weights.

This puzzle brings together elements we’ve seen before. Each group in a valid arrangement needs to have equal weight, which is the total weight divided by 3. Rather than immediately trying to find valid three-group arrangements, we can start with single groups of the right weight, sorted by our scoring criteria, and find the first one that’s part of a valid solution.

In principle, we could reuse the powerset function we made for Day 17 to generate all possible groups, and then filter for the groups that are the correct weight. But in truth, we got lucky on Day 17. There were only 20 elements, so our power set contained (expt 2 20) (about a million) options, which only takes a few seconds to search. This time, we have 28 elements, thus 256 times as many options, which would require 10–15 minutes of searching.

To be more efficient, we’ll use for*/first to alternate between generating lists of possible groups, and then testing them. We’ll sort these lists by “quantum entanglement” so we know we’re testing groups from best to worst (similar to what we did in Day 21 with equipment cost).

After that, we just need to write a function that will test whether a given group is part of a valid solution. The first group that has a solution is our winner. Our has-solution? function works by removing the test group from the set of all packages, and seeing if there is another group within that has the same weight. (We don’t have to check the third group — if the first two groups are the same weight, then the third one is too.)

24.2 What’s the optimal score when divided into four groups?

The loop is similar, but instead of using has-solution? (which in essence tests if there is a two-group solution), we ask if there is a three-group solution after our target group is removed. So we create a recursive relationship between the second question and the first.

24.3 Testing Day 24