Programming Forums > Application Development > Software Design and Algorithms

Sane · Dec 8th, 2007, 3:23 PM

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:

(Toggle Plain Text)

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

(Toggle Plain Text)

1996_2.1b.c

 c Syntax (Toggle Plain Text) 
#include <stdio.h>
#include <stdlib.h>
 
void isMatch(char *with, char *against, int *r_1, int *r_2) {
    int i, j;
    *r_1 = 0;
    *r_2 = 0;
    int used[4];
    int matched[4];
 
    for (i=0; i<4; i++)
        if (with[i] == against[i]) {
            (*r_1)++;
            used[i] = 1; matched[i] = 1;
        }
        else {
            used[i] = 0; matched[i] = 0;
        }
 
    for (i=0; i<4; i++)
        for (j=0; j<4; j++)
            if (i!=j && !matched[j] && !used[i] && with[i] == against[j]) {
                // used[i] = 1; // Redundant once we break;
                matched[j] = 1;
                (*r_2)++;
                break;
            }
}
 
int main() {
    int cases, n, i, r_1, r_2, end;
    char against[10][5];
    char with[5], hasMatch[5];
    int exact[10], moved[10];
    with[4] = 0;
 
    freopen("safe.in", "rt", stdin);
    freopen("safe.out", "wt", stdout);
 
    scanf("%d\n", &cases);
    while (cases--) {
        scanf("%d\n", &n);
        for (i=0; i<n; i++) scanf("%s %d/%d", against[i], &exact[i], &moved[i]);
 
        hasMatch[0] = 0;
        end = 0;
 
        for (with[0]='0'; with[0]<='9' && !end; with[0]++) {
        for (with[1]='0'; with[1]<='9' && !end; with[1]++) {
        for (with[2]='0'; with[2]<='9' && !end; with[2]++) {
        for (with[3]='0'; with[3]<='9' && !end; with[3]++) {
 
                for (i=0; i<n; i++) {
                    isMatch(with, against[i], &r_1, &r_2);
                    if (exact[i] != r_1 || moved[i] != r_2) {
                        i--; break;
                    }
                }
 
                if (i==n) {
                    if (hasMatch[0]) 
                        end = 1; // already a match
                    else 
                        strcpy(hasMatch, with); // new match
                }
 
        }
        }
        }
        }
 
        if (end) 
            printf("indeterminate\n");
        else if (hasMatch[0])
            printf("%s\n", hasMatch);
        else
            printf("impossible\n");
    }
 
    return 0;
}
#include <stdio.h>
#include <stdlib.h>

void isMatch(char *with, char *against, int *r_1, int *r_2) {
    int i, j;
    *r_1 = 0;
    *r_2 = 0;
    int used[4];
    int matched[4];
    
    for (i=0; i<4; i++)
        if (with[i] == against[i]) {
            (*r_1)++;
            used[i] = 1; matched[i] = 1;
        }
        else {
            used[i] = 0; matched[i] = 0;
        }
    
    for (i=0; i<4; i++)
        for (j=0; j<4; j++)
            if (i!=j && !matched[j] && !used[i] && with[i] == against[j]) {
                // used[i] = 1; // Redundant once we break;
                matched[j] = 1;
                (*r_2)++;
                break;
            }
}

int main() {
    int cases, n, i, r_1, r_2, end;
    char against[10][5];
    char with[5], hasMatch[5];
    int exact[10], moved[10];
    with[4] = 0;
    
    freopen("safe.in", "rt", stdin);
    freopen("safe.out", "wt", stdout);
    
    scanf("%d\n", &cases);
    while (cases--) {
        scanf("%d\n", &n);
        for (i=0; i<n; i++) scanf("%s %d/%d", against[i], &exact[i], &moved[i]);

        hasMatch[0] = 0;
        end = 0;
        
        for (with[0]='0'; with[0]<='9' && !end; with[0]++) {
        for (with[1]='0'; with[1]<='9' && !end; with[1]++) {
        for (with[2]='0'; with[2]<='9' && !end; with[2]++) {
        for (with[3]='0'; with[3]<='9' && !end; with[3]++) {
            
                for (i=0; i<n; i++) {
                    isMatch(with, against[i], &r_1, &r_2);
                    if (exact[i] != r_1 || moved[i] != r_2) {
                        i--; break;
                    }
                }
                
                if (i==n) {
                    if (hasMatch[0]) 
                        end = 1; // already a match
                    else 
                        strcpy(hasMatch, with); // new match
                }
                
        }
        }
        }
        }
        
        if (end) 
            printf("indeterminate\n");
        else if (hasMatch[0])
            printf("%s\n", hasMatch);
        else
            printf("impossible\n");
    }
    
    return 0;
}

safe.out

(Toggle Plain Text)

3411
1234
indeterminate
impossible

Dec 8th, 2007, 3:23 PM	#1
Sane Banned Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,101 Rep Power: 6	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: (Toggle Plain Text) 9793 0/1 2384 0/2 6264 0/1 3383 1/0 2795 0/0 0218 1/0 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 (Toggle Plain Text) 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 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 c Syntax (Toggle Plain Text) #include <stdio.h> #include <stdlib.h> void isMatch(char with, char against, int r_1, int r_2) { int i, j; r_1 = 0; r_2 = 0; int used[4]; int matched[4]; for (i=0; i<4; i++) if (with[i] == against[i]) { (r_1)++; used[i] = 1; matched[i] = 1; } else { used[i] = 0; matched[i] = 0; } for (i=0; i<4; i++) for (j=0; j<4; j++) if (i!=j && !matched[j] && !used[i] && with[i] == against[j]) { // used[i] = 1; // Redundant once we break; matched[j] = 1; (r_2)++; break; } } int main() { int cases, n, i, r_1, r_2, end; char against[10][5]; char with[5], hasMatch[5]; int exact[10], moved[10]; with[4] = 0; freopen("safe.in", "rt", stdin); freopen("safe.out", "wt", stdout); scanf("%d\n", &cases); while (cases--) { scanf("%d\n", &n); for (i=0; i<n; i++) scanf("%s %d/%d", against[i], &exact[i], &moved[i]); hasMatch[0] = 0; end = 0; for (with[0]='0'; with[0]<='9' && !end; with[0]++) { for (with[1]='0'; with[1]<='9' && !end; with[1]++) { for (with[2]='0'; with[2]<='9' && !end; with[2]++) { for (with[3]='0'; with[3]<='9' && !end; with[3]++) { for (i=0; i<n; i++) { isMatch(with, against[i], &r_1, &r_2); if (exact[i] != r_1 \|\| moved[i] != r_2) { i--; break; } } if (i==n) { if (hasMatch[0]) end = 1; // already a match else strcpy(hasMatch, with); // new match } } } } } if (end) printf("indeterminate\n"); else if (hasMatch[0]) printf("%s\n", hasMatch); else printf("impossible\n"); } return 0; } #include <stdio.h> #include <stdlib.h> void isMatch(char with, char against, int r_1, int r_2) { int i, j; r_1 = 0; r_2 = 0; int used[4]; int matched[4]; for (i=0; i<4; i++) if (with[i] == against[i]) { (r_1)++; used[i] = 1; matched[i] = 1; } else { used[i] = 0; matched[i] = 0; } for (i=0; i<4; i++) for (j=0; j<4; j++) if (i!=j && !matched[j] && !used[i] && with[i] == against[j]) { // used[i] = 1; // Redundant once we break; matched[j] = 1; (r_2)++; break; } } int main() { int cases, n, i, r_1, r_2, end; char against[10][5]; char with[5], hasMatch[5]; int exact[10], moved[10]; with[4] = 0; freopen("safe.in", "rt", stdin); freopen("safe.out", "wt", stdout); scanf("%d\n", &cases); while (cases--) { scanf("%d\n", &n); for (i=0; i<n; i++) scanf("%s %d/%d", against[i], &exact[i], &moved[i]); hasMatch[0] = 0; end = 0; for (with[0]='0'; with[0]<='9' && !end; with[0]++) { for (with[1]='0'; with[1]<='9' && !end; with[1]++) { for (with[2]='0'; with[2]<='9' && !end; with[2]++) { for (with[3]='0'; with[3]<='9' && !end; with[3]++) { for (i=0; i<n; i++) { isMatch(with, against[i], &r_1, &r_2); if (exact[i] != r_1 \|\| moved[i] != r_2) { i--; break; } } if (i==n) { if (hasMatch[0]) end = 1; // already a match else strcpy(hasMatch, with); // new match } } } } } if (end) printf("indeterminate\n"); else if (hasMatch[0]) printf("%s\n", hasMatch); else printf("impossible\n"); } return 0; } safe.out (Toggle Plain Text) 3411 1234 indeterminate impossible 3411 1234 indeterminate impossible Last edited by Sane; Dec 8th, 2007 at 3:46 PM.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes

Programming Forums > Application Development > Software Design and Algorithms

Mastermind Algorithm