Rosetta Code

24 game/Solve: Difference between revisions

Page Discussion

24 game/Solve (view source)

Revision as of 18:34, 21 June 2011

2,373 bytes added ,  13 years ago
→‎{{header|C}}: replaced incorrect code.
(→‎{{header|C}}: replaced incorrect code.)
Line 612:
 
=={{header|C}}==
{{incorrect|C|This codeis usesa randomsolver shufflingthat's andgeneric aenough limitedto triesdeal towith happenmore uponthan a4 solution.numbers, goals There'sother nothan garantee24, or different digit ranges. It findinggarantees a solution whenif there is one,. or quicklyIts determineoutput it'sformat is reasonably good looking, though not possiblenecessarily otherwiseoptimal.}}
<lang cC>#include <stdio.h>
#include <stdlib.h>
#include <stringtime.h>
#include<time.h>
 
#define NOVALn_cards 99994
#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 0C_SUB: op = " - "; break;
case C_MUL: op = " x "; break;
val[x]=left+right;
case C_DIV: op = " / "; break;
case 1: }
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 parentheval_expr(intexpr ne, 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;
}
 
voidint solve24(int*ar 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 argc,char**argv){
{
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}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/131318"