On Wed, Dec 05, 2001 at 08:36:36PM +0800, Sacha Chua wrote:
> On 04 Dec 2001 02:20:19AM -0600, Michael Chaney ([EMAIL PROTECTED]) said:
>
> > The biggest problem that I see is that "9 9 + 9 +" is identical to
> > "9 9 9 + +", "9 9 9 + *" is identical to "9 9 9 * +", etc. so there is
> > room for optimization. Ultimately, it would probably make sense to run
> > your output through another program to determine which in the list are
>
> Hehehe. No need to determine - just evaluate each expression and sort.
> ;)
Yes, my feeling now is that it doesn't matter. The easiest thing to do
would be to evaluate every possible expression and keep track of the
results. At the end, which would probably take a year of computational
work, we could see which integers haven't been computed.
> > for a bunch of 9's and operators, and ultimately it's probably the
> > same as the number of combinations of operators and parenthetical
>
> Actually, hmmm.. you're right, there's a nuance I think I've missed. Is
> permutation called for, or can we assume that all 9s end up at the left?
> I've a sinking feeling that the former is the case, but I'd like to be
> proven wrong. If so, that raises the complexity a notch, but postfix
> does tend to make it easier - just generate unique permutations, I
> suppose.
>
> What's the total count of possible expressions?
No idea. The possibilities go from:
9 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 +
to
9 9 9 9 9 9 9 9 9 + + + + + + + +
where "9" can be either -9 or 9, and "+" is any of the four basic
operators + - * and /. That means that for each valid equation that you
can come up with, there are 2^25 combinations (2^9 * 4^8) of numbers and
operators. So the above are really equation templates.
Coming up with valid equation templates is the difficult part, but my
belief is that there are only 256. If that's true, then this is
solvable within perhaps a few hours on standard hardware.
Here's why I think there are 256, or 128. We know that a valid equation
must have one more number than operators, so 9 numbers means 8 operators.
Moreover, taken from the left, our count of numbers must always remain
higher than the count of operators. For instance:
9 9 + 9 + +
is clearly wrong.
However, we can come up with two simple facts about all equation
templates, in fact all postfix equations:
1. They will all start with two numbers.
2. They will all end with an operator.
What that means is that we need only concern ourselves with the
locations of the last 7 numbers. This sequence may be the one:
9 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 +
9 9 + 9 + 9 + 9 + 9 + 9 + 9 9 + +
9 9 + 9 + 9 + 9 + 9 + 9 9 + + 9 +
9 9 + 9 + 9 + 9 + 9 + 9 9 + 9 + +
9 9 + 9 + 9 + 9 + 9 + 9 9 9 + + +
9 9 + 9 + 9 + 9 + 9 9 + 9 + + 9 +
9 9 + 9 + 9 + 9 + 9 9 + 9 + 9 + +
9 9 + 9 + 9 + 9 + 9 9 + 9 9 + + +
The brute force approach to this is to create every possible combination
of numbers and operators (there are 2^17, about 128,000) and then decide
which are valid. Given the prior restraints, we know that we can
immediately cut that down by a factor of 2^3, meaning that there are
only 16,384 combinations worth looking at.
Actually, there are 1430 unique valid templates, I have no idea where that
number comes from but here's the program to find them:
#include <stdio.h>
#include <stdlib.h>
/* assume that a 0 bit is a number, and a 1 bit is an operator */
main() {
long i, check, sum;
for (check=1; check<(1<<15) ; check += 2) {
for (sum=2 , i=1<<14 ; i>0 ; i>>=1) {
if (check & i) sum--; else sum++;
if (sum==0) break;
}
if (i==0 && sum==1) {
print_seq(check);
}
}
}
print_seq(long seq) {
long i, check;
for (i=1<<16 ; i>0 ; i>>=1) {
if (seq & i) printf("+ "); else printf("9 ");
}
printf("\n");
}
It would be fairly easy to modify that to subsequently print out all
possible combinations of equations based on the templates, but that
means there are 1430 * 2^25 equations, which works out to somewhere
around 45 billion.
The largest number which can be expressed is 9^9, which is somewhere
under 1,000,000,000 (which is 10^9). It would be possible, and
reasonable, to keep track of which integers have been found by using a
bitmap of around 100MB. The biggest problem that I see is that numbers
like 1/9 end up being repeating sequences in binary, so something like
this:
9 9 9 / / 9 *
may or may not equal 1. Probably not exactly. Rounding is dangerous
because something like this:
9 9 9 9 9 9 9 9 / / / / / / / 9 +
Should not be rounded down to 9, even though it likely would be.
That's more information than you probably wanted :)
Michael
--
Michael Darrin Chaney
[EMAIL PROTECTED]
http://www.michaelchaney.com/
_
Philippine Linux Users Group. Web site and archives at http://plug.linux.org.ph
To leave: send "unsubscribe" in the body to [EMAIL PROTECTED]
To subscribe to the Linux Newbies' List: send "subscribe" in the body to
[EMAIL PROTECTED]
