|
(5+5-6)*6
</pre>
=={{header|C}}==
This is a solver that's generic enough to deal with more than 4 numbers,
goals other than 24, or different digit ranges.
It guarantees a solution if there is one.
Its output format is reasonably good looking, though not necessarily optimal.
<lang C>#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define n_cards 4
#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)
{
const char * op;
switch(e->op) {
case C_NUM: printf("%d", e->value);
return;
case C_ADD: op = " + "; break;
case C_SUB: op = " - "; break;
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("%s", op);
show_expr(e->right, e->op, 1);
if ((e->op == prec && is_right) || e->op < prec) printf(")");
}
void eval_expr(expr e, frac f)
{
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 solve24(int n[])
{
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>
{{out}}
<pre> 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</pre>
For the heck of it, using seven numbers ranging from 0 to 99, trying to calculate 1:
<pre> 54 64 44 67 60 54 97: (54 + 64 + 44) / 54 + 60 / (67 - 97)
83 3 52 50 14 48 55: 55 - (((83 + 3 + 52) - 50 + 14) - 48)
70 14 26 6 4 50 19: ((70 + 14 + 26) / 4 - 19) x 6 - 50
75 29 61 95 1 6 73: 6 / (73 - ((75 + 29 + 61) - 95)) - 1
99 65 59 54 29 3 21: 3 - (99 + 65 + 54) / (59 + 29 + 21)
88 57 18 72 60 70 22: (72 - 70) x (60 + 22) - (88 + 57 + 18)
73 18 76 44 32 3 49: 32 / (49 - (44 + 3)) - ((73 + 18) - 76)
36 53 68 12 82 30 8: ((36 + 53 + 68) - 82) / 30 - 12 / 8
83 35 81 82 99 40 36: ((83 + 35) x 81 - 82 x 99) / 40 / 36
29 43 57 18 1 74 89: (1 + 74) / (((29 + 43) - 57) / 18) - 89</pre>
=={{header|C++}}==
| 