Interesting math problem
Nikos Chantziaras
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 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).
--
Ben.
user923005
Write a program that writes a program.
Paul Hsieh
>
> 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.
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
christian.bau
You have eight numbers, separated by seven operators.
One of the operators has to be evaluated first. There are seven
choices, each leaving you with 7 numbers and six operators.
One of the operators has to be evaluated next. There are six choices,
each leaving you with 6 numbers and five operators.
And so on and so on.
There are 7 x 6 x 5 x 4 x 3 x 2 x 1 cases that get examined that way.
Many of those cases will give identical results, but with only 40,000
cases I wouldn't worry about that. Once you have the order of
evaluations giving the largest result, you can then put in the
parentheses accordingly. Probably easier to do by hand than writing a
program.
Bartc
"Nikos Chantziaras" <rea...@arcor.de> wrote in message
news:go4du9$sai$1...@volcano1.grnet.gr...
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.
--
Bartc
Ben Bacarisse
> On Feb 25, 1:41 pm, Nikos Chantziaras <rea...@arcor.de> wrote:
>> 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.
<snip>
> 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.
--
Ben.
Jujitsu Lizard
news:87bpsq3...@bsb.me.uk...
Correct.
The problem is inherently a tree problem. All the operators are binary, so
any tree you build will be a binary tree (each node has two children).
I think it comes down to the question of how many binary trees you can build
that when they are traversed give the order 2/2-3/3-...
And now, brace yourself ...
The closed form and decisive answer to this problem is ...
.
.
.
.
.
scroll down more
.
.
.
.
.
.
and the answer is ... post it to sci.math.
The Lizard.
Kaz Kylheku
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
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
--
I tried the Vista speech recognition by running the tutorial. I was
amazed, it was awesome, recognised every word I said. Then I said the
wrong word ... and it typed the right one. It was actually just
detecting a sound and printing the expected word! -- pbhj on /.
blargg
[...]
> 2 / 2 - 3 / 3 - 4 / 4 - 5 / 5
> to something > 49 [...] 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 C program to generate another C program that tries the above
expression with all possible parenthesis groupings. Run said program and
get result. This leverages the one thing we can assume you know: C. It
leaves all the heavy-lifting to the compiler.
Larry Gates
>> Any ideas of how this could be done?
>
> 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.
--
larry gates
"Help save the world!" -- Larry Wall in README
Fred
>
> 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.
--
Fred K
Bartc
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.
--
Bartc
Richard Tobin
Fred <fred.l.kl...@boeing.com> wrote:
>((4 - 5) / 5)
>resolves to zero using any C compiler.
Only guaranteed since C99.
-- Richard
--
Please remember to mention me / in tapes you leave behind.
Golden California Girls
Topicality police on this? And you all wonder why Han posts here!
Keith Thompson
> In article
> <95b9d8c1-e487-47bb...@h20g2000yqn.googlegroups.com>,
> Fred <fred.l.kl...@boeing.com> wrote:
>
>>((4 - 5) / 5)
>>resolves to zero using any C compiler.
>
> 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.
--
Keith Thompson (The_Other_Keith) k...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Ralf Damaschke
> ric...@cogsci.ed.ac.uk (Richard Tobin) writes:
>> Fred <fred.l.kl...@boeing.com> wrote:
>>
>>>((4 - 5) / 5)
>>>resolves to zero using any C compiler.
>>
>> 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.
Absolutely. But somehow you failed to realize that one operand in
((4 - 5) / 5) is not non-negative.
-- Ralf
Antoninus Twink
>>>((4 - 5) / 5)
>>>resolves to zero using any C compiler.
>>
>> 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.
(4 - 5) isn't nonnegative, Keith.
Keith Thompson
(Uncrossing eyes.) Yeah, you're right. *blush*
Paul Hsieh
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
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!
--
Ben.
Tim Rentsch
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. :)
Nikos Chantziaras
> On 2009-02-25, Nikos Chantziaras <rea...@arcor.de> wrote:
>> 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.
That's very interesting. I actually didn't even think about using
another language and then "translate" to C. Probably because I'm not
familiar with functional languages :P
> These functions generate all possible formulas from a given input like
>
> 2 / 2 - 3 / 3 - 4 / 4 - 5 / 5
>
> This is done recursively. [...]
>
> 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)))
I must admit I wouldn't even know how to read this. But from the little
I know about Lisp, it seems it feels more "at home" than C does in this
particular case.
> 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.
> [...]
> 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.
I'll have to gnaw a bit on the C version. Did you use some "Lisp to C"
tool to get an initial version in C or is this from scratch?
nick_keigh...@hotmail.com
> Kaz Kylheku wrote:
> > On 2009-02-25, Nikos Chantziaras <rea...@arcor.de> wrote:
<snip>
> > Here is some pseudo-code in Common Lisp syntax that just happens to work,
> > hinting at a possible algorithm.
>
> That's very interesting. I actually didn't even think about using
> another language and then "translate" to C.
learning another language (with a different "paradigm") can be
enlightening
> Probably because I'm not familiar with functional languages :P
Lisp is also good at symbol manipulation, which seems to suit this
problem.
> > These functions generate all possible formulas from a given input like
>
> > 2 / 2 - 3 / 3 - 4 / 4 - 5 / 5
>
> > This is done recursively. [...]
>
> > 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)))
>
> I must admit I wouldn't even know how to read this. But from the little
> I know about Lisp, it seems it feels more "at home" than C does in this
> particular case.
DEFINE FUNCTION map-all-formulae (input function)
operators := remove non-symbols from input
operands := remove non-numbers from input
map-all-formulae-canon (operators operands function)
END FUNC
<snip>
> I'll have to gnaw a bit on the C version. Did you use some "Lisp to C"
> tool to get an initial version in C or is this from scratch
looking at where Kaz posts he probably has one in his head...
--
Nick Keighley
Egon: Try to imagine all life as you know it stopping instantaneously
and every molecule in your body exploding at the speed of light.
Ray: Total protonic reversal....
(Ghost Busters encounter Undefined Behaviour)
nick_keigh...@hotmail.com
Kaz Kylheku
> That's very interesting. I actually didn't even think about using
> another language and then "translate" to C. Probably because I'm not
> familiar with functional languages :P
Solving it one language where it's relatively easy (no distracting low-level
representational or referential issues) lets you verify the sanity of a an
approach. Once you have the confidence that the algorithm is right, it's easier
to re-code it in other languages. It would be foolish to do the exploratory
programming in C, because the cost of re-shaping the program is too high.
Note that the problem couldn't be solved in exactly the Lisp way in actual
functional languages like Haskell, because they are typically statically typed,
and not homoiconic. The Lisp code builds up heterogeneous lists (lists
containing other lists, symbols and numbers) and these serve as Lisp code.
You might want to post your puzzle to comp.lang.functional if you are curious.
> I'll have to gnaw a bit on the C version. Did you use some "Lisp to C"
> tool to get an initial version in C or is this from scratch?
No, it's from scratch. I don't think such a tool would help; there likely
wouldn't be anything in its output that I could use. :)
I hadn't intended to stuff all of the function parameters into a context
structure, nor to mimic the Lisp program's recursive structure and use of
closures quite that closely, but it turned out that way during incremental
development and debugging.
Basically the trampoline_left and trampoline_right are like the lambda's in the
Lisp program. Because they are (of necessity) named functions defined at file
scope, explicit link pointers (left, right, up) are used to gain access to the
parent frames, whereas in the Lisp the functions are nested, so everything
the need to access is reachabel via a straightforward lexical reference.
Richard Bos
> And you all wonder why Han posts here!
Oh, I don't think anyone could be in doubt on that subject.
Richard
Keith Thompson
I have no idea why Han posts here, nor do I care.
Kenny McCormack
Keith Thompson <ks...@mib.org> wrote:
>ral...@xs4all.nl (Richard Bos) writes:
>> Golden California Girls <gldnc...@aol.com.mil> wrote:
>>> And you all wonder why Han posts here!
>>
>> Oh, I don't think anyone could be in doubt on that subject.
>
>I have no idea why Han posts here, nor do I care.
Yet you cared enough to post that you do not care.
Me thinks...
CBFalconer
If you precede it with:
#define three 3.0
#define five 5.0
and then write:
(2 / ((2 - three) / three) - 4) / ((4 - five) / five)
you avoid all integer arithmetic on any C compiler.
--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
Phil Carmody
> ral...@xs4all.nl (Richard Bos) writes:
>> Golden California Girls <gldnc...@aol.com.mil> wrote:
>>> And you all wonder why Han posts here!
>>
>> Oh, I don't think anyone could be in doubt on that subject.
>
> I have no idea why Han posts here, nor do I care.
I think it's to do with spare time.
Personally, mine's valuable. His is evidently not just cheap,
but, one might say, worthless.
Han from China
> Personally, mine's valuable. His is evidently not just cheap,
> but, one might say, worthless.
Bringing the pain to Gang of Three (McIntyre, Falconer, Carmody) village
idiot Phil Comedy since 2009!!!
---------------------------------------------------------------------------
Subject: Fake killfiler Phil Carmody blows his game again
Hello,
I thought after my thread "How to be a fake killfiler on comp.lang.c"
the fake killfilers would learn something. Obviously not. I quote
the relevant portion from that thread:
Third, keep your stories straight. We all know that people who announce
plonks are fake killfilers who then have to resort to piggybacking off
posts as an outlet for their psychological obsession and weakness. That's
fine, but don't contradict yourself in the process. If you're going to
complain about people replying to trolls, and if you're going to assert
that, you know, you're not *really* a technically inept idiot who doesn't
know how to set up a *proper* killfile to filter out such replies by other
people -- that, you know, your news software is limited or some shit --
then you would be wise *not* to emerge in another thread and gloat about
your ability to filter out forged posts by setting up a local news server
and performing complex regexps on header fields such as Message-ID, Path,
etc. The fake killfilers who fall into this category are Martin Ambuhl,
Phil Carmody, and James Kuyper.
True to form, Phil Carmody has blown his game yet again!
On Jan 25 in thread "Getting nanoseconds in a process", Phil Carmody
writes:
No problem. I'm a rampant killfiler, all the doofera are gone,
and so the single most annoying thing to me now is _intelligent_
people who follow up to trolls.
This would imply that Phil Carmody is technically incompetent and
doesn't know how to filter out replies to trolls.
However, on Feb 2 in thread "Gift Certificate not accepted question",
Phil Carmody offers the following:
This is a typical splashback attack. When sci.crypt was undergoing
one a year or two back I found it easiest to just killfile responses
to anonymisers as well as anonymisers, as the original piss always
comes from one. This has the added benefit of making most troll
threads completely disappear, as you don't even see those who should
know better responding to the trolls.
Conclusion: Phil Carmody is a disingenuous fake killfiler with the
IQ of a brick. The trolls win again.
---------------------------------------------------------------------------
Yours,
Han from China
--
"Only entropy comes easy." -- Anton Chekhov
Han from China
> I have no idea why Han posts here, nor do I care.
Glad you care enough to say so, Keith.
In case anyone is wondering, the reason I post here, and the reason
I'll be posting here into the distant future, is that I enjoy
making Thompson look
(1) clueless - *most recent* evidence in thread "More proof of errors
going uncorrected among the 'regs'".
(2) weak - evidence can be seen in the fact that every third post of
his mentions trolls, killfiles, ignoring (how ironic!), or some
combination thereof.
Oh, I also enjoy discussing C with people, but unfortunately for
other readers of this newsgroup, Thompson and his diminishing
gang are the gift that keeps on giving with regard to my above
hobbies.
Richard
I have never really understood the mentality of people who are "rampant
killfilers". It suggests very weak character. It is very, very rare I
have ever killfiled anyone. I kill the occasional thread such as when
Falconer is rambling on about ggets or something equally boring but
rarely posters. Somehow people manage to justify the need to kill entire
sources. It just seems rather, well, pathetic.
Kenny McCormack
Han from China <autistic...@comp.lang.c> wrote:
>Keith Thompson wrote:
>> I have no idea why Han posts here, nor do I care.
>
>Glad you care enough to say so, Keith.
>
>In case anyone is wondering, the reason I post here, and the reason
>I'll be posting here into the distant future, is that I enjoy
>making Thompson look
>
>(1) clueless - *most recent* evidence in thread "More proof of errors
>going uncorrected among the 'regs'".
>
>(2) weak - evidence can be seen in the fact that every third post of
>his mentions trolls, killfiles, ignoring (how ironic!), or some
>combination thereof.
Indeed. In fact, I think it is utterly clear to any observer, other than
Keith or the other hard-core regs, why Han posts - because it is fun and
he is enjoying himself. This is also the reason why I post.
But, what is very unclear to me is why does Keith post? He clearly
isn't having any fun (wailing on and on as he does about trolls and
killfiles, and such things). The only conclusion one can draw is that
most or all of the sad things that the "trolls" say about him and his
personal life, are true. And that, if it becomes publicly acknowledged,
will truly be sad.
Kaz Kylheku
> You have eight numbers, separated by seven operators.
> One of the operators has to be evaluated first. There are seven
> choices, each leaving you with 7 numbers and six operators.
> One of the operators has to be evaluated next. There are six choices,
> each leaving you with 6 numbers and five operators.
> And so on and so on.
>
> There are 7 x 6 x 5 x 4 x 3 x 2 x 1 cases that get examined that way.
I'm afraid this analysis is not right. This is not a straight permutation
problem. Reason being is that the operators cannot be arbitrarily reordered.
For instance, consider the smaller case of A + B * D / C. The number of
expression trees which have this inorder traversal is not 3 x 2.
In the case that + is the major constituent, you have two subcases:
A + ((B * D) / C)
A + (B * (D / C))
But the middle case * generates only one variant:
(A + B) * (D / C)
So when there are four operands and three operators, there are five possible
expressions.
Experimentally, I have obtained this table
operators expressions
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
Interesting:
429/ 132 = 3 1/4
1430/ 429 = 3 1/3
4862/1430 = 3 2/5
The sequence doesn't grow nearly as fast as factorial, which makes it pointless
to implement fancy pruning strategies for this problem, at least as far as
``practical'' expression sizes are concerned.
Now if I imagine the way the subtrees are being combined, it becomes obvious
the relationship might be among the numbers in the sequence. For instance an
expression with six operators is carved into two as 1 and 5, 2 and 4, 3 and 3,
4 and 2 and 5 and 1. I.e a subtree of size one is combined with subtrees of
size 5, 2 with 4 and so on.
So what is the relationship between, say 1 1 2 and 5?
It's 1 * 2 + 1 * 1 + 2 * 1.
That is to say, 5 is the dot product of the vector (1 1 2) and its
reverse (2 1 1)!
There are 5 possible trees with three operators, because such trees are
obtained in three ways: taking a tree with zero operators against all possible
trees with two operators (which is done twice, because of LR symmetry), and
taking all possible left and right trees with one operator.
Similarly, 14 is (1 1 2 5) . (5 2 1 1) = 5 + 2 + 2 + 5 = 14.
Lisp will verify the next few for us:
;; dot product against reverse
(defun dotrev (list) (reduce '+ (mapcar '* list (reverse list))))
(dotrev '(1 1 2 5)) -> 14
(dotrev '(1 1 2 5 14)) -> 42
(dotrev '(1 1 2 5 14 42)) -> 132
(dotrev '(1 1 2 5 14 42 132)) -> 429
(dotrev '(1 1 2 5 14 42 132 429)) -> 1430
(dotrev '(1 1 2 5 14 42 132 429 1430)) -> 4862
That's no proof, but I'm as good as convinced. As a software guy, my alliance
is with computer science rather that mathematics, and the above has
pretty much the required rigor for our camp. :)
Ben Bacarisse
> On 2009-02-26, christian.bau <christ...@cbau.wanadoo.co.uk> wrote:
>> You have eight numbers, separated by seven operators.
>> One of the operators has to be evaluated first. There are seven
>> choices, each leaving you with 7 numbers and six operators.
>> One of the operators has to be evaluated next. There are six choices,
>> each leaving you with 6 numbers and five operators.
>> And so on and so on.
>>
>> There are 7 x 6 x 5 x 4 x 3 x 2 x 1 cases that get examined that way.
>
> I'm afraid this analysis is not right. This is not a straight permutation
> problem. Reason being is that the operators cannot be arbitrarily reordered.
>
> For instance, consider the smaller case of A + B * D / C. The number of
> expression trees which have this inorder traversal is not 3 x 2.
>
> In the case that + is the major constituent, you have two subcases:
>
> A + ((B * D) / C)
> A + (B * (D / C))
>
> But the middle case * generates only one variant:
>
> (A + B) * (D / C)
>
> So when there are four operands and three operators, there are five possible
> expressions.
The number of such trees with n operators is the nth Catalan number:
(2n)!/(n!(n+1)!).
--
Ben.
Kaz Kylheku
> The number of such trees with n operators is the nth Catalan number:
> (2n)!/(n!(n+1)!).
Ha, I was just googling for terms of the sequence as your article arrived.
Fascinating. The Wikipedia page on these numbers even has the example of
enumerating possible binary trees that have the same inorder traversal,
and it has the section on the recurrence relation that I uncovered.
I had a question about how these numbers are related to the Pascal's triangle,
and found a page with the answer to that one also.
I think I will remember these numbers well, having come across them in this
manner. If I were to just read about the Catalan numbers, it would quite likely
be in one ear, out the other. :)
I wonder whether the reversed dot product has a name. It's used as the basic
building block for a discrete convolution, which is known as a Cauchy product.
nick_keigh...@hotmail.com
<snip>
> That's no proof, but I'm as good as convinced. As a software guy, my alliance
> is with computer science rather that mathematics, and the above has
> pretty much the required rigor for our camp. :)
I'd always thought computer science *was* mathematics...
Dik T. Winter
...
> operators expressions
> 0 1
> 1 1
> 2 2
> 3 5
> 4 14
> 5 42
> 6 132
> 7 429
> 8 1430
> 9 4862
If you calculate such a table, it is a good idea to go to:
<http://www.research.att.com/~njas/sequences/>
and look whether the sequence is known. In this case the
sequence is well-known, as others have already remarked.
--
dik t. winter, cwi, science park 123, 1098 xg amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Richard
When I did my degree most CS students flunked the math components
because it meant real work.
Kaz Kylheku
> In article <200903090...@gmail.com> Kaz Kylheku <kkyl...@gmail.com> writes:
> ...
> > operators expressions
> > 0 1
> > 1 1
> > 2 2
> > 3 5
> > 4 14
> > 5 42
> > 6 132
> > 7 429
> > 8 1430
> > 9 4862
>
> If you calculate such a table, it is a good idea to go to:
> <http://www.research.att.com/~njas/sequences/>
> and look whether the sequence is known.
Unless this is part of urgent work, it can wait!
By just searching for the sequence, you miss the opportunity of discovering
some of its properties by yourself.
> In this case the sequence is well-known, as others have already remarked.
By ``others'' do you mean Ben Bacarisse, following up to the same article as
you above? Searching the thread, I can't find any other others. Did they also
post working code? Or even non-working code? I seem to have missed that too.
JosephKK
Given the already known to me some of the useful results produced by
Cauchy, i took a direct poke at wikipedia. As expected it is a much
more general result.
Gene
> On 2009-02-25, Nikos Chantziaras <rea...@arcor.de> wrote:
>
>
>
>
>
> > 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.
>
> > 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?
>
> hinting at a possible algorithm.
>
>
>
> 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)))
>
> (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)
>
> 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.
>
>
> 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.
>
> 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;
>
> }
>
This is fascinating.
When I read the problem weeks ago, I immediately thought about
continuation passing style (CPS) as a nice way to enumerate all the
trees. This works out to:
(defun f (expr cont)
(let ((len (length expr)))
(if (= 1 len) (funcall cont expr)
(do ((i 1 (+ i 2)))
((= i len))
(f (subseq expr 0 i)
(lambda (y)
(f (subseq expr (1+ i))
(lambda (z)
(funcall cont
`( { ,@y ,@(subseq expr i (1+ i)) ,@z } ))))))))))
(defun run () (f '(2 / 2 - 3 / 3 - 4 / 4 - 5 / 5) #'print))
Coding this in C requires a way to express lambda closures. A trick
is to turn the closure inside out: use a struct for the environment
(params and bound data) and include a pointer to a function that
accepts the struct. This is pointer is effectively the "code" part of
of the closure.
It's cool that without studying your solution, I ended up with nearly
the same thing:
#include <stdio.h>
char expr[] ="2/2-3/3-4/4-5/5";
#define NOVAL 1e-100
/* closure with no bound data, only parameters */
typedef struct closure_s {
void (*f)(struct closure_s *);
char pstr[32];
double pval;
} CLOSURE;
/* inner lambda closure */
typedef struct inner_s {
void (*f)(CLOSURE *);
char pstr[32];
double pval;
/* bound data */
int op;
CLOSURE *encl, *cont;
} INNER;
/* outer lambda closure */
typedef struct outer_s {
void (*f)(CLOSURE *);
char pstr[32];
double pval;
/* bound data */
int i0, i1;
CLOSURE *cont;
} OUTER;
/* evaluate a op b allowing for "no value" operands */
double eval(double a, int op, double b)
{
if (a == NOVAL || b == NOVAL) return NOVAL;
switch (expr[op]) {
case '/': return (b == 0) ? NOVAL : a / b;
case '-': return a - b;
}
return 0;
}
/* inner closure code */
void f_inner(CLOSURE *clos)
{
INNER *i = (INNER*)clos;
sprintf(i->cont->pstr, "(%s%c%s)", i->pstr, expr[i->op], i->encl-
>pstr);
i->cont->pval = eval(i->pval, i->op, i->encl->pval);
i->cont->f(i->cont);
}
void parenthesize(int i0, int i1, CLOSURE *cont);
/* outer closure code */
void f_outer(CLOSURE *clos)
{
OUTER *o = (OUTER*)clos;
parenthesize(o->i0, o->i1, o->cont);
}
/* Call the continuation once on each possible
parenthesization (is that a word?) of the expression
starting at index i0 and ending at i1 - 1. */
void parenthesize(int i0, int i1, CLOSURE *cont)
{
if (i1 - i0 == 1) {
/* Base case single digit: Just set up the parameters and call. */
sprintf(cont->pstr, "%c", expr[i0]);
cont->pval = expr[i0] - '0';
cont->f(cont);
}
else {
/* Split the expr all possible ways and recur. */
int op;
for (op = i0 + 1; op < i1; op += 2) {
INNER inner[1] = {{ f_inner, "", 0.0, op, 0, cont }};
OUTER outer[1] = {{ f_outer, "", 0.0, op + 1, i1, (CLOSURE*)
inner }};
/* Fixup because aggregate initializer can'd refer forward: */
inner->encl = (CLOSURE*)outer;
parenthesize(i0, op, (CLOSURE*)outer);
}
}
}
/* code for a printing closure */
void f_print(CLOSURE *clos)
{
if (clos->pval >= 49) printf("%s=%lf\n", clos->pstr, clos->pval);
}
int main(void)
{
CLOSURE printer[1] = {{ f_print }};
parenthesize(0, sizeof expr - 1, printer);
return 0;
}