#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Bob Weems - August 1994, derived from original Mastermind code */
/* Plays Super Mastermind - Available at most toy stores */
/* Uses move elimination + probability notions to find
   a move that is good on average */
/* Two-move openings are taken from The Official Mastermind Handbook
   by Leslie H. Alt, Signet, 1976, pp. 64-66 */

/* "xx" is for a blank in a guess, but not in hidden code */
char *color[9]={"bu","gn","yw","rd","bk","wh","or","bn","xx"};
/* opening1 contains patterns for first guess by program
   corresponding position in opening2 contains pattern for
   second guess.  The negative values must be instantiated (randomly).
   The 8s correspond to blanks (unused positions).
*/ 
int opening1[7][5]={{-6,-1,-2,-3,-4},{-6,-7,-7,-8,-8},
                    {-4,-5,-6,-7,-8},{-6,-7,-8,-1,-2},
                    {-5,-5,-6,-7,-8},{-5,-6,-7,-8,8},
                    {-6,-6,-6,-7,-7}};
int opening2[7][5]={{-1,-2,-3,-4,-5},{-1,-2,-3,-4,-5},
                    {-1,-1,-2,-2,-3},{-1,-2,-3,-4,-5},
                    {-1,-2,-3,-4,-4},{-1,-2,-3,-4,8},
                    {-1,-2,-3,-4,-5}};
/* kpcMap is to avoid wasting space in keyPegCounts when
   recording how many uneliminated moves will get key pegs in
   a particular way.  The first subscript corresponds to the
   number of black pegs, the second subscript to the number of
   white pegs.  Thus, if we have 3 black key pegs and 2 white key
   pegs, kpcMap takes us to position 17 for the second subscript
   of keyPegCounts.  Entries with -1 should NEVER be accessed,
   since they correspond to impossible key peg situations. */
int kpcMap[5][6]={{0,1,2,3,4,5},{6,7,8,9,10,-1},{11,12,13,14,-1,-1},
                  {15,16,17,-1,-1,-1},{18,-1,-1,-1,-1,-1}};
/*inverses of kpcMap*/
int inverseKPCmapBlack[19]={0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,3,3,3,4};
int inverseKPCmapWhite[19]={0,1,2,3,4,5,0,1,2,3,4,0,1,2,3,0,1,2,0};
int possibleMoves[32768][5];  /* stores the uneliminated possibilities */
int numberPossibleMoves; /* number of possibleMoves entries in use */
int keyPegCounts[32768][19];  /* see description for kpcMap */

void determineKeyPegs(keyPegs1,keyPegs2,blackOut,whiteOut)
int keyPegs1[5],keyPegs2[5],*blackOut,*whiteOut;
{
/* Computes key pegs for two rows of code pegs.
   Recall that key pegging is symmetric - it does
   not matter which row is the hidden code.
   The loops are unrolled to reduce execution time by 1/2 */
int kpWork1[5],kpWork2[5];
int black,white;

black=0;
white=0;
kpWork1[0]=keyPegs1[0];
kpWork1[1]=keyPegs1[1];
kpWork1[2]=keyPegs1[2];
kpWork1[3]=keyPegs1[3];
kpWork1[4]=keyPegs1[4];
kpWork2[0]=keyPegs2[0];
kpWork2[1]=keyPegs2[1];
kpWork2[2]=keyPegs2[2];
kpWork2[3]=keyPegs2[3];
kpWork2[4]=keyPegs2[4];
if (kpWork1[0]==kpWork2[0])
{
  black=1;
  kpWork1[0]=9;
  kpWork2[0]=9;
}
if (kpWork1[1]==kpWork2[1])
{
  black++;
  kpWork1[1]=9;
  kpWork2[1]=9;
}
if (kpWork1[2]==kpWork2[2])
{
  black++;
  kpWork1[2]=9;
  kpWork2[2]=9;
}
if (kpWork1[3]==kpWork2[3])
{
  black++;
  kpWork1[3]=9;
  kpWork2[3]=9;
}
if (kpWork1[4]==kpWork2[4])
{
  black++;
  kpWork1[4]=9;
  kpWork2[4]=9;
}
if (kpWork1[0]<9)
  if (kpWork1[0]==kpWork2[1])
  {
    white++;
    kpWork2[1]=9;
  }
  else if (kpWork1[0]==kpWork2[2])
  {
    white++;
    kpWork2[2]=9;
  }
  else if (kpWork1[0]==kpWork2[3])
  {
    white++;
    kpWork2[3]=9;
  }
  else if (kpWork1[0]==kpWork2[4])
  {
    white++;
    kpWork2[4]=9;
  }
if (kpWork1[1]<9)
  if (kpWork1[1]==kpWork2[0])
  {
    white++;
    kpWork2[0]=9;
  }
  else if (kpWork1[1]==kpWork2[2])
  {
    white++;
    kpWork2[2]=9;
  }
  else if (kpWork1[1]==kpWork2[3])
  {
    white++;
    kpWork2[3]=9;
  }
  else if (kpWork1[1]==kpWork2[4])
  {
    white++;
    kpWork2[4]=9;
  }
if (kpWork1[2]<9)
  if (kpWork1[2]==kpWork2[0])
  {
    white++;
    kpWork2[0]=9;
  }
  else if (kpWork1[2]==kpWork2[1])
  {
    white++;
    kpWork2[1]=9;
  }
  else if (kpWork1[2]==kpWork2[3])
  {
    white++;
    kpWork2[3]=9;
  }
  else if (kpWork1[2]==kpWork2[4])
  {
    white++;
    kpWork2[4]=9;
  }
if (kpWork1[3]<9)
  if (kpWork1[3]==kpWork2[0])
  {
    white++;
    kpWork2[0]=9;
  }
  else if (kpWork1[3]==kpWork2[1])
  {
    white++;
    kpWork2[1]=9;
  }
  else if (kpWork1[3]==kpWork2[2])
  {
    white++;
    kpWork2[2]=9;
  }
  else if (kpWork1[3]==kpWork2[4])
  {
    white++;
    kpWork2[4]=9;
  }
if (kpWork1[4]<9)
  if (kpWork1[4]==kpWork2[0] || kpWork1[4]==kpWork2[1] ||
      kpWork1[4]==kpWork2[2] || kpWork1[4]==kpWork2[3])
    white++;
*blackOut=black;
*whiteOut=white;
}

void zeroKeyPegCounts()
{
int i,j;
for (i=0;i<numberPossibleMoves;i++)
  for (j=0;j<19;j++)
    keyPegCounts[i][j]=0;
}

int generateRandom(minRange,maxRange)
int minRange,maxRange;
{
/* returns value x in range minRange <= x <= maxRange */
return minRange+abs(random()) % (maxRange-minRange+1);
}

int eliminateMoves(guess,blackIn,whiteIn)
int guess[5];  /* program's latest guess */
int blackIn,whiteIn; /* key pegs for hidden code and guess */
{
/* Eliminates possible moves using the Fundamental Theorem
   of Mastermind:

   Definition: If x and y are two rows of code pegs, then
   #black(x,y) is the number of black key pegs (number of
   positions with an exact match) and #white(x,y) is the number
   of white key pegs (number of positions with the right color, but 
   in the wrong position, if exact matches are disregarded).

   Theorem:  Let x be the hidden code and y and z are two possible guesses.
   If y is used as a guess, then z can still be a possible guess
   only if #black(x,y)=#black(y,z) and #white(x,y)=#white(y,z). */

int i,j,k,numBlack,numWhite,movesEliminated;

j=0;
movesEliminated=0;
for (i=0;i<numberPossibleMoves;i++)
{
  determineKeyPegs(guess,possibleMoves[i],&numBlack,&numWhite);
  if (numBlack==blackIn && numWhite==whiteIn)
  {
    /* Passes the Fundamental Theorem, so keep it */
    for (k=0;k<5;k++)
      possibleMoves[j][k]=possibleMoves[i][k];
    j++;
  }
  else
    movesEliminated++;
}
/*
printf("debug - movesEliminated=%d numberPossibleMoves=%d\n",
  movesEliminated,numberPossibleMoves);
*/
return movesEliminated;
}

void checkEliminatePower()
{
int i,j,numBlack,numWhite;

for (i=0;i<numberPossibleMoves;i++)
{
/*
if (i%500==0)
printf("debug - checkEliminatePower i=%d\n",i);
*/
  for (j=0;j<i;j++)  /*Peg each move against every other move*/ 
  { /* This code used to be keyPegClassify */
    determineKeyPegs(possibleMoves[i],possibleMoves[j],&numBlack,&numWhite);
    keyPegCounts[i][kpcMap[numBlack][numWhite]]++;
    keyPegCounts[j][kpcMap[numBlack][numWhite]]++;
  }
}
}

void findBestAbility(generateOwnCode,bestGuess)
int generateOwnCode,bestGuess[5];
{
/* Determines a move that is likely to eliminate many others */
int bestPossibility;
int minKept,maxKept,newPossibility,maxMinDiff,i,j;
int pegsFromMin,numNonZeroKeyPegs;
int numberPossibleMovesWithValue,bestGuessNum;

bestPossibility=999999999;

for (i=0;i<numberPossibleMoves;i++)
{
/*
  if (i%500==0)
    printf("debug - findBestAbility i=%d\n",i);
*/
  minKept=32768;  /* Compute minimum # of possible guesses assigned
                     over the key peg situations, ignore those with 0 */
  maxKept=0;      /* Compute maximum # of possible guesses assigned
                     over the key peg situations */
  numNonZeroKeyPegs=0;  /* counts key peg situations that are
                           assigned at least one code */
  for (j=0;j<19;j++)
    if (keyPegCounts[i][j])
    {
      numNonZeroKeyPegs++;
      if (keyPegCounts[i][j]<minKept)
        minKept=keyPegCounts[i][j];
      if (keyPegCounts[i][j]>maxKept)
        maxKept=keyPegCounts[i][j];
    }
  newPossibility=minKept; /* newPossibility is the number of
                             moves that are likely to be kept,
                             we know that at least minKept
                             guesses are kept no matter what the
                             hidden code is */
  if (minKept<maxKept)    /* if minKept==maxKept, newPossibility
                             has its final value */
  {
    maxMinDiff=maxKept-minKept;  /*maximum amount for augmenting
                                   newPossibility */
    for (j=0;j<19;j++)
      if (keyPegCounts[i][j])
      {
        /* Penalize additional amount for guesses kept beyond
           the minimum */
        pegsFromMin=keyPegCounts[i][j]-minKept;
        /*Assume probability of particular key peg situation is
          keyPegCounts[i][j]/numberPossibleMoves, i.e. codemaker wants us
          to keep many potential guesses*/
        newPossibility+=pegsFromMin*keyPegCounts[i][j]/numberPossibleMoves;
      }
  }
  if (newPossibility<bestPossibility)
  {
    bestGuessNum=i;
    bestPossibility=newPossibility;
    numberPossibleMovesWithValue=1;
  }
  else if (newPossibility==bestPossibility)
  {
    /* tiebreaker among "equal" best moves */
    numberPossibleMovesWithValue++;
    if (numberPossibleMovesWithValue==
      generateRandom(1,numberPossibleMovesWithValue))
      bestGuessNum=i;
  }
}
for (i=0;i<5;i++)
  bestGuess[i]=possibleMoves[bestGuessNum][i];
if (!generateOwnCode)
{
  printf("The only key peggings allowed are:\n");
  for (i=0;i<19;i++)
    if (keyPegCounts[bestGuessNum][i])
      printf("black=%d, white=%d\n",inverseKPCmapBlack[i],
        inverseKPCmapWhite[i]);
  printf("black=5, white=0\n");
}
}

void generateRandomCode(generatedCode)
int generatedCode[5];
{
int i;

for (i=0;i<5;i++)
  generatedCode[i]=generateRandom(0,7);
}

void initializeMoves()
{
int i,j,k,l,m,p;

numberPossibleMoves=32768;
p=0;
for (i=0;i<8;i++)
  for (j=0;j<8;j++)
    for (k=0;k<8;k++)
      for (l=0;l<8;l++)
        for (m=0;m<8;m++)
        {
          possibleMoves[p][0]=i;
          possibleMoves[p][1]=j;
          possibleMoves[p][2]=k;
          possibleMoves[p][3]=l;
          possibleMoves[p][4]=m;
          p++;
        }
}

void computerCodeBreaker(generateOwnCode,openingGuess1,openingGuess2)
int generateOwnCode,openingGuess1[5],openingGuess2[5];
{
int i,j,k,l,randomInt;
int pegUsed[8];
int dummy;

for (i=0;i<8;i++)
  pegUsed[i]=0;
/* generate random to determine opening */
randomInt=generateRandom(0,6);
for (i=0;i<5;i++)
{
  openingGuess1[i]=opening1[randomInt][i];
  openingGuess2[i]=opening2[randomInt][i];
}
randomInt=0;
for (j=(-1);j>(-9);j--)
{
  while (pegUsed[randomInt])
    randomInt=generateRandom(0,7);
  for (i=0;i<5;i++)
  {
    if (openingGuess1[i]==j)
      openingGuess1[i]=randomInt;
    if (openingGuess2[i]==j)
      openingGuess2[i]=randomInt;
  }
  pegUsed[randomInt]=1;
}
/*now permute the opening - prevents codemaker from getting clever*/
for (i=0;i<25;i++)
{
  j=generateRandom(0,4);
  k=generateRandom(0,4);
  l=openingGuess1[j];
  openingGuess1[j]=openingGuess1[k];
  openingGuess1[k]=l;
  l=openingGuess2[j];
  openingGuess2[j]=openingGuess2[k];
  openingGuess2[k]=l;
}
if (!generateOwnCode)
{
  printf("Prepare your code & hit any digit + return\n");
  scanf("%d",&dummy);
}
}

void computerCodeGuessing(generateOwnCode,generatedCode,computerGuess1,
  computerGuess2,humanPointsPtr,computerPointsPtr)
int generateOwnCode,generatedCode[5],computerGuess1[5],
    computerGuess2[5];
int *humanPointsPtr,*computerPointsPtr;
{
int i,numBlack,numWhite,movesEliminated,movesRequired;
int computerGuess[5];
int secondMoveKPC[19];

initializeMoves();
movesRequired=0;
for (i=0;i<5;i++)
  computerGuess[i]=computerGuess1[i];

for (;;)
{
  for (i=0;i<5;i++)
    printf("%s ",color[computerGuess[i]]);
  printf("\n");
  if (generateOwnCode)
  {
    determineKeyPegs(generatedCode,computerGuess,&numBlack,&numWhite);
    printf("Black pegs %d White pegs %d\n",numBlack,numWhite);
  }
  else
  {
    printf("Enter key pegs black, then white\n");
    scanf("%d %d",&numBlack,&numWhite);
  }
  movesRequired++;
  if (numBlack==5)
  {
    printf("Moves required %d\n",movesRequired);
    (*humanPointsPtr)+=movesRequired;
    return;
  }
  movesEliminated=eliminateMoves(computerGuess,numBlack,
    numWhite);
  if (numberPossibleMoves==movesEliminated)
  {
    printf("Inconsistent key pegs\n3 points for me & replay\n");
    if (generateOwnCode)
      exit(0);
    (*computerPointsPtr)+=3;
    computerCodeBreaker(generateOwnCode,computerGuess1,computerGuess2);
    initializeMoves();
    movesRequired=0;
  }
  else
  {
    numberPossibleMoves-=movesEliminated;
    if (numberPossibleMoves==1)
    {
      for (i=0;i<5;i++)
        computerGuess[i]=possibleMoves[0][i];
      if (!generateOwnCode)
      {
        printf("The only key peggings allowed are:\n");
        printf("black=5, white=0\n");
      }
    }
    else if (movesRequired==1)
    {
      for (i=0;i<5;i++)
        computerGuess[i]=computerGuess2[i];
      for (i=0;i<19;i++)
        secondMoveKPC[i]=0;
      /* Determine valid key pegs for second move,
         since using checkEliminatePower is way too expensive */
      for (i=0;i<numberPossibleMoves;i++)
      {
        determineKeyPegs(computerGuess,possibleMoves[i],&numBlack,
          &numWhite);
        if (numBlack!=5)
          secondMoveKPC[kpcMap[numBlack][numWhite]]=1;
      }
      if (!generateOwnCode)
      {
        printf("The only key peggings allowed are:\n");
        for (i=0;i<19;i++)
          if (secondMoveKPC[i])
            printf("black=%d, white=%d\n",inverseKPCmapBlack[i],
             inverseKPCmapWhite[i]);
        printf("black=5, white=0\n");
      }
    }
    else
    {
      zeroKeyPegCounts();
      checkEliminatePower();
      findBestAbility(generateOwnCode,computerGuess);
    }
  }
}
}

void computerKeyPegging(generatedCode,computerPointsPtr)
int generatedCode[5],*computerPointsPtr;
{
char guess[5][3];
int guessNumeric[5];
int i,j,numBlack,numWhite,movesRequired,needGuess;

movesRequired=0;

for (;;)
{
  for (needGuess=1;needGuess;)
  {
    printf("Enter your guess\n");
    /* This should be more robust!!! */
    scanf("%s %s %s %s %s",guess[0],guess[1],guess[2],guess[3],guess[4]);
    needGuess=0;
    for (i=0;i<5;i++)
    {
      for (j=0;j<9;j++)
        if (!strcmp(guess[i],color[j]))
        {
          guessNumeric[i]=j;
          break;
        }
      if (j==9)
        needGuess=1;
    }
  }
  movesRequired++;
  determineKeyPegs(guessNumeric,generatedCode,&numBlack,&numWhite);
  if (numBlack!=5 && movesRequired==16)
  {
    printf("16 move limit reached\n");
    movesRequired=17;
    numBlack=5;
  }
  if (numBlack==5)
  {
    printf("Moves required %d\n",movesRequired);
    (*computerPointsPtr)+=movesRequired;
    return;
  }
  printf("Black pegs %d White pegs %d\n",numBlack,numWhite);
}
}

void computerCodeMaker(computerPointsPtr)
int *computerPointsPtr;
{
int generatedCode[5],computerGuess[5];

generateRandomCode(generatedCode);
computerKeyPegging(generatedCode,computerPointsPtr);
}

void playAPair(playSolitaire,generateOwnCode,
  firstPlayer,computerPointsPtr,humanPointsPtr)
int playSolitaire,generateOwnCode,firstPlayer;
int *computerPointsPtr,*humanPointsPtr;
{
int generatedCode[5],computerGuess1[5],computerGuess2[5];

if (playSolitaire)
  if (firstPlayer==1)
    computerCodeMaker(computerPointsPtr);
  else if (generateOwnCode)
  {
    generateRandomCode(generatedCode);
    computerCodeBreaker(generateOwnCode,computerGuess1,
      computerGuess2);
    computerCodeGuessing(generateOwnCode,generatedCode,computerGuess1,
      computerGuess2,humanPointsPtr,computerPointsPtr);
  }
  else
  {
    computerCodeBreaker(generateOwnCode,computerGuess1,computerGuess2);
    computerCodeGuessing(generateOwnCode,generatedCode,computerGuess1,
      computerGuess2,humanPointsPtr,computerPointsPtr);
  }
else if (firstPlayer==1)
{
  computerCodeMaker(computerPointsPtr);
  if (generateOwnCode)
    generateRandomCode(generatedCode);
  computerCodeBreaker(generateOwnCode,computerGuess1,computerGuess2);
  computerCodeGuessing(generateOwnCode,generatedCode,computerGuess1,
    computerGuess2,humanPointsPtr,computerPointsPtr);
}
else
{
  if (generateOwnCode)
    generateRandomCode(generatedCode);
  computerCodeBreaker(generateOwnCode,computerGuess1,computerGuess2);
  computerCodeGuessing(generateOwnCode,generatedCode,computerGuess1,
    computerGuess2,humanPointsPtr,computerPointsPtr);
  computerCodeMaker(computerPointsPtr);
}
}

main()
{
int playSolitaire;       /* switches */
int generateOwnCode;

int firstPlayer;
int numberOfGames,computerPoints=0,humanPoints=0;
int i;
int seed;

printf("Enter # of games\n");
scanf("%d",&numberOfGames);
printf("Enter 2 switches (solitaire & generate own code)\n");
scanf("%d%d",&playSolitaire,&generateOwnCode);
if (playSolitaire)
  printf("playing solitaire\n");
if (generateOwnCode)
  printf("generate own codes\n");

printf("Enter random seed\n");
scanf("%d",&seed);
srandom(seed);
do
{
  printf("Who goes first? 1=human 2=computer\n");
  scanf("%d",&firstPlayer);
} while (firstPlayer!=1 && firstPlayer!=2);
for (i=0;i<numberOfGames;i++)
  playAPair(playSolitaire,generateOwnCode,firstPlayer,
    &computerPoints,&humanPoints);
printf("Computer points %d Human points %d\n",computerPoints,
  humanPoints);
}