Just for fun: Countdown numbers game solver

[Terry Jones]

Hi Arnaud and Dan

>>>>> "Arnaud" == Arnaud Delobelle <arnodel 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.

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.

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)


Here's a pruning example. Are these the "same"?

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

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.

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. And if we go that far, then a really smart person might argue
that this

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

is also the "same" (because all these solutions get to 252 and then add 1,
so they're clearly the "same", right?):


Once you've gone that far, you might even argue that on a particular
problem of a particular difficulty (subjectively matching what your brain
is capable of) all solutions that start out by pushing 1 onto the stack are
actually the "same".

And if you're even smarter than that, you might just look at any problem
and say "Hey, that's easy! The answer is X" or "There's clearly no
solution" because you'd immediately just see the answer (if any) and that
all others were just obvious variants.

E.g., if I said to you: "make 20 out of (20, 10, 10, 3)", I imagine you
could immediately list the answer(s?)

  20 = 20
  20 = 10 + 10
  20 = 20 + 10 - 10
  20 = 20 - 10 + 10

etc., and explain that those are all really the same. You'd prune on the
spot, and consider it obvious that the pruning was fully justified.

But my 6-year-old son couldn't tell you that, and I doubt he'd agree with
your prunings.

OK, enough examples.  I'm just trying to illustrate that the (difficult)
problem of efficiently pruning doesn't have an objective solution.  Pruning
is subjective. OTOH, the decision problem "does this puzzle have any
solutions or not (and if so, produce one)" does.

That's why I'm going to stop working on this. My stack solution code is
fun, but working on making it prune better is a black hole. And to make
matters worse, the more I push it (i.e., the more advanced its prunings
get), the less likely (some) people are to agree that its output is still
correct. You can't win.

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

Terry