Thread: Again, Mastermind Game Assistant Question

  1. #1
    Registered User
    Join Date
    Nov 2012
    Posts
    9

    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!

  2. #2
    Registered User
    Join Date
    Nov 2011
    Location
    Buea, Cameroon
    Posts
    197
    would you mind commenting your code please @jesterira..

  3. #3
    Registered User
    Join Date
    Nov 2011
    Location
    Buea, Cameroon
    Posts
    197
    well looking at the pegstester1 function is black a boolean variable .. if yes it would have been better the argument was (...,bool black,...);

  4. #4
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Quote Originally Posted by Nyah Check View Post
    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.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    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.
    Last edited by stahta01; 11-16-2012 at 07:44 PM. Reason: grammar
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  6. #6
    Registered User
    Join Date
    Nov 2012
    Posts
    9
    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.

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Quote Originally Posted by Jesterira View Post
    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.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  8. #8
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    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

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    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;
    }
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Mastermind Assistant Program - Help needed
    By Jesterira in forum C Programming
    Replies: 12
    Last Post: 11-15-2012, 02:50 AM
  2. Problem with simple Mastermind game(beginner)
    By newbie2012 in forum Game Programming
    Replies: 1
    Last Post: 11-12-2012, 03:51 AM
  3. Finishing up Mastermind game program
    By Charak in forum C Programming
    Replies: 5
    Last Post: 02-17-2011, 02:49 AM
  4. A problem of if-else .Want the assistant
    By poolomlpz in forum C# Programming
    Replies: 4
    Last Post: 07-03-2009, 04:29 PM
  5. Replies: 37
    Last Post: 12-13-2007, 03:40 PM