From: Al Kworithm
Subject: Solving an arihmetic puzzle
Date: 
Message-ID: <f88a47fa.0205251158.22a32722@posting.google.com>
Hi,

I have a homework in LISP.

It states that a list of integers anda goal number is given,
we want to reach that goal number using the list members only once as
operands to 4 basic arithmetic operators, if a solution exists.

For example,
(solve '(1 1 1 3 50 100) 651))

should produce the output
1+1=2
2*3=6
6*100=600
600+60=650
650+1=651

What do you suggest for an approach?
I have been learning LISP very little and I can't figure out what to
do.

Thanks in advance for any kind of help.

From: Frank A. Adrian
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <PoZH8.344$wj4.255286@news.uswest.net>
Since Al Kworithm admits:

> I have been learning LISP very little and I can't figure out what to
> do.

... my first suggestion would be to learn Lisp a little more.

faa
From: Christopher Browne
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <acp69j$rk5qm$1@ID-125932.news.dfncis.de>
Oops! ·········@hotmail.com (Al Kworithm) was seen spray-painting on a wall:
> Hi,
>
> I have a homework in LISP.
>
> It states that a list of integers and a goal number is given,
> we want to reach that goal number using the list members only once as
> operands to 4 basic arithmetic operators, if a solution exists.
>
> For example,
> (solve '(1 1 1 3 50 100) 651))
>
> should produce the output
> 1+1=2
> 2*3=6
> 6*100=600
> 600+60=650
> 650+1=651
>
> What do you suggest for an approach?
> I have been learning LISP very little and I can't figure out what to
> do.

Basically, what you're going to be doing is to explore a search space
where you attach values to the following expression:

result = (op4 (op3 (op2 (op1 v1 v2) v3) v4) v5)

That is, you are applying functions op1 thru op4 to their respective
sets of arguments.

And basically what you'll be doing is to set up a whole bunch of
combinations where op1 thru op4 are chosen from (+ - / *), and (v1 v2
v3 v4 v5) represent some ordering of the set of input values.

So basically you need to go off and generate a set of loops sort of
like:

(loop with ops = '(+ - / *)
      and vals = '(1 1 1 3 50 100)
   for op1 in ops
   do 
   (loop for op2 in ops do
    (loop for op3 in ops do
     (loop for op4 in ops do
      (loop for op5 in ops do
       (loop for v1p from 0 to 5
             for v1 = (elt vals v1p)
             for REST = (take v1p out of vals)
           do (loop for v2p from 0 to 4
                 for v2 = (elt REST v2p)
                 for REST = (take v2p out of REST)
           do (loop for v3p from 0 to 3
                 for v3 = (elt REST v3p)
                 for REST = (take v3p out of REST)
           do (loop for v4p from 0 to 2
                 for v4 = (elt REST v4p)
                 for REST = (take v4p out of REST)
           do (loop for v5p from 0 to 1
                 for v5 = (elt REST v5p)
                 for v6 = (elt REST (- 1 v5p))
                 for val = (calculate value based on op1 thru op5, v1
                            thru v6)
                 when (= val 651)
                 do (save the set of values)))))))))))

This does a fairly ugly combinatorial explosion, so that it would be a
slick idea for some of the choices to actually be goal-oriented so
that they have some marginal "intelligence" to try to avoid obviously
stupid solutions.  Unfortunately, that may only be useful in the very
lowest level of the code (e.g. - when picking v5 and v6).

There are lots of obvious repeated patterns in the above code, which
suggests that maybe what you want to do is to use some more or less
recursive algorithms so that no recoding needs to be done if an extra
couple operators get thrown in, or if the length of the expression
changes.

It obviously doesn't do to have to rewrite the program if the list
gets one entry longer. :-(
-- 
(concatenate 'string "cbbrowne" ·@ntlug.org")
http://www.ntlug.org/~cbbrowne/rdbms.html
"The only completely consistent people are the dead."
-- Aldous Huxley
From: Harald Hanche-Olsen
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <pcog00fc47g.fsf@thoth.math.ntnu.no>
+ ·········@hotmail.com (Al Kworithm):

| I have a homework in LISP.

I am glad you say so from the start.

| It states that a list of integers anda goal number is given,
| we want to reach that goal number using the list members only once as
| operands to 4 basic arithmetic operators, if a solution exists.
| 
| For example,
| (solve '(1 1 1 3 50 100) 651))
| 
| should produce the output
| 1+1=2
| 2*3=6
| 6*100=600
| 600+50=650  [I fixed a type for you]
| 650+1=651
| 
| What do you suggest for an approach?

Not sure, but one approach that would occur to me is this:  Make a
list of all the results you can get in one step.  For example, since
1+1=2 one of the lists could be written

  (1 (2 (+ 1 1)) 3 50 100)

where the result 2 is stored together with an explanation of how it
arose.  Or maybe, for the sake of uniformity and less handling of
special cases, you should make that

  ((1) (2 (+ 1 1)) (3) (50) (100)).

Another would be

  ((1) (1) (1)  (150 (* 3 50)) (100)).

Keep on making new such lists until your target number appears or
you've run out of possibilities.  For efficiency, and to avoid a
combinatorial blowup, you should arrange to generate the next step
  
  ((1) (2 (+ 1 1)) (150 (* 3 50)) (100))

only once, though it can arise from either of the two previous lists.

All this is just off the top of my head, for a start on the problem.
This far, it really has very little to do with Lisp, and everything to
do with algorithms and data structures.  A canonical representation of
equivalent data, and perhaps the use of hash tables to avoid
duplication of work, may be useful hints.  Or maybe I am leading you
astray - but then, it's your homework, and you have to separate the
wheat from the chaff yourself.  Good luck.

-- 
* Harald Hanche-Olsen     <URL:http://www.math.ntnu.no/~hanche/>
- Yes it works in practice - but does it work in theory?
From: Christopher Browne
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <acp69m$rk5qm$5@ID-125932.news.dfncis.de>
The world rejoiced as Harald Hanche-Olsen <······@math.ntnu.no> wrote:
> + ·········@hotmail.com (Al Kworithm):
>
> | I have a homework in LISP.
>
> I am glad you say so from the start.
>
> | It states that a list of integers anda goal number is given,
> | we want to reach that goal number using the list members only once as
> | operands to 4 basic arithmetic operators, if a solution exists.
> | 
> | For example,
> | (solve '(1 1 1 3 50 100) 651))
> | 
> | should produce the output
> | 1+1=2
> | 2*3=6
> | 6*100=600
> | 600+50=650  [I fixed a type for you]
> | 650+1=651
> | 
> | What do you suggest for an approach?
>
> Not sure, but one approach that would occur to me is this:  Make a
> list of all the results you can get in one step.  For example, since
> 1+1=2 one of the lists could be written
>
>   (1 (2 (+ 1 1)) 3 50 100)
>
> where the result 2 is stored together with an explanation of how it
> arose.  Or maybe, for the sake of uniformity and less handling of
> special cases, you should make that
>
>   ((1) (2 (+ 1 1)) (3) (50) (100)).
>
> Another would be
>
>   ((1) (1) (1)  (150 (* 3 50)) (100)).
>
> Keep on making new such lists until your target number appears or
> you've run out of possibilities.  

The problematic issue will be of how to generate those lists.

> For efficiency, and to avoid a combinatorial blowup, you should
> arrange to generate the next step
>   
>   ((1) (2 (+ 1 1)) (150 (* 3 50)) (100))
>
> only once, though it can arise from either of the two previous lists.

That's a thought; it _is_ relevant to the example given, but might not
be, in general.

I'm not sure that there's necessarily going to be any massive "win" in
trying to optimize for this.  It would surely improve performance; no
disagreement there.  But I'd suggest Michael Jackson's "Principles of
Optimization", where:

  Principle #1:  Don't do it.
  Principle #2 (For Experts):  Don't do it _yet_.

It doesn't make sense to clutter the code with optimizations for that
sort of thing when there's not working code yet.  I'd suggest getting
it working, and _then_ think about optimizing it.  To put things in
the other order risks the problem not getting solved.
  
> All this is just off the top of my head, for a start on the problem.
> This far, it really has very little to do with Lisp, and everything to
> do with algorithms and data structures.  A canonical representation of
> equivalent data, and perhaps the use of hash tables to avoid
> duplication of work, may be useful hints.  Or maybe I am leading you
> astray - but then, it's your homework, and you have to separate the
> wheat from the chaff yourself.  Good luck.

Having a canonical representation is certainly critical.

Hash tables would be useful for a "faster version," _maybe_.  Lists
and maybe vectors should suffice for the initial version.
-- 
(concatenate 'string "aa454" ·@freenet.carleton.ca")
http://www.cbbrowne.com/info/x.html
FLORIDA: Where your vote counts and counts and counts.
From: John Paul Wallington
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <87adqnvkkg.fsf@bundalo.shootybangbang.com>
·········@hotmail.com (Al Kworithm) wrote:

> I have a homework in LISP.
> 
> It states that a list of integers anda goal number is given,
> we want to reach that goal number using the list members only once as
> operands to 4 basic arithmetic operators, if a solution exists.

In the UK there is a television show called "Countdown" with a numbers
game where the contestants are given six numbers and must solve the
same problem.

-- 
John Paul Wallington
From: Marc Spitzer
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <slrnaf0jhl.1f4u.marc@oscar.eng.cv.net>
In article <····························@posting.google.com>, Al Kworithm wrote:
> Hi,
> 
> I have a homework in LISP.
> 
> It states that a list of integers anda goal number is given,
> we want to reach that goal number using the list members only once as
> operands to 4 basic arithmetic operators, if a solution exists.
> 
> For example,
> (solve '(1 1 1 3 50 100) 651))
> 
> should produce the output
> 1+1=2
> 2*3=6
> 6*100=600
> 600+60=650
> 650+1=651
> 
> What do you suggest for an approach?
> I have been learning LISP very little and I can't figure out what to
> do.
> 
> Thanks in advance for any kind of help.

one way to do it is a depth first tree traversal program.  you walk a
tree by building sub expressions and when you run out of numbers you
evaluate the resulting expression to get a number and compare it to
your target.  If the numbers are the same then return the expression
otherwise return nil.  The nice part is that it does not use too much
space, you only have 1 path through the tree in memory.  another nice
thing is the basic implementation is straight forward.  And you have
the option of returning all correct answers if you want.  you would
need to build something that does this:
(+ 1 1)
(* (+ 1 1) 3)
(* (* (+ 1 1) 3) 100 )
(+ (* (* (+ 1 1) 3) 100 ) 50)
(+ (+ (* (* (+ 1 1) 3) 100 ) 50) 1)

then you eval it and see if it matches.  

One thing to watch for is that / and - are order sensative so you want
to do both (- a b) and (- b a) 

Good luck 

marc
From: Al Kworithm
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <f88a47fa.0205260505.36258f2c@posting.google.com>
····@oscar.eng.cv.net (Marc Spitzer) wrote in message news:<····················@oscar.eng.cv.net>...
> In article <····························@posting.google.com>, Al Kworithm wrote:

thanks for all repliers.

I admit that this is an algorithm and data structure stuff rather than LISP.


thanks once again.
From: Herb Martin
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <f3BJ8.629$X53.281818304@newssvr11.news.prodigy.com>
This puzzle got under my skin and worried me
until I found a solution....unfortunately it is an
ugly, brute force method that takes a LONG time
to run, e.g., on the offered example:

     (solve '(1 1 1 3 50 100) 651)

My naive method:
    Find all the permutations of the list
    Combine with all the four operators in each
        position
    Eval againt the Goal (651) -- (using ignore-errors)
        to catch any problems of divide by zero)
    Push successful trials onto the result list.

With the example this request:
    4 operators ^ 5th (pairs) * 6! permutations of the list
or  1024 * 720 = 737280

It is really worse than this, since each of these trials
requires (n - 1) operator-operand elements on the list:

    5 * 737280 = 3686400  (3 1/2 million)

It works but it sure ain't purdy.

Herb Martin
Try ADDS for great Weather too:
http://adds.aviationweather.noaa.gov/projects/adds

"Al Kworithm" <·········@hotmail.com> wrote in message
·································@posting.google.com...
> ····@oscar.eng.cv.net (Marc Spitzer) wrote in message
news:<····················@oscar.eng.cv.net>...
> > In article <····························@posting.google.com>, Al
Kworithm wrote:
>
> thanks for all repliers.
>
> I admit that this is an algorithm and data structure stuff rather than
LISP.
>
>
> thanks once again.
>
From: Joe Marshall
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <A7BJ8.3294$fT5.1160360@typhoon.ne.ipsvc.net>
You might be able to prune the search space, after all
you aren't going to get anywhere near the answer of 651
by using only subtraction.

"Herb Martin" <·····@LearnQuick.Com> wrote in message
····························@newssvr11.news.prodigy.com...
> This puzzle got under my skin and worried me
> until I found a solution....unfortunately it is an
> ugly, brute force method that takes a LONG time
> to run, e.g., on the offered example:
>
>      (solve '(1 1 1 3 50 100) 651)
>
> My naive method:
>     Find all the permutations of the list
>     Combine with all the four operators in each
>         position
>     Eval againt the Goal (651) -- (using ignore-errors)
>         to catch any problems of divide by zero)
>     Push successful trials onto the result list.
>
> With the example this request:
>     4 operators ^ 5th (pairs) * 6! permutations of the list
> or  1024 * 720 = 737280
>
> It is really worse than this, since each of these trials
> requires (n - 1) operator-operand elements on the list:
>
>     5 * 737280 = 3686400  (3 1/2 million)
>
> It works but it sure ain't purdy.
>
> Herb Martin
> Try ADDS for great Weather too:
> http://adds.aviationweather.noaa.gov/projects/adds
>
> "Al Kworithm" <·········@hotmail.com> wrote in message
> ·································@posting.google.com...
> > ····@oscar.eng.cv.net (Marc Spitzer) wrote in message
> news:<····················@oscar.eng.cv.net>...
> > > In article <····························@posting.google.com>, Al
> Kworithm wrote:
> >
> > thanks for all repliers.
> >
> > I admit that this is an algorithm and data structure stuff rather than
> LISP.
> >
> >
> > thanks once again.
> >
>
>
From: Herb Martin
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <TPBJ8.637$At4.287469718@newssvr11.news.prodigy.com>
True, but you might use ALL but one subtraction,
to get it -- or another problem might have a component
which is greater than 651.

I couldn't for the life of me think of a way, that was
truly general, to solve this.

Herb Martin
Try ADDS for great Weather too:
http://adds.aviationweather.noaa.gov/projects/adds

"Joe Marshall" <·············@attbi.com> wrote in message
···························@typhoon.ne.ipsvc.net...
> You might be able to prune the search space, after all
> you aren't going to get anywhere near the answer of 651
> by using only subtraction.
>
> "Herb Martin" <·····@LearnQuick.Com> wrote in message
> ····························@newssvr11.news.prodigy.com...
> > This puzzle got under my skin and worried me
> > until I found a solution....unfortunately it is an
> > ugly, brute force method that takes a LONG time
> > to run, e.g., on the offered example:
> >
> >      (solve '(1 1 1 3 50 100) 651)
> >
> > My naive method:
> >     Find all the permutations of the list
> >     Combine with all the four operators in each
> >         position
> >     Eval againt the Goal (651) -- (using ignore-errors)
> >         to catch any problems of divide by zero)
> >     Push successful trials onto the result list.
> >
> > With the example this request:
> >     4 operators ^ 5th (pairs) * 6! permutations of the list
> > or  1024 * 720 = 737280
> >
> > It is really worse than this, since each of these trials
> > requires (n - 1) operator-operand elements on the list:
> >
> >     5 * 737280 = 3686400  (3 1/2 million)
> >
> > It works but it sure ain't purdy.
> >
> > Herb Martin
> > Try ADDS for great Weather too:
> > http://adds.aviationweather.noaa.gov/projects/adds
> >
> > "Al Kworithm" <·········@hotmail.com> wrote in message
> > ·································@posting.google.com...
> > > ····@oscar.eng.cv.net (Marc Spitzer) wrote in message
> > news:<····················@oscar.eng.cv.net>...
> > > > In article <····························@posting.google.com>, Al
> > Kworithm wrote:
> > >
> > > thanks for all repliers.
> > >
> > > I admit that this is an algorithm and data structure stuff rather than
> > LISP.
> > >
> > >
> > > thanks once again.
> > >
> >
> >
>
>
From: Christopher Browne
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <ad707d$v3cle$1@ID-125932.news.dfncis.de>
Centuries ago, Nostradamus foresaw when "Herb Martin" <·····@LearnQuick.Com> would write:
> True, but you might use ALL but one subtraction,
> to get it -- or another problem might have a component
> which is greater than 651.
>
> I couldn't for the life of me think of a way, that was
> truly general, to solve this.

Dynamic programming (ala Richard Bellman) would try to cut down on the
size of the state space by using metrics to indicate how each choice
brings you "closer" to the desired solution.

If you've got a good such metric, you can rule out really bad
proposals early on.  Unfortunately, it's not evident that the problem
admits this possibility.  If there are three 1's, that somewhat limits
the choices, but you're still free to stick operators whereever you
like.  

The only point at which you can be _sure_ that you can treat the
remaining state space analytically is when all that's left is to
decide the last operator.
-- 
(reverse (concatenate 'string ·············@" "sirhc"))
http://www.ntlug.org/~cbbrowne/linuxdistributions.html
"You'll be  rid of most of us  when BSD-detox or GNU  comes out, which
should happen in the next few months (yeah, right)." -- Richard Tobin,
1992. [BSD did follow within a year]
From: Herb Martin
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <lCDJ8.669$yh.302746832@newssvr11.news.prodigy.com>
> The only point at which you can be _sure_ that you can treat the
> remaining state space analytically is when all that's left is to
> decide the last operator.
> --

And that of course is pretty much the most worthless
point.

This would require eval'ing to figure out which operators
cannot help; which means really that we only cut the
total down by 1/2 in exchange for twice as many evals.

I don't see it unless you have some ACTUAL algorythm.

My solution is worthless for any more arguments (probably);
but it works (marginally) for the 6 operator list.

For anything less than 6 operators the answers are fairly
quickly achieved.

We could also quit if we find ONE answer, but that doesn't
address the issues of "no answer" or "the answer is at the
end of the search."


--
Herb Martin
Try ADDS for great Weather too:
http://adds.aviationweather.noaa.gov/projects/adds

"Christopher Browne" <········@acm.org> wrote in message
···················@ID-125932.news.dfncis.de...
> Centuries ago, Nostradamus foresaw when "Herb Martin"
<·····@LearnQuick.Com> would write:
> > True, but you might use ALL but one subtraction,
> > to get it -- or another problem might have a component
> > which is greater than 651.
> >
> > I couldn't for the life of me think of a way, that was
> > truly general, to solve this.
>
> Dynamic programming (ala Richard Bellman) would try to cut down on the
> size of the state space by using metrics to indicate how each choice
> brings you "closer" to the desired solution.
>
> If you've got a good such metric, you can rule out really bad
> proposals early on.  Unfortunately, it's not evident that the problem
> admits this possibility.  If there are three 1's, that somewhat limits
> the choices, but you're still free to stick operators whereever you
> like.
>
> The only point at which you can be _sure_ that you can treat the
> remaining state space analytically is when all that's left is to
> decide the last operator.
> --
> (reverse (concatenate 'string ·············@" "sirhc"))
> http://www.ntlug.org/~cbbrowne/linuxdistributions.html
> "You'll be  rid of most of us  when BSD-detox or GNU  comes out, which
> should happen in the next few months (yeah, right)." -- Richard Tobin,
> 1992. [BSD did follow within a year]
From: Jacek Generowicz
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <tyf6614u3bz.fsf@pcitapi22.cern.ch>
"Herb Martin" <·····@LearnQuick.Com> writes:

> This puzzle got under my skin and worried me

Yes, I found it kinda irresistible too.

> until I found a solution....unfortunately it is an
> ugly, brute force method that takes a LONG time
> to run, e.g., on the offered example:
> 
>      (solve '(1 1 1 3 50 100) 651)
> 
> My naive method:
>     Find all the permutations of the list
>     Combine with all the four operators in each
>         position
>     Eval againt the Goal (651) -- (using ignore-errors)
>         to catch any problems of divide by zero)
>     Push successful trials onto the result list.

I took pairs of numbers and combined them with operators, and fed the
result to a higher level (ie, a recursive approach).

This allows (at least) two methods of reducing the search space:

1) Observe that multiplication and addition are commutative, thereby
   reducing the number of (op num1 num2) combinations from 8 to
   6.

2) At each level remove any duplicates from the results. For example
   (* 1 1) and (/ 1 1) both give a 1, so there is no point in keeping
   both in the tree. I also removed any zeros; these can only lead to
   the same number as the other operand[*], another zero, or a divison
   by zero.

Of course, if there is a requirement that all numbers be used up in
the process, then you shouldn't prune zeros.

Some rough experimenting suggests that no. 2 gives me the following
worst case savings:

  number of operands    solution set reduced by factor of
         3                    2.5
         4                    5
         5                   10
         6                   20 

So the saving factor seems to double . . .


I really must discipline myself not to analyze this any further :-)



[*] or its additive inverse! I think I missed that in my version. This
could be fixed by introducing a unary minus once the first zero has
been produced. However, I don't want to get distracted by this again,
so I'll let it pass :-)
From: Gareth McCaughan
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <slrnafimnh.veg.Gareth.McCaughan@g.local>
Herb Martin wrote:
> This puzzle got under my skin and worried me
> until I found a solution....unfortunately it is an
> ugly, brute force method that takes a LONG time
> to run, e.g., on the offered example:
> 
>      (solve '(1 1 1 3 50 100) 651)
> 
> My naive method:
>     Find all the permutations of the list
>     Combine with all the four operators in each
>         position
>     Eval againt the Goal (651) -- (using ignore-errors)
>         to catch any problems of divide by zero)
>     Push successful trials onto the result list.

Ways to make it go faster:

1. Pick some heuristic measuring "distance to solution"
   and do something like A* search. Finding decent heuristics
   seems likely to be hard.

2. Trade space for time. You're looking for a path of length N
   from one place to another; instead, enumerate the paths of
   length N/2 from each end, and look for common endpoints.

Things that will make less difference but might still be worth
doing:

3. Eliminate duplicate solutions as you go. (You get a bunch
   of duplicates trivially from having, e.g., three 1s; and
   others, e.g., because 2+2 = 2*2.)

4. Use commutativity and such stuff. This is just a way
   of eliminating duplicates "in advance".

-- 
Gareth McCaughan  ················@pobox.com
.sig under construc
From: Seo Sanghyeon
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <45e6545c.0205310140.6b866f2@posting.google.com>
·········@hotmail.com (Al Kworithm) wrote:

> A list of integers and a goal number is given,
> we want to reach that goal number using the list members only once as
> operands to 4 basic arithmetic operators, if a solution exists.
> 
> For example,
> (solve '(1 1 1 3 50 100) 651))
> 
> should produce the output
> 1+1=2
> 2*3=6
> 6*100=600
> 600+50=650
> 650+1=651
> 
> What do you suggest for an approach?

Hello! I am new to this group. I learned some Scheme myself, and I
found
this problem interesting. So I tried it as an exercise. (Disclaimer: I
am
from Korea. If my English is not so good, forgive me)

All codes below are written in Scheme.

----

First, I assumed that we use integers from given list in order.
So in your example, (solve '(1 1 3 100 50 1) 651) gives '(+ * * + +),
but
(solve '(1 1 1 3 50 100) 651) evaluates to #f. (There is no way to
obtain
goal if one must use numbers in order)

It is possible to get permutation of list, right? So if we can solve
simplified problem, we can solve original one, too.

And given this, if only two integers are given, everything is simple:

(define (solve-2 lst ans)
  (cond
   ((= (+ (car lst) (cadr lst)) ans) '+)
   ((= (- (car lst) (cadr lst)) ans) '-)
   ((= (* (car lst) (cadr lst)) ans) '*)
   ((= (/ (car lst) (cadr lst)) ans) '/)))

(solve-2 '(1 2) 3) ==> '+

It works.

-- (car lst) gives the first element of the list,
-- (cadr lst) gives the second element of the list.

If more than two integers are given, we can use recursion, as usual.
For that, let's modify solve-2 a little:

(define (solve-2 lst ans)
  (cond
   ((= (+ (car lst) (cadr lst)) ans) (list '+))
   ((= (- (car lst) (cadr lst)) ans) (list '-))
   ((= (* (car lst) (cadr lst)) ans) (list '*))
   ((= (/ (car lst) (cadr lst)) ans) (list '/))
   (else #f)))

(solve-2 '(1 2) 3) ==> '(+)
(solve-2 '(1 2) 4) ==> #f

Now solve-2 returns list. And if it fails, returns #f.

Now, if more than two integers are given, we try +, -, *, / to first
two
elements, and cons it with rest of the list, and then call solve
recursively.
If it suceeds, cons +, -, *, / to the result. If it fails, try
another.

Let's translate it into Scheme:

1. try op to first two elements: (+ (car lst) (cadr lst))
2. cons it with the rest of the list: (cons (+ (car lst) (cadr lst))
(cddr lst))
3. recursion: (solve ... ans)
4. if succeed: (if (solve ... ans) ...
-- if suceed, (solve ... ans) is not #f, therefore true.
4-1. cons op to the result: (cons '+ (solve ... ans))
4-2. if failed, try another.
4-3. if all failed, returns #f.

Since there are 4 operators, we better use cond. Following is what I
wrote:

(define (solve lst ans)
  (if (= (length lst) 2)
      (cond
       ((= (+ (car lst) (cadr lst)) ans) (list '+))
       ((= (- (car lst) (cadr lst)) ans) (list '-))
       ((= (* (car lst) (cadr lst)) ans) (list '*))
       ((= (/ (car lst) (cadr lst)) ans) (list '/))
       (else #f))
      (cond
       ((solve (cons (+ (car lst) (cadr lst)) (cddr lst)) ans)
        (cons '+ (solve (cons (+ (car lst) (cadr lst)) (cddr lst))
ans)))
       ((solve (cons (- (car lst) (cadr lst)) (cddr lst)) ans)
        (cons '- (solve (cons (- (car lst) (cadr lst)) (cddr lst))
ans)))
       ((solve (cons (* (car lst) (cadr lst)) (cddr lst)) ans)
        (cons '* (solve (cons (* (car lst) (cadr lst)) (cddr lst))
ans)))
       ((solve (cons (/ (car lst) (cadr lst)) (cddr lst)) ans)
        (cons '/ (solve (cons (/ (car lst) (cadr lst)) (cddr lst))
ans)))
       (else #f))))

(solve '(3 4 5) 17) ==> '(* +)

Look horrible and lengthy. But code are generated by copy-and-paste.
There is nothing difficult in the code.

And it works.

Let's try the original example:

(solve '(1 1 3 100 50 1) 651) ==> '(+ * * + +)

Wow! I made it! (^^ Happy ^^)

I modifed my first version with named let.

----

(define (solve lst ans)
  (if (= (length lst) 2)
      (let loop ((op (list + - * /)) (opq '(+ - * /)))
        (if (null? op) #f
            (if (= ((car op) (car lst) (cadr lst)) ans)
                (list (car opq))
                (loop (cdr op) (cdr opq)))))
      (let loop ((op (list + - * /)) (opq '(+ - * /)))
        (if (null? op) #f
            (let ((rst (solve (cons ((car op) (car lst) (cadr lst))
(cddr lst)) ans)))
              (if rst
                  (cons (car opq) rst)
                  (loop (cdr op) (cdr opq))))))))

(solve '(1 2 3 4 5 6 7 8 9) 100) ==> '(+ + + + * - + +)

I have a question. Should I use op and opq as above? There must be a
better
way to do that, but I am a Scheme newbie.
From: Joe Marshall
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <qwJJ8.3585$fT5.1327540@typhoon.ne.ipsvc.net>
"Seo Sanghyeon" <··········@hanmail.net> wrote in message
································@posting.google.com...
>
> Hello! I am new to this group. I learned some Scheme myself, and I
> found
> this problem interesting. So I tried it as an exercise. (Disclaimer: I
> am
> from Korea. If my English is not so good, forgive me)
>
> All codes below are written in Scheme.

You might be interested in reading comp.lang.scheme
While the topic of scheme does arise here, the focus of this
group is on Common Lisp.

Alternatively, you might want to try solving the same
problem in Common Lisp.
From: Kenny Tilton
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <3CF8206C.A1E8B3FC@nyc.rr.com>
I guess this means I can't post my Logo solution. :(

You might be interested in starting comp.lang.lisp.moderated. While
c.l.l. posters frequently try to tell others what and what not to post,
this group is not restricted to discussions of CL by any charter.

:)


-- 

 kenny tilton
 clinisys, inc
 ---------------------------------------------------------------
"Harvey has overcome not only time and space but any objections."
                                                        Elwood P. Dowd
From: Herb Martin
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <wELJ8.21714$d36.3645341812@newssvr30.news.prodigy.com>
[BTW, you scheme approach is MORE INTERESTING
than the message taking up space, which suggests you
might better read another newsgroup -- if he really cared
about newsgroup bandwidth, he would have sent you
private email.]

In any case (back to the problem), when I ran the large
recursive version, my CLisp would pause every 4100 or
so outer lists (even if I filtered these to exclude those
that don't work) so it appears that the 'sublists' were
causing the problem.

I am assuming that this is some kind of garbage
collections pause, but it takes LONGER than the
previous calculation phase and re-occurs each 4100
or so.

Does anyone know a quick way to determine if this
is the GC.

Herb Martin
Try ADDS for great Weather too:
http://adds.aviationweather.noaa.gov/projects/adds

"Seo Sanghyeon" <··········@hanmail.net> wrote in message
································@posting.google.com...
> ·········@hotmail.com (Al Kworithm) wrote:
>
> > A list of integers and a goal number is given,
> > we want to reach that goal number using the list members only once as
> > operands to 4 basic arithmetic operators, if a solution exists.
> >
> > For example,
> > (solve '(1 1 1 3 50 100) 651))
> >
> > should produce the output
> > 1+1=2
> > 2*3=6
> > 6*100=600
> > 600+50=650
> > 650+1=651
> >
> > What do you suggest for an approach?
>
> Hello! I am new to this group. I learned some Scheme myself, and I
> found
> this problem interesting. So I tried it as an exercise. (Disclaimer: I
> am
> from Korea. If my English is not so good, forgive me)
>
> All codes below are written in Scheme.
>
> ----
>
> First, I assumed that we use integers from given list in order.
> So in your example, (solve '(1 1 3 100 50 1) 651) gives '(+ * * + +),
> but
> (solve '(1 1 1 3 50 100) 651) evaluates to #f. (There is no way to
> obtain
> goal if one must use numbers in order)
>
> It is possible to get permutation of list, right? So if we can solve
> simplified problem, we can solve original one, too.
>
> And given this, if only two integers are given, everything is simple:
>
> (define (solve-2 lst ans)
>   (cond
>    ((= (+ (car lst) (cadr lst)) ans) '+)
>    ((= (- (car lst) (cadr lst)) ans) '-)
>    ((= (* (car lst) (cadr lst)) ans) '*)
>    ((= (/ (car lst) (cadr lst)) ans) '/)))
>
> (solve-2 '(1 2) 3) ==> '+
>
> It works.
>
> -- (car lst) gives the first element of the list,
> -- (cadr lst) gives the second element of the list.
>
> If more than two integers are given, we can use recursion, as usual.
> For that, let's modify solve-2 a little:
>
> (define (solve-2 lst ans)
>   (cond
>    ((= (+ (car lst) (cadr lst)) ans) (list '+))
>    ((= (- (car lst) (cadr lst)) ans) (list '-))
>    ((= (* (car lst) (cadr lst)) ans) (list '*))
>    ((= (/ (car lst) (cadr lst)) ans) (list '/))
>    (else #f)))
>
> (solve-2 '(1 2) 3) ==> '(+)
> (solve-2 '(1 2) 4) ==> #f
>
> Now solve-2 returns list. And if it fails, returns #f.
>
> Now, if more than two integers are given, we try +, -, *, / to first
> two
> elements, and cons it with rest of the list, and then call solve
> recursively.
> If it suceeds, cons +, -, *, / to the result. If it fails, try
> another.
>
> Let's translate it into Scheme:
>
> 1. try op to first two elements: (+ (car lst) (cadr lst))
> 2. cons it with the rest of the list: (cons (+ (car lst) (cadr lst))
> (cddr lst))
> 3. recursion: (solve ... ans)
> 4. if succeed: (if (solve ... ans) ...
> -- if suceed, (solve ... ans) is not #f, therefore true.
> 4-1. cons op to the result: (cons '+ (solve ... ans))
> 4-2. if failed, try another.
> 4-3. if all failed, returns #f.
>
> Since there are 4 operators, we better use cond. Following is what I
> wrote:
>
> (define (solve lst ans)
>   (if (= (length lst) 2)
>       (cond
>        ((= (+ (car lst) (cadr lst)) ans) (list '+))
>        ((= (- (car lst) (cadr lst)) ans) (list '-))
>        ((= (* (car lst) (cadr lst)) ans) (list '*))
>        ((= (/ (car lst) (cadr lst)) ans) (list '/))
>        (else #f))
>       (cond
>        ((solve (cons (+ (car lst) (cadr lst)) (cddr lst)) ans)
>         (cons '+ (solve (cons (+ (car lst) (cadr lst)) (cddr lst))
> ans)))
>        ((solve (cons (- (car lst) (cadr lst)) (cddr lst)) ans)
>         (cons '- (solve (cons (- (car lst) (cadr lst)) (cddr lst))
> ans)))
>        ((solve (cons (* (car lst) (cadr lst)) (cddr lst)) ans)
>         (cons '* (solve (cons (* (car lst) (cadr lst)) (cddr lst))
> ans)))
>        ((solve (cons (/ (car lst) (cadr lst)) (cddr lst)) ans)
>         (cons '/ (solve (cons (/ (car lst) (cadr lst)) (cddr lst))
> ans)))
>        (else #f))))
>
> (solve '(3 4 5) 17) ==> '(* +)
>
> Look horrible and lengthy. But code are generated by copy-and-paste.
> There is nothing difficult in the code.
>
> And it works.
>
> Let's try the original example:
>
> (solve '(1 1 3 100 50 1) 651) ==> '(+ * * + +)
>
> Wow! I made it! (^^ Happy ^^)
>
> I modifed my first version with named let.
>
> ----
>
> (define (solve lst ans)
>   (if (= (length lst) 2)
>       (let loop ((op (list + - * /)) (opq '(+ - * /)))
>         (if (null? op) #f
>             (if (= ((car op) (car lst) (cadr lst)) ans)
>                 (list (car opq))
>                 (loop (cdr op) (cdr opq)))))
>       (let loop ((op (list + - * /)) (opq '(+ - * /)))
>         (if (null? op) #f
>             (let ((rst (solve (cons ((car op) (car lst) (cadr lst))
> (cddr lst)) ans)))
>               (if rst
>                   (cons (car opq) rst)
>                   (loop (cdr op) (cdr opq))))))))
>
> (solve '(1 2 3 4 5 6 7 8 9) 100) ==> '(+ + + + * - + +)
>
> I have a question. Should I use op and opq as above? There must be a
> better
> way to do that, but I am a Scheme newbie.
From: Christopher Browne
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <X0OJ8.10330$eJ5.1308897@news20.bellglobal.com>
Oops! "Herb Martin" <·····@LearnQuick.Com> was seen spray-painting on a wall:
> [BTW, you scheme approach is MORE INTERESTING
> than the message taking up space, which suggests you
> might better read another newsgroup -- if he really cared
> about newsgroup bandwidth, he would have sent you
> private email.]
>
> In any case (back to the problem), when I ran the large
> recursive version, my CLisp would pause every 4100 or
> so outer lists (even if I filtered these to exclude those
> that don't work) so it appears that the 'sublists' were
> causing the problem.
>
> I am assuming that this is some kind of garbage
> collections pause, but it takes LONGER than the
> previous calculation phase and re-occurs each 4100
> or so.
>
> Does anyone know a quick way to determine if this
> is the GC.

I'm quite sure that is the cause; it seems unlikely that there would
be any other reason for the slowdown.
-- 
(reverse (concatenate 'string ·············@" "enworbbc"))
http://www3.sympatico.ca/cbbrowne/sap.html
"We are all somehow dreadfully cracked about the head, and sadly need
mending." --/Moby-Dick/, Ch 17 
From: Herb Martin
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <nIrK8.143364$9F5.8118830@typhoon.austin.rr.com>
Ok, I think I have this out of my system now --
but don't necessarily bet on it.

This was one of those cases where optimization
was the only practical procedure -- unless you just
wanted to wait for it to finish.

I stuck with my original algorithm -- in principle --
brute force.

    Find all the permutations of the list
    Combine with all the four operators in each
        position
    Eval againt the Goal (651) -- (using ignore-errors)
        to catch any problems of divide by zero)
    Push successful trials onto the result list.

Originally this took a LONG time to run for the six
elements in the proferred example.  After cleaning
up some just plain BAD coding, I got it down to a
something like an hour.

My permute was fast, so I decided to use pushnew
and avoid duplicates and I moved the final result
collection with the EVAL to my routine that inserted
the operators.  At this point, I also started compiling
the processor bound portions.  After this round I was
at about 60 seconds

The eval was still in there and 25% of my time at this
point was garbage collection.

So, I made my own eval (tuned for the problem) and
even with a (small amount) of instrumenting code the
result was 3 seconds.  (Dumping that extra code gets
me to about 2.7 seconds.)

Real time: 3.004 sec.
Run time: 3.00432 sec.
Space: 11121304 Bytes
GC: 17, GC time: 0.300432 sec.
(((+ 1 (+ 50 (* 100 (* 3 (+ 1 1))))) = 651)
 ((+ 1 (+ 50 (* 3 (* 100 (+ 1 1))))) = 651)
 ((+ 50 (+ 1 (* 3 (* 100 (+ 1 1))))) = 651)
 ((+ 50 (+ 1 (* 100 (* 3 (+ 1 1))))) = 651))

BTW, if anyone should care in any way, I have been
a professional programmer, but not now, and Lisp has
always been an on-again/off-again hobby for me.

I do have quite a bit of experience with optimizing
production code however.

So from about 60 minutes (I don't want to admit how
long some versions took) to 3 seconds is about a
1200 to 1 improvement, mostly by just cleaning up
the code, and replacing slow functions with faster ones,
i.e., the algorithm stayed pretty much the same.

BTW:  For 7 elements it took right at 100 seconds:

(time (findit '(1 1 1 3 20 50 100) 671))
Real time: 99.423 sec.
Run time: 99.05243 sec.
Space: 360938424 Bytes
GC: 551, GC time: 11.045883 sec.
(((+ 1 (+ 50 (+ 20 (* 3 (* 100 (+ 1 1)))))) = 671)
 ((+ 1 (+ 50 (+ 20 (* 100 (* 3 (+ 1 1)))))) = 671)
 ((+ 1 (+ 20 (+ 50 (* 3 (* 100 (+ 1 1)))))) = 671)
 ((+ 1 (+ 20 (+ 50 (* 100 (* 3 (+ 1 1)))))) = 671)
 ((+ 20 (+ 1 (+ 50 (* 3 (* 100 (+ 1 1)))))) = 671)
 ((+ 20 (+ 1 (+ 50 (* 100 (* 3 (+ 1 1)))))) = 671)
 ((+ 20 (+ 50 (+ 1 (* 100 (* 3 (+ 1 1)))))) = 671)
 ((+ 20 (+ 50 (+ 1 (* 3 (* 100 (+ 1 1)))))) = 671)
 ((+ 50 (+ 20 (+ 1 (* 100 (* 3 (+ 1 1)))))) = 671)
 ((+ 50 (+ 20 (+ 1 (* 3 (* 100 (+ 1 1)))))) = 671)
 ((+ 50 (+ 1 (+ 20 (* 3 (* 100 (+ 1 1)))))) = 671)
 ((+ 50 (+ 1 (+ 20 (* 100 (* 3 (+ 1 1)))))) = 671))

Herb Martin
Try ADDS for great Weather too:
http://adds.aviationweather.noaa.gov/projects/adds

"Christopher Browne" <········@acm.org> wrote in message
····························@news20.bellglobal.com...
> Oops! "Herb Martin" <·····@LearnQuick.Com> was seen spray-painting on a
wall:
> > [BTW, you scheme approach is MORE INTERESTING
> > than the message taking up space, which suggests you
> > might better read another newsgroup -- if he really cared
> > about newsgroup bandwidth, he would have sent you
> > private email.]
> >
> > In any case (back to the problem), when I ran the large
> > recursive version, my CLisp would pause every 4100 or
> > so outer lists (even if I filtered these to exclude those
> > that don't work) so it appears that the 'sublists' were
> > causing the problem.
> >
> > I am assuming that this is some kind of garbage
> > collections pause, but it takes LONGER than the
> > previous calculation phase and re-occurs each 4100
> > or so.
> >
> > Does anyone know a quick way to determine if this
> > is the GC.
>
> I'm quite sure that is the cause; it seems unlikely that there would
> be any other reason for the slowdown.
> --
> (reverse (concatenate 'string ·············@" "enworbbc"))
> http://www3.sympatico.ca/cbbrowne/sap.html
> "We are all somehow dreadfully cracked about the head, and sadly need
> mending." --/Moby-Dick/, Ch 17
From: Kenny Tilton
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <3CFAB56C.92071E7E@nyc.rr.com>
Herb Martin wrote:
> 
> Ok, I think I have this out of my system now --
> but don't necessarily bet on it.

See if you can match these numbers:

((1 50 3 100 1 1) (+ + * * +)) 
((1 50 100 3 1 1) (+ + * * +)) 
((50 1 3 100 1 1) (+ + * * +)) 
((50 1 100 3 1 1) (+ + * * +)) 
; cpu time (non-gc) 471 msec user, 0 msec system
; cpu time (gc)     120 msec user, 0 msec system
; cpu time (total)  591 msec user, 0 msec system
; real time  591 msec
; space allocation:
;  241 cons cells, 0 symbols, 5,239,936 other bytes, 144 static bytes
> 
((1 20 50 3 100 1 1) (+ + + * * +)) 
((1 20 50 100 3 1 1) (+ + + * * +)) 
((1 50 20 3 100 1 1) (+ + + * * +)) 
((1 50 20 100 3 1 1) (+ + + * * +)) 
((20 1 50 3 100 1 1) (+ + + * * +)) 
((20 1 50 100 3 1 1) (+ + + * * +)) 
((20 50 1 3 100 1 1) (+ + + * * +)) 
((20 50 1 100 3 1 1) (+ + + * * +)) 
((50 1 20 3 100 1 1) (+ + + * * +)) 
((50 1 20 100 3 1 1) (+ + + * * +)) 
((50 20 1 3 100 1 1) (+ + + * * +)) 
((50 20 1 100 3 1 1) (+ + + * * +)) 
; cpu time (non-gc) 16,244 msec user, 0 msec system
; cpu time (gc)     2,423 msec user, 0 msec system
; cpu time (total)  18,667 msec user, 0 msec system
; real time  18,667 msec
; space allocation:
;  821 cons cells, 0 symbols, 208,904,248 other bytes, 492 static bytes

:)

-- 

 kenny tilton
 clinisys, inc
 ---------------------------------------------------------------
""Well, I've wrestled with reality for thirty-five years, Doctor, 
  and I'm happy to state I finally won out over it.""
                                                  Elwood P. Dowd
From: Herb Martin
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <sHAK8.145573$9F5.8204134@typhoon.austin.rr.com>
I doubt that I can match you fellow.

I was just cleaning up (my mess) before I saw
your note and was down to under 2 seconds, but
with this strategy I doubt there is much more I can
do.

Result scales too; I am about 4 times slower than
you on the 7 place puzzle also.

What is your algorithm?

Herb Martin, PP-SEL
(...and aerobatic student)
Try ADDS for great Weather too:
http://adds.aviationweather.noaa.gov/projects/adds

"Kenny Tilton" <·······@nyc.rr.com> wrote in message
······················@nyc.rr.com...
>
>
> Herb Martin wrote:
> >
> > Ok, I think I have this out of my system now --
> > but don't necessarily bet on it.
>
> See if you can match these numbers:
>
> ((1 50 3 100 1 1) (+ + * * +))
> ((1 50 100 3 1 1) (+ + * * +))
> ((50 1 3 100 1 1) (+ + * * +))
> ((50 1 100 3 1 1) (+ + * * +))
> ; cpu time (non-gc) 471 msec user, 0 msec system
> ; cpu time (gc)     120 msec user, 0 msec system
> ; cpu time (total)  591 msec user, 0 msec system
> ; real time  591 msec
> ; space allocation:
> ;  241 cons cells, 0 symbols, 5,239,936 other bytes, 144 static bytes
> >
> ((1 20 50 3 100 1 1) (+ + + * * +))
> ((1 20 50 100 3 1 1) (+ + + * * +))
> ((1 50 20 3 100 1 1) (+ + + * * +))
> ((1 50 20 100 3 1 1) (+ + + * * +))
> ((20 1 50 3 100 1 1) (+ + + * * +))
> ((20 1 50 100 3 1 1) (+ + + * * +))
> ((20 50 1 3 100 1 1) (+ + + * * +))
> ((20 50 1 100 3 1 1) (+ + + * * +))
> ((50 1 20 3 100 1 1) (+ + + * * +))
> ((50 1 20 100 3 1 1) (+ + + * * +))
> ((50 20 1 3 100 1 1) (+ + + * * +))
> ((50 20 1 100 3 1 1) (+ + + * * +))
> ; cpu time (non-gc) 16,244 msec user, 0 msec system
> ; cpu time (gc)     2,423 msec user, 0 msec system
> ; cpu time (total)  18,667 msec user, 0 msec system
> ; real time  18,667 msec
> ; space allocation:
> ;  821 cons cells, 0 symbols, 208,904,248 other bytes, 492 static bytes
>
> :)
>
> --
>
>  kenny tilton
>  clinisys, inc
>  ---------------------------------------------------------------
> ""Well, I've wrestled with reality for thirty-five years, Doctor,
>   and I'm happy to state I finally won out over it.""
>                                                   Elwood P. Dowd
From: Kenny Tilton
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <3CFAE65B.7E3D6793@nyc.rr.com>
Herb Martin wrote:
> 
> I doubt that I can match you fellow.
> 
> I was just cleaning up (my mess) before I saw
> your note and was down to under 2 seconds, but
> with this strategy I doubt there is much more I can
> do.
> 
> Result scales too; I am about 4 times slower than
> you on the 7 place puzzle also.
> 
> What is your algorithm?

heh-heh... I was going to ask you what is your clock speed and compiler,
we're pretty close.

I'm running at 1.4ghz on NT4 and compiling with ACL5. No declarations.

Your timer shows diff stats, but it looks like you are consing, I tried
hard to elim any of that. AH, here it is:

> My permute was fast, so I decided to use pushnew
> and avoid duplicates and I moved the final result
> collection with the EVAL to my routine that inserted
> the operators. 

I avoided consing by iteratively and recursively modifying a single
argument permutation list and single "formula" list, then evaluated by
applying the formula to the permutation (no eval of a constructed form). 

ie, I do not make a collection of permutations, rather as I generate
each one (avoiding dups by simply checking if I have already used the
same value at the same position) I go ahead and try all possible
formulas if you will (without actually inserting anything anywhere).
Roughly:

for each permutation (de-duped without consing)
   for each formula
       calculate and test against target result

FWIW, here is one permutation and formula being evaluated (via
(calculate 0 0)):

(defun calculate (perm-x formula-x)
  (let ((arg1 (svref *perm* perm-x))
        (arg2 (if (> (- *arg-ct* perm-x) 2)
                   (calculate (1+ perm-x) (1+ formula-x))
                 (svref *perm* (1+ perm-x)))))
    (ecase (svref *formula* formula-x)
      (/ (if (zerop arg2)
             (throw :nope nil)
           (/ arg1 arg2)))
      (* (* arg1 arg2))
      (+ (+ arg1 arg2))
      (- (- arg1 arg2)))))

I just now changed the lists to vectors in search of better performance,
slowed things down 20%. :( I thought svref on a vector would be faster
than elt on a list. Go figure. Maybe declarations are needed?

I keep thinking about using the commutative property to optimize, but it
always seems the cost of detecting such things would exceed the cost of
the redundant effort, arithmetic being so fast. Pretty sure I am missing
something here, tho.

-- 

 kenny tilton
 clinisys, inc
 ---------------------------------------------------------------
"Well, I've wrestled with reality for thirty-five years, Doctor, 
  and I'm happy to state I finally won out over it."
                                                  Elwood P. Dowd
From: Herb Martin
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <6kDK8.146077$9F5.8234284@typhoon.austin.rr.com>
I am using Gnu CLisp 2.26 (2001-05-23)

Running on a laptop at 1Ghz with Win2000
server and a bunch of stuff (but I am not taking
refuge in the stuff that's running.)

You get a little advantage from the 1.4 processor;
maybe a little or not, from the lisp itself.

I didn't do commutation because I actually think the
spirit of the puzzle is to find all solutions, including
those that use a different order.  Ok, (* x y) is probably
the same as (* y x).  But (* x (* y z)) is different than
(* y (* x z)), I think.

Mine is prettier than yours because it prints it out as
it would eval <grin>

BTW, does yours work on ((1 1) 2)  ?

(I had a bug and had to fix that trivial case.)

I thought vectors would be faster too, but I am
an OLD (yet amateur) list program and know lists
better.

Herb Martin, PP-SEL
(...and aerobatic student)
Try ADDS for great Weather too:
http://adds.aviationweather.noaa.gov/projects/adds

"Kenny Tilton" <·······@nyc.rr.com> wrote in message
······················@nyc.rr.com...
> Herb Martin wrote:
> >
> > I doubt that I can match you fellow.
> >
> > I was just cleaning up (my mess) before I saw
> > your note and was down to under 2 seconds, but
> > with this strategy I doubt there is much more I can
> > do.
> >
> > Result scales too; I am about 4 times slower than
> > you on the 7 place puzzle also.
> >
> > What is your algorithm?
>
> heh-heh... I was going to ask you what is your clock speed and compiler,
> we're pretty close.
>
> I'm running at 1.4ghz on NT4 and compiling with ACL5. No declarations.
>
> Your timer shows diff stats, but it looks like you are consing, I tried
> hard to elim any of that. AH, here it is:
>
> > My permute was fast, so I decided to use pushnew
> > and avoid duplicates and I moved the final result
> > collection with the EVAL to my routine that inserted
> > the operators.
>
> I avoided consing by iteratively and recursively modifying a single
> argument permutation list and single "formula" list, then evaluated by
> applying the formula to the permutation (no eval of a constructed form).
>
> ie, I do not make a collection of permutations, rather as I generate
> each one (avoiding dups by simply checking if I have already used the
> same value at the same position) I go ahead and try all possible
> formulas if you will (without actually inserting anything anywhere).
> Roughly:
>
> for each permutation (de-duped without consing)
>    for each formula
>        calculate and test against target result
>
> FWIW, here is one permutation and formula being evaluated (via
> (calculate 0 0)):
>
> (defun calculate (perm-x formula-x)
>   (let ((arg1 (svref *perm* perm-x))
>         (arg2 (if (> (- *arg-ct* perm-x) 2)
>                    (calculate (1+ perm-x) (1+ formula-x))
>                  (svref *perm* (1+ perm-x)))))
>     (ecase (svref *formula* formula-x)
>       (/ (if (zerop arg2)
>              (throw :nope nil)
>            (/ arg1 arg2)))
>       (* (* arg1 arg2))
>       (+ (+ arg1 arg2))
>       (- (- arg1 arg2)))))
>
> I just now changed the lists to vectors in search of better performance,
> slowed things down 20%. :( I thought svref on a vector would be faster
> than elt on a list. Go figure. Maybe declarations are needed?
>
> I keep thinking about using the commutative property to optimize, but it
> always seems the cost of detecting such things would exceed the cost of
> the redundant effort, arithmetic being so fast. Pretty sure I am missing
> something here, tho.
>
> --
>
>  kenny tilton
>  clinisys, inc
>  ---------------------------------------------------------------
> "Well, I've wrestled with reality for thirty-five years, Doctor,
>   and I'm happy to state I finally won out over it."
>                                                   Elwood P. Dowd
From: Gabe Garza
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <ofesil7g.fsf@anubis.kynopolis.org.kynopolis.org>
"Herb Martin" <·····@LearnQuick.Com> writes:

> I am using Gnu CLisp 2.26 (2001-05-23)
>
> You get a little advantage from the 1.4 processor;
> maybe a little or not, from the lisp itself.

You'll probably find that the difference between compiled code running
under Allegro is (generally--not always) going to be a great deal
faster then a byte-compiled implementation like CLisp.

> I didn't do commutation because I actually think the
> spirit of the puzzle is to find all solutions, including
> those that use a different order.  Ok, (* x y) is probably
> the same as (* y x).  But (* x (* y z)) is different than
> (* y (* x z)), I think.

It seems like they're two very different puzzles then.  Exploiting
commutativity seems like it could be a big win (I haven't tried this
yet)--consider something like:

(+ ( .. a big narly tree .. ) ( .. another narly tree .. ))

You're going to save a lot of work by knowing you don't have to 
check all the permutations of:

(+ ( .. another narly tree .. ) ( .. a big narly tree .. ))

This seems like a case where memoization (maybe augmented with
knowledge of permutation--for example, after permuting a tree whose
root node is a "+" operation, memoize it *and* it's mirror image by
reversing the left and right subtrees and memoizing that too) could be
something to try.

Just some suggestions that may (or may not) work.  Let me know if you
try them--I'm kind of curious now. :)

Gabe Garza
From: Herb Martin
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <ztKK8.147855$9F5.8265031@typhoon.austin.rr.com>
I think the tree will always be like this:

(Op Operand (Op2 Operand) etc)

(+ 3 (* 2 (/ 1 (+ 50 (+ 100)))))

--
Herb Martin, PP-SEL
(...and aerobatic student)
Try ADDS for great Weather too:
http://adds.aviationweather.noaa.gov/projects/adds

"Gabe Garza" <·······@ix.netcom.com> wrote in message
·················@anubis.kynopolis.org.kynopolis.org...
> "Herb Martin" <·····@LearnQuick.Com> writes:
>
> > I am using Gnu CLisp 2.26 (2001-05-23)
> >
> > You get a little advantage from the 1.4 processor;
> > maybe a little or not, from the lisp itself.
>
> You'll probably find that the difference between compiled code running
> under Allegro is (generally--not always) going to be a great deal
> faster then a byte-compiled implementation like CLisp.
>
> > I didn't do commutation because I actually think the
> > spirit of the puzzle is to find all solutions, including
> > those that use a different order.  Ok, (* x y) is probably
> > the same as (* y x).  But (* x (* y z)) is different than
> > (* y (* x z)), I think.
>
> It seems like they're two very different puzzles then.  Exploiting
> commutativity seems like it could be a big win (I haven't tried this
> yet)--consider something like:
>
> (+ ( .. a big narly tree .. ) ( .. another narly tree .. ))
>
> You're going to save a lot of work by knowing you don't have to
> check all the permutations of:
>
> (+ ( .. another narly tree .. ) ( .. a big narly tree .. ))
>
> This seems like a case where memoization (maybe augmented with
> knowledge of permutation--for example, after permuting a tree whose
> root node is a "+" operation, memoize it *and* it's mirror image by
> reversing the left and right subtrees and memoizing that too) could be
> something to try.
>
> Just some suggestions that may (or may not) work.  Let me know if you
> try them--I'm kind of curious now. :)
>
> Gabe Garza
From: Joe Marshall
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <QdLK8.10566$fT5.2614258@typhoon.ne.ipsvc.net>
"Herb Martin" <·····@LearnQuick.Com> wrote in message ·····························@typhoon.austin.rr.com...
> I think the tree will always be like this:
>
> (Op Operand (Op2 Operand) etc)
>
> (+ 3 (* 2 (/ 1 (+ 50 (+ 100)))))
>

You can always find a form like the above that is *equivalent*,
but I don't think you can use the same numbers.

How would you represent (/ (+ 7 4) (- 5 2))
for example?
From: John Atwood
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <adgfps$lb4$1@news.orst.edu>
This paper might be of interest:

 http://www.cs.nott.ac.uk/~gmh/bib.html#countdown
 The countdown problem
 Graham Hutton.  To appear in the Journal of Functional Programming, 
 Cambridge University Press, 2002.

 We systematically develop a functional program that solves the
 countdown problem, a numbers game in which the
 aim is to construct arithmetic expressions satisfying
 certain constraints.  Starting from a formal
 specification of the problem, we present a simple but inefficient program
 that solves the problem, and prove that this program is correct.  We then
 use program fusion to calculate an equivalent but more efficient program,
 which is then further improved by exploiting arithmetic properties.


John Atwood
From: Dennis Marti
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <dennis_marti-0641C7.01512903062002@virt-reader.news.rcn.net>
In article <························@typhoon.austin.rr.com>,
 "Herb Martin" <·····@LearnQuick.Com> wrote:

> Ok, I think I have this out of my system now --

And then they drag you back in...

> (time (findit '(1 1 1 3 20 50 100) 671))
> Real time: 99.423 sec.
> Run time: 99.05243 sec.
> Space: 360938424 Bytes
> GC: 551, GC time: 11.045883 sec.
> (((+ 1 (+ 50 (+ 20 (* 3 (* 100 (+ 1 1)))))) = 671)
>  ((+ 1 (+ 50 (+ 20 (* 100 (* 3 (+ 1 1)))))) = 671)
>  ((+ 1 (+ 20 (+ 50 (* 3 (* 100 (+ 1 1)))))) = 671)
>  ((+ 1 (+ 20 (+ 50 (* 100 (* 3 (+ 1 1)))))) = 671)
>  ((+ 20 (+ 1 (+ 50 (* 3 (* 100 (+ 1 1)))))) = 671)
>  ((+ 20 (+ 1 (+ 50 (* 100 (* 3 (+ 1 1)))))) = 671)
>  ((+ 20 (+ 50 (+ 1 (* 100 (* 3 (+ 1 1)))))) = 671)
>  ((+ 20 (+ 50 (+ 1 (* 3 (* 100 (+ 1 1)))))) = 671)
>  ((+ 50 (+ 20 (+ 1 (* 100 (* 3 (+ 1 1)))))) = 671)
>  ((+ 50 (+ 20 (+ 1 (* 3 (* 100 (+ 1 1)))))) = 671)
>  ((+ 50 (+ 1 (+ 20 (* 3 (* 100 (+ 1 1)))))) = 671)
>  ((+ 50 (+ 1 (+ 20 (* 100 (* 3 (+ 1 1)))))) = 671))

I think you missed one.

? (time (solve2 '(1 1 1 3 20 50 100) 671))

(+ (+ (+ (* (* (+ 1 1) 100) 3) 20) 1) 50) 
(+ (+ (+ (* (* (+ 1 1) 3) 100) 20) 1) 50) 
(+ (+ (+ (* (* (+ 1 1) 100) 3) 1) 20) 50) 
(+ (+ (+ (* (* (+ 1 1) 3) 100) 1) 20) 50) 
(+ (+ (+ (* (* (+ 1 1) 100) 3) 50) 1) 20) 
(+ (+ (+ (* (* (+ 1 1) 3) 100) 50) 1) 20) 
(+ (+ (+ (* (* (+ 1 1) 100) 3) 1) 50) 20) 
(+ (+ (+ (* (* (+ 1 1) 3) 100) 1) 50) 20) 
(+ (/ (+ (* (- (- 100 1) 1) 20) 50) 3) 1)  <--
(+ (+ (+ (* (* (+ 1 1) 100) 3) 50) 20) 1) 
(+ (+ (+ (* (* (+ 1 1) 3) 100) 50) 20) 1) 
(+ (+ (+ (* (* (+ 1 1) 100) 3) 20) 50) 1) 
(+ (+ (+ (* (* (+ 1 1) 3) 100) 20) 50) 1) 
(SOLVE2 '(1 1 1 3 20 50 100) 671) took 6,198 milliseconds (6.198 
seconds) to run.
Of that, 42 milliseconds (0.042 seconds) were spent in The Cooperative 
Multitasking Experience.
155 milliseconds (0.155 seconds) was spent in GC.
 35,118,584 bytes of memory allocated.
13

This is on a G4 400 running MCL 4.3.1 in Classic.

Dennis
From: Kenny Tilton
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <3CFB7101.F1F5292D@nyc.rr.com>
Dennis Marti wrote:
> 
> 
> I think you missed one.
> 
> ? (time (solve2 '(1 1 1 3 20 50 100) 671))
> 
> (+ (+ (+ (* (* (+ 1 1) 100) 3) 20) 1) 50)
> (+ (+ (+ (* (* (+ 1 1) 3) 100) 20) 1) 50)
> (+ (+ (+ (* (* (+ 1 1) 100) 3) 1) 20) 50)
> (+ (+ (+ (* (* (+ 1 1) 3) 100) 1) 20) 50)
> (+ (+ (+ (* (* (+ 1 1) 100) 3) 50) 1) 20)
> (+ (+ (+ (* (* (+ 1 1) 3) 100) 50) 1) 20)
> (+ (+ (+ (* (* (+ 1 1) 100) 3) 1) 50) 20)
> (+ (+ (+ (* (* (+ 1 1) 3) 100) 1) 50) 20)
> (+ (/ (+ (* (- (- 100 1) 1) 20) 50) 3) 1)  <--
> (+ (+ (+ (* (* (+ 1 1) 100) 3) 50) 20) 1)
> (+ (+ (+ (* (* (+ 1 1) 3) 100) 50) 20) 1)
> (+ (+ (+ (* (* (+ 1 1) 100) 3) 20) 50) 1)
> (+ (+ (+ (* (* (+ 1 1) 3) 100) 20) 50) 1)
> (SOLVE2 '(1 1 1 3 20 50 100) 671) took 6,198 milliseconds (6.198
> seconds) to run.
> Of that, 42 milliseconds (0.042 seconds) were spent in The Cooperative
> Multitasking Experience.
> 155 milliseconds (0.155 seconds) was spent in GC.
>  35,118,584 bytes of memory allocated.
> 13
> 
> This is on a G4 400 running MCL 4.3.1 in Classic.
> 

I missed that, too. Gotta start over to handle associativity properly, I
think.

Wow, a larger search space, slower box and much faster. Just curious:
are you using declarations at all? 

-- 

 kenny tilton
 clinisys, inc
 ---------------------------------------------------------------
""Well, I've wrestled with reality for thirty-five years, Doctor, 
  and I'm happy to state I finally won out over it.""
                                                  Elwood P. Dowd
From: Dennis Marti
Subject: Re: Solving an arihmetic puzzle -- if anyone cares
Date: 
Message-ID: <dennis_marti-F0374A.02055604062002@virt-reader.news.rcn.net>
In article <·················@nyc.rr.com>,
 Kenny Tilton <·······@nyc.rr.com> wrote:

> > This is on a G4 400 running MCL 4.3.1 in Classic.

> Wow, a larger search space, slower box and much faster. Just curious:
> are you using declarations at all?

Slower box? Apparently not! :)

No declarations yet. I'm pruning duplicates from the list then 
recursively solving smaller problems.

Dennis
From: Greg Menke
Subject: Re: Solving an arihmetic puzzle
Date: 
Message-ID: <m37klgh8gr.fsf@europa.pienet>
> For example,
> (solve '(1 1 1 3 50 100) 651))
> 
> should produce the output
> 1+1=2
> 2*3=6
> 6*100=600
> 600+60=650
> 650+1=651
> 
> What do you suggest for an approach?
> I have been learning LISP very little and I can't figure out what to


This was a fun puzzle, here's my attempt;

Instead of generating a list of permutations, then solving, I used a
recursive approach that permutes the list and operators, but
accumulates the arithmetic on the way down, leaving the operations
involving the last digit at the end of each branch where the = tests
are also performed.  This avoids the big list problem and avoids doing
evals.  It also avoids redundant computation of permutations already
selected higher up in the tree.  On the other hand, it is a completely
brute force approach and does not attempt to recognize ineffectual
operations, duplicate numbers or branches which cannot reach the goal.
I'm not sure about the desirability of permuting duplicate numbers, on
the other hand, it does ensure all digits in the list are used once
which was a requirement of the puzzle.  The consing is due to the list
manipulations I use to keep track of the permutation and build the
output string when the test is sucessful.  The hashtable stuff is
there for a variation I'm working on that caches values of
permutations of varying lengths- but its not working yet.  Since the
brute force approach runs into performance trouble when the input list
gets a bit longer (9 digits), I thought a smarter version would be
interesting to try.

I'm using Lispworks 4.2 with the 4.2.6 patch, all runs are done with
code compiled using default compiler settings.  The OS is Linux,
kernel ver 2.2.19, the hardware is a dual Celeron 466 SMP box with 512
megs ram.


GDMP 29 > (time (solve-it '(1 1 1 3 50 100) 651))
Timing the evaluation of (solve-it (quote (1 1 1 3 50 100)) 651)

brute force solver; Goal 651, data (1 1 1 3 50 100)

(1 + 1 * 3 * 100 + 1 + 50)
(1 + 1 * 3 * 100 + 50 + 1)
(1 + 1 * 100 * 3 + 1 + 50)
(1 + 1 * 100 * 3 + 50 + 1)
(1 + 1 * 3 * 100 + 1 + 50)
(1 + 1 * 3 * 100 + 50 + 1)
(1 + 1 * 100 * 3 + 1 + 50)
(1 + 1 * 100 * 3 + 50 + 1)
(1 + 1 * 3 * 100 + 1 + 50)
(1 + 1 * 3 * 100 + 50 + 1)
(1 + 1 * 100 * 3 + 1 + 50)
(1 + 1 * 100 * 3 + 50 + 1)
(1 + 1 * 3 * 100 + 1 + 50)
(1 + 1 * 3 * 100 + 50 + 1)
(1 + 1 * 100 * 3 + 1 + 50)
(1 + 1 * 100 * 3 + 50 + 1)
(1 + 1 * 3 * 100 + 1 + 50)
(1 + 1 * 3 * 100 + 50 + 1)
(1 + 1 * 100 * 3 + 1 + 50)
(1 + 1 * 100 * 3 + 50 + 1)
(1 + 1 * 3 * 100 + 1 + 50)
(1 + 1 * 3 * 100 + 50 + 1)
(1 + 1 * 100 * 3 + 1 + 50)
(1 + 1 * 100 * 3 + 50 + 1)

24 solutions, 737280 tests

user time    =      2.000
system time  =      0.000
Elapsed time =   0:00:02
Allocation   = 10261184 bytes standard / 21161272 bytes fixlen
0 Page faults
nil




(time (solve-it '(1 1) 2))
Timing the evaluation of (solve-it (quote (1 1)) 2)

brute force solver; Goal 2, data (1 1)

(1 + 1)
(1 + 1)

2 solutions, 8 tests

user time    =      0.010
system time  =      0.000
Elapsed time =   0:00:00
Allocation   = 1296 bytes standard / 4158 bytes fixlen
0 Page faults
nil

GDMP 31 > 







(defun solve-tree (level digitlist accum goal test-sequence)

  (cond ((> (length digitlist) 1)
         (loop with elem-count     = (length digitlist)
               and  remaining-list = nil
               and  chosen-item    = nil

               for i from 0 below elem-count

               do
               (setf chosen-item (nth i digitlist))
               (setf remaining-list (append (when (> i 0) (subseq digitlist 0 i))
                                            (when (< i (1- elem-count)) (subseq digitlist (1+ i)))) )

               (cond ((zerop level)
                      (solve-tree (1+ level)
                                  remaining-list
                                  chosen-item
                                  goal
                                  (list chosen-item)) )

                     (t
                      (solve-tree (1+ level)
                                  remaining-list 
                                  (+ accum chosen-item) 
                                  goal
                                  (append test-sequence (list "+" chosen-item)))

                      (solve-tree (1+ level)
                                  remaining-list 
                                  (- accum chosen-item) 
                                  goal
                                  (append test-sequence (list "-" chosen-item)))

                      (solve-tree (1+ level)
                                  remaining-list 
                                  (* accum chosen-item) 
                                  goal
                                  (append test-sequence (list "*" chosen-item)))

                      (solve-tree (1+ level)
                                  remaining-list 
                                  (/ accum chosen-item) 
                                  goal
                                  (append test-sequence (list "/" chosen-item))) ))))


        (t (let ((chosen-item     (car digitlist)))

             (cond ((numberp goal)
                    (incf *num-tests* 4)
                    (when (= (+ accum chosen-item) goal) (incf *num-solutions*)
                      (format t "~A~%" (append test-sequence (list "+" chosen-item)) ))
                    (when (= (- accum chosen-item) goal) (incf *num-solutions*)
                      (format t "~A~%" (append test-sequence (list "-" chosen-item)) ))
                    (when (= (* accum chosen-item) goal) (incf *num-solutions*)
                      (format t "~A~%" (append test-sequence (list "*" chosen-item)) ))
                    (when (= (/ accum chosen-item) goal) (incf *num-solutions*)
                      (format t "~A~%" (append test-sequence (list "/" chosen-item)) )) )

                   ((hash-table-p goal)
                    (setf (gethash (+ accum chosen-item) goal) t)
                    (setf (gethash (- accum chosen-item) goal) t)
                    (setf (gethash (* accum chosen-item) goal) t)
                    (setf (gethash (/ accum chosen-item) goal) t)) )) )))



(defun solve-it (digitlist goal)
  (setf *num-solutions* 0)
  (setf *num-tests* 0)

  (format t "~%brute force solver; Goal ~A, data ~A~%~%" goal digitlist)
  (solve-tree 0 digitlist 0 goal nil)
  (format t "~%~A solutions, ~A tests~%" *num-solutions* *num-tests*) )