Re: Getting to a number from a sequence


Willem wrote:

I notice you are using integer operations.

Can this program crack the old chestnut (1, 3, 4, 6) = 24 ?

(I hope I got the right chestnut..)

IIRC, (1, 3, 4, 6) = 24 can only be solved with non-integer subexpressions.

One solution is 6 / (1 - 3/4) = 24

Cool again. The below incorporates fractions. Rational arithmetic
would be better than doubles, but doubles seem to work ok. It prints
the solution you suggested and no others. It also finds quite a few
more solutions to the original problem than with integer ops only.

#include <stdio.h>

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

//#define SUM 50
//int opd[] = { 4, 5, 6, 7, 8 }, opd_p = 5, stk_p;

#define SUM 24
int opd[] = { 1, 3, 4, 6 }, opd_p = 4, stk_p;

double stk[100];
char buf[100]; int buf_p;

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

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

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

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

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

if (stk_p == 1 && opd_p == 0) { // check for base case
double eps = stk[0] - SUM;
if (-.001 < eps && eps < .001) {
t = buf_p;
print();
printf("\n");
buf_p = t;
}
}
else
eval(); // recur

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

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

.

Relevant Pages

  • Re: factorial and exponent
    ... implementation which put the limits. ... int add ... operations to simulate 64-bit integer operations. ... The C compiler can double that up to simulate ...
    (comp.lang.c)
  • Re: Isnt bool __invert__ behaviour "strange"?
    ... Since bool is a subclass of int, ... all the integer operations will remain integer ... This was done for backwards ... compatability, and is unlikely to change in the 2.x ...
    (comp.lang.python)