Just for fun: Countdown numbers game solver

[Arnaud Delobelle]

On Jan 23, 3:45 pm, Terry Jones <te... at jon.es> wrote:
> Hi Arnaud and Dan

Hi Terry

> >>>>> "Arnaud" == Arnaud Delobelle <arno... at googlemail.com> writes:
> >> What was wrong with the very fast(?) code you sent earlier?
>
> Arnaud> I thought it was a bit convoluted, wanted to try something I
> Arnaud> thought had more potential.  I think the problem with the second
> Arnaud> one is that I repeat the same 'fold' too many times.
>
> and later:
>
> Arnaud> Yes, I've been doing this by writing an 'action' (see my code) that
> Arnaud> takes note of all reached results.
>
> These are both comments about pruning, if I understand you. In the first
> you weren't pruning enough and in the second you're planning to prune more.

Yes I think the first one is about pruning, I couldn't think of the
english word.

> I'm giving up thinking about this problem because I've realized that the
> pruning solution is fundamentally subjective. I.e., whether or not you
> consider two solutions to be the "same" depends on how hard you're willing
> to think about them (and argue that they're the same), or how smart you
> are.

FWIW, I have a clear idea of what the space of solutions is, and which
solutions I consider to be equivalent.  I'll explain it below.  I'm
not saying it's the right model, but it's the one within which I'm
thinking.

> I have a new version that does some things nicely, but in trying to do
> efficient pruning, I've realized that you can't satisfy everyone.
>
> Some examples for the problem with target 253, numbers = 100, 9, 7, 6, 3, 1
>
> Firstly, there are nice solutions that go way negative, like:
>
>   1 7 6 3 9 sub mul mul sub   or   1 - 7 * 6 * (3 - 9)

I think it's best to forbid negatives.  Solutions always be written
without any negative intermediate answer.  E.g. 1-7*6*(3-9) can be
done as 1+7*6*(9-3).

>
> Here's a pruning example. Are these the "same"?
>
>   1 3 7 100 9 sub sub mul sub  or  1 - 3 * (7 - 100 - 9)

rather 1 - 3*(7 - (100 - 9))

>   1 3 7 9 100 sub add mul sub  or  1 - 3 * (7 - 9 - 100)

rather 1 - 3*(7 + (9 - 100))

Not allowing negatives means these are
   3*(100 - 9 - 7) + 1
or 3*(100 - (9 + 7)) + 1
or 3*(100 - 7 - 9) + 1

I don't consider these to be equivalent, because their equivalence
depends on understanding the meaning of subtraction and addition.
(I've also applied the 'big then small' rule explained below)

>
> I think many people would argue that that's really the "same" and that one
> of the two should not appear in the output. The same goes for your earlier
> example for 406. It's 4 * 100 + 2 x 3, and 2 x 3 + 100 * 4, and so on.

There is a simple rule that goes a long way: "big then small", i.e.
only allow a <op> b when a > b.
So the above is canonically written as 100*4 + 2*3.

>
> My latest program does all these prunings.
>
> But you can argue that you should push even further into eliminating things
> that are the same. You could probably make a pretty fast program that
> stores globally all the states it has passed through (what's on the stack,
> what numbers are yet to be used, what's the proposed op) and never does
> them again. But if you push that, you'll wind up saying that any two
> solutions that look like this:
>
>   ....... 1 add
>
> e.g.
>
>   6 9 3 sub mul 7 mul 1 add   or  6 * (9 - 3) * 7 + 1
>   7 6 mul 9 3 sub mul 1 add   or  7 * 6 * (9 - 3) + 1
>
> are the same.

I honestly think this is outside the scope of this problem, which must
remain simple.  I'm not trying to convince you of anything, but I'll
just explain briefly what solutions I don't want to repeat.

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

so     6 9 3 sub mul 7 mul 1 add -> (((6 * (9 - 3)) * 7) + 1)
and    7 6 mul 9 3 sub mul 1 add -> (((7 * 6) * (9 - 3)) + 1)

are two distinct solutions according to my criterion.

But
       9 3 sub 6 mul 7 mul 1 add -> ((((9 - 3) * 6) * 7) + 1)

is not a solution because 9-3 < 6

To be perfectly honest (and expose my approach a little to your
argument) I added a three additional rules:

* Don't allow x - x
* Don't allow x * 1
* Don't allow x / 1

My aim was find and efficient way to generate all solutions exactly
once if there is no repeat in the list of starting numbers.  This is a
clearly defined problem and I wanted to find a nice way of solving
it.  I realised that the folding method was redundant in that respect
and this is what I wanted to fix (I have a fix, I think, but the
'proof' of it is only in my head and might be flawed).

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

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

I'd like to see it :)

--
Arnaud