Anonymous user
24 game/Solve: Difference between revisions
no edit summary
Alextretyak (talk | contribs) m (→{{header|11l}}) |
No edit summary |
||
Line 1,730:
(5+5-6)*6
</pre>
=={{header|C}}==
Tested with GCC 10.2.0, but should work with all versions supporting C99.<br>
Provided code prints all solutions or nothing in case no solutions are found.<br>
It can be modified or extended to work with more than 4 numbers, goals other than 24 and additional operations.<br>
Note: This a brute-force approach with time complexity <em>O(6<sup>n</sup>.n.(2n-3)!!)</em> and recursion depth <em>n</em>.<br>
<lang c>#include <stdio.h>
typedef struct {int val, op, left, right;} Node;
Node nodes[10000];
int iNodes;
int b;
float eval(Node x){
if (x.op != -1){
float l = eval(nodes[x.left]), r = eval(nodes[x.right]);
switch(x.op){
case 0: return l+r;
case 1: return l-r;
case 2: return r-l;
case 3: return l*r;
case 4: return r?l/r:(b=1,0);
case 5: return l?r/l:(b=1,0);
}
}
else return x.val*1.;
}
void show(Node x){
if (x.op != -1){
printf("(");
switch(x.op){
case 0: show(nodes[x.left]); printf(" + "); show(nodes[x.right]); break;
case 1: show(nodes[x.left]); printf(" - "); show(nodes[x.right]); break;
case 2: show(nodes[x.right]); printf(" - "); show(nodes[x.left]); break;
case 3: show(nodes[x.left]); printf(" * "); show(nodes[x.right]); break;
case 4: show(nodes[x.left]); printf(" / "); show(nodes[x.right]); break;
case 5: show(nodes[x.right]); printf(" / "); show(nodes[x.left]); break;
}
printf(")");
}
else printf("%d", x.val);
}
int float_fix(float x){ return x < 0.00001 && x > -0.00001; }
void solutions(int a[], int n, float t, int s){
if (s == n){
b = 0;
float e = eval(nodes[0]);
if (!b && float_fix(e-t)){
show(nodes[0]);
printf("\n");
}
}
else{
nodes[iNodes++] = (typeof(Node)){a[s],-1,-1,-1};
for (int op = 0; op < 6; op++){
int k = iNodes-1;
for (int i = 0; i < k; i++){
nodes[iNodes++] = nodes[i];
nodes[i] = (typeof(Node)){-1,op,iNodes-1,iNodes-2};
solutions(a, n, t, s+1);
nodes[i] = nodes[--iNodes];
}
}
iNodes--;
}
};
int main(){
// define problem
int a[4] = {8, 3, 8, 3};
float t = 24;
// print all solutions
nodes[0] = (typeof(Node)){a[0],-1,-1,-1};
iNodes = 1;
solutions(a, sizeof(a)/sizeof(int), t, 1);
return 0;
}</lang>
=={{header|C++}}==
| |||