Again, Mastermind Game Assistant Question

This program supposes to print out all the possible solution of given the guess pattern, the number of black pegs, and the number of white pegs in a mastermind game.

In addition, it has to be done by using recursion, and it has to have a runtime less than 15 second with a pattern length of 15.

An example of the output of the code would look like below:

Code:

Enter the pattern length: 3
Input the guess pattern: abc
Enter the number of black pegs in the feedback: 2
Enter the number of white pegs in the feedback: 0
The possible key patterns are:
aac
aba
abb
abd
abe
abf
acc
adc
aec
afc
bbc
cbc
dbc
ebc
fbc

and here is the my code:

Code:

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






void scanIn(char *pattern, int length)
{
    char input[length + 1];
    scanf("%s", input);


    int i;
    for(i = 0; i < length; i++)
    {
        pattern[i] = input[i];
    }
}


bool pegsTester1(char *guess, char *test, int black, int white, int length)
{
    int i,j,k;
    bool guess_Hit[length];
    bool testHit[length];
    int blackFeedBack;
    int whiteFeedBack;


    for(i = 0; i < length; i++)
    {
        guess_Hit[i] = false;
        testHit[i] = false;
        blackFeedBack = 0;
        whiteFeedBack = 0;
    }
    if(black)
    {
        for(i = 0; i < length; i++)
        {
            if(guess[i] == test[i])
            {
                blackFeedBack++;
                guess_Hit[i] = true;
                testHit[i] = true;
            }
        }
    }
    if(white)
    {
        for(i = 0; i < length; i++)
        {
            for(j = 0; j < length && !testHit[i]; j++)
            {
                if(guess[i] == test[j] && !gues........[j])
                {
                    whiteFeedBack++;
                    testHit[i] = true;
                    guess_Hit[j] = true;
                }
            }
        }
    }
    if(blackFeedBack != black || whiteFeedBack != white)
        return false;
    else
        return true;


}




void printresult(int length, int count, char *guess, int black, int white, char *test)
{
    if(count == length)
    {
        bool rightGuess = pegsTester1(guess, test, black, white, length);
        if(rightGuess)
        {
            int x;
            for(x = 0; x < length; x++)
                printf("%c", test[x]);
            printf("\n");
        }
        return;
    }


    else
    {
        char t;
        for (t = 'a'; t <= 'f'; t++)
        {
            test[count] = t;
            printresult(length, count + 1, guess, black, white, test);
        }
    }
}


int main(void)
{
    int length;
    printf("Enter the pattern length: ");
    scanf("%d", &length);


    char guess[length];
    printf("Input the guess pattern: ");
    scanIn(guess, length);


    int black, white;
    printf("Enter the number of black pegs in the feedback: ");
    scanf("%d", &black);


    printf("Enter the number of white pegs in the feedback: ");
    scanf("%d", &white);




    char test[length+1];
    int i;
    for(i = 0; i < length; i++)
    {
        test[i]='a';
    }
    test[length] = '\0';




    printf("The possible key patterns are: \n");
    printresult(length, 0, guess, black, white, test);


    return 0;


}

The only problem I have now is that it takes too long to generate all the possibility. What can I do to make it faster? Should I check for matches as the program generates the pattern? If so, how? Please help. You can either help by changing my code or make a brand new one.

Thank you!

would you mind commenting your code please @jesterira..

well looking at the pegstester1 function is black a boolean variable .. if yes it would have been better the argument was (...,bool black,...);

Originally Posted by Nyah Check

well looking at the pegstester1 function is black a boolean variable .. if yes it would have been better the argument was (...,bool black,...);

Mastermind (board game) - Wikipedia, the free encyclopedia

Black and White are ints that total a max of the length of the pattern.

Tim S.

While printresult() function is being used in a recursion manner; it is not really a good example of a useful recursion function.

Your grader might not agree; depends on the grader.

Edit: Are the "possible key patterns" required to be in alphabetical order in the list?

Edit2: I am thinking making a re-write of pegsTester and making it the recursion function might be a possible solution.
I just am not seeing a way to make pegsTester a recursion function.

My original idea was a complete re-write with the size of the pattern length being decreased in a recursion function; but, I could not think of what that function would return in C. In math it would be a set; but, I am not sure a set maps to an char array correctly.

Tim S.

Yes, the generated pattern has to be in alphabetical order
What should I change in printresult() to make it a useful recursive function?

It has to have a runtime less than 15 seconds for pattern that has a length of 15 characters according to my grader.

P.S. I will post a commented version of my code tonight.

Originally Posted by Jesterira

Yes, the generated pattern has to be in alphabetical order
What should I change in printresult() to make it a useful recursive function?

It has to have a runtime less than 15 seconds for pattern that has a length of 15 characters according to my grader.

P.S. I will post a commented version of my code tonight.

Nearly all useful recursive function use the result of the recursive function to find an answer.
The is rarely a void recursive function that is useful in other words.

Tim S.

Your white peg calculations are wrong.

For example:

Code:

Enter the pattern length: 2
Input the guess pattern: ab
Enter the number of black pegs in the feedback: 0
Enter the number of white pegs in the feedback: 1
The possible key patterns are: 
aa
ac
ad
ae
af
bb
bc
bd
be
bf
ca
cb
da
db
ea
eb
fa
fb

If a is the correct character in the wrong position (1 white peg), than the solutions where a is on the left aren't possible.
The same is true for b (it can't be on the right).

Another example:

Code:

Enter the pattern length: 3
Input the guess pattern: aab
Enter the number of black pegs in the feedback: 0
Enter the number of white pegs in the feedback: 2
The possible key patterns are: 
aaa
aac
aad
...

All the solutions with 2 a's are wrong because if there are two a's in the correct code than there has to be at least one black peg in the feedback.

Bye, Andreas

I have worked on this problem; reached a stopping point decided to post the updated pegsTester function. I figure by now the due date must be in the past.

I completely re-wrote all the code except for user input and the pegsTester function. The first program I remember writing in my life was the master mind game on a TI calculator. So, I spent more time on this than was warranted.

My code takes about 8 minutes to solve for length 12.
The recursion function must be what needs optimize to improve the speed; I decided I need to finish a report before spending anymore time on this.

Tim S.

Code:

bool pegsTester(char *inputInitialGuess, char *test, int black, int white, int length)
{
    int i,j;
    int blackFeedBack = 0;
    int whiteFeedBack = 0;

    bool guess_Hit[length];
    bool testHit[length];

    for(i = 0; i < length; i++)
    {
        guess_Hit[i] = false;
        testHit[i] = false;
    }

    for(i = 0; i < length; i++)
    {
        if(inputInitialGuess[i] == test[i])
        {
            blackFeedBack++;
            guess_Hit[i] = true;
            testHit[i] = true;
        }
        if (blackFeedBack > black)
        {
            break;
        }
    }

    if (blackFeedBack == black && !(black == length && white == 0))
    {
        for(i = 0; i < length; i++)
        {
            for(j = 0; j < length && !testHit[i]; j++)
            {
                if(inputInitialGuess[i] == test[j] && !guess_Hit[j])
                {
                    whiteFeedBack++;
                    testHit[i] = true;
                    guess_Hit[j] = true;
                }
            }
            if (whiteFeedBack > white)
            {
                break;
            }
        }
    }

    if(blackFeedBack != black || whiteFeedBack != white)
        return false;
    else
        return true;
}