Checking The Easy Cases First

Over the weekend, I was amusing myself with this problem from the always entertaining Programming Praxis. The problem is to partition the set {1, 2, ..., 16} into two equally sized subsets such that

• The sums of the integers in each subset are equal.
• The sums of the squares of the integers in each subset are equal.
• The sums of the cubes of the integers in each subset are equal.

That seems straight forward enough. My strategy was to generate combinations of the 16 integers 8 at a time and for each combination, s1:

1. Calculate the set difference, s2, of {1, 2, ..., 16} with s1.
2. Check if the sums in S1 and s2 were equal.
3. Return the answer (s1 s2) if so,
4. Get the next combination and return to step 1 if not.

That plan worked remarkably wells and gave me the answer in under .02 seconds.

Then I realized that the goal sums were known in advance. For example each sum of integers would have to be one-half the sum of 1 to 16 or 68. Using that fact meant that the number of summings was cut in half and there was no need to calculate a set difference until s1 had the correct sums. That cut the running time in about half. I felt pretty good about that but then I wondered how many correct sums for the integers, the squares, and the cubes there were.

So I adapted the code to count how many combinations summed to the correct amount for each type of sum. There were lots of integer combinations that were correct, just a few combinations of the squares, and exactly 1 of the cubes. Now the code is:

(dolist (c all-combinations)
  (if (= (reduce (lambda (x y) (+ x (* y y y))) c :initial-value 0) 9248)
      (return (list c
                    (set-difference '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
                                    c)))))

which produced the correct answer in .002 seconds. The point of this post is that it can pay to experiment a bit before you write a lot of code ¹.