www.pudn.com > bingo_decipher.rar > bingo_decipher.cpp
//----------------------------------------------
// bingo_decipher.cpp- a wise computer
// assistant which helps you to get
// get the answer of bingo rapidly
//
// Version 2.0
//
// Composed by JobXu,021234,2003/5/28
// Modified by JobXu,021234,2003/6/1
//
#define SPACE 4
#define TOTAL (10*9*8*7) //all possible numbers
#define LEN sizeof(struct Record)
#define FIGURES(p) p->figure[3],p->figure[2],p->figure[1],p->figure[0]
#define PRINT_FIGURES(p) printf("%c%c%c%c",FIGURES(p)); //print out an arbitrary number
#define CONST1 7 //the most important constant in this program (=p)
#define CHANGE_FUNCTION 7
#define DEBUG 0
#define DISPLAY 0
#include
#include
#include
#include
#include
typedef enum{False,True} BOOLEAN;
struct Record
{
char figure[SPACE]; //arrange these figure as: 3,2,1,0
//three pointers of the three linked list
struct Record *possible_next;
struct Record *useful_next;
struct Record *general_next;
};
struct Record *Useful_head,*Possible_head,*General_head; //heads of linked lists
int A_response,B_response; //use "Wen Qu Xing"'s notation
int A_suppose,B_suppose;
int Round; //now in which round of guessing,use this parameter to change the judge function
int Step[]={1,6,40,320,2049,2400,10000}; //experience constant
int Multiple;
//functions about linked list
struct Record *list_creat(void);
void free_list(void);
void delete_guessed(struct Record *p);
void delete_impossible(struct Record *p);
void list_rearrange(void);
//functions about data_handling
void compare(struct Record *p,struct Record *p1);
int whole_weight(int part[SPACE+1][SPACE+1]);
int estimate_weight(struct Record *p);
struct Record *min_weight(void);
BOOLEAN handle_response(struct Record *p);
//functions about the interface
void get_response(struct Record *p);
BOOLEAN succeed(void);
void welcome(void);
void good_bye(void);
void next_page(void);
void inform_guessed(void);
struct Record *first_guess(void);
//functions about debugging
#if DEBUG
void possible_list_display(void);
void useful_list_display(void);
#endif
#ifndef TEST
void main(void)
{
struct Record *p;
BOOLEAN guess_again;
BOOLEAN found;
General_head=list_creat(); //creat linked list
Useful_head=General_head;
Possible_head=General_head;
welcome();
do
{
Round=0;
Multiple=1;
p=first_guess(); //first guess
get_response(p);
while(A_response!=SPACE) //loop until get the correct answer
{
found=handle_response(p);
if(found) //have confidence that has found the answer
{
inform_guessed();
break;
}
Round++;
Multiple*=CONST1;
p=min_weight();
get_response(p);
}
list_rearrange();
guess_again=succeed();
next_page();
}while(guess_again);
free_list();
good_bye();
}
#endif
//======================================
// this function builds up
// two linked list(but use
// the same address),one is
// the "possible right" numbers
// the other is "maybe worth to
// guess" numbers
// returns the pointer of the head
// of the lists
//======================================
struct Record *list_creat(void)
{
struct Record *head;
struct Record *p1,*p2;
char i,j,k,l; //4 figures
head=NULL;
p1=p2=(struct Record *)malloc(LEN);
//generate all numbers and put them in the linked list
for(i='0';i<='9';i++)
for(j='0';j<='9';j++)
for(k='0';k<='9';k++)
for(l='0';l<='9';l++)
if(j!=i && k!=i && k!=j && l!=i && l!=j && l!=k)
{
if(head==NULL)
head=p1;
else
{
p2->useful_next=p1;
p2->possible_next=p1;
p2->general_next=p1;
}
p1->figure[0]=i;
p1->figure[1]=j;
p1->figure[2]=k;
p1->figure[3]=l;
p2=p1;
p1=(struct Record *)malloc(LEN);
}
p2->useful_next=NULL;
p2->possible_next=NULL;
p2->general_next=NULL;
return(head);
}
#if DEBUG
//==================================
// this function is for
// debugging
//==================================
void possible_list_display(void)
{
struct Record *p;
int n=0; //total number of the list
printf("\nNow,the possible list is:\n");
p=Possible_head;
if(p==NULL)
printf("Vacant possible list!\n");
else
{
do
{
PRINT_FIGURES(p);
putchar('\t');
n++;
p=p->possible_next;
}while(p!=NULL);
}
printf("\nThe total number of possible list is %d\n",n);
}
//==================================
// this function is for
// debugging
//==================================
void useful_list_display(void)
{
struct Record *p;
int n=0; //total number of the list
printf("\nNow,the useful list is:\n");
p=Useful_head;
if(p==NULL)
printf("Vacant useful list!\n");
else
{
do
{
PRINT_FIGURES(p);
putchar('\t');
n++;
p=p->useful_next;
}while(p!=NULL);
}
printf("\nThe total number of useful list is %d\n",n);
}
#endif
//==============================
// this function frees
// the internal storage
// of the linked list
//==============================
void free_list(void)
{
struct Record *p1,*p2;
p2=General_head;
do
{
p1=p2->general_next;
free(p2);
p2=p1;
}while(p1!=NULL);
}
//======================================
// suppose p's record is correct,
// see if we input p1's record,
// A_suppose and B_suppose's value
// will be what
//======================================
void compare(struct Record *p,struct Record *p1)
{
int i,j;
int c; //c=a+b("Wen Qu Xing"'s notation
A_suppose=B_suppose=c=0;
for(i=0;ifigure[i]==p1->figure[i]) //find 'A'
A_suppose++;
for(j=0;jfigure[i]==p1->figure[j])
c++;
}
B_suppose=c-A_suppose; //find 'B'
}
//======================================
// this function calculates the
// 'weight' of an array 'part'
//======================================
int whole_weight(int part[SPACE+1][SPACE+1])
{
int a,c; //'Wen Qu Xing''s notation
int element; //element of the array 'part'
int weight=0;
int i; //use 'i' and 'stage' to construct the weight function
int stage;
for(c=0;c<=SPACE;c++)
for(a=0;a<=c;a++) //all possible choice of 'aAcC'(c=a+b)
{
#if DISPLAY
printf("%dA%dB:%d\t",a,c-a,part[a][c-a]);
#endif
//whole weight function
if(Round0;i++,stage++) //'Round' directs the entry of 'Step'
//'stage' records the weight of this 'Step'
{
element-=Step[i];
weight+=Step[i]*stage;
}
weight+=element*(stage-1);
}
else
{
if(part[a][c-a]>weight) //one guess's 'weight' is its maximum part's
weight=part[a][c-a]; //amount of elements
}
}
return(weight);
}
//======================================
// this function gets the
// 'weight' of p's 'guess'
//======================================
int estimate_weight(struct Record *p)
{
int part[SPACE+1][SPACE+1]={0};
struct Record *p1;
int weight;
//travel the possible list
p1=Possible_head;
do
{
compare(p,p1);
part[A_suppose][B_suppose]++; //add the p1's 'guess' to appropriate part
p1=p1->possible_next;
}while(p1!=NULL);
weight=whole_weight(part);
return(weight);
}
//==================================
// this function travels
// the useful list, find
// out the 'guess'(partition)
// which has minimum weight
//==================================
struct Record *min_weight(void)
{
struct Record *p;
struct Record *min_p; //pointer points to the 'minimum weight' guess
int min_weight,weight;
min_weight=estimate_weight(Useful_head);
min_p=Useful_head;
p=Useful_head->useful_next;
while(p!=NULL)
{
weight=estimate_weight(p);
if(weightuseful_next;
}
return(min_p);
}
//==================================
// delete the previous
// guessed record
//==================================
void delete_guessed(struct Record *p)
{
struct Record *p1,*p2;
p1=Useful_head;
while(p1!=p && p1->useful_next!=NULL)
{
p2=p1;
p1=p1->useful_next;
}
if(p1==p) //has found
{
if(p1==Useful_head)
Useful_head=p1->useful_next;
else
p2->useful_next=p1->useful_next;
}
}
//==================================
// delete impossible records
// from 'possible list'
//==================================
void delete_impossible(struct Record *p)
{
struct Record *p1,*p2;
p1=Possible_head;
do
{
compare(p,p1);
if(A_suppose!=A_response || B_suppose!=B_response) //p1's record should be deleted
{
if(p1==Possible_head) //p1 is the head
{
Possible_head=p1->possible_next;
p1=Possible_head;
}
else //p1 is not the head
{
p2->possible_next=p1->possible_next;
p1=p1->possible_next;
}
}
else //don't delete,simply move a step forword
{
p2=p1;
p1=p1->possible_next;
}
}while(p1!=NULL);
}
//==================================
// get user's response
//==================================
void get_response(struct Record *p)
{
printf("\nI guess:" );
PRINT_FIGURES(p);
printf("\nHow many figures are correct and in (right\\wrong) place?\n");
printf("Please tell me in the style--(right place,wrong place):");
scanf("%d,%d",&A_response,&B_response);
while(A_response+B_response>SPACE) //input wrong
{
printf("Input error,please in this style--(right place,wrong place):");
scanf("%d,%d",&A_response,&B_response);
}
}
//==================================
// handle the information
// user gave,delete the
// elements of the chains
//==================================
BOOLEAN handle_response(struct Record *p)
{
BOOLEAN found=False;
delete_guessed(p);
delete_impossible(p);
#if DEBUG
possible_list_display();
//useful_list_display();
#endif
if(Possible_head==NULL) //maybe some input is incorrect
{
printf("\nNo number conforms to you inputing!");
free_list();
getchar();
getchar();
exit(0);
}
if(Possible_head->possible_next==NULL) //only one choice
found=True;
return(found);
}
//==================================
// generate a random
// number guess first
//==================================
struct Record *first_guess(void)
{
int position;
long int u;
int i;
struct Record *p;
u=time( NULL );
u*=u;
srand( (unsigned)u ); //to increase random's sensitivity
//generate a random position in the list
position=(int)( ((double)rand()/RAND_MAX)*TOTAL );
p=Useful_head;
for(i=0;iuseful_next;
return(p); //returns the position of the list
}
//==================================
// play over,ask user
// whether he want to play
// again
//==================================
BOOLEAN succeed(void)
{
char again;
printf("\n\nDo you want to play again?(Y/N)\n");
scanf(" %c",&again);
if(again=='Y' || again=='y')
return(True);
else
return(False);
}
//==============================
// welcome interface
//==============================
void welcome(void)
{
printf("\t*********************************************************\n");
printf("\t\t Welcome to use the software!\n\n");
printf("\t\t\t Version 1.0\n");
printf("\t\t Composed by JobXu,021234,2003/5/28\n");
printf("\t*********************************************************\n");
}
void next_page(void)
{
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
}
void good_bye(void)
{
printf("Thank you to use this software!\n\n");
printf("Press any key to continue...");
_getch();
}
void inform_guessed(void)
{
printf("\nI've got the number!");
printf(" It must be: ");
PRINT_FIGURES(Possible_head);
}
//======================================
// this function rearranges the
// linked list
//======================================
void list_rearrange(void)
{
struct Record *p;
//conform the useful list and the possible list
//to the general list
Useful_head=General_head;
Possible_head=General_head;
p=General_head;
do
{
p->possible_next=p->general_next;
p->useful_next=p->general_next;
p=p->general_next;
}while(p!=NULL);
}