cvMasterMind.cpp

cvMasterMind.cpp

/*
  cvMasterMind.cpp

  "C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\bin\Hostx64\x64\cl.exe"
   -source-charset:utf-8 -execution-charset:utf-8
   -EHsc -FecvMasterMind.exe cvMasterMind.cpp
   -IC:\OpenCV3\include
   -I..\FreeType\include
   -link
    /LIBPATH:C:\OpenCV3\x64\vc15\lib
    /LIBPATH:..\FreeType\x64
    /LIBPATH:"C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\lib\x64"
    /LIBPATH:"C:\Program Files (x86)\Windows Kits\10\Lib\10.0.17763.0\ucrt\x64"
    /LIBPATH:"C:\Program Files (x86)\Windows Kits\10\Lib\10.0.17763.0\um\x64"
    opencv_world3412.lib
    freetype.lib

  del .\cvMasterMind.obj
  cvMasterMind.exe
*/

#define UNICODE
#define _UNICODE
#include <wchar.h>

// use CV_PI instead of M_PI
// #define _USE_MATH_DEFINES
#include <opencv2/opencv.hpp>

// #include <opencv2/imgproc.hpp> // cv::FONT *, cv::LINE *, cv::FILLED

#include <iomanip>
#include <iostream>
#include <sstream>
#include <map>
#include <vector>
#include <string>

#include <stdexcept>
#include <exception>

#include <ctime>
// #include <time.h>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BASEDIR "E:\\virtual2\\SlowShutter\\"
#define V_W 640
#define V_H 480
#define OUTDIR BASEDIR
#define IM_W 640
#define IM_H 480

#define BASECOUNT 40000
#define BREAKCOUNT 600 // when NOWAIT (600/24sec 1536KB) (save 10fps:60frms)
// #define NOWAIT // NOWAIT: <30fps, no NOWAIT: <17fps (depends on CPU)

using namespace std;

class MasterMind {
private:
  const uchar naa = -1; // sieve flag for not an answer
  const uint maxcol = 8; // oct decimal (8 colors 0-7)
  uint maxlen; // 5 (or 4) digits
  uint maxtbl;
  uint rightans;
  uchar *table;
public:
  MasterMind(uint _maxlen) : maxlen(_maxlen) {
    maxtbl = (uint)1 << (3 * maxlen); // 3 = log2(8)
    rightans = maxlen << 8; // resp 0x0P0C-0x0500 ans 0x0500 (when maxlen==5)
    table = new uchar[maxtbl];
  }

  virtual ~MasterMind(){
    if(table) delete [] table;
  }

  bool isvalid(){
    if(maxlen < 4 || maxlen > 5) return false;
    if(!table) return false;
    return true;
  }

  bool solve(){
    if(!isvalid()) return false;
    uchar *ques = new uchar[maxlen];
    if(!ques) return false;
    uint reac, count;
    memset(table, 0, maxtbl);
    int tbladr = first_question();
    while((reac = reaction(adr2str(tbladr % maxtbl, ques))) != rightans){
      switch(count = remake_table(ques, reac)){
      case 0: fputs("There is no possible answer.\n", stdout); break;
      case 1: fputs("The answer should be ", stdout); break;
      default: fprintf(stdout, "There are %d candidates in my mind.\n", count);
      }
#if 0
      if((tbladr = next_question()) < 0) break;
#else
      tbladr = next_question();
#endif
    }
    fprintf(stdout, "The answer is [%.*s]\n", maxlen, ques);
    if(ques) delete [] ques;
    return true;
  }

  uint reaction(uchar *q){
    uint reac;
    fprintf(stdout, "%.*s -? (PPCC) \a", maxlen, q);
#if 0
    fscanf(stdin, "%x", &reac);
#else
    while(1){
      char buf[6]; // >= 4+2 ('0500' + '\n' + '\0')
      if(!fgets(buf, sizeof(buf), stdin)) return rightans;
      uint last = strlen(buf) - 1;
      if(buf[last] == 0x0a || buf[last] == 0x0d) buf[last] = '\0';
      if(strlen(buf) != sizeof(buf) - 2){
        fflush(stdin);
        fputs("(Enter just 4 characters.) \a", stderr);
        continue;
      }
      if(buf[0] != '0' || buf[2] != '0'){
        fputs("(0P0C) \a", stderr);
        continue;
      }
      if(buf[1] < '0' || buf[1] > '7' || buf[3] < '0' || buf[3] > '7'){
        fputs("(P or C must be a number 0-7.) \a", stderr);
        continue;
      }
      sscanf(buf, "%x", &reac);
      if(reac < 0 || reac > rightans){
        fprintf(stderr, "(PPCC must be in 0000-%04x.) \a", rightans);
        continue;
      }
      if((reac >> 8) + (reac & 0x00ff) > maxlen){
        fputs("(PP + CC must be in 00-05.) \a", stderr);
        continue;
      }
      break;
    }
#endif
    return reac;
  }

  uint check_ans(uchar *q, uchar *a){
    uchar *cond = new uchar[maxlen];
    if(!cond) return 0;
    for(int i = 0; i < maxlen; ++i) cond[i] = a[i] == q[i] ? 1 : 0;
    for(int i = 0; i < maxlen; ++i)
      if(cond[i] != 1)
        for(int j = 0; j < maxlen; ++j)
          if(!cond[j] && a[i] == q[j]){ cond[j] = 2; break; }
    uint high = 0, low = 0;
    for(int i = 0; i < maxlen; ++i)
      if(cond[i] == 1) ++high; else if(cond[i] == 2) ++low;
    if(cond) delete [] cond;
    return (high << 8) | low; // ans 0x0500 (when maxlen==5)
  }

  uint remake_table(uchar *q, uint reac){
    uint count = 0;
    uchar *ans = new uchar[maxlen];
    if(!ans) return count;
    for(uint tbladr = 0; tbladr < maxtbl; ++tbladr)
      if(table[tbladr] != naa)
        if(check_ans(q, adr2str(tbladr, ans)) != reac) table[tbladr] = naa;
        else ++count;
    if(ans) delete [] ans;
    return count;
  }

  uchar *adr2str(uint tbladr, uchar *q){
    for(int i = 0; i < maxlen; ++i) q[i] = adr2chr(tbladr, i);
    return q;
  }

  uchar adr2chr(uint tbladr, int num){
    return (uchar)((tbladr >> (3 * (maxlen - 1 - num))) & 0x07) + '0';
  }

  int first_question(){
#if 0
    return 012345; // 5 digits oct decimal (8 colors 0-7)
#else
    srand((unsigned)time(NULL));
    for(int i = rand() % maxlen; i-- >= 0; ){} // dummy loop
    return rand();
#endif
  }

  int next_question(){
    int tbladr;
#if 0
    for(tbladr = 0; tbladr < maxtbl; ++tbladr) if(table[tbladr] != naa) break;
#else
    for(tbladr = maxtbl; --tbladr >= 0; ) if(table[tbladr] != naa) break;
#endif
    return tbladr;
  }
};

int main(int ac, char **av)
{
  fprintf(stdout, "sizeof(size_t): %zu\n", sizeof(size_t));

  MasterMind mm(5);
  if(!mm.solve()) fprintf(stdout, "Can not solved.\n");
  fprintf(stdout, "done.\n");
  return 0;
}