From: "David G. Andersen" <dga@...>
Date: 2004-11-15T11:41:45+09:00
Subject: Re: [non-SOLUTION] Countdown (#7)

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.

  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.

  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