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`

:

- Calculate the set difference,
`s2`

, of`{1, 2, ..., 16}`

with`s1`

. - Check if the sums in
`S1`

and`s2`

were equal. - Return the answer
`(s1 s2)`

if so, - 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 ^{1}.

## Footnotes:

^{1} Of course, this is a bit silly since you have to write most of the code to discover the fact that finding the correct sum of cubes suffices but the point stands: a little experimentation can save a bunch of time.

If you were really clever you would have immediately written just the check for the cubes, since that would give you a smaller sample size for the other two checks.