David G. Andersen wrote:
> On Mon, Nov 15, 2004 at 01:23:26AM +0900, Hans Fugal scribed:
> 
>>If people can do this in 30 seconds, they either know a trick I don't 
>>know, or they are probably doing a sort of greedy search. Pick the 
>>number/operation that gets you closer than the others, and if that 
>>doesn't get you there fish around in the vicinity. So I think greedy 
>>would work pretty well.

Hmm, I just realized that may not have come across how I wanted. What I 
meant was, if human beings on a game show can do it in 30 seconds...

>   The trick is being clever about the combinations you try.
> You don't need to do things like 1/1, or any changes that
> produce the same number (4/2, for example, since it consumes a 4 and
> a 2 and only produces a 2).  Also, only some of the operations don't
> commute -- so you need to try a + b, but not b + a.  Since fractions
> aren't allowed, you only need to do one division.  Etc.

Yeah, it was a combination of special cases I knew would help and the 
details of spawning expressions methodically that I didn't get 
straightened out in my head in the time I had. For example, adding a 
term and operator each time would search through (a+b)+c but not 
(a+b)+(c+d). I think the bottom-up approach is perhaps what I was 
searching for.

>   If you really want to speed it up, you can memoize it to avoid
> searching the same sub-parts of the solution space over and over.
> It consumes a bit of memory - I use a stupid memoization scheme
> that represents the state as a string of numbers separated by
> dashes that consumes about 10 megs - but it works pretty well.
> 
>   -Dave
> 
>