Programming Forums

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   Software Design and Algorithms (http://www.programmingforums.org/forum64.html)
-   -   Mastermind Algorithm (http://www.programmingforums.org/showthread.php?t=14713)

Sane Dec 8th, 2007 3:23 PM

Mastermind Algorithm
 
I stumbled across a very difficult programming challenge.

The challenge is... given a set of clues and results from the game "Mastermind", determine the answer, and whether or not there's many or no possible answers.

For example:

:

9793 0/1
2384 0/2
6264 0/1
3383 1/0
2795 0/0
0218 1/0


The number 3411 is the only one that satisfies the rules.

An explanation of the challenge, and the rules of Mastermind are here:
http://cemc.math.uwaterloo.ca/ccc/1996/21b-prob.html

Now, it's not a difficult challenge at all if you brute force it. Go through every number from 0000 to 9999 and see which ones satisfy all of the clues.

But... that's a terribly ugly algorithm. Very bad complexity. There must be a way to deduce an answer more logically? Thinking about it sends my brain in wild directions though. Seems very difficult.

Have any ideas?

This is my brute force method:

safe.in
:

4
6
9793 0/1
2384 0/2
6264 0/1
3383 1/0
2795 0/0
0218 1/0
1
1234 4/0
1
1234 2/2
2
6428 3/0
1357 3/0


1996_2.1b.c
:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. void isMatch(char *with, char *against, int *r_1, int *r_2) {
  5.     int i, j;
  6.     *r_1 = 0;
  7.     *r_2 = 0;
  8.     int used[4];
  9.     int matched[4];
  10.  
  11.     for (i=0; i<4; i++)
  12.         if (with[i] == against[i]) {
  13.             (*r_1)++;
  14.             used[i] = 1; matched[i] = 1;
  15.         }
  16.         else {
  17.             used[i] = 0; matched[i] = 0;
  18.         }
  19.  
  20.     for (i=0; i<4; i++)
  21.         for (j=0; j<4; j++)
  22.             if (i!=j && !matched[j] && !used[i] && with[i] == against[j]) {
  23.                 // used[i] = 1; // Redundant once we break;
  24.                 matched[j] = 1;
  25.                 (*r_2)++;
  26.                 break;
  27.             }
  28. }
  29.  
  30. int main() {
  31.     int cases, n, i, r_1, r_2, end;
  32.     char against[10][5];
  33.     char with[5], hasMatch[5];
  34.     int exact[10], moved[10];
  35.     with[4] = 0;
  36.  
  37.     freopen("safe.in", "rt", stdin);
  38.     freopen("safe.out", "wt", stdout);
  39.  
  40.     scanf("%d\n", &cases);
  41.     while (cases--) {
  42.         scanf("%d\n", &n);
  43.         for (i=0; i<n; i++) scanf("%s %d/%d", against[i], &exact[i], &moved[i]);
  44.  
  45.         hasMatch[0] = 0;
  46.         end = 0;
  47.  
  48.         for (with[0]='0'; with[0]<='9' && !end; with[0]++) {
  49.         for (with[1]='0'; with[1]<='9' && !end; with[1]++) {
  50.         for (with[2]='0'; with[2]<='9' && !end; with[2]++) {
  51.         for (with[3]='0'; with[3]<='9' && !end; with[3]++) {
  52.  
  53.                 for (i=0; i<n; i++) {
  54.                     isMatch(with, against[i], &r_1, &r_2);
  55.                     if (exact[i] != r_1 || moved[i] != r_2) {
  56.                         i--; break;
  57.                     }
  58.                 }
  59.  
  60.                 if (i==n) {
  61.                     if (hasMatch[0])
  62.                         end = 1; // already a match
  63.                     else
  64.                         strcpy(hasMatch, with); // new match
  65.                 }
  66.  
  67.         }
  68.         }
  69.         }
  70.         }
  71.  
  72.         if (end)
  73.             printf("indeterminate\n");
  74.         else if (hasMatch[0])
  75.             printf("%s\n", hasMatch);
  76.         else
  77.             printf("impossible\n");
  78.     }
  79.  
  80.     return 0;
  81. }


safe.out
:

3411
1234
indeterminate
impossible


InfiNate Dec 8th, 2007 4:22 PM

Re: Mastermind Algorithm
 
Very fun problem. My first thoughts at a more efficient solution were to analyze the clues and eliminate possible numbers from the solution, as well as to determine any correct numbers.

In the 1st example you can deduce that the correct solution is 3411 using only the clues given.

9793 0/1
2384 0/2
6264 0/1
3383 1/0
2795 0/00218 1/0

Ok, this may get messy.

Possibly in solution: {0,1,2,3,4,5,6,7,8,9}

clue 5 eliminates 2,5,7,9 from the solution.

Possibly in solution: {0,1,3,4,6,8}

Now clue 1 tells us 3 is definitely in the solution. In comparing clue 1 and clue 4 we see that 3 cant be in the last spot, and comparing clue 2 with clue 4, 3 cannot be in the 2nd spot. Also, 8 cannot be in the 3rd spot using clues 2 and 4.
Thus, 3 must be in the 1st spot using clue 4.

SOLUTION: 3xxx

clue 3 tells us that there is only one 3 in the solution, so we eliminate it from the list, clue 3 also eliminates 8 as a possible answer.

Possibly in solution: {0,1,4,6}

Now, clue 2 tells us 4 is in the solution, but this eliminates 6 from the possible solutions.

For sure in solution: {4}
Possibly in solution: {0,1,4}

Clue 6 tells us 1 goes in spot 3, and also eliminates 0 from the possible solutions.

SOLUTION: 3x1x
For sure in solution: {4}
Possibly in solution: {1,4}

Using clue 2 or 3, we know 4 cannot go in the last column so it must go in the 2nd.

SOLUTION: 341x
Possibly in solution {1,4}

Again, 4 cannot go in the last column.. so 1 must.

SOLUTION 3411

That was really messy and still doesn't provide a good enough approach for an algorithm.

From stepping through that I think a good approach to start with would be to look at the clues with 0/0 and eliminate all those numbers first.
Next looking for rows that have 1/* or 2/*, etc. In those rows see if you can eliminate any possibilities by first checking your possible number list, and then by using other clues. The clues you want to check are ones with that have a same number in the same column.

I wouldn't want to write this algorithm, and since your doing this for the CCC I would just stick with the brute force myself. Let me know if I mess contains any mistakes or if you get anything out of it.

InfiNate Dec 8th, 2007 4:27 PM

Re: Mastermind Algorithm
 
I should add, its very easy to look for 0/0 clues, eliminate those numbers, then iterate through possible solutions using your algorithm.

Sane Dec 8th, 2007 4:44 PM

Re: Mastermind Algorithm
 
Given that this is one of three problems (all about as hard) that need to be written in less than 3 hours (I think)... is it even possible to write a logical algorithm for this?

The way you logically deduced it is very good. It just seems extremely hard to implement swiftly, especially in a language that's not so abstract about manipulating datatypes.

InfiNate Dec 8th, 2007 4:50 PM

Re: Mastermind Algorithm
 
How is the CCC judged? With a strict time limit I would not try to write this algorithm. If you get extra points for creativity or efficiency or anything else I might include the quick check for 0/0 clues to just eliminate those numbers and lessen the number of solutions to iterate through.

Sane Dec 8th, 2007 4:55 PM

Re: Mastermind Algorithm
 
Since this is a stage 2 question, it's between a limited number of top tier programmers. It's judged on complexity, efficiency-- all that jazz.

And that sounds like a good suggestion. Thanks.

InfiNate Dec 8th, 2007 5:12 PM

Re: Mastermind Algorithm
 
Definitely add something into the bruteforce approach then. I'm sure there will be a lot of quality programmers in this contest and you know they will all be trying to improve their algorithms as well. Just make sure you can get a solution down for every problem before you concern yourself with efficiency.

These problems are pretty fun, be sure to ask if you get stuck on anything else.

Sane Dec 8th, 2007 6:08 PM

Re: Mastermind Algorithm
 
Great, okay. I have another one you might find interesting. I won't make another thread for it though.

http://cemc.math.uwaterloo.ca/ccc/1996/21c-prob.html

The reason I most find it interesting, is I think mine is better than the suggested solution. His makes a 32/32 array of all the pixels, and then counts how many filled up.

I think my solution is optimal, considering it implicitely interprets the string as a tree, does not muck around with any datatype conversions, and only traverses each string a maximum of one time.

The problem is it's really messy. And I kind of hacked around to add the two trees together.

But messiness aside... it's quite spiffy I'd say.

quad.in
:

3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe


1996_2.1c.c
:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. char i_pre[50], j_pre[50], blank_pre[50] = {};
  6.  
  7. int depthToPixels(int depth) {
  8.     // 0 depth is 1024, 1 depth is 256 ... 8 depth is 1
  9.     int pixels;
  10.     pixels = 1024;
  11.     while (depth--)
  12.         pixels /= 4;
  13.     return pixels;
  14. }
  15.  
  16. void count(char *i_pre, char *j_pre, int *i, int *j, int depth, int *blacks, int add) {
  17.     int leaves, temp, doAdd;
  18.     if (!depth) leaves = 1;
  19.     else {
  20.                 leaves = 4;
  21.                 (*i)++;
  22.                 (*j)++;
  23.     }
  24.     while (leaves --) {
  25.         //printf("[%d] %d (%d->%c, %d->%c)\n", depth, add, *i, i_pre[*i], *j, j_pre[*j]);
  26.         if (add && i_pre[*i] == 'f' || j_pre[*j] == 'f') {
  27.             (*blacks) += depthToPixels(depth);
  28.         }
  29.         if (i_pre[*i] == 'p' && j_pre[*j] == 'p') // Traverse both
  30.             count(i_pre, j_pre, i, j, depth+1, blacks, 1);
  31.         else if (i_pre[*i] == 'p') { // Traverse only i_pre
  32.             doAdd = 0;                      // j_pre's full node takes precendence OR
  33.             if (j_pre[*j] == 'e') doAdd = 1; // i_pre's child is added to j_pre's empty node
  34.             temp = *j; /* Save */
  35.             count(i_pre, blank_pre, i, j, depth+1, blacks, doAdd);
  36.             *j = temp+1; /* Restore */
  37.         }
  38.         else if (j_pre[*j] == 'p') { // Traverse only j_pre
  39.             doAdd = 0;                      // i_pre's full node takes precendence OR
  40.             if (i_pre[*i] == 'e') doAdd = 1; // j_pre's child is added to i_pre's empty node
  41.             temp = *i; /* Save */
  42.             count(blank_pre, j_pre, i, j, depth+1, blacks, doAdd);
  43.             *i = temp+1; /* Restore */
  44.         }
  45.         else {
  46.             (*i) ++;
  47.             (*j) ++;
  48.         }
  49.     }
  50. }
  51.  
  52. int main() {
  53.     int cases, sum, i=0, j=0;
  54.  
  55.     freopen("quad.in", "rt", stdin);
  56.     freopen("quad.out", "wt", stdout);
  57.  
  58.     scanf("%d\n", &cases);
  59.  
  60.     while (cases--) {
  61.         scanf("%s\n", i_pre);
  62.         scanf("%s\n", j_pre);
  63.         i=0, j=0, sum = 0;
  64.         count(i_pre, j_pre, &i, &j, 0, &sum, 1)
  65.         printf("There are %d black pixels.\n", sum);
  66.     }
  67.  
  68.     return 0;
  69. }


quad.out
:

There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.


InfiNate Dec 8th, 2007 10:57 PM

Re: Mastermind Algorithm
 
I'm actually surprised that their model solution was done that way. Traversing the quadtree's simultaneously and summing as you go seemed like the obvious approach.

I like your solution more than theirs, nice work.

InfiNate Dec 8th, 2007 11:00 PM

Re: Mastermind Algorithm
 
I should start coding some of these problems to get ready for next school term. My last 4 months have been spent at a company coding UI stuff in C#, and doing this kind of stuff would certainly help for the algorithms course I'm taking next term. Send me a pm if you want to work on anything together.


All times are GMT -5. The time now is 3:40 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC