On Jan 23, 8:40 pm, Terry Jones <[EMAIL PROTECTED]> wrote: > >>>>> "Arnaud" == Arnaud Delobelle <[EMAIL PROTECTED]> 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? :-)
I think I can have it both ways, here's why: the "big then small" and "no negatives" rules are applied indiscriminately by the algorithm: it doesn't need to know about the history of operations in order to make a decision depending on their nature. OTOH, identifying (a + b) - c and a + (b - c) for example, requires inspection of the stack/tree/ calculation history. It is an *informed* decision made by the algorithm > Arnaud> (I've also applied the 'big then small' rule explained below) > > And now you're taking advantage of your knowledge of > and < ... Again, *I* have the knowledge, the algorithm does it indiscriminately... [...] > 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!). Note that disallowing 0 and disallowing x - x are equivalent, as the only way to get your first 0 is by doing x - x. Thanks for the discussion, it's made me realise more clearly what I was doing. -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
