justin appears online

Some friends at work were discussing the problem of generating all of the numbers from 1900 through 2100 with the following constraints: each calculation must consist of the numbers 1 through 9 in order, combined using the binary arithmetic operators +, -, x, ÷, and arbitrary bracketing. for example,

((1 + ((2 + 3) + (((4 + (5 * 6)) * 7) * 8))) + 9) = 1919

Zach approached this by generating random expressions and evaluating them until he'd obtained the entire set. Ben made the observation that if obvious duplicates (i.e. expressions that are identical modulo bracketing) are removed there are not all that many solutions to check. In particular, the solution space is the set of all binary trees with all possible combinations of the aforementioned operators as nodes and the numbers 1 to 9 in order (depth first) as leaves. However, he wasn't generating all of these trees, only a random subset.

While this strategy often obtains the solution set, I thought a nicer approach would be to just build all of the possible tree shapes and then iterate through each using all of the possible operator combinations.

I think the solution is pleasantly simple. The code is about 30 lines (provided you aren't using gratuitous line breaks in an attempt to avoid the horizontal scrollbar on the embedded Gist) and reads rather like the description of my approach.

I don't (usually) enjoy optimizing code for speed and in this case I've deliberately avoided it. I'm sure there are a number of minor changes that could make this program much, much faster. However, I've instead tried to optimize for readability.

Having said that I'm quite pleased with how fast it *does* run. With CCL 1.4 on a 2.5GHz Core2Duo laptop in energy-saving mode this simple ~30 line program produces a correct answer in sixty seconds or so. Think about that for a moment--this performance is being acheived using generic dispatch and the full numeric tower everywhere.

notes:

• the results of pretty-print-tree are actually valid s-expressions that can be evaluated at a lisp prompt or via eval. out of curiosity I tried replacing evaluate with (eval (pretty-print-tree ...)) in the final block. eval is actually more than twice as slow as my unoptimized evaluate that's built on tree-reduce. keep this in mind the next time someone is whining about how one should never use eval
• running this program will produce four compiler warnings for unused lexical variables. I could have added a (declare (ignore variable)) to silence each of these but wanted to keep the code free of annotations
• there are many ways to generate all of the target numbers (317.29 solutions for each on average, min 4, max 6406). the ordering of the trees in the main loop isn't optimal, but I haven't thought of a simple way to reorder them that would work better. in the ordering produced by btrees-of-size, 340 out of 1430 possible trees need to be examined to generate all of the target numbers