China DOS Union

Sender: wfaye (Down with NATO), Board: GreatTurn
Title: A program to make 24
Source: BBS Shuimu Tsinghua Station (Wed Feb 7 10:48:30 2001)

Seeing everyone persistently trying to solve the 24-point problem, I might as well post a program.
It can solve any 24-point problem within 1 second. Of course, if you want to calculate 25, 26...
that is also possible. I hope this can serve as the definitive end to the 24 problem.

#include "stdafx.h"
//
//Principle: arrange 4 numbers and 3 operators into a sequence in "Polish notation",
// then calculate whether the value of that sequence is the target we want.
// We can traverse the possible compositions of this sequence
// to determine whether a solution exists.
//According to my calculation, if we only use numbers from 1 to 10 to make 24, there are
// 715 different problems in total, of which 566 have solutions. If it is 1 to 13, then there are
// 1820 different problems, of which 1362 have solutions
//
int total = 0; //number of solutions
int sp; //current expression stack pointer
int s; //expression stack
void Evaluate(int& fz, int& fm)
//calculate the value of the expression; fz, fm are the numerator and denominator of the result
{
int op, l, m, opn;
op = s; //take the top stack element
for (l = 0; l 0) //is a number
{
opn = m;
opn = 1;
}
else //is an operator
Evaluate(opn, opn);
}
//calculate according to the operator
//opn/opn is the first operand,
//opn/opn is the second operand,
switch (op)
{
case -4: //multiplication
fz = opn * opn;
fm = opn * opn;
break;
case -3: //addition
fz = opn * opn + opn * opn;
fm = opn * opn;
break;
case -2: //subtraction
fz = opn * opn - opn * opn;
fm = opn * opn;
break;
case -1: //division
fz = opn * opn;
fm = opn * opn;
break;
}
}
void Display(CString& m)
//convert the expression into a string
{
int i;
CString n;
m = "";
for (i = 0; i < 7; i++)
{
switch (s)
{
case -4: m += " *"; break;
case -3: m += " +"; break;
case -2: m += " -"; break;
case -1: m += " /"; break;
default: n.Format("%3d", s); m += n; break;
}
}
}
void Compute(int target, int a, int b, int c, int d, CStringArray& ma)
// target - result to compute (usually 24)
// a, b, c, d - the 4 numbers used in the calculation
// ma - string form of the solutions
{
int l1, l2, l3, op1, op2, op3;
int l, fz, fm, num;
CString m;

//record the arrangement of the middle four elements in the expression
// where loc, loc indicate the positions of the second and third operators
// loc, loc indicate the positions of the first and second operands
int loc = {{1, 2, 3, 4}, {1, 3, 2, 4}, {1, 4, 2, 3},
{2, 3, 1, 4}, {2, 4, 1, 3}};
//num records one permutation of a, b, c, d
for (l1 = 0; l1 < 4; l1++)
{
num = a;
for (l2 = 0; l2 < 4; l2++)
{
if (l2 == l1) continue;
num = b;
for (l3 = 0; l3 < 4; l3++)
{
if (l3 == l1 || l3 == l2) continue;
num = c;
num = d;
//the last two of the expression must be numbers
s = num;
s = num;
for (l = 0; l < 5; l++)
{
s] = num;
s] = num;
for (op1 = -4; op1 < 0; op1++)
{
//the first one in the expression must be an operator
s = op1;
for (op2 = -4; op2 < 0; op2++)
{
s] = op2;
for (op3 = -4; op3 < 0; op3++)
{
s] = op3;
sp = 0;
Evaluate(fz, fm);
//denominator not 0, divisible, quotient 24 means success
if (fm != 0 && fz % fm == 0 && fz / fm == target)
{
Display(m);
ma.Add(m);
total++;
//adding return here means only finding one solution,
//otherwise it finds all solutions (without removing duplicates)
return;
}
}
}
}
}
}
}
}
}

--

※ Source:·BBS Shuimu Tsinghua Station smth.org·

(This article was copied using the S-Term article copy script)
==================================================

Posting another program:
Also from Tsinghua, a program for making 24.
#include
#include
int get1(int (*p1),char (*p2))
{ int temp;
switch((*p2))
{ case 0: temp=(*p1)+(*p1); break;
case 1: temp=(*p1)-(*p1); break;
case 2: temp=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ temp=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp+=(*p1); break;
case 1: temp-=(*p1); break;
case 2: temp*=(*p1); break;
case 3: if ((*p1)&&(temp%(*p1)==0))
{ temp=temp/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp+=(*p1); break;
case 1: temp-=(*p1); break;
case 2: temp*=(*p1); break;
case 3: if ((*p1)&&(temp%(*p1)==0))
{ temp=temp/(*p1);
break;
}
else return(0);
}
return(temp);
}
int get2(int (*p1),char (*p2))
{ int temp;
switch((*p2))
{ case 0: temp=(*p1)+(*p1); break;
case 1: temp=(*p1)-(*p1); break;
case 2: temp=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ temp=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp=(*p1)+temp; break;
case 1: temp=(*p1)-temp; break;
case 2: temp=(*p1)*temp; break;
case 3: if ((temp)&&((*p1)%temp==0))
{ temp=(*p1)/temp;
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp+=(*p1); break;
case 1: temp-=(*p1); break;
case 2: temp*=(*p1); break;
case 3: if ((*p1)&&(temp%(*p1)==0))
{ temp=temp/(*p1);
break;
}
else return(0);
}
return(temp);
}
int get3(int (*p1),char (*p2))
{ int temp;
switch((*p2))
{ case 0: temp=(*p1)+(*p1); break;
case 1: temp=(*p1)-(*p1); break;
case 2: temp=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ temp=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp+=(*p1); break;
case 1: temp-=(*p1); break;
case 2: temp*=(*p1); break;
case 3: if ((*p1)&&(temp%(*p1)==0))
{ temp=temp/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp=(*p1)+temp; break;
case 1: temp=(*p1)-temp; break;
case 2: temp=(*p1)*temp; break;
case 3: if ((temp)&&(*p1)%temp==0)
{ temp=(*p1)/temp;
break;
}
else return(0);
}
return(temp);
}
int get4(int (*p1),char (*p2))
{ int temp;
switch((*p2))
{ case 0: temp=(*p1)+(*p1); break;
case 1: temp=(*p1)-(*p1); break;
case 2: temp=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ temp=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp=(*p1)+temp; break;
case 1: temp=(*p1)-temp; break;
case 2: temp=(*p1)-temp; break;
case 3: if ((temp)&&(*p1)%temp==0)
{ temp=(*p1)/temp;
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp=(*p1)+temp; break;
case 1: temp=(*p1)-temp; break;
case 2: temp=(*p1)*temp; break;
case 3: if ((temp)&&(*p1)==0)
{ temp=(*p1)/temp;
break;
}
else return(0);
}
return(temp);
}
int get5(int (*p1),char (*p2))
{ int tmp1,tmp2;
switch((*p2))
{ case 0: tmp1=(*p1)+(*p1); break;
case 1: tmp1=(*p1)-(*p1); break;
case 2: tmp1=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ tmp1=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: tmp2=(*p1)+(*p1); break;
case 1: tmp2=(*p1)-(*p1); break;
case 2: tmp2=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ tmp2=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: tmp1+=tmp2; break;
case 1: tmp1-=tmp2; break;
case 2: tmp1*=tmp2; break;
case 3: if ((tmp2)&&(tmp1%tmp2==0))
{ tmp1/=tmp2;
break;
}
else return(0);
}
return(tmp1);
}
void main()
{ int num,(*pp1),input,goal,i,j,k,m,n;
char (*pp2),code;
cout<>goal;
cout<<"Input four numbers:";
for(i=0;i>input;
m=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
for(k=0;k<4;k++)
{ code=i;
code=j;
code=k;
m++;
}
n=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if (j!=i) for(k=0;k<4;k++)
if ((k!=i)&&(k!=j)) { m=6-i-j-k;
num=input;
num=input;
num=input;
num=input;
n++;
}
m=0;
for(i=0,pp1=num;i<24;i++,pp1++)
{ for(j=0,pp2=code;j<64;j++,pp2++)
{ k=get1(pp1,pp2); if (k==goal) {m=1; break;}
k=get2(pp1,pp2); if (k==goal) {m=2; break;}
k=get3(pp1,pp2); if (k==goal) {m=3; break;}
k=get4(pp1,pp2); if (k==goal) {m=4; break;}
k=get5(pp1,pp2); if (k==goal) {m=5; break;}
}
if(m) break;
}
if(m)
{ char analyst;
for(i=0;i<3;i++)
switch((*pp2))
{ case 0*pp2)='+'; break;
case 1*pp2)='-'; break;
case 2*pp2)='*'; break;
case 3*pp2)='/';
}
switch (m)
{ //The following may be hard to understand!
//See how and why to do in the end of the program!
// ( ( a ? b ) ? c ) ? d ?=+,-,*,/
// 0 1 2 3 4 5 6 7 8 9 10
case 1:strcpy(analyst,"((a?b)?c)?d";
analyst=(*pp2);
analyst=(*pp2);
analyst=(*pp2);
if((analyst=='*'||(analyst=='/'||
(analyst=='+'||(analyst=='-')
{ analyst='0'; analyst='0'; }
if((analyst=='*'||(analyst=='/'||
(analyst=='+'||(analyst=='-')
{ analyst='0'; analyst='0'; }
break;
// ( a ? ( b ? c ) ) ? d
// 0 1 2 3 4 5 6 7 8 9 10
case 2:strcpy(analyst,"(a?(b?c))?d";
analyst=(*pp2);
analyst=(*pp2);
analyst=(*pp2);
if((analyst=='+'||(analyst!='/'&&
((analyst=='*'||(analyst=='/'))
{ analyst='0'; analyst='0'; }
if((analyst=='*'||(analyst=='/'||
(analyst=='+'||(analyst=='-')
{ analyst='0'; analyst='0'; }
break;
// a ? ( ( b ? c ) ? d )
// 0 1 2 3 4 5 6 7 8 9 10
case 3:strcpy(analyst,"a?((b?c)?d";
analyst=(*pp2);
analyst=(*pp2);
analyst=(*pp2);
if((analyst=='*'||(analyst=='/'||
(analyst=='+'||(analyst=='-')
{ analyst='0'; analyst='0'; }
if((analyst=='+'||(analyst!='/'&&
((analyst=='*'||(analyst=='/'))
{ analyst='0'; analyst='0'; }
break;
// a ? ( b ? ( c ? d ) )
// 0 1 2 3 4 5 6 7 8 9 10
case 4:strcpy(analyst,"a?(b?(c?d))";
analyst=(*pp2);
analyst=(*pp2);
analyst=(*pp2);
if((analyst=='+'||(analyst!='/'&&
((analyst=='*'||(analyst=='/'))
{ analyst='0'; analyst='0'; }
if((analyst=='+'||(analyst!='/'&&
((analyst=='*'||(analyst=='/'))
{ analyst='0'; analyst='0'; }
break;
// ( a ? b ) ? ( c ? d )
// 0 1 2 3 4 5 6 7 8 9 10
case 5:strcpy(analyst,"(a?b)?(c?d)";
analyst=(*pp2);
analyst=(*pp2);
analyst=(*pp2);
if((analyst=='*'||(analyst=='/'||
(analyst=='+'||(analyst=='-')
{ analyst='0'; analyst='0'; }
if((analyst=='+'||(analyst!='/'&&
((analyst=='*'||(analyst=='/'))
{ analyst='0'; analyst='0'; }
}
for(i=0;i<11;i++)
switch(analyst)
{ case 'a': cout<<(*pp1); break;
case 'b': cout<<(*pp1); break;
case 'c': cout<<(*pp1); break;
case 'd': cout<<(*pp1); break;
case '0': break;
default: cout<<analyst;
}
cout<<endl;
}
else
{ for(i=0,pp1=num;i<24;i++,pp1++)
{ j=(*pp1)*(*pp1);
k=(*pp1)*(*pp1);
if(k%(*pp1)==0)
{ k/=(*pp1);
if(j+k==goal) { m=1; break; }
else if(j-k==goal) { m=2; break; }
else if(k-j==goal) { m=3; break; }
}
else
{ j=(*pp1)*(*pp1);
k=(*pp1)*(*pp1);
n=(*pp1);
if((k+n)&&(j%(k+n)==0))
{ if(j/(k+n)==goal)
{ m=4; break; }
}
else
if((k-n)&&(j%(k-n)==0))
if(j/(k-n)==goal) { m=5; break; }
else if(j/(n-k)==goal) { m=6; break; }
}
}
if(!m) cout<<"If you get it,please E-mail to:publicfrk@netease.com\n";
else switch (m)
{ case 1:cout<<(*pp1)<<"*("<<(*pp1)<<'+'
<<(*pp1)<<'/'<<(*pp1)<<''<<endl;
break;
case 2:cout<<(*pp1)<<"*("<<(*pp1)<<'-'
<<(*pp1)<<'/'<<(*pp1)<<''<<endl;
break;
case 3:cout<<(*pp1)<<"*("<<(*pp1)<<'/'
<<(*pp1)<<'-'<<(*pp1)<<''<<endl;
break;
case 4:cout<<(*pp1)<<"/("<<(*pp1)<<'+'
<<(*pp1)<<'/'<<(*pp1)<<''<<endl;
break;
case 5:cout<<(*pp1)<<"/("<<(*pp1)<<'-'
<<(*pp1)<<'/'<<(*pp1)<<''<<endl;
break;
case 6:cout<<(*pp1)<<"/("<<(*pp1)<<'/'
<<(*pp1)<<'-'<<(*pp1)<<''<<endl;
}
}
}
// .T. means you can get ride of ( )
// a?(b?c) (a?b)?c
// + + .T. .T.
// + - .T. .T.
// + * .T. .F.
// + / .T. .F.
// - + .F. .T.
// - - .F. .T.
// - * .T. .F.
// - / .T. .F.
// * + .F. .T.
// * - .F. .T.
// * * .T. .T.
// * / .T. .T.
// / + .F. .T.
// / - .F. .T.
// / * .F. .T.
// / / .F. .T.
//----------------------------------------------------------------
//Conculsion + +,-,*,/ *,/ +,-,*,/
// *,- *,/

Posting another program: also from Tsinghua, the definitive version of the 24 program (TC20)


/*TO24 lasy 2002.01.25*/

#define PRE 1E-6
#define DES 24.0

#include
#include

double add(double a,double b){return a+b;}
double sub(double a,double b){return a-b;}
double mul(double a,double b){return a*b;}
double div(double a,double b){return a/b;}

double (*fun)(double,double)={add,sub,mul,div};
const char op={'+','-','*','/'};

struct num
{
double f;
struct num *a,*b;
char op;
};

char to24(int n,struct num *f);
char output(struct num f);
char *fml(struct num f);

main()
{
int i,tmp;
struct num f;
for(i=0;i<4;i++)
{
printf("\nInput Number %d:",i+1);
scanf("%d",&tmp);
f.f=(double)tmp;f.a=f.b=NULL;f.op=0;
}
printf("\nSolutions:\n";
if(to24(4,f)==0)printf("None!";
}

char to24(int n,struct num *f)
{
char flag=0,*tmp;
int i,j,k,l;
struct num *h;
if(n==1)
{
if(fabs(f.f-DES)<PRE)flag=output(f);
}
else
{
for(i=0;i<n;i++)for(j=i+1;j<n;j++)for(k=0;k<4;k++)
{
h=(struct num *)malloc((n-1)*sizeof(struct num));
for(l=0;l<i;l++)h=f;
for(l=i+1;l<j;l++)h=f;
for(l=j;lPRE)
{
h.f=fun(f.f,f.f);
h.a=f+i;
h.b=f+j;
flag=to24(n-1,h)||flag;
}
if(k==1||(k==3&&fabs(f.f)>PRE))
{
h.f=fun(f.f,f.f);
h.a=f+j;
h.b=f+i;
flag=to24(n-1,h)||flag;
}
free(h);
}
}
return flag;
}

char output(struct num f)
{
static int count=0;
char *tmp;
count++;
printf("%3d: %s\t",count,tmp=fml(f));
if(count%3==0)printf("\n";
free(tmp);
return 1;
}

char *fml(struct num f)
{
char *buf,*a,*b;
buf=(char *)malloc(20*sizeof(char));
if(f.a!=NULL&&f.b!=NULL&&f.op!=0)
{
sprintf(buf,"(%s%c%s)",a=fml(*f.a),f.op,b=fml(*f.b));
free(a);free(b);
}
else
sprintf(buf,"%d",(int)f.f);
return buf;
}


＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
KO says: using programming to solve the 24-point problem, awesome!
Can anyone understand it? Post a reply.