AI for the "Bulls and Cows" game

BullsandCowsAI.cpp

#include <algorithm>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <vector>

std::string all = "0123456789";
std::random_device rd;
std::mt19937 gen(rd());
std::vector<std::string> valid;
const int trysize = 50;

bool isvalid(std::string s) {
  std::sort(s.begin(), s.end());
  for (int i = 0; i < 3; ++i) {
    if (s[i] == s[i + 1]) return false;
  }
  return true;
}

int myrand(int N) {
  std::uniform_int_distribution<int> dist(0, N);
  return dist(gen);
}

std::pair<int, int> countbullscows(const std::string& state,
                                   const std::string& guess) {
  std::pair<int, int> ret{0, 0};
  std::map<char, int> statemissing, guessmissing;
  for (int i = 0; i < state.size(); ++i) {
    if (state[i] == guess[i])
      ret.first++;
    else {
      statemissing[state[i]]++;
      guessmissing[guess[i]]++;
    }
  }
  for (auto elem : statemissing) {
    ret.second += std::min(elem.second, guessmissing[elem.first]);
  }
  return ret;
}

std::string getstring(int N, int L) {
  std::string ret = std::to_string(N);
  while (ret.size() < L) ret = "0" + ret;
  return ret;
}

class game {
 public:
  game();

  std::string randomguess();
  std::string smartguess1();
  std::string smartguess2();
  void updatepossibilities(const std::string& guess,
                           std::pair<int, int> response);
  bool impossible();

 private:
  std::vector<std::string> poss;
};

game::game() {
  poss = valid;
  gen.seed(rd());
}

std::string game::randomguess() {
  if (poss.empty()) return "";
  return poss[myrand(poss.size() - 1)];
}

std::string game::smartguess1() {
  if (poss.empty()) return "";
  if (poss.size() == valid.size()) return poss[myrand(poss.size() - 1)];

  std::string ret = poss[0];
  int best = poss.size(), lim = std::max(0, (int)poss.size() - trysize);
  for (int i = poss.size() - 1; i >= lim; --i) {
    std::swap(poss[i], poss[myrand(i)]);
    std::map<std::pair<int, int>, int> resultcount;
    int worst = 0;
    for (auto state : poss) {
      auto result = countbullscows(state, poss[i]);
      worst = std::max(worst, ++resultcount[result]);
      if (worst >= best) break;
    }
    if (worst < best) {
      best = worst;
      ret = poss[i];
    }
  }
  return ret;
}

std::string game::smartguess2() {
  if (poss.empty()) return "";
  if (poss.size() == valid.size()) return poss[myrand(poss.size() - 1)];

  std::string ret = poss[0];
  int best = poss.size() * poss.size(),
      lim = std::max(0, (int)poss.size() - trysize);
  for (int i = poss.size() - 1; i >= lim; --i) {
    std::swap(poss[i], poss[myrand(i)]);
    std::map<std::pair<int, int>, int> resultcount;
    int worst = 0;
    for (auto state : poss) {
      auto result = countbullscows(state, poss[i]);
      worst += ++resultcount[result];
      if (worst >= best) break;
    }
    if (worst < best) {
      best = worst;
      ret = poss[i];
    }
  }
  return ret;
}

void game::updatepossibilities(const std::string& guess,
                               std::pair<int, int> response) {
  for (int i = 0; i < poss.size();) {
    if (countbullscows(poss[i], guess) == response) {
      ++i;
    } else {
      swap(poss[i], poss.back());
      poss.pop_back();
    }
  }
}

bool game::impossible() { return poss.empty(); }

class adversary {
 public:
  adversary(std::string);
  std::pair<int, int> respond(const std::string&);

 private:
  std::string secret;
};

adversary::adversary(std::string secret_) : secret(secret_) {}

std::pair<int, int> adversary::respond(const std::string& guess) {
  std::pair<int, int> ret;
  return countbullscows(secret, guess);
}

int main() {
  for (int i = 0; i < 10000; ++i) {
    std::string s = getstring(i, 4);
    if (isvalid(s)) valid.push_back(s);
  }
  std::cerr << valid.size() << "\n";

  for (auto s : valid) {
    game g;
    adversary a(s);

    for (int G = 1;; ++G) {
      std::string guess = g.smartguess2();
      auto response = a.respond(guess);
      if (response == std::pair<int, int>(4, 0)) {
        std::cout << "Answer found to be " << guess << " after " << G
                  << " guesses\n";
        break;
      }
      g.updatepossibilities(guess, response);
      if (g.impossible()) {
        std::cerr << "Adversary is cheating!\n";
        break;
      }
    }
  }
  return 0;
}