Just for fun: Countdown numbers game solver

[Terry Jones]

>>>>> "Arnaud" == Arnaud Delobelle <arnodel 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? :-)

Arnaud> (I've also applied the 'big then small' rule explained below)

And now you're taking advantage of your knowledge of > and < ...

My original code did this big then small canonicalization too.

That's my point exactly - pruning depends on who you are, how smart you
are, how hard you work, your personal taste, etc.

Arnaud> I see a solution as a full ordered binary tree.  Each node has a
Arnaud> weight (which is the result of the calculation it represents) and
Arnaud> the left child of a node has to be at least as heavy as the right
Arnaud> child.  Each parent node can be labeled + - * or /.  If a node x
Arnaud> has two children y and z and is labeled <op>, let me write x = (y
Arnaud> <op> z)

Where does the sequence of numbers enter into this? You have a tree of
operations - is it acting on a stack? What's on the stack?

It sounds similar to what I've done. I walk up and down the tree, keeping
the stack and the stack history, doing operations (including pushing onto
the stack) and undoing them.

There are several more prunings I could be doing, but these require looking
further back in the stack.  E.g., I force div before mul and sub before
add, and I also apply the "big then small" rule to the intermediate stack
results if there are series of identical operations (not just to a single
operation). E.g. X / Y / Z can be re-ordered so that Y >= Z, and A + B + C
can be reordered so A >= B >= C. Doing it on the stack results is different
(but similar) to doing it on the raw input numbers.

There are lots of other little and more complex things you can do to prune.

You want to prune early, of course. The stack model of computation make
this hard because it's always legitimate to push all the numbers onto the
stack, by which point you're already deep in the tree.

And this approach only lets you do local pruning - i.e., that affect the
branch of the tree you're on. If you stored the state of the stack, the
operation you're about to do, and the (sorted) numbers remaining to be
input, then if you ever hit that configuration elsewhere in the massive
tree, you could know that you'd been that way before. But are you justified
in pruning at that point? The identical state of the computation could have
been arrived at via a very different method.

But that's where the big speed-up in this approach is.

At this realization I decided to give up :-)

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!).

Arnaud> If there are repeats in the list of starting numbers, I don't worry
Arnaud> about repeating solutions.

I handle most of those cases, but I didn't push all the way. With target 32
and input 8, 8, 8, 8 my code still gives 2 answers:

        8 8 add 8 8 add add
        8 8 add 8 add 8 add

>> If anyone wants the stack simulation code, send me an email.

Arnaud> I'd like to see it :)

I'll send it.

Terry