On Jan 23, 3:45 pm, Terry Jones <[EMAIL PROTECTED]> wrote:
> Hi Arnaud and Dan
Hi Terry
> >>>>> "Arnaud" == Arnaud Delobelle <[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
