# 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 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.

This entry was posted in Programming and tagged . Bookmark the permalink.

### One Response to Checking The Easy Cases First

1. Malgannis says:

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.