Getting to a number from a sequence [General Programming]

Prev: doubly linked list
Next: van Emde Boas tree implementation

From: Phil Cairns on 15 Jun 2006 06:41

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?"

And then I wandered off to write this code. Given this
(mis)preconception, LISP or Prolog would have been the choice, but I
started in C++ because it's what I know and use at work. It was going to
be beautiful. Right up until I thought about the brackets. Suddenly my
std::list<double> and a bit of recursion just wasn't enough. Even mixing
up multiplication/division and addition/subtraction was going to play
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. :)

There has to be a nice way of doing this, and over the next couple of
years, I might think about it every now and then. One day, I'll show him
a solution (if he doesn't beat me to it). In the meantime, if anyone
wants to take this problem as their own, feel free ... I'm willing to
share :)

Phil.

From: Bart on 15 Jun 2006 07:48

Phil Cairns 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."
....
>There has to be a nice way of doing this, and over the next couple of
> years, I might think about it every now and then. One day, I'll show him
> a solution (if he doesn't beat me to it). In the meantime, if anyone
> wants to take this problem as their own, feel free ... I'm willing to
> share :)

The "Countdown" TV game show in the UK has a round where contestants
have to arrange up to 6 numbers to form a target 100 to 999, using the
same constraints except no Power and no fractions or decimals.

I did write a program to achieve this, so it's quite possible, but you
might note:

* Not all targets can be achieved
* In this version, not all numbers need be used
* It comes down to finding all ways of arranging the numbers in a
binary tree, with an operator (+ - * /) at each fork. Evaulate the tree
at each iteration and jump out at the first correct result.
* I found it easier to have 2 versions of the minus "-" operator, so
that A op B would be either A-B (as normal) or B-A. And the same for
divide "/".
* Finding the *simplest* solution is somewhat more difficult.

Bart

From: Willem on 15 Jun 2006 09:15

Phil 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?"
)
) And then I wandered off to write this code. Given this
) (mis)preconception, LISP or Prolog would have been the choice, but I
) started in C++ because it's what I know and use at work. It was going to
) be beautiful. Right up until I thought about the brackets. Suddenly my
) std::list<double> and a bit of recursion just wasn't enough. Even mixing
) up multiplication/division and addition/subtraction was going to play
) 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. :)
)
) There has to be a nice way of doing this, and over the next couple of
) years, I might think about it every now and then. One day, I'll show him
) a solution (if he doesn't beat me to it). In the meantime, if anyone
) wants to take this problem as their own, feel free ... I'm willing to
) share :)

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

Then, all you need is to generate all valid(*) orderings of N numbers
and N-1 operators, and check what they evaluate to.

for example:
(4 + 7 x 8) / 6 x 5 becomes 4 7 8 x + 6 5 x /
(8 x 7) - 6 x (5 - 4) becomes 8 7 x 6 5 4 - x -

*) To keep track of validity, simply make sure that at every step, you have
more numbers than operators. At the end you should have exactly one more.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

From: gw7rib on 15 Jun 2006 09:21

From: mensanator@aol.com on 15 Jun 2006 14:16

Willem wrote:
> Phil 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?"
> )
> ) And then I wandered off to write this code. Given this
> ) (mis)preconception, LISP or Prolog would have been the choice, but I
> ) started in C++ because it's what I know and use at work. It was going to
> ) be beautiful. Right up until I thought about the brackets. Suddenly my
> ) std::list<double> and a bit of recursion just wasn't enough. Even mixing
> ) up multiplication/division and addition/subtraction was going to play
> ) 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. :)
> )
> ) There has to be a nice way of doing this, and over the next couple of
> ) years, I might think about it every now and then. One day, I'll show him
> ) a solution (if he doesn't beat me to it). In the meantime, if anyone
> ) wants to take this problem as their own, feel free ... I'm willing to
> ) share :)
>
> The way I did this is to change to RPN (Reverse Polish Notation),
> which eliminates the brackets entirely.

Although for this problem, there are plenty of solutions that
don't require brackets:

ans = 4.0 + 5.0 + 6.0 * 8.0 - 7.0 = 50.0
ans = 4.0 + 5.0 - 7.0 + 6.0 * 8.0 = 50.0
ans = 4.0 + 5.0 - 7.0 + 8.0 * 6.0 = 50.0
ans = 4.0 + 5.0 + 8.0 * 6.0 - 7.0 = 50.0
ans = 4.0 + 6.0 * 8.0 + 5.0 - 7.0 = 50.0
ans = 4.0 + 6.0 * 8.0 - 7.0 + 5.0 = 50.0
ans = 4.0 - 7.0 + 5.0 + 6.0 * 8.0 = 50.0
ans = 4.0 * 7.0 + 5.0 * 6.0 - 8.0 = 50.0
ans = 4.0 - 7.0 + 5.0 + 8.0 * 6.0 = 50.0
ans = 4.0 * 7.0 + 6.0 * 5.0 - 8.0 = 50.0
ans = 4.0 - 7.0 + 6.0 * 8.0 + 5.0 = 50.0
ans = 4.0 * 7.0 - 8.0 + 5.0 * 6.0 = 50.0
ans = 4.0 - 7.0 + 8.0 * 6.0 + 5.0 = 50.0
ans = 4.0 * 7.0 - 8.0 + 6.0 * 5.0 = 50.0
ans = 4.0 * 8.0 + 5.0 + 6.0 + 7.0 = 50.0
ans = 4.0 * 8.0 + 5.0 + 7.0 + 6.0 = 50.0
ans = 4.0 + 8.0 * 6.0 + 5.0 - 7.0 = 50.0
ans = 4.0 * 8.0 + 6.0 + 5.0 + 7.0 = 50.0
ans = 4.0 + 8.0 * 6.0 - 7.0 + 5.0 = 50.0
ans = 4.0 * 8.0 + 6.0 + 7.0 + 5.0 = 50.0
ans = 4.0 * 8.0 + 7.0 + 5.0 + 6.0 = 50.0
ans = 4.0 * 8.0 + 7.0 + 6.0 + 5.0 = 50.0
ans = 5.0 + 4.0 + 6.0 * 8.0 - 7.0 = 50.0
ans = 5.0 + 4.0 - 7.0 + 6.0 * 8.0 = 50.0
ans = 5.0 + 4.0 - 7.0 + 8.0 * 6.0 = 50.0
ans = 5.0 + 4.0 + 8.0 * 6.0 - 7.0 = 50.0
ans = 5.0 + 4.0 * 8.0 + 6.0 + 7.0 = 50.0
ans = 5.0 + 4.0 * 8.0 + 7.0 + 6.0 = 50.0
ans = 5.0 * 6.0 + 4.0 * 7.0 - 8.0 = 50.0
ans = 5.0 + 6.0 + 4.0 * 8.0 + 7.0 = 50.0
ans = 5.0 + 6.0 + 7.0 + 4.0 * 8.0 = 50.0
ans = 5.0 * 6.0 + 7.0 * 4.0 - 8.0 = 50.0
ans = 5.0 + 6.0 + 7.0 + 8.0 * 4.0 = 50.0
ans = 5.0 + 6.0 + 8.0 * 4.0 + 7.0 = 50.0
ans = 5.0 + 6.0 * 8.0 + 4.0 - 7.0 = 50.0
ans = 5.0 * 6.0 - 8.0 + 4.0 * 7.0 = 50.0
ans = 5.0 + 6.0 * 8.0 - 7.0 + 4.0 = 50.0
ans = 5.0 * 6.0 - 8.0 + 7.0 * 4.0 = 50.0
ans = 5.0 - 7.0 + 4.0 + 6.0 * 8.0 = 50.0
ans = 5.0 + 7.0 + 4.0 * 8.0 + 6.0 = 50.0
ans = 5.0 - 7.0 + 4.0 + 8.0 * 6.0 = 50.0
ans = 5.0 + 7.0 + 6.0 + 4.0 * 8.0 = 50.0
ans = 5.0 + 7.0 + 6.0 + 8.0 * 4.0 = 50.0
ans = 5.0 - 7.0 + 6.0 * 8.0 + 4.0 = 50.0
ans = 5.0 + 7.0 + 8.0 * 4.0 + 6.0 = 50.0
ans = 5.0 - 7.0 + 8.0 * 6.0 + 4.0 = 50.0
ans = 5.0 + 8.0 * 4.0 + 6.0 + 7.0 = 50.0
ans = 5.0 + 8.0 * 4.0 + 7.0 + 6.0 = 50.0
ans = 5.0 + 8.0 * 6.0 + 4.0 - 7.0 = 50.0
ans = 5.0 + 8.0 * 6.0 - 7.0 + 4.0 = 50.0
ans = 6.0 + 4.0 * 8.0 + 5.0 + 7.0 = 50.0
ans = 6.0 + 4.0 * 8.0 + 7.0 + 5.0 = 50.0
ans = 6.0 * 5.0 + 4.0 * 7.0 - 8.0 = 50.0
ans = 6.0 + 5.0 + 4.0 * 8.0 + 7.0 = 50.0
ans = 6.0 + 5.0 + 7.0 + 4.0 * 8.0 = 50.0
ans = 6.0 * 5.0 + 7.0 * 4.0 - 8.0 = 50.0
ans = 6.0 + 5.0 + 7.0 + 8.0 * 4.0 = 50.0
ans = 6.0 + 5.0 + 8.0 * 4.0 + 7.0 = 50.0
ans = 6.0 * 5.0 - 8.0 + 4.0 * 7.0 = 50.0
ans = 6.0 * 5.0 - 8.0 + 7.0 * 4.0 = 50.0
ans = 6.0 + 7.0 + 4.0 * 8.0 + 5.0 = 50.0
ans = 6.0 + 7.0 + 5.0 + 4.0 * 8.0 = 50.0
ans = 6.0 + 7.0 + 5.0 + 8.0 * 4.0 = 50.0
ans = 6.0 + 7.0 + 8.0 * 4.0 + 5.0 = 50.0
ans = 6.0 + 8.0 * 4.0 + 5.0 + 7.0 = 50.0
ans = 6.0 * 8.0 + 4.0 + 5.0 - 7.0 = 50.0
ans = 6.0 + 8.0 * 4.0 + 7.0 + 5.0 = 50.0
ans = 6.0 * 8.0 + 4.0 - 7.0 + 5.0 = 50.0
ans = 6.0 * 8.0 + 5.0 + 4.0 - 7.0 = 50.0
ans = 6.0 * 8.0 + 5.0 - 7.0 + 4.0 = 50.0
ans = 6.0 * 8.0 - 7.0 + 4.0 + 5.0 = 50.0
ans = 6.0 * 8.0 - 7.0 + 5.0 + 4.0 = 50.0
ans = 7.0 * 4.0 + 5.0 * 6.0 - 8.0 = 50.0
ans = 7.0 * 4.0 + 6.0 * 5.0 - 8.0 = 50.0
ans = 7.0 + 4.0 * 8.0 + 5.0 + 6.0 = 50.0
ans = 7.0 * 4.0 - 8.0 + 5.0 * 6.0 = 50.0
ans = 7.0 + 4.0 * 8.0 + 6.0 + 5.0 = 50.0
ans = 7.0 * 4.0 - 8.0 + 6.0 * 5.0 = 50.0
ans = 7.0 + 5.0 + 4.0 * 8.0 + 6.0 = 50.0
ans = 7.0 + 5.0 + 6.0 + 4.0 * 8.0 = 50.0
ans = 7.0 + 5.0 + 6.0 + 8.0 * 4.0 = 50.0
ans = 7.0 + 5.0 + 8.0 * 4.0 + 6.0 = 50.0
ans = 7.0 + 6.0 + 4.0 * 8.0 + 5.0 = 50.0
ans = 7.0 + 6.0 + 5.0 + 4.0 * 8.0 = 50.0
ans = 7.0 + 6.0 + 5.0 + 8.0 * 4.0 = 50.0
ans = 7.0 + 6.0 + 8.0 * 4.0 + 5.0 = 50.0
ans = 7.0 + 8.0 * 4.0 + 5.0 + 6.0 = 50.0
ans = 7.0 + 8.0 * 4.0 + 6.0 + 5.0 = 50.0
ans = 8.0 * 4.0 + 5.0 + 6.0 + 7.0 = 50.0
ans = 8.0 * 4.0 + 5.0 + 7.0 + 6.0 = 50.0
ans = 8.0 * 4.0 + 6.0 + 5.0 + 7.0 = 50.0
ans = 8.0 * 4.0 + 6.0 + 7.0 + 5.0 = 50.0
ans = 8.0 * 4.0 + 7.0 + 5.0 + 6.0 = 50.0
ans = 8.0 * 4.0 + 7.0 + 6.0 + 5.0 = 50.0
ans = 8.0 * 6.0 + 4.0 + 5.0 - 7.0 = 50.0
ans = 8.0 * 6.0 + 4.0 - 7.0 + 5.0 = 50.0
ans = 8.0 * 6.0 + 5.0 + 4.0 - 7.0 = 50.0
ans = 8.0 * 6.0 + 5.0 - 7.0 + 4.0 = 50.0
ans = 8.0 * 6.0 - 7.0 + 4.0 + 5.0 = 50.0
ans = 8.0 * 6.0 - 7.0 + 5.0 + 4.0 = 50.0

>
> Then, all you need is to generate all valid(*) orderings of N numbers
> and N-1 operators, and check what they evaluate to.
>
> for example:
> (4 + 7 x 8) / 6 x 5 becomes 4 7 8 x + 6 5 x /
> (8 x 7) - 6 x (5 - 4) becomes 8 7 x 6 5 4 - x -
>
>
> *) To keep track of validity, simply make sure that at every step, you have
> more numbers than operators. At the end you should have exactly one more.
>
>
> SaSW, Willem
> --
> Disclaimer: I am in no way responsible for any of the statements
> made in the above text. For all I know I might be
> drugged or something..
> No I'm not paranoid. You all think I'm paranoid, don't you !
> #EOT

| Next | Last
Pages: 1 2
Prev: doubly linked list
Next: van Emde Boas tree implementation