mastermind.cpp

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <cmath>

#include <chrono>

using namespace std::chrono;

/// you can add other headers as needed
/// but only headers from the standard library
/// and not the algorithm header

/// do not use using namespace std

/// functions for random number generation, do not alter the declarations
void set_random_seed();
int randn(int n);

/// you can define and use additional functions and structs,
/// add here the declarations for any other functions
/// and/or structs you wish to define and use
/// (the implementation for functions that don't belong to a struct
/// should be added after the main)
void getnthcode(int num, int length, int n, std::vector<int>& attempt);
void feedback_attempt(const std::vector<int>& temp, const std::vector<int>& attempt, int& blacktemp, int& whitetemp, int num);

/// this is the struct definition for the code maker
/// do not alter the name
struct mm_code_maker{

    /// this member function sets the values for the member data
    /// representing the length of the code
    /// and the number of symbols (the symbols will be 0 to i_num)
    /// (this should be a constructor in proper OOP but ok)
    /// do not alter this function
    void init(int i_length, int i_num){
        length = i_length;
        num = i_num;
    }

    /// this member function generates a random sequence based
    /// on the length and num parameters stored as member data
    /// do not alter this function
    void generate_sequence(){
      for(int i = 0; i < length; i++){
          sequence.push_back(randn(num));
        }
    }

    /// do not alter name and parameter list for this function
    void give_feedback(const std::vector<int>& attempt, int& black_hits, int& white_hits){
        /// write here your implementation for this function
        /// which takes in input an attempt
        /// and provides feedback in terms of black hits
        /// and white hits (see linked paper)
        black_hits = 0;
        for (int i=0; i < attempt.size(); i++) { //black hits
          if (attempt[i] == sequence[i]){
            black_hits = black_hits + 1;
          }
        }
        int min = 0;
        for (int number = 0; number <= num; number++) { //total hits
          int attempt_counter = 0;
          int sequence_counter = 0;
          for (int i=0; i < attempt.size(); i++) {
            if (attempt[i] == number){
              attempt_counter = attempt_counter + 1; // to keep count of how many 'number's there are in attempt
            }
            if (sequence[i] == number){
              sequence_counter = sequence_counter + 1; // to keep count of how many 'number's there are in sequence
            }
          }
          if (attempt_counter <= sequence_counter) {
            min = min + attempt_counter;
          }
          else if (attempt_counter > sequence_counter) {
            min = min + sequence_counter;
          }
        }
        white_hits = min - black_hits;
    }

    /// member data holding the sequence generated by generate_sequence
    /// do not alter this
    std::vector<int> sequence;

    /// member data holding the values for length of code and number of symbols
    /// do not alter these
    int length;
    int num;

    /// do not add any other member data,
    /// in particular note that any variables needed for function give_feedback
    /// need to be declared within give_feedback
    /// (they are not member data of the struct)

    /// you may add other member functions if needed
};


/// this is the struct definition for the solver, do not alter the name
struct mm_solver{

    /// this member function sets the values for the member data
    /// representing the lenght of the code
    /// and the number of symbols (the symbols will be 0 to i_num)
    /// (this should be a constructor in proper OOP but ok)
    /// do not alter the function interface (name, parameter list, void return)
    void init(int i_length, int i_num){
        length = i_length;
        num = i_num;

        /// you can include additional implementation lines here if needed
        total = std::pow(num, length);
        if (total > 17000000){
          number = 0;
          position = 0;
          temp_attempt.assign(length, 0);
        }
        else {
          for (int i = 0; i < std::pow(num, length); i++) {
            possible.push_back(i);
          }
        }
    }


    /// this member function creates an attempt to find the right code
    /// (see the other examples provided for clarifications)
    /// do not alter the function interface (name, parameter list, void return)
    void create_attempt(std::vector<int>& attempt){
        /// write your implementation here
        if (total > 17000000){
          attempt = temp_attempt;
        }
        else {
          // unsigned choice_index = randn(possible.size());
          // getnthcode(num, length, possible[choice_index], attempt);
          if (possible.size() == std::pow(num, length)){
            if (length%2 == 1){ //odd
              for (int i = 0; i < (length/2); i++){
                attempt.push_back(0);
              }
              for (int i = 0; i < (length/2); i++){
                attempt.push_back(1);
              }
              while (length > attempt.size()){
                attempt.push_back(2);
              }
            }
            else if (length%2 == 0){ //even
              for (int i = 0; i < (length/2); i++)
              attempt.push_back(0);
              for (int i = 0; i < ((length/2)-1); i++){
                attempt.push_back(1);
              }
              while (length > attempt.size()){
                attempt.push_back(2);
              }
            }
          }
          else {
            if (total < 2000){
              std::vector<bool> partstable;
              int blacktemp = 0;
              int whitetemp = 0;
              int maxparts = 0;
              int position;
              int parts;
              for(int i = 0; i < possible.size(); i++) {
              partstable.assign(std::pow((length+1), 2), false);
              parts = 0;
                for(int j = 0; j < possible.size(); j++) {
                  std::vector<int> code1;
                  std::vector<int> code2;
                  getnthcode(num, length, possible[i], code1);
                  getnthcode(num, length, possible[j], code2);
                  feedback_attempt(code1, code2, blacktemp, whitetemp, num);
                  int hash = blacktemp*(length+1)+whitetemp;
                  if (partstable[hash] == false){
                    parts++;
                    partstable[hash]= true;
                  }
                }
                  partstable.clear();
                  if (parts > maxparts){
                    maxparts = parts;
                    position = i;
                  }
              }
              getnthcode(num, length, possible[position], attempt);
            }
            else{
              unsigned choice_index = randn(possible.size());
              getnthcode(num, length, possible[choice_index], attempt);
            }
          }
        }
    }

    /// this member function acquires the feedback about a certain attempt
    /// (see the other examples provided for clarifications)
    /// do not alter the function interface (name, parameter list, void return)
    void learn(std::vector<int>& attempt, int black_hits, int white_hits) {
        /// write your implementation here
        if (total > 17000000){
          if (position == 0 && number == 0){
            prev_black = black_hits;
          }
          if (black_hits > prev_black) {
            position++;
            temp_attempt[position] = 1;
            prev_black = black_hits;
            number = 1;
          }
          else if (black_hits < prev_black) {
            temp_attempt[position] = 0;
            position++;
            temp_attempt[position] = 1;
          }
          else{
            number++;
            temp_attempt[position] = number;
            prev_black = black_hits;
          }
        }
        else {
          std::vector<int> newpossible;
          int blacktemp = 0;
          int whitetemp = 0;
          // repeat for all numbers in possible
          for (int i = 0; i < possible.size(); i++) {
            // getnthcode for number in possible
            std::vector<int> temp;
            getnthcode(num, length, possible[i], temp);
            // get feedback for that number
            feedback_attempt(temp, attempt, blacktemp, whitetemp, num);
            // compare to the get feedback for the attempt & if same get feedback
            if ((blacktemp == black_hits) && (whitetemp == white_hits)){
                // put number in newpossible vector
                newpossible.push_back(possible[i]);
            }
          }
          // put newpossible vector into possible vector
          possible = newpossible;
        }
    }

    int length;
    int num;

    /// you may add other member functions and member data as needed
    /// (keep in mind the distinction between member function variables
    /// and member data of the struct)
    std::vector<int> possible;
    long long total;
    int position;
    int number;
    int prev_black;
    std::vector<int> temp_attempt;
};

/// before the submission you need to remove the main
/// (either delete it or comment it out)
/// otherwise it will intefere with the automated testing

int main(){
    /// write the code for the main here in order to test your functions
    /// our program uses random features so we need to call the function setting a random seed
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    set_random_seed();

    float length, num, total_game = 100, total_attempt = 0, max=0;
    std::vector<int> worse;
    float average;
    std::cout << "enter length of sequence and number of possible values:" << std::endl;
    std::cin >> length >> num;

    for(int k=0; k < total_game; k++){
			std::cout << "game number: " << k << '\n';
      mm_solver solver;
      solver.init(length, num);
      mm_code_maker maker;
      maker.init(length, num);
      maker.generate_sequence();
      std::cout << "generate_sequence" << '\n';
      std::cout << "the sequence generated by the code maker was:" << std::endl;
      for(int i = 0; i < maker.sequence.size(); i++){
          std::cout << maker.sequence[i] << " ";
      }
      std::cout << std::endl;
      int black_hits=0, white_hits=0;
      int attempts_limit = 1000;
      int attempts = 0;
      while((black_hits < length) && (attempts < attempts_limit)){
          std::vector<int> attempt;
          solver.create_attempt(attempt);
          maker.give_feedback(attempt, black_hits, white_hits);
          std::cout << "attempt number " << attempts << " : " <<std::endl;
          for(int i = 0; i < attempt.size(); i++){
              std::cout << attempt[i] << " ";
          }
          std::cout << std::endl;
          std::cout << "black pegs: " << black_hits << " " << " white pegs: " << white_hits << std::endl;
          solver.learn(attempt, black_hits, white_hits);
          attempts++;
      }

      if(black_hits == length){
          std::cout << "the solver has found the sequence in " << attempts << " attempts" << std::endl;
          total_attempt = total_attempt+attempts;
      }
      else{
          std::cout << "after " << attempts << " attempts still no solution" << std::endl;
      }
      if(attempts > max){
        max = attempts;
        worse = maker.sequence;
      }
    }
    high_resolution_clock::time_point t2 = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>( t2 - t1 ).count();
    average = total_attempt/total_game;
    std::cout << "average is " << average << '\n';
    std::cout << "worst attempts: " << max << '\n';
    std::cout << "out of " << total_attempt << '\n';
    std::cout << "time elapsed:" << duration << '\n';
    std::cout << "average time per game: " << duration/total_game << '\n';
    return 0;
}

/// not a great implementation for set_random_seed and for randn;
/// if you are trying to get better results you may want to change
/// the implementation using C++11 features, see for instance
/// https://isocpp.org/files/papers/n3551.pdf
/// but don't change the interface/declaration of the functions

void set_random_seed(){
    std::srand(std::time(0));
}

int randn(int n){
    return std::rand() % n;
}

/// add here the implementation for any other functions you wish to define and use

void getnthcode(int num, int length, int n, std::vector<int>& attempt){
  //get nth code from permutationlist
  while (n > 0){
    attempt.insert(attempt.begin(), (n % num));
    n = n / num;
  }
  while (length > attempt.size()){
    attempt.insert(attempt.begin(), 0);
  }
}

void feedback_attempt(const std::vector<int>& temp, const std::vector<int>& attempt, int& blacktemp, int& whitetemp, int num){
    blacktemp = 0;
    for (int i=0; i < temp.size(); i++) { //black hits
      if (temp[i] == attempt[i]){
        blacktemp = blacktemp + 1;
      }
    }
    int min = 0;
    for (int number = 0; number <= num; number++) { //total hits
      int temp_counter = 0;
      int attempt_counter = 0;
      for (int i=0; i < temp.size(); i++) {
        if (temp[i] == number){
          temp_counter = temp_counter + 1; // to keep count of how many 'number's there are in temp
        }
        if (attempt[i] == number){
          attempt_counter = attempt_counter + 1; // to keep count of how many 'number's there are in attempt
        }
      }
      if (temp_counter <= attempt_counter) {
        min = min + temp_counter;
      }
      else if (temp_counter > attempt_counter) {
        min = min + attempt_counter;
      }
    }
    whitetemp = min - blacktemp;
}