#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define GAME_MAX (5)
#define BUFFER_SIZE (4096)
void init(int com[]); //コンピュータの手を初期化する関数
void input(int man[]); //プレーヤーの答えを入力する関数
int judge(int r[],int q[]);//hitとblowを2桁の整数で返す(1hit2blowなら12)
int resolver(int man_r[]);
int choice(int rgroup[7*8*9*10][5]);
int man_resolve(void);
/* 性能評価テストをするかどうかのフラグ */
int G_test;

main(int argc,char **argv){
  int i,j,k,l; //カウンタ
  int man_r[4]; //プレイヤーの答えを格納
  int man_num[4]; //プレイヤーの手を格納
  int try; //プレイヤーの試行回数
  int hit; //ヒットの数
  int try_num[GAME_MAX]; //プレイヤーの試行回数
  int q_num[GAME_MAX];
  int p_win=0;
  int c_win=0;
  G_test = 0;

  /* 性能評価のためのテストモード */
  if(argc > 1 && strcmp(argv[1],"test") == 0){
    int sum = 0;
    int n0,n1,n2,n3;
    int tmp,bunpu[12];
    G_test = 1;
    for(i=0;i<12;i++) bunpu[i] = 0;
    for(i=0;i<9877;i++){
      n0=(int)(i/1000);
      n1=(int)(i/100 - n0*10);
      n2=(int)(i/10 -n0*100 -n1*10);
      n3=(int)(i - n0*1000 -n1*100 -n2*10);
      if(n0!=n1 && n0!=n1 && n0!=n2 && n0!=n3 
                && n1!=n2 && n1!=n3 && n2!=n3){
                      man_r[0]=n0;
                      man_r[1]=n1;
                      man_r[2]=n2;
                      man_r[3]=n3;
                      tmp = resolver(man_r);
                      bunpu[tmp-1]++;
                      sum += tmp;
      }
    }
    for(i = 0;i<12;i++) printf("質問回数%d回:%d\n",i+1,bunpu[i]);
    printf("平均質問回数:%f\n",sum/5040.0);
    exit(0);
  }
  for(i=0;i<GAME_MAX;i++) try_num[i] = q_num[i] = 0;

  /* 乱数のシードを時刻をもとにここで設定 */
  srand(time(NULL));

  for(i=0;i<GAME_MAX;i++){
    printf("あなたが答える番です．\n");
    try_num[i]=man_resolve();
    printf("コンピュータが答える番です．\n");
    input(man_r);
    q_num[i]=resolver(man_r);
    if(try_num[i] < q_num[i]){
      printf("あなたの勝ちです．\n");
      p_win++;
    }else if(try_num[i] == q_num[i]){
      printf("引き分けです．\n");
    }else{
      printf("コンピュータの勝ちです．\n");
      c_win++;
    }
    k=0;
    l=0;
    for(j=0;j<=i;j++){
      k+=try_num[j]; //プレイヤーの合計質問回数
      l+=q_num[j]; //コンピュータの合計質問回数
    }
    printf("********************\nゲーム成績\n");
    printf("勝敗%d勝%d敗%d分\n",p_win,c_win,i-p_win-c_win+1);
    printf("平均の質問回数\n");
    printf("プレイヤー:%.2f回\nコンピュータ:%.2f回\n********************\n",(double) k/(i+1),(double) l/(i+1));
  }
  return;
}

void init(int com[]){ //引数はコンピュータの手の配列
  int r; //乱数を格納
  r=(int) ((double)rand()*10000/RAND_MAX);
  /* 各桁の数字を配列に代入する */
  com[0]=(int) (r/1000);
  com[1]=(int) (r/100 - com[0]*10);
  com[2]=(int) (r/10 - com[0]*100 - com[1]*10);
  com[3]=(int) (r - com[0]*1000 - com[1]*100 - com[2]*10);
  /* 桁ごとに異なる数にならなかったらやり直す */
  if(com[0]==com[1] || com[0]==com[2] || com[0]==com[3] 
         || com[1]==com[2] || com[1]==com[3] || com[2]==com[3]){
    init(com);
  }
}

/* hit&blowに使う4桁の数を入力する関数 */
void input(int man[]){ 
  char buffer[BUFFER_SIZE];
  int n = 0; //プレイヤーが入力した数を格納
  while(n==0){
    printf("４桁の数字を入力してください\n");
    fgets(buffer, BUFFER_SIZE -1, stdin);
    n = atoi(buffer);
    if(10000 < n) n = 0;
  }
  man[0]=(int)(n/1000);
  man[1]=(int)(n/100-man[0]*10);
  man[2]=(int)(n/10-man[0]*100-man[1]*10);
  man[3]=(int)(n-man[0]*1000-man[1]*100-man[2]*10);
  if(!(man[0]!=man[1] && man[0]!=man[2] && man[0]!=man[3] 
         && man[1]!=man[2] && man[1]!=man[3] && man[2]!=man[3])){
             printf("各桁は異ならなければなりません．\n");
             input(man);
  }
  if(man[0]>9){
    printf("4桁の数でなければなりません．");
    input(man);
  }
}

/* hitとblowを判定する */
int judge(int r[],int q[]){
  int i,j;
  int hit=0;
  int blow=0;
  for(i=0; i<4; i++)
    for(j=0; j<4; j++)
      if(r[i]==q[j]) 
         if(i==j) hit++;
	     else blow++;
  return hit*10 + blow;
}

/* 計算機がhit&blowを解く部分 */
int resolver(int man_r[]){
  int try_num=0; //質問の回数をカウント
  int rgroup[10*9*8*7][5];
  int i,j=0;
  int n0,n1,n2,n3;
  int com[4];
  int tmp;
  int hit=0,blow=0;
  int h,b;
  int next_q;
  /* 配列rgroupに，問題のルール上合法的な解の候補をすべて登録する */
  for(i=0;i<9877;i++){
    n0=(int)(i/1000);
    n1=(int)(i/100 - n0*10);
    n2=(int)(i/10 -n0*100 -n1*10);
    n3=(int)(i - n0*1000 -n1*100 -n2*10);
    if(n0!=n1 && n0!=n1 && n0!=n2 && n0!=n3 
              && n1!=n2 && n1!=n3 && n2!=n3){
      rgroup[j][0]=n0;
      rgroup[j][1]=n1;
      rgroup[j][2]=n2;
      rgroup[j][3]=n3;
      rgroup[j][4]=0;		/* 可能性のフラグ，-１ならもう排除されている */
      j++;
    }
  }
  if(G_test == 0){
    /* 最初のtryはただの当てずっぽう */
    init(com);
  }else{
    /* テストの時は最初のtryは固定 */
    com[0] = 0;
    com[1] = 1;
    com[2] = 2;
    com[3] = 3;
  }
  while(hit<4){
    printf("コンピュータの手は%d%d%d%d\n",
                 com[0],com[1],com[2],com[3]);
    tmp = judge(man_r,com);
    blow = tmp % 10;
    hit = tmp / 10;
    try_num++;
    printf("Hit=%d,Blow=%d\n",hit,blow);
    /* 質問の結果を見て，全候補からその結果を返さない候補を除外する． */
    for(i=0;i<5040;i++){
      if(rgroup[i][4]!=-1){
          tmp = judge(com,rgroup[i]);
          h = tmp /10;
          b = tmp % 10;
          if(hit!=h || blow!=b)rgroup[i][4]=-1;
      }
    }
    /* 質問を生成する関数 */
    next_q=choice(rgroup);
    com[0]=(int)(next_q/1000);
    com[1]=(int)(next_q/100 - com[0]*10);
    com[2]=(int)(next_q/10 -com[0]*100 -com[1]*10);
    com[3]=(int)(next_q - com[0]*1000 -com[1]*100 -com[2]*10);
  }
  printf("正解しました答えは%d%d%d%dです\n",com[0],com[1],com[2],com[3]);
  printf("質問の回数は%d回です．\n",try_num);
  return try_num;
}

/* 残った可能性から，最適な質問を導く */
/* シンプルなKnuthのHeight法を使っている */
int choice(int rgroup[10*9*8*7][5]){
  int tmp,hit=0,blow=0;
  int i,j;
  int n[4]; //評価する質問を保持
  int next_q=0; //次の質問を保持
  int f[14]; //Hit,Blow分布を保持
  int is4hit=0;
  int f_max; //現在のnに対してのfの最大値を保持
  int min=5040; //fの最大数で，これまでで最小のものを保持
  /* 質問はすでに可能性がなくなっている数も含めてすべてを試す */
  for(i=0;i<9877;i++){
    n[0]=(int)(i/1000);
    n[1]=(int)(i/100 - n[0]*10);
    n[2]=(int)(i/10 -n[0]*100 -n[1]*10);
    n[3]=(int)(i - n[0]*1000 -n[1]*100 -n[2]*10);
    for(j=0;j<14;j++) f[j]=0;
    if(n[0]!=n[1] && n[0]!=n[1] && n[0]!=n[2] && n[0]!=n[3] 
       && n[1]!=n[2] && n[1]!=n[3] && n[2]!=n[3]){
      /* まだ可能性のある数字が，それぞれの質問に対してどのような返答が帰ってくるのかを配列に計算する */
      for(j=0;j<5040;j++){
        if(rgroup[j][4]!=-1){
          tmp = judge(n,rgroup[j]);
          hit = tmp / 10;
          blow = tmp % 10;
          if(hit==0 && blow==0) f[0]++;
          else if(hit==0 && blow==1) f[1]++;
          else if(hit==0 && blow==2) f[2]++;
          else if(hit==0 && blow==3) f[3]++;
          else if(hit==0 && blow==4) f[4]++;
          else if(hit==1 && blow==0) f[5]++;
          else if(hit==1 && blow==1) f[6]++;
          else if(hit==1 && blow==2) f[7]++;
          else if(hit==1 && blow==3) f[8]++;
          else if(hit==2 && blow==0) f[9]++;
          else if(hit==2 && blow==1) f[10]++;
          else if(hit==2 && blow==2) f[11]++;
          else if(hit==3 && blow==0) f[12]++;
          else f[13]++;//4hit
        }
      }
      /* もっとも件数が多い返答を調べる */
      f_max=f[0];
      for(j=1;j<14;j++) if(f_max<f[j]) f_max=f[j];
      /* 上の件数が，すでに求まっている最小件数よりも小さければ，それを記録する */
      if(min>f_max){
        min=f_max;
        next_q=i;
        if(f[13]==0) is4hit=0;
        else is4hit=1;
        /* すでに求まっている最小件数と同じであれば，完全正解の可能性が残っているほうを採用する */
      }else if(min==f_max && is4hit==0 && f[13]==1){
        min=f_max;
        next_q=i;
        is4hit=1;
      }
    }
  }
  return next_q;
}

/* 人間がhit&blowを解く部分．返り値は解くまでに質問した回数 */
int man_resolve(){
  int try=0; //質問の回数
  int com_num[4]; //答え
  int man_num[4]; //プレイヤーの質問
  int tmp,hit,blow;
  init(com_num);
  printf("com_num:%1d%1d%1d%1d\n",
           com_num[0],com_num[1],com_num[2],com_num[3]);
  while(hit!=4){
    input(man_num);
    tmp = judge(com_num,man_num);
    hit = tmp / 10;
    blow = tmp % 10;
    printf("Hit=%d,Blow=%d\n",hit,blow);
    try++;
  }
  printf("正解！コンピュータの手は%d%d%d%dでした．\nあなたは%d回の質問で正解しました．\n",com_num[0],com_num[1],com_num[2],com_num[3],try);
  return try;
}