Game of Master Mind

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.

My initial thoughts:
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.

My initial codes:

	public static Pair<Integer> masterMind
						(String guess, String solution) {
		Hashtable<Character, Integer> table 
					= new Hashtable<Character, Integer>();
		int hits = 0;
		for (int i = 0; i < Math.min(solution.length(), 
				guess.length()); ++i) {
			char charAtGuess = guess.charAt(i);
			char charAtSol = solution.charAt(i);

			table.put(charAtSol,
					table.keySet().contains(charAtSol) ? 
					table.get(charAtSol) + 1 : 1);

			if (charAtGuess == charAtSol)
				hits++;
		}
		int counts = 0;
		for (int i = 0; i < guess.length(); ++i) {
			char charAtGuess = guess.charAt(i);
			if (table.keySet().contains(charAtGuess)) {
				counts++;
				table.put(charAtGuess, table.get(charAtGuess) - 1);
				if (table.get(charAtGuess) == 0)
					table.remove(charAtGuess);
			}
		}
		return new Pair<Integer>(hits, counts - hits);
	}

Solution

	public static class Result {
		public int hits;
		public int pseudoHits;
	};

	public static Result estimate(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;
	}

Comments:
My solution handles more general cases than the solution but the solution is more time and space efficient.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: