Hi Arnaud and Dan >>>>> "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. 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 -- http://mail.python.org/mailman/listinfo/python-list