Irreal

I’m just starting a Lisp project that, among other things, involves fiddling with dates. Working with dates isn’t particularly hard but it’s also not very rewarding. Oddly, Common Lisp doesn’t have any functions to format and manipulate dates. I certainly didn’t want to write a bunch of uninteresting code so I fired up Quicklisp to see what was available. Happily, I found the Simple-Date-Time library that did all the things I wanted it to.

The only problem was that there are a lot of functions but no documentation other than the doc strings in the functions. I thought about writing a quick script to extract them for use as documentation when I thought that this was surely something that someone else had already done. So I fired up Quicklisp again and found Edi Weitz’s DOCUMENTATION-TEMPLATE library. I had Quicklisp retrieve it for me, loaded it at the REPL, typed

(create-template 'simple-date-time :target #P"~/Desktop/dt.html")

and ended up with nicely formatted html documentation that I added to the documentation stack in my browser.

Sadly, it only works with LispWorks, SBCL, and AllegroCL but if you have one of those systems and need some documentation for a library, this is a quick and easy way to generate it. If you want to see what the finished product looks like, here is the documentation for DOCUMENTATION-TEMPLATE generated with DOCUMENTATION-TEMPLATE.

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