#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

#define MAX 1296
#define MAX_POSSIBLE_SCORES 14

char guesses[MAX][4];
int numValidGuesses;

void resetGuesses (void);
int calculateScore (char *a, char *b);
void markImpossible (char *guess, int score);
void pickGuess (char *guess);
void pickBestGuess (char *guess);
void play (void);
int testPlay (char *number);
void test (int numPlays);

int main (void)
{
  srand(time(NULL));
  
  play();

  return 0;
}


void play (void)
{
  int score;
  char guess[4];
  int numGuesses = 0;

  resetGuesses();

  do {
    pickGuess(guess);
    
    printf("My guess is: %d%d%d%d\n", guess[0], 
	   guess[1],
	   guess[2],
	   guess[3]);
    numGuesses++;
    printf("Enter the score: ");
    scanf("%d", &score);

    markImpossible(guess, score);

  } while (numValidGuesses > 1);

  if (numValidGuesses == 1) {
    if (score != 40) {
      numGuesses++;
    }
    
    printf("Your number is: %d%d%d%d\n",  guesses[0][0], 
	   guesses[0][1],
	   guesses[0][2],
	   guesses[0][3]);
    printf("I got it in %d guesses!\n", numGuesses);
  } else {
    printf("You are cheating. Scores are inconsistent.\n");
    printf("Game ends afer %d guesses.\n", numGuesses);
  }

}

void pickGuess (char *guess)
{
  int i;
  
  printf("There are %d possibilities left.\n", numValidGuesses);

  if (numValidGuesses <= 40) {
    printf("Your number is one of: \n");

    for (i = 0; i < numValidGuesses; i++) {
      printf("%d%d%d%d ", guesses[i][0], guesses[i][1], guesses[i][2], guesses[i][3]);

      if (!((i+1)%10)) {
	printf("\n");
      }
      
    }

    printf("\n");
  }

  if (numValidGuesses == MAX) {
    guess[0] = guess[1] = 1;
    guess[2] = guess[3] = 2;
  } else {
    pickBestGuess (guess);
  }
}


void pickBestGuess (char *guess)
{
  int i, j, k, score;
  int distribution[MAX_POSSIBLE_SCORES];
  int bestGuessIndex = 0;
  int bestGuessScore = INT_MAX;
  int currentScore = INT_MAX;

  for (i = 0; i < numValidGuesses; i++) {

    for (k = 0; k < MAX_POSSIBLE_SCORES; k++) {
      distribution[k] = 0;
    }

    for (j = 0; j < numValidGuesses; j++) {
      score = calculateScore(guesses[i], guesses[j]);
      
      switch (score) {
      case 0:
	distribution[0]++;
	break;
      case 1:
	distribution[1]++;
	break;
      case 2:
	distribution[2]++;
	break;
      case 3:
	distribution[3]++;
	break;
      case 4:
	distribution[4]++;
	break;
      case 10:
	distribution[5]++;
	break;
      case 11:
	distribution[6]++;
	break;
      case 12:
	distribution[7]++;
	break;
      case 13:
	distribution[8]++;
	break;
      case 20:
	distribution[9]++;
	break;
      case 21:
	distribution[10]++;
	break;
      case 22:
	distribution[11]++;
	break;
      case 30:
	distribution[12]++;
	break;
      case 40:
	distribution[13]++;
	break;
      default:
	printf("Error! Received a score of %d!\n", score);
	break;
      }

    }

    
    currentScore = 0;

    for (k = 1; k < MAX_POSSIBLE_SCORES; k++) {
	currentScore += distribution[k]*distribution[k];
    }
    
    if (currentScore < bestGuessScore) {
      bestGuessScore = currentScore;
      bestGuessIndex = i;
    }

  }

  for (k = 0; k < 4; k++) {
    guess[k] = guesses[bestGuessIndex][k];
  }

}


void markImpossible (char *guess, int score)
{
  int i=0, j;

  while (i < numValidGuesses) {

    if (calculateScore(guess, guesses[i]) != score) {

      for (j = 0; j < 4; j++) {
	guesses[i][j] = guesses[numValidGuesses - 1][j];
      }

      numValidGuesses--;

    } else {
      i++;
    }
  }
}

int calculateScore (char *a, char *b)
{
  char digitsA[4];
  char digitsB[4];

  int score = 0;
  int i, j;

  for (i = 0; i < 4; i++) {
    digitsA[i] = a[i];
    digitsB[i] = b[i];
  }

  /* Score for exact matches. */

  for (i = 0; i < 4; i++) {
    
    if (digitsA[i] == digitsB[i]) {
      score += 10;
      digitsA[i] = 0;
      digitsB[i] = 0;
    }
    
  }

  /* Score for incorrect place matches. */

  for (i = 0; i < 4; i++) {
    
    if (digitsA[i] <= 0) {
      continue;
    }
   
    for (j = 0; j < 4; j++) {

      if (digitsA[i] == digitsB[j]) {
	score++;
	digitsA[i] = -1;
	digitsB[j] = -1;
	break;
      }

    }
  }

  return score;
}

void resetGuesses(void)
{
  int i=0;
  int a, b, c, d;

  for (a = 1; a <= 6; a++) {
    for (b = 1; b <= 6; b++) {
      for (c = 1; c <= 6; c++) {
	for (d = 1; d <=6; d++) {
	  guesses[i][0] = a;
	  guesses[i][1] = b;
	  guesses[i][2] = c;
	  guesses[i][3] = d;
	  ++i;
	}
      }
    }
  }

  numValidGuesses = MAX;
}


void test (int numPlays) 
{
  int i, j;
  char number[4];
  int totalGuesses = 0;
  double mean;

  for (i = 0; i < numPlays; i++) {
    for (j = 0; j < 4; j++) {
      number[j] = rand() % 6 + 1;
    }

    totalGuesses += testPlay(number);

  }

  mean = (double)totalGuesses / (double)numPlays;

  printf("\nThe numbers were found in %1.2f guesses on average.\n", mean);

  return;
}

int testPlay (char *number)
{
  int score;
  char guess[4];
  int numGuesses = 0;

  resetGuesses();

  do {
    pickGuess(guess);
    printf("Best guess out of %d is %d%d%d%d\n", numValidGuesses, guess[0], guess[1], guess[2], guess[3]);

    numGuesses++;

    score = calculateScore(guess, number);

    markImpossible(guess, score);

  } while (numValidGuesses > 1);

  if (numValidGuesses == 1) {
    if (score != 40) {
      numGuesses++;
    }
    
  } else {
    printf("Error found in testing.\n");
  }

  return numGuesses;
}