Interesting math problem

[Nikos Chantziaras]

I've recently came across a math puzzle. This:

2 / 2 - 3 / 3 - 4 / 4 - 5 / 5

evaluates to -2. Now the puzzle is to place parentheses in such a way
so that it will evaluate to something > 49. It's a nice puzzle, and
after a bit of trial and error, I arrived at:

(2 / ((2 - 3) / 3) - 4) / ((4 - 5) / 5)

which evaluates to 50. Puzzle solved.

But this got me thinking about brute forcing all the combinations in a C
program. I'm not even sure where to begin with this. Actual evaluation
would probably complicate things. So maybe it's doable by playing
around with the actual string and outputing the combinations in order to
pipe them to a program that would then do the actual evaluation.

Any ideas of how this could be done?

 

[Ben Bacarisse]

I've recently came across a math puzzle. This:

2 / 2 - 3 / 3 - 4 / 4 - 5 / 5

evaluates to -2. Now the puzzle is to place parentheses in such a way
so that it will evaluate to something > 49. It's a nice puzzle, and
after a bit of trial and error, I arrived at:

(2 / ((2 - 3) / 3) - 4) / ((4 - 5) / 5)

which evaluates to 50. Puzzle solved.

But this got me thinking about brute forcing all the combinations in a
C program. I'm not even sure where to begin with this. Actual
evaluation would probably complicate things. So maybe it's doable by
playing around with the actual string and outputing the combinations
in order to pipe them to a program that would then do the actual
evaluation.

Any ideas of how this could be done?

I would not use the string representation. I'd have the program
manipulate a tree representing the expression. I have not thought it
though, but it seems at first glance to be less effort than messing
with a string and a pipe (the evaluation of such a tree is very
simple).

 

[user923005]

I've recently came across a math puzzle.  This:

   2 / 2 - 3 / 3 - 4 / 4 - 5 / 5

evaluates to -2.  Now the puzzle is to place parentheses in such a way
so that it will evaluate to something > 49.  It's a nice puzzle, and
after a bit of trial and error, I arrived at:

   (2 / ((2 - 3) / 3) - 4) / ((4 - 5) / 5)

which evaluates to 50.  Puzzle solved.

But this got me thinking about brute forcing all the combinations in a C
program.  I'm not even sure where to begin with this.  Actual evaluation
would probably complicate things.  So maybe it's doable by playing
around with the actual string and outputing the combinations in order to
pipe them to a program that would then do the actual evaluation.

Any ideas of how this could be done?

Write a program that writes a program.

 

[Paul Hsieh]

I've recently came across a math puzzle.  This:

   2 / 2 - 3 / 3 - 4 / 4 - 5 / 5

evaluates to -2.  Now the puzzle is to place parentheses in such a way
so that it will evaluate to something > 49.  It's a nice puzzle, and
after a bit of trial and error, I arrived at:

   (2 / ((2 - 3) / 3) - 4) / ((4 - 5) / 5)

which evaluates to 50.  Puzzle solved.

But this got me thinking about brute forcing all the combinations in a C
program.  I'm not even sure where to begin with this.  Actual evaluation
would probably complicate things.

Such evaluators are actually interesting to write and I would
recommend doing so for a case like this.

[...] So maybe it's doable by playing
around with the actual string and outputing the combinations in order to
pipe them to a program that would then do the actual evaluation.

There is no need to "pipe around" at the OS level. Just maintain an
internal "string" and pass it around directly.

Any ideas of how this could be done?

Ben Bacarisse is recommending that you somehow throw it into a tree
structure to begin with and manipulate the tree directly and avoid
string manipulation, however, I don't see what exactly this
accomplishes. I don't know how you can know for sure that you are
trying every possible parse tree, for example.

I would rather suggest you have a middle ground between string and
trees as follows: Make an array of parentheses counts which
represents the number of parentheses (either opening or closing)
between each character position. Aside from this you can make a pair
of mask arrays indicating which parenthesis type can legally be placed
in each position. Now you need to write a "virtual string" parser and
evaluator that will take the string with the imaginary number of
rectangles inserted according to your original array and the actual
string in question. Personally I would also write a virtual string
"printer" so you can check and test your functions for correctness.

Then its a farily simple recursive exercise:

int insertParentheses (virtualString * vs,
int leftParenthesesLowerLimit,
int rightParenthesesUpperLimit,
int (* eval) (virtualString *, void * ctx),
void * ctx);

This function would first call eval(vs, ctx); then it would try every
possible insertion of one single parentheses pair subject to the
obvious constraints given by leftParenthesesLowerLimit and
rightParenthesesUpperLimit with the exception of the one pair of
parentheses on the very outer limits set by this constraint. You
would skip anything that you knew was illegal as dictated by the masks
like: ( / 5. For each insertion go ahead and insert the parenthesis
pair into vs (you will undo this at the end of the loop)

For each parenthesis pair (pb, pe), you now have (up to) 3 new
regions:

[leftParenthesesLowerLimit, pb]
[pb,pe]
[pe,rightParenthesesUpperLimit]

Recurse into insertParentheses with these limits except if the limits
overlap (at the same; i.e., corresponding to a sub-region of length
0). Undo the [pb,pe] insertion and continue the loop.

And that's it. The result is the eval() will be called exactly once
for every legal parenthesis combination, without redundant parentheses
calls; ie: (( .. )) . Its possible that some illegal "virtual
strings" may also be generated, but I would have to think about this
more carefully than I am willing to do so right now. Either way you
would want to check this in your eval function and just ignore
anything generated that was illegal. So in this function you can
evaluate the "virtual string" expression and print it out, or tell
when you have matched a particular value etc. If you really don't
feel like you are up to the challenge of writing an expression
evaluator then you can just write a virtual string to real string
translator and feed it to bc or whatever you have access to through
system() or popen() or whatever.

Obviously with such a method you could generalize this to any
algebraic string.

 

[Bartc]

I've recently came across a math puzzle. This:

2 / 2 - 3 / 3 - 4 / 4 - 5 / 5

evaluates to -2. Now the puzzle is to place parentheses in such a way so
that it will evaluate to something > 49. It's a nice puzzle, and after a
bit of trial and error, I arrived at:

(2 / ((2 - 3) / 3) - 4) / ((4 - 5) / 5)

which evaluates to 50. Puzzle solved.

But this got me thinking about brute forcing all the combinations in a C
program. I'm not even sure where to begin with this. Actual evaluation
would probably complicate things. So maybe it's doable by playing around
with the actual string and outputing the combinations in order to pipe
them to a program that would then do the actual evaluation.

Any ideas of how this could be done?

I found simple string manipulation worked well, although I limited it to
single digit values.

I've no idea about how to solve these things, so I just inserted random lots
of parentheses into the string, then evaluated it ( "(" goes before a digit,
")" after a digit, and keep them balanced).

You need some code to evaluate the string (making sure * / precedence is
higher than + -), and probably a more systematic way of adding parenthesis.

Even so, my random method found 4 combinations yielding 50 or more in the
first 100000 tried (the highest was 52.5).

One hint though: use an easier language than C to get the thing working.
Perhaps translate back to C in the end.

 

[Ben Bacarisse]

Ben Bacarisse is recommending that you somehow throw it into a tree
structure to begin with and manipulate the tree directly and avoid
string manipulation, however, I don't see what exactly this
accomplishes. I don't know how you can know for sure that you are
trying every possible parse tree, for example.

No, I agree. If there were a neat algorithm to iterate over the
trees, then it would pay off but I can't think of one off hand so it
does not! I'll give it some more thought, but I think a semi-textual
representation...

I would rather suggest you have a middle ground between string and
trees as follows: Make an array of parentheses counts which
represents the number of parentheses (either opening or closing)
between each character position.

.... like this is likely to be better.

 

[Kaz Kylheku]

I've recently came across a math puzzle. This:

2 / 2 - 3 / 3 - 4 / 4 - 5 / 5

evaluates to -2. Now the puzzle is to place parentheses in such a way
so that it will evaluate to something > 49. It's a nice puzzle, and
after a bit of trial and error, I arrived at:

(2 / ((2 - 3) / 3) - 4) / ((4 - 5) / 5)

which evaluates to 50. Puzzle solved.

But this got me thinking about brute forcing all the combinations in a C
program. I'm not even sure where to begin with this. Actual evaluation
would probably complicate things. So maybe it's doable by playing
around with the actual string and outputing the combinations in order to
pipe them to a program that would then do the actual evaluation.

Any ideas of how this could be done?

Here is some pseudo-code in Common Lisp syntax that just happens to work,
hinting at a possible algorithm.

These functions generate all possible formulas from a given input like

2 / 2 - 3 / 3 - 4 / 4 - 5 / 5

This is done recursively. At the top level of the recursion, we iterate over
the operator and split the formula: we want to generate all the formulas in
which the first division / is the main constituent. Then generate all the
formulas in which the first - is the main constituent and so on.

The formulas are generated as a syntax tree for which we use a prefix
representation.

The input is first simplified into two separate lists: operators and operands,
i.e.:

/ - / - / - /
2 2 3 3 4 4 5 5

So for instance if we split this on the fourth operator we end up with:

/ - / - / - /
2 2 3 3 4 4 5 5

The separation into operators and operands is not strictly necessary, but it
makes the code clearer.

First, let's define the original input as a constant:

(defconstant %problem-input% '(2 / 2 - 3 / 3 - 4 / 4 - 5 / 5))

Then here are the two functions that generate all formulas:

(defun map-all-formulas (input function)
(let ((operators (remove-if-not #'symbolp input))
(operands (remove-if-not #'numberp input)))
(map-all-formulas-canon operators operands function)))

(defun map-all-formulas-canon (operators operands function)
(cond
((null operators)
(funcall function (first operands)))
((= 1 (length operators))
(funcall function
`(,(first operators)
,(first operands)
,(second operands))))
(t
(loop for position below (length operators)
do (let ((op (nth position operators))
(left-opr (subseq operators 0 position))
(right-opr (subseq operators (1+ position)))
(left-opd (subseq operands 0 (1+ position)))
(right-opd (subseq operands (1+ position))))
(map-all-formulas-canon
left-opr left-opd
(lambda (each-left-formula)
(map-all-formulas-canon
right-opr right-opd
(lambda (each-right-formula)
(funcall function
`(,op
,each-left-formula
,each-right-formula)))))))))))

So here is a test run using CLISP, on a smaller input:

[1]> (map-all-formulas '(1 + 2 - 3 / 4 * 5) #'print)

(+ 1 (- 2 (/ 3 (* 4 5))))
(+ 1 (- 2 (* (/ 3 4) 5)))
(+ 1 (/ (- 2 3) (* 4 5)))
(+ 1 (* (- 2 (/ 3 4)) 5))
(+ 1 (* (/ (- 2 3) 4) 5))
(- (+ 1 2) (/ 3 (* 4 5)))
(- (+ 1 2) (* (/ 3 4) 5))
(/ (+ 1 (- 2 3)) (* 4 5))
(/ (- (+ 1 2) 3) (* 4 5))
(* (+ 1 (- 2 (/ 3 4))) 5)
(* (+ 1 (/ (- 2 3) 4)) 5)
(* (- (+ 1 2) (/ 3 4)) 5)
(* (/ (+ 1 (- 2 3)) 4) 5)
(* (/ (- (+ 1 2) 3) 4) 5)

We can see by inspection that it's generating the right kind of stuff.

Now solving the problem (listing all formulas that evaluate to at least 50) can
be expressed like this:

(let (list)
(map-all-formulas %problem-input%
(lambda (formula)
(ignore-errors
(when (>= (eval formula) 50)
(push formula list)))))
(reverse list))

->

((/ 2 (/ (/ (- 2 3) (- (/ (- 3 4) 4) 5)) 5))
(/ (- (/ 2 (/ (- 2 3) 3)) 4) (/ (- 4 5) 5)))

IGNORE-ERRORS is a quick and dirty way way of trapping division by zero.

So there are two. Now you just need a trivial function to print it back in
infix.

(defun to-infix (formula)
(if (atom formula)
formula
(let ((left (to-infix (second formula)))
(right (to-infix (third formula)))
(op (first formula)))
`(,left ,op ,right))))

(mapcar #'to-infix '((/ 2 (/ (/ (- 2 3) (- (/ (- 3 4) 4) 5)) 5))
(/ (- (/ 2 (/ (- 2 3) 3)) 4) (/ (- 4 5) 5))))

->

((2 / (((2 - 3) / (((3 - 4) / 4) - 5)) / 5))
(((2 / ((2 - 3) / 3)) - 4) / ((4 - 5) / 5)))

The second element of the list coincides with your solution:

(2 / ((2 - 3) / 3) - 4) / ((4 - 5) / 5)

I'm not sure there is anything interesting about doing this sort of thing in C.
Most of the solution would have to do with representing the problem at a very
low level and correctly managing the resources of the machine.

Even the Lisp is irksomely boring.

For instance we could write C that does it similarly to the above algortihm.
Define a tree structure for representing expressions, parse the input into a
list of symbols, then generate different shapes of trees, pass them through an
evaluate function, etc.

In a C program, I would focus on just solving the problem. Don't develop
anything fancy, like the ability to actually generate all the formulas and map
them through an arbitrary function. The recursion can be roughly the same, but
its fundamental step is to find all /evaluations/ of the subformula.

We can use simple arrays to represent the operators and operands, and integer
indices to select slices of these arrays to represent subformulas.

here goes!

#include <stdio.h>
#include <limits.h>
#include <float.h>
#include <assert.h>

#define ERR_VALUE DBL_MIN

#define array_elems(X) (sizeof (X) / sizeof (X)[0])

typedef struct context {
char *opr;
double *opd;
int from, to;
void (*fun)(struct context *);
char formula_text[512];
double formula_value;
struct context *right;
struct context *left;
struct context *up;
} context;

double eval_op(char op, double left, double right)
{
if (left == ERR_VALUE || right == ERR_VALUE)
return ERR_VALUE;

/* TODO: add overflow checks, not just division by zero */
switch (op) {
case '+':
return left + right;
break;
case '-':
return left - right;
break;
case '*':
return left * right;
break;
case '/':
if (right == 0)
return ERR_VALUE;
return left / right;
break;
}

return ERR_VALUE;
}

static void trampoline_right(context *);
static void trampoline_left(context *);

void evaluate_all(context *pctx)
{
int from = pctx->from;
int to = pctx->to;
int num = pctx->to - pctx->from, i;

switch (num) {
case 0:
sprintf(pctx->formula_text, "%g", pctx->opd[from]);
pctx->formula_value = pctx->opd[from];
pctx->fun(pctx);
break;
case 1:
sprintf(pctx->formula_text, "(%g %c %g)",
pctx->opd[from], pctx->opr[from],
pctx->opd[from+1]);
pctx->formula_value = eval_op(pctx->opr[from],
pctx->opd[from],
pctx->opd[from+1]);
pctx->fun(pctx);
break;
default:
for (i = from; i < to; i++) {
context ctx_left = { 0 };
context ctx_right = { 0 };

ctx_left.opr = ctx_right.opr = pctx->opr;
ctx_left.opd = ctx_right.opd = pctx->opd;
ctx_left.from = from;
ctx_left.to = i;
ctx_left.fun = trampoline_left;
ctx_left.left = 0;
ctx_left.right = &ctx_right;
ctx_left.up = pctx;
ctx_right.from = i + 1;
ctx_right.to = to;
ctx_right.fun = trampoline_right;
ctx_right.left = &ctx_left;
ctx_right.right = 0;
ctx_right.up = pctx;

evaluate_all(&ctx_left);
}
}
}

void trampoline_left(context *left)
{
evaluate_all(left->right);
}

void trampoline_right(context *right)
{
context *up = right->up;
char op = right->opr[right->from - 1];

sprintf(up->formula_text, "(%s %c %s)",
right->left->formula_text, op,
right->formula_text);

up->formula_value = eval_op(op,
right->left->formula_value,
right->formula_value);

up->fun(up);
}

void print_over_49(context *pctx)
{
if (pctx->formula_value > 49)
printf("%s = %g\n", pctx->formula_text, pctx->formula_value);
}

int main(void)
{
double problem_operands[] = {
2, 2, 3, 3, 4, 4, 5, 5
};

char problem_operators[] = {
'/', '-', '/', '-', '/', '-', '/'
};

context ctx = { 0 };

ctx.opr = problem_operators;
ctx.opd = problem_operands;
ctx.from = 0;
ctx.to = array_elems(problem_operators);
ctx.fun = print_over_49;

evaluate_all(&ctx);
return 0;
}

Cheers ...

 

[Kaz Kylheku]

We can see by inspection that it's generating the right kind of stuff.

Now solving the problem (listing all formulas that evaluate to at least 50)
can be expressed like this:

(let (list)
(map-all-formulas %problem-input%
(lambda (formula)
(ignore-errors
(when (>= (eval formula) 50)
(push formula list)))))
(reverse list))

That's incorrect because the problem specification is > 49, not >= 50. The
values are rational, not integral. It happens not to make a difference because
there are no values in the interval (49,50).

 

[Phil Carmody]

I've recently came across a math puzzle. This:

2 / 2 - 3 / 3 - 4 / 4 - 5 / 5

evaluates to -2. Now the puzzle is to place parentheses in such a way
so that it will evaluate to something > 49. It's a nice puzzle, and
after a bit of trial and error, I arrived at:

(2 / ((2 - 3) / 3) - 4) / ((4 - 5) / 5)

which evaluates to 50. Puzzle solved.

But this got me thinking about brute forcing all the combinations in a
C program. I'm not even sure where to begin with this. Actual
evaluation would probably complicate things. So maybe it's doable by
playing around with the actual string and outputing the combinations
in order to pipe them to a program that would then do the actual
evaluation.

Any ideas of how this could be done?

Pretty much the same in any language. C's mostly irrelevant to
the question.

I'd stick the numbers and operators into a single array,
alternating, and define an expression to be an odd length
sub-array starting on a number. I'd then have a function
which could be asked to find extremal (which extremum
would be defined by a parameter) values of such expressions.

Something not dissimilar to:
double findExtremum(int const *expr, int length, int which);

For an expression of length 1, the value is returned
immediately. Otherwise this function would walk through
the odd-indexed elements of expr, namely the operators,
and recurse on the left and right subarrays, making sure
it passed sensible choices for the extremum type.
E.g. If you're looking for a positive maximum, and are on
a '+' operator (I'm thinking of a generalisation of the
puzzle, not this specific instance), then look for positive
maxima of both the left and the right subarrays, but if
you're looking at a '-', then you want a maximum for the
left, and a minimum for the right. '*' (again unused in
this particular puzzle) and '/' leave you with _two_
possibly optimal choices, so you must recurse twice, and
then compare the two results. Once you've walked through
all operators, return the one which gave you the correct
extremum.

Actaully generating the algebraic expression which evaluates
to the required maxima is left as an exercise to the reader,
but you will need to pass more information back out from
each function call.

Phil

 

[Larry Gates]

Pretty much the same in any language. C's mostly irrelevant to
the question.

By that, do you mean clc is mostly irrelevant, because The Topic can't
produce something useful?

I'd certainly like to see the syntax that solves the question at hand.

I can't decide if 5**8 is a large number. I guess it's less than 10^8, so
it's shy of combinatorial size.

 

[Fred]

I've recently came across a math puzzle.  This:

   2 / 2 - 3 / 3 - 4 / 4 - 5 / 5

evaluates to -2.  Now the puzzle is to place parentheses in such a way
so that it will evaluate to something > 49.  It's a nice puzzle, and
after a bit of trial and error, I arrived at:

   (2 / ((2 - 3) / 3) - 4) / ((4 - 5) / 5)

which evaluates to 50.  Puzzle solved.

Wrong.

((4 - 5) / 5)
resolves to zero using any C compiler.
So the expression results in a divide by zero.

 

[Bartc]

Wrong.

((4 - 5) / 5)
resolves to zero using any C compiler.
So the expression results in a divide by zero.

Which C compiler do you have that accepts that expression as it is?

Since the OP says 50, we have to assume he's talking about everyday (not C)
arithmetic, and that the expression is /data/ for a C program rather than C
source.

 

[Richard Tobin]

((4 - 5) / 5)
resolves to zero using any C compiler.

Only guaranteed since C99.

-- Richard

 

[Keith Thompson]

Only guaranteed since C99.

Oh? What C99 change are you thinking of? The behavior of integer
division for non-negative operands hasn't changed as far as I know;
1/5 == 0, and has been since time immemorial.

 

[Ralf Damaschke]

Oh? What C99 change are you thinking of? The behavior of integer
division for non-negative operands hasn't changed as far as I know;
1/5 == 0, and has been since time immemorial.

Absolutely. But somehow you failed to realize that one operand in
((4 - 5) / 5) is not non-negative.

-- Ralf

 

[Antoninus Twink]

Oh? What C99 change are you thinking of? The behavior of integer
division for non-negative operands hasn't changed as far as I know;
1/5 == 0, and has been since time immemorial.

(4 - 5) isn't nonnegative, Keith.

 

[Keith Thompson]

Absolutely. But somehow you failed to realize that one operand in
((4 - 5) / 5) is not non-negative.

(Uncrossing eyes.) Yeah, you're right. *blush*

 

[Paul Hsieh]

No, I agree.  If there were a neat algorithm to iterate over the
trees, then it would pay off but I can't think of one off hand so it
does not!  I'll give it some more thought, but I think a semi-textual
representation...


... like this is likely to be better.

Well its easier to implement, but also just as easy to go astray. If
you look at my solution carefully its actually wrong. It does the
equivalent of a depth-first search, which is actually not nearly
sufficient. So I think the right way to do this is to iterate over a
"next left-most parentheses lower bound" index, and explicitly avoid
redundant parentheses. So the idea is that you would loop over every
possible left position of the next newest left-most parentheses pair
and set it as the recursive lower bound, but avoid (( .. )) .

Interesting that nobody caught my error. Probably they are still
searching for it in the C standard documentation somewhere ...

Seriously though, more than likely there is a direct way of
translating these extra parentheses into tree rotations or something
meaning there is probably a way of doing this with a direct tree
manipulation, but its just not intuitive.

 

[Ben Bacarisse]

Well its easier to implement, but also just as easy to go astray. If
you look at my solution carefully its actually wrong. It does the
equivalent of a depth-first search, which is actually not nearly
sufficient. So I think the right way to do this is to iterate over a
"next left-most parentheses lower bound" index, and explicitly avoid
redundant parentheses. So the idea is that you would loop over every
possible left position of the next newest left-most parentheses pair
and set it as the recursive lower bound, but avoid (( .. )) .

Interesting that nobody caught my error. Probably they are still
searching for it in the C standard documentation somewhere ...

I did not because I did not want to look at you method before I'd had
a go at a tree-based version.

Seriously though, more than likely there is a direct way of
translating these extra parentheses into tree rotations or something
meaning there is probably a way of doing this with a direct tree
manipulation, but its just not intuitive.

Yes there probably is, but it has eluded me so far. Time to look in
some books!

 

[Tim Rentsch]

I did not because I did not want to look at you method before I'd had
a go at a tree-based version.


Yes there probably is, but it has eluded me so far. Time to look in
some books!

I wrote a simple program in prolog that turns "expression"
lists into trees (in the non-deterministic prolog style)
and then evaluates the trees to yield a value.
The simple version worked okay on small examples,
but on larger examples I had to write the evaluator
to do fractional arithmetic, because using straight
floating-point I was getting horrible cancellation
errors (producing values like 5e18).

Note that I didn't try to manipulate one tree into
the next, just produced all trees (in sequence) from
the original list.

Disclaimer: I completely skipped any input routines,
by putting the examples in directly as prolog lists,
e.g.,

[2,div,2,minus,3,div,3,minus,4,div,4,minus,5,div,5]

Result, after granting disclaimer: the whole program
was 34 lines of code, including the routines that
do (very simple-minded) fractional arithmetic.

Will I post the program? No, let's leave this one
as an exercise for the reader.