Anonymous user
24 game/Solve: Difference between revisions
→{{header|C}}: replaced incorrect code.
(→{{header|C}}: replaced incorrect code.) |
|||
Line 612:
=={{header|C}}==
<lang
#include <stdlib.h>
#include <
#define
#define solve_goal 24
#define max_digit 9
typedef struct { int num, denom; } frac_t, *frac;
typedef enum { C_NUM = 0, C_ADD, C_SUB, C_MUL, C_DIV, } op_type;
typedef struct expr_t *expr;
typedef struct expr_t {
op_type op;
expr left, right;
int value;
} expr_t;
void show_expr(expr e, op_type prec, int is_right)
{
char * op;
switch(e->op) {
case C_NUM: printf("%d", e->value);
return;
case C_ADD: op = " + "; break;
case
case C_MUL: op = " x "; break;
case C_DIV: op = " / "; break;
if ((e->op == prec && is_right) || e->op < prec) printf("(");
show_expr(e->left, e->op, 0);
printf(op);
show_expr(e->right, e->op, 1);
if ((e->op == prec && is_right) || e->op < prec) printf(")");
}
void
{
frac_t left, right;
if (e->op == C_NUM) {
f->num = e->value;
f->denom = 1;
return;
}
eval_expr(e->left, &left);
eval_expr(e->right, &right);
switch (e->op) {
case C_ADD:
f->num = left.num * right.denom + left.denom * right.num;
f->denom = left.denom * right.denom;
return;
case C_SUB:
f->num = left.num * right.denom - left.denom * right.num;
f->denom = left.denom * right.denom;
return;
case C_MUL:
f->num = left.num * right.num;
f->denom = left.denom * right.denom;
return;
case C_DIV:
f->num = left.num * right.denom;
f->denom = left.denom * right.num;
return;
default:
fprintf(stderr, "Unknown op: %d\n", e->op);
return;
}
}
int solve(expr ex_in[], int len)
{
int i, j;
expr_t node;
expr ex[n_cards];
frac_t final;
if (len == 1) {
eval_expr(ex_in[0], &final);
if (final.num == final.denom * solve_goal && final.denom) {
show_expr(ex_in[0], 0, 0);
return 1;
}
return 0;
}
for (i = 0; i < len - 1; i++) {
for (j = i + 1; j < len; j++)
ex[j - 1] = ex_in[j];
ex[i] = &node;
for (j = i + 1; j < len; j++) {
node.left = ex_in[i];
node.right = ex_in[j];
for (node.op = C_ADD; node.op <= C_DIV; node.op++)
if (solve(ex, len - 1))
return 1;
node.left = ex_in[j];
node.right = ex_in[i];
node.op = C_SUB;
if (solve(ex, len - 1)) return 1;
node.op = C_DIV;
if (solve(ex, len - 1)) return 1;
ex[j] = ex_in[j];
}
ex[i] = ex_in[i];
}
return 0;
}
{
int i;
expr_t ex[n_cards];
expr e[n_cards];
for (i = 0; i < n_cards; i++) {
e[i] = ex + i;
ex[i].op = C_NUM;
ex[i].left = ex[i].right = 0;
ex[i].value = n[i];
}
return solve(e, n_cards);
}
int main(
{
int i, j, n[] = { 3, 3, 8, 8, 9 };
srand(time(0));
for (j = 0; j < 10; j++) {
for (i = 0; i < n_cards; i++) {
n[i] = 1 + (double) rand() * max_digit / RAND_MAX;
printf(" %d", n[i]);
}
printf(": ");
printf(solve24(n) ? "\n" : "No solution\n");
}
return 0;
}</lang>Sample output:<lang> 1 8 2 1: 1 x 8 x (2 + 1)
6 8 2 8: 6 + 8 + 2 + 8
4 2 8 1: (4 - 2 + 1) x 8
3 1 9 9: (9 - 1) / (3 / 9)
5 7 5 1: No solution
5 8 4 1: (5 + 1) x (8 - 4)
8 3 4 9: 8 + 3 + 4 + 9
3 7 4 4: ((3 + 7) - 4) x 4
5 6 4 1: 4 / (1 - 5 / 6)
5 5 9 8: 5 x 5 - 9 + 8</lang>
=={{header|Clojure}}==
|