Just for fun: Countdown numbers game solver

[Arnaud Delobelle]

On Jan 23, 8:40 pm, Terry Jones <te... at jon.es> wrote:
> >>>>> "Arnaud" == Arnaud Delobelle <arno... at googlemail.com> writes:
>
> Arnaud> FWIW, I have a clear idea of what the space of solutions is, and
> Arnaud> which solutions I consider to be equivalent.  I'll explain it
> Arnaud> below.  I'm not saying it's the right model, but it's the one
> Arnaud> within which I'm thinking.
>
> OK. This reinforces why I'm not going to work on it anymore, the solution
> is subjective (once you start pruning).
>
> Arnaud> I think it's best to forbid negatives.  Solutions always be written
> Arnaud> without any negative intermediate answer.  E.g. 1-7*6*(3-9) can be
> Arnaud> done as 1+7*6*(9-3).
>
> That's a good optimization, and I think it's easy to prove that it's
> correct supposing the target is positive and the inputs are all positive.
>
> If you consider the intermediate results in a solution, then if you ever go
> negative it's because of an operation X (must be a sub or a div) and when
> you next become positive it's due to an operation Y (must be add or
> mul). So you can "reflect" that part of the computation by doing the
> opposite operations for that formerly sub-zero intermediate sequence.
>
> Arnaud> I don't consider these to be equivalent, because their equivalence
> Arnaud> depends on understanding the meaning of subtraction and addition.
>
> 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? :-)

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

> Arnaud> (I've also applied the 'big then small' rule explained below)
>
> And now you're taking advantage of your knowledge of > and < ...

Again, *I* have the knowledge, the algorithm does it
indiscriminately...

[...]

> Arnaud> To be perfectly honest (and expose my approach a little to your
> Arnaud> argument) I added a three additional rules:
>
> Arnaud> * Don't allow x - x
> Arnaud> * Don't allow x * 1
> Arnaud> * Don't allow x / 1
>
> Yes, I do these too, including not allowing a zero intermediate (which is a
> useless calculation that simply could not have been done - see, I have deep
> knowledge of zero!).

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

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

--
Arnaud