Sunday, March 1, 2015

Game of Master

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.

This problem is from Cracking the Coding interview. The book provides a very neat solution (shown below), except there is a bug in it. Consider a case where solution is "RGGB" and the guess is "GGGR", the code should return 2 hits and 1 pseudo hits, however, the solution gives us 2 hits and 2 pseudo hits. The reason is that the solution_mask only takes into account if there exists such character in the solution, so for the first "G", of course there exists another 2 Gs in the solution, but not in the correct position. However, in real time, we should taken into account the number of duplicate characters in the solution and the guess. I use a hashmap. My solution does need extra space. But since we only need at most 4 key, value pairs, it won't take too much extra space.

The solution provided by the book:
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;
}


My solution:
import java.util.*;
public class GameofMaster {
 private static class Result{
  public int hits;
  public int pseudoHits;
  public Result(int hits, int pseudoHits){
   this.hits = hits;
   this.pseudoHits = pseudoHits;
  }
  public String toString(){
   return "hits: " + String.valueOf(hits) + "; pseudoHits: " + String.valueOf(pseudoHits);
  }
 }
 
 public static Result estimate(String guess, String solution){
  Map map = new HashMap();
  for (int i = 0; i < 4; i++){
   char c = solution.charAt(i);
   if (!map.containsKey(c))
    map.put(c, 1);
   else
    map.put(c, map.get(c) + 1);
  }
  int hits = 0;
  int pse = 0;
  for (int i = 0; i < 4; i++){
   char c = guess.charAt(i);
   if (c == solution.charAt(i)){
    hits++; 
    if (!map.containsKey(c)) {
     pse--;
     continue;
    }
    map.put(c, map.get(c) - 1);
    if (map.get(c) == 0)
     map.remove(c);
   }
   else if (map.containsKey(c)) {
    pse++;
    map.put(c, map.get(c) - 1);
    if (map.get(c) == 0)
     map.remove(c);
   }
  }
  return new Result(hits, pse);
 }

 public static void main(String[] args) {
  System.out.println(estimate("RGGB", "RGGB").toString());

 }

}

No comments:

Post a Comment