1 /* ColorCode, a free MasterMind clone with built in solver
2 * Copyright (C) 2009 Dirk Laebisch
3 * http://www.laebisch.com/
4 *
5 * ColorCode is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * ColorCode is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with ColorCode. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include "ccsolver.h"
20 #include <time.h>
21 #include <iomanip>
22
23 using namespace std;
24
25 const int CCSolver::STRENGTH_LOW = 0;
26 const int CCSolver::STRENGTH_MEDIUM = 1;
27 const int CCSolver::STRENGTH_HIGH = 2;
28 const int CCSolver::STRENGTH_DYNAMIC = 3;
29
30 const int CCSolver::mFGCnts[4][9][4] = {
31 {
32 {2, 0, 0, 0},
33 {2, 0, 0, 0},
34 {1, 1, 0, 0},
35 {1, 1, 0, 0},
36 {1, 1, 0, 0},
37 {1, 1, 0, 0},
38 {1, 1, 0, 0},
39 {1, 1, 0, 0},
40 {1, 1, 0, 0}
41 },
42 {
43 {3, 0, 0, 0},
44 {2, 1, 0, 0},
45 {1, 1, 1, 0},
46 {1, 1, 1, 0},
47 {1, 1, 1, 0},
48 {1, 1, 1, 0},
49 {1, 1, 1, 0},
50 {1, 1, 1, 0},
51 {1, 1, 1, 0}
52 },
53 {
54 {3, 1, 0, 0},
55 {3, 1, 0, 0},
56 {2, 1, 1, 0},
57 {2, 2, 0, 0},
58 {2, 2, 0, 0},
59 {1, 1, 1, 1},
60 {1, 1, 1, 1},
61 {1, 1, 1, 1},
62 {1, 1, 1, 1}
63 },
64 {
65 {4, 1, 0, 0},
66 {3, 2, 0, 0},
67 {3, 1, 1, 0},
68 {2, 2, 1, 0},
69 {2, 1, 1, 1},
70 {2, 2, 1, 0},
71 {2, 1, 1, 1},
72 {2, 1, 1, 1},
73 {2, 1, 1, 1}
74 }
75 };
76
77 const int CCSolver::GAME_NOS_CNT = 66;
78
79 const int CCSolver::mGameNos[66][4] = {
80 { 2, 2, 2, 0},
81 { 6, 2, 2, 1},
82 { 12, 3, 2, 0},
83 { 21, 3, 2, 1},
84 { 33, 4, 2, 0},
85 { 49, 4, 2, 1},
86 { 69, 5, 2, 0},
87 { 94, 5, 2, 1},
88 { 124, 6, 2, 0},
89 { 160, 6, 2, 1},
90 { 202, 7, 2, 0},
91 { 251, 7, 2, 1},
92 { 307, 8, 2, 0},
93 { 371, 8, 2, 1},
94 { 443, 9, 2, 0},
95 { 524, 9, 2, 1},
96 { 614, 10, 2, 0},
97 { 714, 10, 2, 1},
98 { 722, 2, 3, 1},
99 { 728, 3, 3, 0},
100 { 755, 3, 3, 1},
101 { 779, 4, 3, 0},
102 { 843, 4, 3, 1},
103 { 903, 5, 3, 0},
104 { 1028, 5, 3, 1},
105 { 1148, 6, 3, 0},
106 { 1364, 6, 3, 1},
107 { 1574, 7, 3, 0},
108 { 1917, 7, 3, 1},
109 { 2253, 8, 3, 0},
110 { 2765, 8, 3, 1},
111 { 3269, 9, 3, 0},
112 { 3998, 9, 3, 1},
113 { 4718, 10, 3, 0},
114 { 5718, 10, 3, 1},
115 { 5734, 2, 4, 1},
116 { 5815, 3, 4, 1},
117 { 5839, 4, 4, 0},
118 { 6095, 4, 4, 1},
119 { 6215, 5, 4, 0},
120 { 6840, 5, 4, 1},
121 { 7200, 6, 4, 0},
122 { 8496, 6, 4, 1},
123 { 9336, 7, 4, 0},
124 { 11737, 7, 4, 1},
125 { 13417, 8, 4, 0},
126 { 17513, 8, 4, 1},
127 { 20537, 9, 4, 0},
128 { 27098, 9, 4, 1},
129 { 32138, 10, 4, 0},
130 { 42138, 10, 4, 1},
131 { 42170, 2, 5, 1},
132 { 42413, 3, 5, 1},
133 { 43437, 4, 5, 1},
134 { 43557, 5, 5, 0},
135 { 46682, 5, 5, 1},
136 { 47402, 6, 5, 0},
137 { 55178, 6, 5, 1},
138 { 57698, 7, 5, 0},
139 { 74505, 7, 5, 1},
140 { 81225, 8, 5, 0},
141 {113993, 8, 5, 1},
142 {129113, 9, 5, 0},
143 {188162, 9, 5, 1},
144 {218402, 10, 5, 0},
145 {318402, 10, 5, 1}
146 };
147
CCSolver(QObject * parent)148 CCSolver::CCSolver(QObject* parent) : QThread(parent)
149 {
150 mColorCnt = 0;
151 mPegCnt = 0;
152 mDoubles = -1;
153 mLevel = -1;
154 mMaxGuessCnt = 0;
155
156 mAllCnt = 0;
157 mPosCnt = 0;
158 mHistCnt = 0;
159 mGuessCnt = 0;
160 mMaxRes = 0;
161 mResCnt = 0;
162
163 mRestartCnt = 0;
164
165 mResTable = NULL;
166 mCascade = NULL;
167 mPossible = NULL;
168 mPos2AllIx = NULL;
169 mAllTable = NULL;
170 mHist = NULL;
171
172 mS = NULL;
173 mP = NULL;
174
175 mInterrupt = false;
176 }
177
~CCSolver()178 CCSolver::~CCSolver()
179 {
180 wait();
181 FreeTables();
182 }
183
GetRandGameNo(const int ccnt,const int pcnt,const int doubles) const184 int CCSolver::GetRandGameNo(const int ccnt, const int pcnt, const int doubles) const
185 {
186 int min = 0;
187 int max = 0;
188 int i;
189 for (i = 0; i < GAME_NOS_CNT; ++i)
190 {
191 if (mGameNos[i][1] == ccnt && mGameNos[i][2] == pcnt && mGameNos[i][3] == doubles)
192 {
193 max = mGameNos[i][0];
194 if (i > 0)
195 {
196 min = mGameNos[i - 1][0];
197 }
198 break;
199 }
200 }
201
202 if (max == 0)
203 {
204 return 1;
205 }
206
207 int range = max - min;
208 int rndm = (qrand() % range) + 1;
209
210 return min + rndm;
211 }
212
GetRealGameNo(const uint no) const213 int CCSolver::GetRealGameNo(const uint no) const
214 {
215 int realno = 1;
216 if (no > 0)
217 {
218 realno = no % mGameNos[GAME_NOS_CNT - 1][0];
219 }
220 return realno;
221 }
222
GetGameIxByNo(const int no) const223 int CCSolver::GetGameIxByNo(const int no) const
224 {
225 int ix = -1;
226 int i;
227 for (i = 0; i < GAME_NOS_CNT; ++i)
228 {
229 if (mGameNos[i][0] >= no)
230 {
231 ix = i;
232 break;
233 }
234 }
235
236 if (ix == -1)
237 {
238 ix = 0;
239 }
240
241 return ix;
242 }
243
GetGameByNo(const int no) const244 const int* CCSolver::GetGameByNo(const int no) const
245 {
246 int realno = GetRealGameNo(no);
247 int ix = GetGameIxByNo(realno);
248
249 return mGameNos[ix];
250 }
251
GetSolutionByNo(const uint no) const252 vector<int> CCSolver::GetSolutionByNo(const uint no) const
253 {
254 int realno = GetRealGameNo(no);
255 int gameix = GetGameIxByNo(realno);
256
257
258 if (gameix > 0)
259 {
260 realno -= mGameNos[gameix - 1][0];
261 }
262
263 vector<int> solvec;
264 int* sol = mAllTable[mPos2AllIx[realno - 1]];
265 for (int i = 0; i < mPegCnt; ++i)
266 {
267 solvec.push_back(sol[i]);
268 }
269
270 return solvec;
271 }
272
NewGame(const int ccnt,const int pcnt,const int doubles,const int level,const int gcnt)273 void CCSolver::NewGame(const int ccnt, const int pcnt, const int doubles, const int level, const int gcnt)
274 {
275 FreeTables();
276
277 mColorCnt = ccnt;
278 mPegCnt = pcnt;
279 mDoubles = doubles;
280 mLevel = level;
281 mMaxGuessCnt = gcnt;
282
283 mMaxPosCnt = 0;
284 mAllCnt = 0;
285 mPosCnt = 0;
286 mHistCnt = 0;
287 mGuessCnt = 0;
288 mMaxRes = 0;
289 mResCnt = 0;
290
291 mRestartCnt = 0;
292 mLastPosCnt = 0;
293
294 InitTables();
295 }
296
RestartGame()297 void CCSolver::RestartGame()
298 {
299 if (mGuessCnt > 0)
300 {
301 ++mRestartCnt;
302 }
303
304 for (int i = 0 ; i < mMaxGuessCnt ; ++i)
305 {
306 mHist[i] = NULL;
307 }
308
309 mGuessCnt = 0;
310 }
311
Interrupt()312 void CCSolver::Interrupt()
313 {
314 mInterrupt = true;
315 }
316
run()317 void CCSolver::run()
318 {
319 mInterrupt = false;
320 mLastGuess = Guess();
321
322 if (mLastGuess < 0 || mLastGuess >= mAllCnt)
323 {
324 ;
325 }
326 else
327 {
328 mLastPosCnt = mPosCnt;
329 }
330 }
331
GetAllCnt() const332 int CCSolver::GetAllCnt() const
333 {
334 return mAllCnt;
335 }
336
GuessIn(string str)337 void CCSolver::GuessIn(string str)
338 {
339 int ix = Row2Ix(str);
340 mHist[mGuessCnt] = new int[2];
341 mHist[mGuessCnt][0] = ix;
342 }
343
GuessIn(const vector<int> * rowsol)344 void CCSolver::GuessIn(const vector<int>* rowsol)
345 {
346 int ix = Row2Ix(rowsol);
347 mHist[mGuessCnt] = new int[2];
348 mHist[mGuessCnt][0] = ix;
349 }
350
StartGuess()351 void CCSolver::StartGuess()
352 {
353 if (mPosCnt == mLastPosCnt && (mGuessCnt > 0 || mRestartCnt > 0))
354 {
355 emit GuessDoneSignal();
356 return;
357 }
358
359 mLastGuess = -1;
360 start(QThread::NormalPriority);
361 }
362
GuessOut()363 int* CCSolver::GuessOut()
364 {
365 if (mLastGuess < 0 || mLastGuess >= mAllCnt)
366 {
367 return NULL;
368 }
369
370 return mAllTable[mLastGuess];
371 }
372
ResIn(const vector<int> * res)373 int CCSolver::ResIn(const vector<int>* res)
374 {
375 int r = 0;
376 int len = res->size();
377 int i;
378 for (i = 0; i < len; ++i)
379 {
380 if (res->at(i) == 2)
381 {
382 r += 10;
383 }
384 else if (res->at(i) == 1)
385 {
386 r += 1;
387 }
388 }
389
390 mHist[mGuessCnt][1] = r;
391 UpdPos(mHist[mGuessCnt][0], r);
392 ++mGuessCnt;
393
394 return r;
395 }
396
FreeTables()397 void CCSolver::FreeTables()
398 {
399 int i;
400
401 delete [] mPos2AllIx;
402 mPos2AllIx = NULL;
403
404 delete [] mCascade;
405 mCascade = NULL;
406
407 delete [] mPossible;
408 mPossible = NULL;
409
410 for (i = 0 ; i < mAllCnt ; ++i)
411 {
412 delete [] mAllTable[i] ;
413 }
414 delete [] mAllTable;
415 mAllTable = NULL;
416
417 for (i = 0 ; i < mMaxGuessCnt ; ++i)
418 {
419 delete [] mHist[i] ;
420 }
421
422 delete [] mHist;
423 mHist = NULL;
424
425 delete [] mResTable;
426 mResTable = NULL;
427
428 delete [] mS;
429 mS = NULL;
430
431 delete [] mP;
432 mP = NULL;
433 }
434
InitTables()435 void CCSolver::InitTables()
436 {
437 int i, j, k;
438
439 if (mDoubles != 1 && mColorCnt < mPegCnt)
440 {
441 return;
442 }
443
444 mMaxPosCnt = CalcPosCnt(mColorCnt, mPegCnt, mDoubles);
445
446 mPos2AllIx = new int [mMaxPosCnt];
447
448 mCascade = new int [mPegCnt];
449
450 for (i = 0; i < mPegCnt; ++i)
451 {
452 mCascade[i] = IntPow(mColorCnt, mPegCnt - i - 1);
453 }
454
455 mAllCnt = CalcAllCnt(mColorCnt, mPegCnt);
456
457 mAllTable = new int* [mAllCnt];
458
459 for (i = 0; i < mAllCnt; ++i)
460 {
461 mAllTable[i] = new int [mPegCnt];
462 }
463
464
465 mPossible = new int [mAllCnt];
466
467 for (i = 0; i < mAllCnt; ++i)
468 {
469 FillTable(i);
470 }
471
472 mHist = new int* [mMaxGuessCnt];
473 for (i = 0 ; i < mMaxGuessCnt ; ++i)
474 {
475 mHist[i] = NULL;
476 }
477
478 mS = new int [mColorCnt];
479 mP = new int [mColorCnt];
480
481 mMaxRes = mPegCnt * 10;
482
483 mResCnt = (IntFac(mPegCnt + 2)) / (IntFac(mPegCnt) * 2) - 1;
484
485 mResTable = new int[mResCnt];
486
487 k = 0;
488 for (i = 0; i <= mPegCnt; ++i)
489 {
490 for (j = 0; j <= mPegCnt - i; ++j, ++k)
491 {
492 if (i == mPegCnt - 1 && j == 1)
493 {
494 --k;
495 continue;
496 }
497 mResTable[k] = i * 10 + j;
498 }
499 }
500 }
501
FillTable(const int ix)502 void CCSolver::FillTable(const int ix)
503 {
504 int i;
505 int v = ix;
506 int pos = 1;
507 int j;
508
509 for (i = 0; i < mPegCnt; ++i)
510 {
511 mAllTable[ix][i] = 0;
512 }
513
514 for (i = 0; i < mPegCnt; ++i)
515 {
516 while (v >= mCascade[i])
517 {
518 ++mAllTable[ix][i];
519 v -= mCascade[i];
520 }
521 if (mDoubles != 1 && pos == 1)
522 {
523 for (j = 0; j < i; j++)
524 {
525 if (mAllTable[ix][j] == mAllTable[ix][i])
526 {
527 pos = 0;
528 break;
529 }
530 }
531 }
532 }
533
534 if (pos == 1)
535 {
536 mPos2AllIx[mPosCnt] = ix;
537 }
538 mPosCnt += pos;
539 mPossible[ix] = pos;
540 }
541
RowCmp(const int * sol,const int * pat)542 int CCSolver::RowCmp(const int* sol, const int* pat)
543 {
544 int bl = 0;
545 int wh = 0;
546 int i;
547
548 for (i = 0; i < mColorCnt; ++i)
549 {
550 mS[i] = mP[i] = 0;
551 }
552
553 for (i = 0; i < mPegCnt; ++i)
554 {
555 if (sol[i] == pat[i])
556 {
557 ++bl;
558 }
559 else
560 {
561 if (mP[sol[i]] > 0)
562 {
563 ++wh;
564 --mP[sol[i]];
565 }
566 else
567 {
568 ++mS[sol[i]];
569 }
570
571 if (mS[pat[i]] > 0)
572 {
573 ++wh;
574 --mS[pat[i]];
575 }
576 else
577 {
578 ++mP[pat[i]];
579 }
580 }
581 }
582
583 return (10 * bl + wh);
584 }
585
UpdPos(const int ix,const int res)586 void CCSolver::UpdPos(const int ix, const int res)
587 {
588 int i;
589 for (i = 0; i < mAllCnt; ++i)
590 {
591 if (!mPossible[i])
592 {
593 continue;
594 }
595
596 if (RowCmp(mAllTable[i], mAllTable[ix]) != res)
597 {
598 mPossible[i] = 0;
599 --mPosCnt;
600 }
601 }
602 }
603
FirstGuess()604 string CCSolver::FirstGuess()
605 {
606 int i, j, r;
607 int pegcnt = 0;
608 int diffcnt = 0;
609
610 const int* fg = mFGCnts[mPegCnt-2][mColorCnt-2];
611 char s[mPegCnt];
612 int t[mColorCnt];
613
614 for (i = 0; i < mColorCnt; ++i)
615 {
616 t[i] = 0;
617 }
618
619 if (mDoubles == 1)
620 {
621 for (i = 0; i < 4; ++i)
622 {
623 if (fg[i] == 0)
624 {
625 break;
626 }
627
628 do
629 {
630 r = rand() % mColorCnt;
631 }
632 while (t[r] > 0);
633 ++t[r];
634 ++diffcnt;
635 for (j = 0; j < fg[i]; ++j)
636 {
637 s[pegcnt++] = 'A' + r;
638 }
639 if (pegcnt == mPegCnt)
640 {
641 break;
642 }
643 }
644
645 if (mPegCnt > 2 && diffcnt > 1)
646 {
647 for (int i = 0; i < (mPegCnt - 1); ++i)
648 {
649 r = i + (rand() % (mPegCnt - i));
650 if (i != r)
651 {
652 char tmp = s[i];
653 s[i] = s[r];
654 s[r] = tmp;
655 }
656 }
657 }
658 }
659 else
660 {
661 for (i = 0; i < mPegCnt; ++i)
662 {
663 do
664 {
665 r = rand() % mColorCnt;
666 }
667 while (t[r] > 0);
668 ++t[r];
669 s[i] = 'A' + r;
670 }
671 }
672
673 return string(s, mPegCnt);
674 }
675
Guess()676 int CCSolver::Guess()
677 {
678 //clock_t start, finish;
679 //start = clock();
680
681 if (mLevel > STRENGTH_LOW && mGuessCnt == 0 && mRestartCnt == 0)
682 {
683 return Row2Ix(FirstGuess());
684 }
685
686 int level = mLevel;
687
688 if (level == STRENGTH_HIGH && mPosCnt > 10000)
689 {
690 level = STRENGTH_MEDIUM;
691 }
692
693 int i, j;
694
695 if (level == STRENGTH_LOW)
696 {
697 for (i = 0; i < mAllCnt; ++i)
698 {
699 if (mPossible[i])
700 {
701 break;
702 }
703 }
704 }
705 else if (level == STRENGTH_MEDIUM)
706 {
707 int m = mPosCnt >> 1;
708 for (i = 0; i < mAllCnt; ++i)
709 {
710 if (mPossible[i])
711 {
712 if (--m <= 0)
713 {
714 break;
715 }
716 }
717 }
718 }
719 else
720 {
721 // Donald E. Knuth. The Computer as Master Mind. J. Recreational Mathematics, 9 (1976-77), 1-6.
722 // Kenji Koyama, Tony W. Lai. An optimal Mastermind Strategy. J. Recreational Mathematics, 1994.
723 // we'll only take the still possible ones into account, but ...
724
725 int solix = -1;
726 int shortest = 1000000;
727 int longest;
728 int res2pos[mMaxRes];
729
730 for (j = 0; j <= mMaxRes; ++j)
731 {
732 res2pos[j] = 0;
733 }
734
735 for (i = 0; i < mAllCnt; ++i)
736 {
737 if (mInterrupt)
738 {
739 i = -1;
740 break;
741 }
742
743 if (!mPossible[i])
744 {
745 continue;
746 }
747
748 for (j = 0; j < mAllCnt; ++j)
749 {
750 if (!mPossible[j])
751 {
752 continue;
753 }
754 ++res2pos[RowCmp(mAllTable[j], mAllTable[i])];
755 }
756
757 longest = 0;
758 for (j = 0; j < mResCnt; ++j)
759 {
760 if (res2pos[mResTable[j]] > longest)
761 {
762 longest = res2pos[mResTable[j]];
763 }
764 res2pos[mResTable[j]] = 0;
765 }
766
767 if (longest < shortest)
768 {
769 shortest = longest;
770 solix = i;
771 }
772 }
773
774 i = solix;
775 }
776
777 //finish = clock();
778
779 return i;
780 }
781
RowOut(const int * r)782 string CCSolver::RowOut(const int* r)
783 {
784 char s[mPegCnt];
785
786 int i;
787 for (i = 0; i < mPegCnt; ++i)
788 {
789 s[i] = 'A' + r[i];
790 }
791
792 return string(s, mPegCnt);
793 }
794
Row2Ix(const vector<int> * v)795 int CCSolver::Row2Ix(const vector<int>* v)
796 {
797 int i;
798 int ix = 0;
799 int len = v->size();
800
801 if (len != mPegCnt)
802 {
803 return -1;
804 }
805
806 int j;
807 for (i = 0; i < mPegCnt; ++i)
808 {
809 j = v->at(i);
810 if (j >= mColorCnt)
811 {
812 ix = -1;
813 break;
814 }
815 ix += j * mCascade[i];
816 }
817
818 if (ix >= 0 && ix < mAllCnt)
819 {
820 return ix;
821 }
822
823 return -1;
824 }
825
Row2Ix(const string str)826 int CCSolver::Row2Ix(const string str)
827 {
828 int i;
829 int ix = 0;
830 int len = int(str.size());
831
832 if (len != mPegCnt)
833 {
834 return -1;
835 }
836
837 int j;
838 for (i = 0; i < mPegCnt; ++i)
839 {
840 j = toupper(int(str[i])) - 'A';
841 if (j >= mColorCnt)
842 {
843 ix = -1;
844 break;
845 }
846 ix += j * mCascade[i];
847 }
848
849 if (ix >= 0 && ix < mAllCnt)
850 {
851 return ix;
852 }
853
854 return -1;
855 }
856
IntPow(const int b,const int e) const857 int CCSolver::IntPow(const int b, const int e) const
858 {
859 int i;
860 int ret = 1;
861 for (i = 0; i < e; ++i)
862 {
863 ret *= b;
864 }
865 return ret;
866 }
867
IntFac(const int n) const868 int CCSolver::IntFac(const int n) const
869 {
870 int fac = 1;
871 int i;
872 for (i = n; i > 1; --i)
873 {
874 fac *= i;
875 }
876 return fac;
877 }
878
CalcAllCnt(const int ccnt,const int pcnt) const879 int CCSolver::CalcAllCnt(const int ccnt, const int pcnt) const
880 {
881 if (ccnt < 2 || pcnt < 2)
882 {
883 return 0;
884 }
885
886 return IntPow(ccnt, pcnt);
887 }
888
CalcPosCnt(const int ccnt,const int pcnt,const int doubles) const889 int CCSolver::CalcPosCnt(const int ccnt, const int pcnt, const int doubles) const
890 {
891 if (ccnt < 2 || pcnt < 2 || (doubles != 0 && doubles != 1))
892 {
893 return 0;
894 }
895
896 if (ccnt < pcnt && doubles == 0)
897 {
898 return 0;
899 }
900
901 if (doubles == 1)
902 {
903 return CalcAllCnt(ccnt, pcnt);
904 }
905
906 return IntFac(ccnt) / IntFac(ccnt - pcnt);
907
908 }
909