From: Hans Fugal <fugalh@...>
Date: 2004-11-15T01:23:26+09:00
Subject: [non-SOLUTION] Countdown (#7)

I didn't actually implement it, but my approach was going to be the 
following.

The problem is basically a search through the (large) space of possible 
expressions. I figured brute force would take a long time, and others 
have proven that hypothesis correct.

I at first was going to use an A* search, but I realized that A* would 
try to optimize the path length which (the way I was planning on 
implementing it) would mean it would strive for the shortest correct 
solution. The length of the solution didn't matter, though, all that 
mattered was that a correct answer was found. So I decided a greedy 
search would be better.

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 of course is when an exact answer is not available. You would 
have to exhaust the search space, and that takes a long time no matter 
the algorithm. It would be natural to impose the time limit and 
empirically strive for an algorithm that more often than not finds a 
close answer within that time limit.

The reason I didn't finish the implementation is that I couldn't quite 
decide how to build the state space tree in the time I had. I'm 
interested in how others did this.