Just for fun: Countdown numbers game solver

[Terry Jones]

>>>>> "Arnaud" == Arnaud Delobelle <arnodel at googlemail.com> writes:
>> 
>> Ha - you can't have it both ways Arnaud! You don't want the computation to
>> go negative... doesn't that (and my "proof") have something to do with the
>> inverse nature of add and sub? :-)

Arnaud> I think I can have it both ways, here's why: the "big then small"
Arnaud> and "no negatives" rules are applied indiscriminately by the
Arnaud> algorithm: it doesn't need to know about the history of operations
Arnaud> in order to make a decision depending on their nature.  OTOH,
Arnaud> identifying (a + b) - c and a + (b - c) for example, requires
Arnaud> inspection of the stack/tree/ calculation history.  It is an
Arnaud> *informed* decision made by the algorithm

But this is having it both ways too :-)

The reason the algorithm can do it indiscriminately is because *you* know
that it always applies, and *you* figure out and implement the algorithm
that way. The algorithm doesn't have a mind of its own, after all.

BTW, there are some very important issues here. One is about representation
(thinking about representation is one of my pet vices). When you try to
solve some real-world problem with a computer, you must choose a
representation. What many people seem to fail to recognize is that in so
doing you've already begun to solve the problem. If you pick a better
representation, your algorithm can potentially be much dumber and still be
hugely faster than a brilliant algorithm on a terrible representation.

In maintaining an A > B invariant in operations A + B and A * B, you're
using insight into the problem to influence representation. With that
better representation, your algorithm doesn't have to do so much work.

I wrote some more about this a while ago at

  http://www.fluidinfo.com/terry/2007/03/19/why-data-information-representation-is-the-key-to-the-coming-semantic-web/

Arnaud> Note that disallowing 0 and disallowing x - x are equivalent, as
Arnaud> the only way to get your first 0 is by doing x - x.

That depends. I allow negative numbers in the input, and also 0 (I just
don't let you use it :-))

Arnaud> Thanks for the discussion, it's made me realise more clearly what I
Arnaud> was doing.

Me too! Thanks.

Terry