24 game/Solve: Difference between revisions
Content added Content deleted
(→{{header|C}}: replaced incorrect code.) |
|||
Line 612: | Line 612: | ||
=={{header|C}}== |
=={{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 garantees a solution if there is one. Its output format is reasonably good looking, though not necessarily optimal. |
|||
<lang |
<lang C>#include <stdio.h> |
||
#include<stdlib.h> |
#include <stdlib.h> |
||
#include< |
#include <time.h> |
||
#include<time.h> |
|||
#define |
#define n_cards 4 |
||
#define solve_goal 24 |
|||
#define max_digit 9 |
|||
typedef struct { int num, denom; } frac_t, *frac; |
|||
void die(char*s){ |
|||
typedef enum { C_NUM = 0, C_ADD, C_SUB, C_MUL, C_DIV, } op_type; |
|||
printf("Error: %s\n",s); |
|||
exit(0); |
|||
} |
|||
typedef struct expr_t *expr; |
|||
int getvalue(int*val,int x,int dir){ |
|||
typedef struct expr_t { |
|||
int r=NOVAL; |
|||
op_type op; |
|||
if(dir>0)++x; |
|||
expr left, right; |
|||
while(1){ |
|||
int value; |
|||
if(val[x]!=NOVAL){ |
|||
} expr_t; |
|||
r=val[x]; |
|||
val[x]=NOVAL; |
|||
break; |
|||
} |
|||
x+=dir; |
|||
} |
|||
return r; |
|||
} |
|||
void show_expr(expr e, op_type prec, int is_right) |
|||
int calc(int*val,int*op,int*order){ |
|||
{ |
|||
int c=0,left,right,x; |
|||
char * op; |
|||
while(c<3){ |
|||
switch(e->op) { |
|||
x=order[c]; |
|||
case C_NUM: printf("%d", e->value); |
|||
left=getvalue(val,x,-1); |
|||
return; |
|||
right=getvalue(val,x,1); |
|||
case C_ADD: op = " + "; break; |
|||
switch(op[x]){ |
|||
case |
case C_SUB: op = " - "; break; |
||
case C_MUL: op = " x "; break; |
|||
val[x]=left+right; |
|||
break; |
case C_DIV: op = " / "; break; |
||
} |
|||
val[x]=left-right; |
|||
break; |
|||
case 2: |
|||
val[x]=left*right; |
|||
break; |
|||
case 3: |
|||
if(!right)return 0; |
|||
if(left%right)return 0; |
|||
val[x]=left/right; |
|||
break; |
|||
} |
|||
++c; |
|||
} |
|||
return getvalue(val,-1,1); |
|||
} |
|||
if ((e->op == prec && is_right) || e->op < prec) printf("("); |
|||
void shuffle(int*p,int n){ |
|||
show_expr(e->left, e->op, 0); |
|||
int x=n,r,t; |
|||
printf(op); |
|||
while(x--){ |
|||
show_expr(e->right, e->op, 1); |
|||
r=rand()%n; |
|||
if ((e->op == prec && is_right) || e->op < prec) printf(")"); |
|||
t=p[x]; |
|||
p[x]=p[r]; |
|||
p[r]=t; |
|||
} |
|||
} |
} |
||
void |
void eval_expr(expr e, frac f) |
||
{ |
|||
while(n>0)--n,putchar('('); |
|||
frac_t left, right; |
|||
while(n<0)++n,putchar(')'); |
|||
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) { |
|||
int getpriority(int x,int*order){ |
|||
eval_expr(ex_in[0], &final); |
|||
int z=3; |
|||
if (final.num == final.denom * solve_goal && final.denom) { |
|||
while(z--){ |
|||
show_expr(ex_in[0], 0, 0); |
|||
if(order[z]==x)return 3-z; |
|||
return 1; |
|||
} |
|||
} |
|||
return 0; |
|||
return 0; |
|||
} |
|||
} |
|||
for (i = 0; i < len - 1; i++) { |
|||
void showsol(int*val,int*op,int*order){ |
|||
for (j = i + 1; j < len; j++) |
|||
char*oper="+-*/"; |
|||
ex[j - 1] = ex_in[j]; |
|||
int x=0; |
|||
ex[i] = &node; |
|||
int p=0; |
|||
for (j = i + 1; j < len; j++) { |
|||
int lp=0; |
|||
node.left = ex_in[i]; |
|||
int v=0; |
|||
node.right = ex_in[j]; |
|||
while(x<4){ |
|||
for (node.op = C_ADD; node.op <= C_DIV; node.op++) |
|||
if(x<3){ |
|||
if (solve(ex, len - 1)) |
|||
lp=p; |
|||
return 1; |
|||
p=getpriority(x,order); |
|||
v=p-lp; |
|||
node.left = ex_in[j]; |
|||
if(v>0)parenth(v); |
|||
node.right = ex_in[i]; |
|||
} |
|||
node.op = C_SUB; |
|||
printf("%d",val[x]); |
|||
if (solve(ex, len - 1)) return 1; |
|||
if(x<3){ |
|||
node.op = C_DIV; |
|||
if(v<0)parenth(v); |
|||
if (solve(ex, len - 1)) return 1; |
|||
printf("%c",oper[op[x]]); |
|||
} |
|||
ex[j] = ex_in[j]; |
|||
++x; |
|||
} |
|||
} |
|||
ex[i] = ex_in[i]; |
|||
parenth(-p); |
|||
} |
|||
putchar('\n'); |
|||
return 0; |
|||
} |
} |
||
int solve24(int n[]) |
|||
{ |
|||
int op[3],order[3]={0,1,2}; |
|||
int i; |
|||
int z=100000,value[4],n,r; |
|||
expr_t ex[n_cards]; |
|||
srand(time(0)); |
|||
expr e[n_cards]; |
|||
while(z--){ |
|||
for (i = 0; i < n_cards; i++) { |
|||
r=rand(); |
|||
e[i] = ex + i; |
|||
op[0]=r&3; |
|||
ex[i].op = C_NUM; |
|||
op[1]=(r>>2)&3; |
|||
ex[i].left = ex[i].right = 0; |
|||
op[2]=(r>>4)&3; |
|||
ex[i].value = n[i]; |
|||
shuffle(ar,4); |
|||
} |
|||
memcpy(value,ar,4*sizeof(int)); |
|||
return solve(e, n_cards); |
|||
shuffle(order,3); |
|||
n=calc(value,op,order); |
|||
if(n!=24)continue; |
|||
showsol(ar,op,order); |
|||
break; |
|||
} |
|||
} |
} |
||
int main( |
int main() |
||
{ |
|||
int ar[4]; |
|||
int i, j, n[] = { 3, 3, 8, 8, 9 }; |
|||
if(argc!=5)die("Usage: prog.exe 1 2 3 4"); |
|||
srand(time(0)); |
|||
ar[0]=atol(argv[1]); |
|||
ar[1]=atol(argv[2]); |
|||
ar[2]=atol(argv[3]); |
|||
ar[3]=atol(argv[4]); |
|||
solve24(ar); |
|||
return 0; |
|||
} |
|||
</lang> |
|||
Examples: |
|||
<pre>C:\>prog 1 2 3 4 |
|||
(((3*4)*2)*1) |
|||
for (j = 0; j < 10; j++) { |
|||
C:\>prog 1 1 2 7 |
|||
for (i = 0; i < n_cards; i++) { |
|||
(((2+1))*(1+7)) |
|||
n[i] = 1 + (double) rand() * max_digit / RAND_MAX; |
|||
printf(" %d", n[i]); |
|||
} |
|||
printf(": "); |
|||
printf(solve24(n) ? "\n" : "No solution\n"); |
|||
} |
|||
return 0; |
|||
C:\>prog 5 6 7 8 |
|||
}</lang>Sample output:<lang> 1 8 2 1: 1 x 8 x (2 + 1) |
|||
((8/(7-5))*6) |
|||
6 8 2 8: 6 + 8 + 2 + 8 |
|||
</pre> |
|||
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}}== |
=={{header|Clojure}}== |