Here is a script in Python that exhaustively calculates all values, then spits out the formulas for the 1900-2100 range: http://pastie.org/777044
The code is about 30 lines and runs in under seven seconds on my machine.
It works by splitting the list of numbers into all possible sets of two sublists, recursively calculating the possible values of expressions for each sublist, then merging the expression values together using each possible operator.
I think this approach runs faster than the Java/Lisp solutions because it can collapse equal-valued subtrees together, which helps particularly when you have a subtree that consists only of additions, multiplications, or divisions.
(Edit: It also caches the value set of each subtree, which probably helps even more.)
On further experimentation, the approach is maybe too aggressive in trading memory for speed... It runs out of memory on my 32-bit machine if you try to run it for the range 1-10 instead of 1-9.
Very non-descriptive title, though it results in a number fairly close to Pi. It's based on this:
The challenge: calculate all numbers between 1900 and 2100 with
exactly one operator between the sequential numbers 123456789
with as many brackets as desired.
There are links to two other methods of solving the problem, both of which are significantly more "intelligent" methods, but it's an interesting starting point for all three.
Compared to the Ruby one, of course. Semantic tree > string mangling.
I'm not a Java hater (I just think it's a horrible language to start in), but I'll make the counter-point that the Java approach is significantly larger and less readable than either of the others. There's likely a significantly simpler implementation somewhere deep in Java's frameworks, but ouch.
The code is about 30 lines and runs in under seven seconds on my machine.
It works by splitting the list of numbers into all possible sets of two sublists, recursively calculating the possible values of expressions for each sublist, then merging the expression values together using each possible operator.
I think this approach runs faster than the Java/Lisp solutions because it can collapse equal-valued subtrees together, which helps particularly when you have a subtree that consists only of additions, multiplications, or divisions.
(Edit: It also caches the value set of each subtree, which probably helps even more.)