Friday, July 18, 2014

Game of Master Mind

Problem

The Game of Master Mind is played as follows:
The computer has four slots containing balls that are red (R), yellow (Y), green (G) or blue (B). For example, the computer might have RGGB (e.g., Slot #1 is red, Slots #2 and #3 are green, Slot #4 is blue).
You, the user, are trying to guess the solution You might, for example, guess YRGB.
When you guess the correct color for the correct slot, you get a “hit” If you guess a color that exists but is in the wrong slot, you get a “pseudo-hit”. For example, the guess YRGB has 2 hits and one pseudo hit.
For each guess, you are told the number of hits and pseudo-hits.
Write a method that, given a guess and a solution, returns the number of hits and pseudo-hits.

Solution

1st scan, we can find out how many hits there are by comparing character by character. During this scan, we can also build a hashtable for all the characters in the solution. The second scan, we count how many characters in the guess are matched in the hashtable. The counts – hints is the pseudo-hits.
public static class Result {
    public int hits;
    public int pseudoHits;
};
 
public static Result masterMind(String guess, String solution) {
    Result res = new Result();
    int solution_mask = 0;
    for (int i = 0; i < 4; ++i) {
        solution_mask |= 1 << (1 + solution.charAt(i) - 'A');
    }
    for (int i = 0; i < 4; ++i) {
        if (guess.charAt(i) == solution.charAt(i)) {
            ++res.hits;
        } else if ((solution_mask & (1 << (1 + guess.charAt(i) - 'A'))) >= 1) {
            ++res.pseudoHits;
        }
    }
    return res;
}

//runner main
public static void main(String[] args) {
   masterMind("YRGB", "RGGB");
}


Thanks.
References

0 comments:

Post a Comment