Re: Make 100 by using + - x / and 1~9

Alfred Heiligenbrunner <xyz@xxxxxx> wrote:
On 2007-10-25 17:22:50 -0400, 131208@xxxxxxxxx said:

100 = 1 ( ) 2 ( ) 3 ( ) 4 ( ) 5 ( ) 6 ( ) 7 ( ) 8 ( ) 9
( ) can only be among +, - , *, /

Here a solution in Mathematica:

Select[Flatten[
Table[
Inner[StringJoin, {"1", "2", "3", "4", "5", "6", "7", "8"},
{"+", "-", "*", "/"}[[{i1, i2, i3, i4, i5, i6, i7, i8}]],
StringJoin]
<> "9",
{i1, 4}, {i2, 4}, {i3, 4}, {i4, 4}, {i5, 4}, {i6, 4}, {i7, 4},
{i8, 4}]],
(ToExpression[#] == 100) &]

time is rather short (6 seconds on a Pentium 4, 3 GHz, 1.5 GB RAM)
I wonder, if there is not a more efficient or more elegant code.

Brute-force string manipulation is neither efficient nor elegant.
Towards such, here is an elementary _recursive_ solution that is
1000 times faster. Below is a simple Common Lisp implementation
(it will also run under Emacs Lisp). It collects a sum (= list L)
of products P of consecutive integers (or inverses thereof).
It recurses, either multiplying the current product P by the
current integer J (and also by 1/J in the case J divides P);
or terminating the product P, with +/- sign, appending it to L,
and decrementing the target sum N appropriately (except suppress
initial negative products since no sign is allowed at the front).

(defun F (N J P L) ; N + sum L is invariant
(if (> J 10)
(if (= N 0) (print (cons '+ (reverse L))))
(progn
(if (< J 10)
(progn
(if (= 0 (mod P J))
(F N (+ J 1) (/ P J) L ))
(F N (+ J 1) (* P J) L )))
(F (- N P) (+ J 1) J (cons P L))
(if L
(F (+ N P) (+ J 1) J (cons (- P) L))))))

(F 100 2 1 ())

(+ 24 5 6 56 9)
(+ 24 5 6 -7 72)
(+ 6 -20 42 72)
(+ 6 4 5 6 7 72)
(+ 1 20 7 72)
(+ 1 6 20 -6 7 72)
(+ 1 -6 20 6 7 72)
(+ 1 -6 -4 30 7 72)
(+ 1 -6 -4 -5 42 72)
(+ 1 2 -12 30 7 72)
(+ 1 2 -12 -5 42 72)
(+ 1 2 3 -20 42 72)
(+ 1 2 3 4 5 6 7 72)
(+ 1 -2 60 42 8 -9)
(+ 1 -2 60 -6 56 -9)

Note: To keep the code simple for those who do not know Lisp,
I didn't preserve the product factors (they're easily inferred).
The code would be just as fast even if it preserved the factors.
Of course one could make further optimizations but it would be
overkill for such a small problem (e.g. one can easily mentally
eliminate almost all divisions, which e.g. require J|(J-1)! ).

--Bill Dubuque
.