Prev: doubly linked list
Next: van Emde Boas tree implementation
From: Phil Cairns on 15 Jun 2006 16:42
gw7rib(a)aol.com wrote:
> Willem wrote:
>> Phil wrote:
....
>> ) Arrange the numbers 4, 5, 6, 7 and 8 in any order, using BODMAS ordering
>> ) to get to 50. (BODMAS is Brackets, pOwers, Division, Multiplication,
>> ) Addition, Subtraction: their way of remembering operator precedence). He
>> ) came up with (4 + 7 x 8) / 6 * 5 in the test. I found (8 x 7) - 6 x (5 -
>> ) 4), and this just happens to be the numbers in reverse order. I said,
>> ) "Hmmm ... it should be really easy to write a program that would figure
>> ) out all of those combinations for you."
>> ) "Cool, Dad ... how would that work?"
>> ) "Well," I said, "you just take the first number and try adding,
>> ) subtracting, multiplying or dividing the rest of the numbers to get to
>> ) ... err ... getting confused, let me show you, son. If the first
>> ) operator is going to be a plus, the whole thing will be 4 + (5, 6, 7 & 8
>> ) arranged to be 46). Or it could be 4 - (5, 6, 7 & 8 arranged to be -54).
>> ) See?"
....
>>
>> The way I did this is to change to RPN (Reverse Polish Notation),
>> which eliminates the brackets entirely.

That is really nice.

> Neat. The last time I tried anything like this, I wrote a program to
> write a program - the first program printed out all the possible
> expressions, this was saved to a file so it too could be executed.

I almost did this ... I've got a copy of the Dragon book that I pull out
every now and then, and I thought that this was going to be a good use.
But with RPN, the problem is much easier.

Phil.
From: Gene on 15 Jun 2006 17:27
Phil Cairns wrote:
> My son (12 years old) came home and said that he just had a math test,
> and the question went something like this:
>
> Arrange the numbers 4, 5, 6, 7 and 8 in any order, using BODMAS ordering
> to get to 50. (BODMAS is Brackets, pOwers, Division, Multiplication,
> Addition, Subtraction: their way of remembering operator precedence). He
> came up with (4 + 7 x 8) / 6 * 5 in the test. I found (8 x 7) - 6 x (5 -
> 4), and this just happens to be the numbers in reverse order. I said,
> "Hmmm ... it should be really easy to write a program that would figure
> out all of those combinations for you."
> "Cool, Dad ... how would that work?"
> "Well," I said, "you just take the first number and try adding,
> subtracting, multiplying or dividing the rest of the numbers to get to
> ... err ... getting confused, let me show you, son. If the first
> operator is going to be a plus, the whole thing will be 4 + (5, 6, 7 & 8
> arranged to be 46). Or it could be 4 - (5, 6, 7 & 8 arranged to be -54).
> See?"
>

Cool problem. Here's one idea. (It omits powers of numbers) No doubt
there is a cleaner way.

--------
#include <stdio.h>

char ops[] = "+-*/";

int opd[] = { 4, 5, 6, 7, 8 }, opd_p = 5;
int stk[100], stk_p;
char buf[100]; int buf_p;

// print reverse polish expression in buf in infix
// destroys buf_p
void print(void)
{
int val = buf[--buf_p];
if ('0' <= val && val <= '9')
printf("%c", val);
else {
printf("(");
print();
printf("%c", val);
print();
printf(")");
}
}

// evaluate and print all expressions == 50 over the
// list of operands in opd[] using stack stk and
// rpn buffer buf
void eval(void)
{
int i, t;

for (i = 0; i < opd_p; i++) {
buf[buf_p++] = opd[i] + '0'; // append opnd to rpn
stk[stk_p++] = opd[i]; // push opnd on stack
--opd_p; // remove opnd from list
t = opd[i];
opd[i] = opd[opd_p];
eval(); // recur
opd[i] = t; // restore opnd list
++opd_p;
--stk_p; // pop stack
--buf_p; // restore rpn
}
if (stk_p >= 2) {
int x = stk[--stk_p], // pop operands
y = stk[--stk_p];
for (i = 0; i < sizeof ops - 1; i++) { // choose op

switch (ops[i]) { // compute
case '+': stk[stk_p++] = x + y; break;
case '-': stk[stk_p++] = x - y; break;
case '*': stk[stk_p++] = x * y; break;
case '/': if (y == 0 || x % y != 0)
continue;
stk[stk_p++] = x / y; break;
}

buf[buf_p++] = ops[i]; // append to rpn

if (stk_p == 1 && opd_p == 0) { // check for base case
if (stk[0] == 50) {
t = buf_p;
print();
printf("\n");
buf_p = t;
}
}
else
eval(); // recur

--stk_p; // restore stack and buffer
--buf_p;
}
stk[stk_p++] = y; stk[stk_p++] = x; // re-push operands
}
}

int main(void)
{
eval();
return 0;
}

From: Logan Shaw on 16 Jun 2006 03:16
Phil Cairns wrote:
> My son (12 years old) came home and said that he just had a math test,
> and the question went something like this:
>
> Arrange the numbers 4, 5, 6, 7 and 8 in any order, using BODMAS ordering
> to get to 50. (BODMAS is Brackets, pOwers, Division, Multiplication,
> Addition, Subtraction: their way of remembering operator precedence). He
> came up with (4 + 7 x 8) / 6 * 5 in the test. I found (8 x 7) - 6 x (5 -
> 4), and this just happens to be the numbers in reverse order. I said,
> "Hmmm ... it should be really easy to write a program that would figure
> out all of those combinations for you."
> "Cool, Dad ... how would that work?"
> "Well," I said, "you just take the first number and try adding,
> subtracting, multiplying or dividing the rest of the numbers to get to
> ... err ... getting confused, let me show you, son. If the first
> operator is going to be a plus, the whole thing will be 4 + (5, 6, 7 & 8
> arranged to be 46). Or it could be 4 - (5, 6, 7 & 8 arranged to be -54).
> See?"

> havoc. And after checking with the numbers in order, the numbers would
> have to be rearranged. The whole concept jumped from being merely
> interesting to devilishly difficult, and perhaps fiendishly or even
> diabolically difficult. Perhaps I should talk to L. da Q. :)

The simplest way I can think of is to make a few observations:

1. The numbers can appear in any order.
2. Each position (space between numbers) can have any of the operators,
and a given expression can re-use a single operator as many times
as it wants or can use it no times at all. So it's not merely a
matter of changing their order; you must try all possible lists
of operators. If you have 5 operators and 5 numbers, that's 4
possible positions for the operators, so that means 5^4 different
lists of operators.
3. Open brackets can appear immediately before a number and nowhere
else; close brackets can appear immediately after a number and
nowhere else. So, in order to produce every set of brackets, it
is sufficient (if not necessarily *efficient*) to treat each
position as a bit, then go through all possible bit strings,
inserting a bracket if the bit is 1, or leaving out the bracket
if it's not. This will yield some strings which are syntactically
invalid, but you can toss those out easily enough.

Once you have all the possible lists of brackets, all the possible
orders of the numbers, and all the possible lists of operators, if
you cross these together, you get all possible legal expressions.
Then it's just a matter of finding one (or all the ones) that evaluate
to the appropriate value.

Evaluating is a bit irritating, but maybe not that bad. Since this is
infix, you'd think you need to consider the precedence rules, but
actually you don't: since we've already established that you can
generate all possible valid sequences of brackets, you can toss out
precedence rules, merely evaluate left to right, and be sure that
if a non-left-to-right order expression is needed, it will be found
since you will be generating the fully parenthesized version.

Since 5! * 4^5 * 2^(5*2) isn't that large a number, it seems like you
can just brute force this one. Yeah, it's 125 million possible
expressions, but lots of them are invalid. If you generate the list
of possible brackets first in your outer loop, you could eliminate
the invalid ones before you try all remaining 5! * 4^5 combinations
of operators and numbers, thus greatly reducing the number of
expressions you actually have to test.

- Logan
From: Gene on 16 Jun 2006 13:47
Logan Shaw wrote:
> Phil Cairns wrote:
> > My son (12 years old) came home and said that he just had a math test,
> > and the question went something like this:
> >
> > Arrange the numbers 4, 5, 6, 7 and 8 in any order, using BODMAS ordering
> > to get to 50. (BODMAS is Brackets, pOwers, Division, Multiplication,
> > Addition, Subtraction: their way of remembering operator precedence). He
> > came up with (4 + 7 x 8) / 6 * 5 in the test. I found (8 x 7) - 6 x (5 -
> > 4), and this just happens to be the numbers in reverse order. I said,
> > "Hmmm ... it should be really easy to write a program that would figure
> > out all of those combinations for you."
> > "Cool, Dad ... how would that work?"
> > "Well," I said, "you just take the first number and try adding,
> > subtracting, multiplying or dividing the rest of the numbers to get to
> > ... err ... getting confused, let me show you, son. If the first
> > operator is going to be a plus, the whole thing will be 4 + (5, 6, 7 & 8
> > arranged to be 46). Or it could be 4 - (5, 6, 7 & 8 arranged to be -54).
> > See?"
>
> The simplest way I can think of is to make a few observations:
>
> 1. The numbers can appear in any order.
> 2. Each position (space between numbers) can have any of the operators,
> and a given expression can re-use a single operator as many times
> as it wants or can use it no times at all. So it's not merely a
> matter of changing their order; you must try all possible lists
> of operators. If you have 5 operators and 5 numbers, that's 4
> possible positions for the operators, so that means 5^4 different
> lists of operators.
> 3. Open brackets can appear immediately before a number and nowhere
> else; close brackets can appear immediately after a number and
> nowhere else. So, in order to produce every set of brackets, it
> is sufficient (if not necessarily *efficient*) to treat each
> position as a bit, then go through all possible bit strings,
> inserting a bracket if the bit is 1, or leaving out the bracket
> if it's not. This will yield some strings which are syntactically
> invalid, but you can toss those out easily enough.
>
> Once you have all the possible lists of brackets, all the possible
> orders of the numbers, and all the possible lists of operators, if
> you cross these together, you get all possible legal expressions.
> Then it's just a matter of finding one (or all the ones) that evaluate
> to the appropriate value.
>
> Evaluating is a bit irritating, but maybe not that bad. Since this is
> infix, you'd think you need to consider the precedence rules, but
> actually you don't: since we've already established that you can
> generate all possible valid sequences of brackets, you can toss out
> precedence rules, merely evaluate left to right, and be sure that
> if a non-left-to-right order expression is needed, it will be found
> since you will be generating the fully parenthesized version.
>
> Since 5! * 4^5 * 2^(5*2) isn't that large a number, it seems like you
> can just brute force this one. Yeah, it's 125 million possible
> expressions, but lots of them are invalid. If you generate the list
> of possible brackets first in your outer loop, you could eliminate
> the invalid ones before you try all remaining 5! * 4^5 combinations
> of operators and numbers, thus greatly reducing the number of
> expressions you actually have to test.
>
> - Logan

Right. A more conventional way to say this is enumerate all the
expression trees with leaves 4,5,6,7,8. Evaluate them and print the
ones with value 50.

Coding this is interesting because enumeratinging trees, evaluating
them, and printing them as infix don't combine in an obvious way.

From: Gerry Quinn on 17 Jun 2006 11:08
In article <slrne92naq.9n2.willem(a)turtle.stack.nl>, willem(a)stack.nl
says...

> The way I did this is to change to RPN (Reverse Polish Notation),
> which eliminates the brackets entirely.

To put it another way, the brackets and precedence rules are
collectively a herring, because the brackets exist only for the purpose
of rendering the precedence irrelevant.

- Gerry Quinn
First  |  Prev  | 
Pages: 1 2
Prev: doubly linked list
Next: van Emde Boas tree implementation