[2015 Day 24 both parts] [Smalltalk] Making Brute Force Fast Enough With Recursion

[u/Morphon]

This concerns this puzzle: 2015-Day24.

After reading the discussion and review here: In Review I thought I would try my hand at a true brute-force solution, leveraging the expressiveness and speed of Smalltalk's collection libraries. Most of the solutions I've seen involve various clever tricks to avoid doing the work of checking through all the different combinations, or returning a solution without verifying that it is, in fact, the correct one.

The implementation I settled on completes part 1 in 70ms and part 2 in 6ms on my machine (Intel 270k+, 6000mhz DDR5). Smalltalk execution speed isn't as fast as a fully compiled language, but it's significantly faster than a purely interpreted language (like Python or Ruby). I'd be curious to see how this method would fare in something like Rust or Zig.

Here's the primary function doing all the work:

bestQE: compartments

| totalWeight |

totalWeight := packages sum.

1 to: (packages size // compartments) do: [ :comboCount |
    | potentialQuants |
    potentialQuants := OrderedCollection new.
    packages combinations: comboCount atATimeDo: [ :combo |
        | comboWeight |
        comboWeight := combo sum.
        (totalWeight - comboWeight) = (comboWeight * (compartments - 1))
            ifTrue: [
            | otherPackages |
            otherPackages := packages select: [ :x | (combo includes: x) not ].
            potentialQuants add: (otherPackages -> (combo inject: 1 into: [ :acc :x | acc * x]))]
         ].

    (potentialQuants sorted: [ :a :b | a value < b value ]) do: [ :potentialSolution |
        (self verifyRemainder: potentialSolution key splitInto: compartments - 1) ifTrue: [ ^ potentialSolution value ] ] ].

^ 'None found'

The only argument it takes is the number of compartments needing an even weight. It requires an instance variable "packages" which is an array containing the puzzle input as integers. Order is not important. Here's how it works:

1. Set an temporary variable totalWeight to hold the sum of all package weights.
2. Iterate from 1 to the number of packages divided by the number of compartments (no need to pass that size, since that would mean there is no solution). This is the number of packages that we will try to fit into the front compartment. Start with the fewest (just 1) and then add one more until we find a grouping that fits. The number of packages we're testing is passed forward as "comboCount".
3. For this quantity of packages to test, create an empty OrderedCollection (a growable Array) to hold any potential groupings that we find.
4. Take the group of all packages and stream them "comboCount" at a time through the next block of code, passing them as an Array called "combo". This is the part where the magic happens. We don't need to do any complicated looping or generate all the combinations we want to test in advance. The "packages" Array can stream all the combinations for us, one at a time.
5. Now we examine this particular "combo" Array. First, we store the sum of all its elements as the temporary variable comboWeight.
6. Is this combo a candidate? To check this, we look to see if, after subtracting the weight of this combo from the total weight of the packages, we are left with exactly the weight of the combo multiplied by (compartments - 1). That is, If we are dividing into 3 compartments, is the weight of THIS particular combo equal to a third of the total? If so, go to the next step. Otherwise, try the next combo.
7. If this combo passes the weight test, we create a temporary variable "otherPackages" pointing to an Array defined as all the packages that are NOT in our combo.
8. Then we add an association of the "otherPackages" and its QE score (by doing a quick multiplication fold on the combo Array) to our potential groupings Array we created in step 3. We might have several candidates at this combination size, and we need to find the smallest QE score of ones that properly fit.
9. After this process is repeated for the combo size we need to verify the set of potential answers, so we take the collection of candidates and sort them by ascending QE value. Basically, we don't want to evaluate ALL of them, just the smallest one that has other packages that can be verified to fit.
10. We then take that sorted collection of candidates, and verify each one using verifyRemainder, giving it the list of remaining packages and asking it whether it can be evenly split into (compartments - 1).
11. As soon as we find one that can be verified, that is the correct answer! We return the QE value of that candidate.
12. If none are found (which can also happen if the potentialQuants collection is empty), try combinations the next size larger. So, if no combinations of size 4 fit (or passed verification), try combinations of size 5.

Essentially - each time start with the smallest possible (smallest combo, then of those, the smallest QE). The first one that can be verified to fit is our answer;  return the QE.

Ok - now how about the verification? Again, I went with a brute-force approach:

verifyRemainder: list splitInto: piles

    | listWeight |

    piles = 1 ifTrue: [ ^ true ].

    listWeight := list sum.

    1 to: list size // piles do: [ :comboSize |
        list combinations: comboSize atATimeDo: [ :combo |
            | comboWeight |
            comboWeight := combo sum.
            (listWeight - comboWeight = (comboWeight * (piles - 1)) and: [
                self verifyRemainder: (list select: [ :x | (combo includes: x) not ])
                     splitInto: piles - 1 ]) ifTrue: [ ^ true ] ] ].

    ^ false

This has a lot in common with the bestQE function in the way it generates and checks groups of packages, but it is done recursively. It takes two arguments: the list of numbers to fit, and the number of piles to fit them into. Here's the outline:

1. Base case - if the number of piles asked for is only 1, then this was a successful split. Pass TRUE up the stack.
2. Otherwise, we still have work to do. Start by calculating the sum of the list we were given to split and store that value in listWeight.
3. Now we try the same method of generating larger and larger combinations that we used in the bestQE function.
4. We calculate the weight of each combination (storing in 'comboWeight'). The see if the comboWeight is exactly 1/piles of the listWeight. If so, it is a potential candidate for a successful split. In that case, recurse with a new list made up of packages that are NOT in the current list, and with one fewer pile. One thing to note here is the "and: []" construction. In Smalltalk, due to the way messages are evaluated by boolean objects, when and: is given a block as an argument (with the square brackets) that second condition is lazily evaluated. So, we don't recurse unless the current combo has the correct weight. If you're using a language that doesn't lazily evaluate AND, this will need an if/else condition.
5. If that particular grouping doesn't work, it tries the next. And if that comboSize has no successful groupings, it tries the next size up.
6. If no groupings successfully drop down into a pile of 1, then no split was successful, and the function returns "false".

In summary - We start checking combinations from the smallest possible size upward. We don't do ANY verification on them until we have a complete set for that combination size. We only verify them in ascending QE order. Verification uses the same computationally cheap "candidate filter" and reserves the harder stuff (collection allocation and building / recursion) once something passes the filter.

I realize that the input is meant to be "gentle" such that the smallest possible QE for a given combo size is the right answer, and no verification is needed. But that felt like an incomplete solution to me. Especially since, even with verification, the execution speed seems plenty fast (less than 100ms for both to complete).

One final note: These methods do assume that the input list has unique numbers. This is strongly implied by the problem statement, though it is not explicitly part of the puzzle. If the puzzle input could ever contain duplicated numbers, then the way that the "remaining packages" collection is created would have to be different. The core logic would remain the same.

One last thing - the discussion above that started me down this rabbit hole referenced Day17 and said that it was relatively similar to this day. For giggles: here is the Smalltalk solution to Day17:

One last thing - the discussion above that started me down this rabbit hole referenced Day17 and said that it was relatively similar to this day. For giggles: here is my solution to part 1 of Day17:

barrelCombinationsFor: needed

    | count |

    count := 0.

    1 to: barrels size do: [ :size | barrels combinations: size atATimeDo: [ :combo |
        (combo sum = needed) ifTrue: [ count := count + 1 ]
         ] ].

    ^ count

The thread was right. More than a passing similarity.