I've recently came across amathpuzzle. 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 anythinginterestingabout 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;
}
