Cracking Coding Interview - 16.15 Master Mind

Master Mind: The Game of Master Mind is played as follows:

The computer has four slots, and each slot will contain a ball that is red (R). yellow (Y). green (G) or blue (B). For example, the computer might have RGGB (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:’ Note that a slot that is a hit can never count as a pseudo-hit.

For example, if the actual solution is RGBY and you guess GGRR, you have one hit and one pseudo-hit. Write a method that, given a guess and a solution, returns the number of hits and pseudo-hits.

Hints: #639, #730

解法

关键字,4个slot,4种颜色

hit容易计算,相同位置相同颜色的则+1;

peseudoHit可以这样计算:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
           v
solution: RGBY
guess   : GGRR

上面指向的G的位置跳过,记录solution中RGBY出现的次数:
R=1, G=0, B=1, Y=1
通用计算guess中RGBY出现的次数:
R=2, G=1, B=0, Y=0

那么
R的pseudoHit = min(1, 2) = 1
G的pseudoHit = min(0, 1) = 0
B的pseudoHit = min(1, 0) = 0
Y的pseudoHit = min(1, 0) = 0
所以,总pseudoHit = 1

代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void check(char[] solution, char[] guess) {
  int hits = 0;
  Map<Char, Integer> solutionColor = new HashMap<>();
  Map<Char, Integer> guessColor = new HashMap<>();
  initialize(solutionColor); // 把R、G、B、Y初始化为0
  initialize(guessColor);
  
  for (int i = 0; i < solution.length; i++) {
    if (solution[i] == guess[i]) {
      hits++;
      continue;
    }
    countForColor(solutionColor, solution[i]);
    countForColor(guessColor, guess[i]);
  }
  
  int pseudoHit = 0;
  for (Char c : solutionColor.keySet()) {
    pseudoHit += Math.min(solutionColor.get(c), guessColor.get(c));
  }
  System.out.println("Hits: " + hits + ", Pseudo hits: " + pseudoHits);
}

也可以不用Map:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private int index(char c) {
  switch (c) {
    case 'B':
      return 0;
    case 'G':
      return 1;
    case 'R':
      return 2;
    case 'Y':
      return 3;
  }
  return -1;
}
public void check(char[] solution, char[] guess) {
  int hits = 0;
  int[] solutionColor = new int[4];
  int[] guessColor = new int[4];
  
  for (int i = 0; i < solution.length; i++) {
    if (solution[i] == guess[i]) {
      hits++;
      continue;
    }
    solutionColor[index(solution[i])]++;
    guessColor[index(guess[i])]++;
  }
  
  int pseudoHit = 0;
  for (int i = 0; i <  solutionColor.length; i++) {
    pseudoHit += Math.min(solutionColor[i], guessColor[i]);
  }
  System.out.println("Hits: " + hits + ", Pseudo hits: " + pseudoHits);
}

版权

评论