Donald E. Knuth's method to solve MasterMind Game

mastermind_solve.cpp

#include <iostream>

class solution {
 private:
  // game configs
  int positions;
  int options;
  char *secret;
  int chances;

  // structures needed
  char *set;
  int set_size;

  // private methods
  void init();
  char evaluate(char *, char *);
  void remove(char *, char);
  void move(char *, char *);
  char *minmax();
  void print(char *);

 public:
  solution() = delete;
  solution(const solution &c) = delete;
  solution(int, int, int, char *);
  ~solution();
  void solve();
};

/*
 * game constructor
 * takes input as no of holes, no of diffrent colors
 * and also the secret code
 * max holes = 8
 * max choices = 10
 * secret code must be all small latin characters
 * from a-j depending on no of choices
 */
solution::solution(int holes, int choices, int moves, char *code) {
  positions = holes < 4 ? 4 : (holes > 8 ? 8 : holes);
  options = choices < 6 ? 6 : (choices > 10 ? 10 : choices);
  chances = moves < positions ? positions : (moves > 100 ? 100 : moves);
  secret = new char[positions];
  for (int i = 0; i < positions; i++) {
    secret[i] = code[i];
  }
  init();
}

/*
 *Free Dynamic Memory
 */
solution::~solution() {
  delete set;
  delete secret;
}

/*
 * Allocate Memory
 * Building the set
 */
void solution::init() {
  int powers[positions + 1];
  powers[0] = 1;
  for (int i = 1; i <= positions; i++) {
    powers[i] = powers[i - 1] * options;
  }
  set_size = powers[positions] * positions;
  set = new char[set_size];
  char *base;
  int itercount;
  for (int i = 0; i < positions; i++) {
    for (int j = 0; j < powers[i]; j++) {
      for (int k = 0; k < options; k++) {
        base = (set + i) +
               (j * powers[positions - i] + k * powers[positions - i - 1]) *
                   positions;
        itercount = powers[positions - i - 1] * positions;
        for (int l = 0; l < itercount; l += positions) {
          base[l] = 'a' + k;
        }
      }
    }
  }
}

/*
 * evaluate two codes for score
 */
char solution::evaluate(char *guess, char *code) {
  char arr1[options] = {0};
  char arr2[options] = {0};
  char black = 0;
  char white = 0;
  for (char i = 0; i < positions; i++) {
    if (guess[i] == code[i]) black++;
    arr1[guess[i] - 'a']++;
    arr2[code[i] - 'a']++;
  }
  for (int i = 0; i < options; i++) {
    white += (arr1[i] < arr2[i] ? arr1[i] : arr2[i]);
  }
  white -= black;
  return (black * positions + white);
}

/*
 * move contents of array
 */
void solution::move(char *a, char *b) {
  for (char i = 0; i < positions; i++) {
    *(a + i) = *(b + i);
  }
}

/*
 * remove from array impossible guesses
 */
void solution::remove(char *guess, char score) {
  for (int i = 0; i < set_size; i += positions) {
    if (evaluate(guess, set + i) != score) {
      move(set + i, set + set_size - positions);
      set_size -= positions;
      i -= positions;
    }
  }
}

/*
 * use minmax to find next best guess
 */
char *solution::minmax() {
  if (set_size == positions) {
    return (set + 0);
  }
  int pos = (positions * positions) + 1;
  int count = set_size / positions;
  char score;
  char **scores = new char *[count];
  for (int i = 0; i < count; i++) {
    scores[i] = new char[pos]();
  }
  for (int i = 0; i < count; i++) {
    for (int j = i; j < count; j++) {
      score = evaluate(set + i * positions, set + j * positions);
      scores[i][score]++;
      scores[j][score]++;
    }
  }
  int max = 0;
  char *guess = nullptr;
  for (int i = 0; i < count; i++) {
    char max2 = 0;
    for (int j = 0; j < pos; j++) {
      max2 = max2 > scores[i][j] ? max2 : scores[i][j];
    }
    delete scores[i];
    if (count - (int)max2 > max) {
      guess = set + i * positions;
      max = count - (int)max2;
    }
  }
  delete scores;
  return guess;
}

/*
 * play the game
 * takes input as number of channces
 */
void solution::solve() {
  char winScore = positions * positions;
  char guess[positions];
  char score;
  char *nextBest;
  char win = 0;
  for (int i = 0; i < positions / 2; i++) {
    guess[i] = 'a';
  }
  for (int i = positions / 2; i < positions; i++) {
    guess[i] = 'b';
  }
  for (int i = 0; i < chances; i++) {
    if (set_size >= positions) {
      print(guess);
      score = evaluate(guess, secret);
      if (score == winScore) {
        win = 1;
        break;
      }
      remove(guess, score);
      nextBest = minmax();
      if (nextBest != nullptr) {
        move(guess, nextBest);
      }
    } else {
      std::cout << "Invalid Secret Given!";
      std::cout << std::endl;
      return;
    }
  }
  // Win or Not
  if (win) {
    std::cout << "You Win";
  } else {
    std::cout << "You Lose";
  }
  std::cout << std::endl;
  return;
}

/*
 * print guess
 */
void solution::print(char *s) {
  std::cout << "Guess: ";
  for (int i = 0; i < positions; i++) {
    std::cout << s[i];
  }
  std::cout << std::endl;
}

/* 
 * Example Game 
 */
int main() {
  char x[5] = {'1', '2', '3', '4', '5'};
  solution t(5, 8, 10, x);
  t.solve();
  return 0;
}