EinsteinRiddle.rar

/* Einstein's riddle - Who has the Fish? Time:2012-7-12 22:25:02 Author��Awakening Intro��Try to solve the classic Einstain's riddle by C programming. Algorithm: Bruteforce & pre-calculated permutaion table. Version 1: 5 "for loop" calculating method will cost hundreds of hours. It's useless. Version 2: Try to optimize bruteforce cource in different loop layer. It's lightening fast! (less than 1 second) Version 3: Try to reconstruct awkward codes and tidy them up. */ #include "stdio.h" #include "stdlib.h" #include "string.h" #define PERM 120 #define COL 5 //#define DBGBINSEARCH #if defined(DBGBINSEARCH) #define DBGTRACE(fmt...) printf(fmt) #else #define DBGTRACE(fmt...) do{}while(0) #endif //stringtable is for outputing quickly. char stringtable[5][5][15]={ {"blue","green","red","white","yellow"}, {"Dane","Englishman","German","Swede","Norwegian"}, {"bier","coffee","milk","tea","water"}, {"Blend","BlueMaster","Dunhill","PallMall","Prince"}, {"birds","cats","dogs","fish","horses"} }; enum Color {blue=1,green,red,white,yellow}; enum Nationality {Dane=1,Englishman,German,Swede,Norwegian}; enum Cigarette {Blend=1,BlueMaster,Dunhill,PallMall,Prince}; enum Drink {bier=1,coffee,milk,tea,water}; enum Pet {birds=1,cats,dogs,fish,horses}; enum Relation{same=1,neighbor,left,right}; //Function Prototypes. static int genperm(char perm[PERM][COL],int loopcnt); static inline int checkCondition(char perm[][COL],int stype,int svalue,int otype,int ovalue,enum Relation relation); static int dispalyresult(char array[COL][COL]); int main() { char array[5][5]={{0,0,0,0,0}}; char perm[PERM][COL]; int loopcounter=0; int icolor,ination,icigar,idrink,ipet; int i,j; //Generate different permutations for next phase to use. genperm(perm,0); /*for(i=0;i<PERM;i++){ printf("row %d:",i); for(j=0;j<COL;j++){ printf("%d\t",perm[i][j]); } printf("\n"); }*/ //Start to find correct cases. //There are 5 attributes row(color,nation,drink,cigar,pet), //and each attribute row can has 5!=120 cases. //We have 5 loop for 5 attributes,and we try process the conditions as early as possible. for(icolor=0;icolor<PERM;icolor++){ DBGTRACE("enter icolor loop\n"); /*---------Basic Exculision Operation------*/ //C14 if(perm[icolor][1]!=blue) continue; //C4 if(!checkCondition(perm,icolor,green,icolor,white,left)) continue; /*====End of Basic Exculision Operation====*/ for(ination=0;ination<PERM;ination++){ DBGTRACE("enter ination loop\n"); /*---------Basic Exculision Operation------*/ //C9 if(perm[ination][0]!=Norwegian) continue; //C1 if(!checkCondition(perm,ination,Englishman,icolor,red,same)) continue; /*====End of Basic Exculision Operation====*/ for(idrink=0;idrink<PERM;idrink++){ DBGTRACE("enter idrink loop\n"); /*---------Basic Exculision Operation------*/ //C8 if(perm[idrink][2]!=milk) continue; //C5 if(!checkCondition(perm,icolor,green,idrink,coffee,same)) continue; //C3 if(!checkCondition(perm,ination,Dane,idrink,tea,same)) continue; /*====End of Basic Exculision Operation====*/ for(icigar=0;icigar<PERM;icigar++){ DBGTRACE("enter icigar loop\n"); /*---------Basic Exculision Operation------*/ //C7 if(!checkCondition(perm,icolor,yellow,icigar,Dunhill,same)) continue; //C11 if(!checkCondition(perm,idrink,bier,icigar,BlueMaster,same)) continue; //C13 if(!checkCondition(perm,ination,German,icigar,Prince,same)) continue; /*====End of Basic Exculision Operation====*/ for(ipet=0;ipet<PERM;ipet++){ int index[5]; loopcounter++; DBGTRACE("loopcounter:%d\n",loopcounter); //C6 if(!checkCondition(perm,icigar,PallMall,ipet,birds,same)) continue; //C2 if(!checkCondition(perm,ination,Swede,ipet,dogs,same)) continue; //C10 if(!checkCondition(perm,icigar,Blend,ipet,cats,neighbor)) continue; //C12 if(!checkCondition(perm,ipet,horses,icigar,Dunhill,neighbor)) continue; //C15 if(!checkCondition(perm,icigar,Blend,idrink,water,neighbor)) continue; /*=================================================*/ //If we reach here,the final results has been found. //Output the results and return. DBGTRACE("We have found the correct case using times:%d\n",loopcounter); index[0]=icolor; index[1]=ination; index[2]=idrink; index[3]=icigar; index[4]=ipet; for(i=0;i<COL;i++){ for(j=0;j<COL;j++) array[i][j]=perm[index[i]][j]; } //Call function to format the output. dispalyresult(array); return 0; } } } } } return 0; } static int genperm(char perm[PERM][COL],int loopcnt) { static int rowcnt=0; //Will cause error when called second time. static char column[COL]={1,2,3,4,5}; static char temp[COL]; int i,j; //DBGTRACE("genperm loopcnt=%d rowcnt=%d\n",loopcnt,rowcnt); for(i=0;i<COL;i++){ if(column[i]<0) continue; if(column[i]>0){ temp[loopcnt]=column[i]; column[i]=-1; } //End condition! if(loopcnt==4){ for(j=0;j<COL;j++) perm[rowcnt][j]=temp[j]; rowcnt++; if(rowcnt>120){ printf("Error! 5! can be only 120 cases."); exit(2); } }else{ genperm(perm,loopcnt+1); } column[i]=temp[loopcnt]; } return 0; } /* *checkCondition() function is used to check each condition from the original question. *Each conditon consists of a subject/a object and their relation. *Subject and object need key-value pairs to represent. *Relation can be an integer only. *parameters: *0)char perm[][COL]:input the permutation table. *1)int stype:subject type(including color,nation,cigar,drink,pet,position etc.) *2)int svalue:subject corresponding value. *3)int otype:object type(including color,nation,cigar,drink,pet,position etc.) *4)int ovalue:object corresponding value. *5)int relation:relation for subject and object: 1:on the same column. 2:they are neighbors. 3:subject is to the left of object. 4:subject is to the right of objct. enum Relation{same=1,neighbor,left,right} */ static inline int checkCondition(char perm[][COL],int stype,int svalue,int otype,int ovalue,enum Relation relation) { int i; //Process different relations. switch(relation){ //Two attributes are on the same column. case same: for(i=0;i<COL;i++) if(perm[stype][i]==svalue&&perm[otype][i]==ovalue) return 1; return 0; break; //They are neighbors. case neighbor: for(i=0;i<COL;i++) if(perm[stype][i]==svalue){ if(0==i&&perm[otype][1]==ovalue) return 1; else if(COL-1==i&&perm[otype][COL-2]==ovalue) return 1; else if(perm[otype][i-1]==ovalue||perm[otype][i+1]==ovalue) return 1; } return 0; break; //subject is to the left of object. case left: for(i=0;i<COL;i++) if(perm[stype][i]==svalue&&i<COL-1&&perm[otype][i+1]==ovalue) return 1; return 0; break; //subject is to the right of objct. case right: for(i=0;i<COL;i++) if(perm[stype][i]==svalue&&i>0&&perm[otype][i-1]==ovalue) return 1; return 0; break; default: printf("Error! Can't process this relation!"); exit(1); } } static int dispalyresult(char array[COL][COL]) { int i,j; int row=COL; int temp; printf("Einstein's riddle - Who has the Fish?\n"); for(i=0;i<row;i++){ printf("-------------------------\n"); for(j=0;j<COL;j++){ temp=array[i][j]-1; printf("%s\t",stringtable[i][temp]); } printf("\n"); } return 0; }