Irreal

Back in April, Robert Smith of Symbo1ics Ideas wrote an excellent post on solving the m-of-n Boolean Circuit problem. The problem is nominally about building a boolean circuit having n inputs that returns TRUE if at least m of the inputs are TRUE. Most of us aren’t electrical engineers, of course, so Smith quickly recasts the problem as building a function that does the same thing.

That’s a pretty easy problem with some obvious solutions but Smith asks how we might go about finding an optimal solution. Optimal in the sense that each input is examined at most once and that a solution is returned as soon as the answer can be definitely determined. That leaves out solutions that just spin through the inputs counting those with a value of TRUE. Smith finds a general formula for the solution and uses that to write a function to make the check.

Then things get interesting. Next, instead of writing a function to make the check he writes a function to generate Lisp code to make the check. With just a little cleverness—you’ll think, “Oh, I would have thought of that”—he has the function generating optimal code. The next step is to take that code and turn it into a compiler macro. Now when the function is called to check if m of the n inputs are TRUE the function will generate direct code if it can and call the iterative function if it can’t.

This is the best description of compiler macros that I’ve come across. I was going to blog about them myself but I couldn’t do better without just copying his post so you should definitely go take a look if you’re a Lisper.

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