题目
原文：
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.
译文：
Master Mind游戏规则如下：
4个槽，里面放4个球，球的颜色有4种，红(R )，黄(Y)，绿(G)，蓝(B)。比如， 给出一个排列RGGB，表示第一个槽放红色球，第二和第三个槽放绿色球，第四个槽放蓝色球。
你要去猜这个排列。比如你可能猜排列是：YRGB。当你猜的颜色是正确的，位置也是正确的， 你就得到一个hit，比如上面第3和第4个槽猜的和真实排列一样(都是GB)，所以得到2个hit。 如果你猜的颜色在真实排列中是存在的，但位置没猜对，你就得到一个pseudo-hit。比如， 上面的R，猜对了颜色，但位置没对，得到一个pseudo-hit。
对于你的每次猜测，你会得到两个数：hits和pseudo-hits。写一个函数， 输入一个真实排列和一个猜测，返回hits和pseudo-hits。
解答
这个问题十分直观，但有一个地方需要去向面试官明确一下题意。关于pseudo-hits的定义， 猜对颜色但位置没对，得到一个pseudo-hit，这里是否可以包含重复？举个例子， 比如真实排列是：RYGB，猜测是：YRRR。那么hits很明显为0了。pseudo-hits呢？ 猜测中Y对应真实排列中的Y，得到一个pseudo-hits。猜测中有3个R， 而真实排列中只有一个，那这里应该认为得到1个pseudo-hits还是3个？ CTCI书认为是3个，想必理由是猜测中的3个R都满足：出现在真实排列中，位置不正确。 所以算3个。但我认为，这里算1个比较合理，真实排列中的R只和猜测中的一个R配对， 剩余的没有配对，不算。弄清题意后，代码就不难写出了。
以下是两种不同理解的实现：
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstring>
using namespace std;
struct Result{
int hits;
int pseudo_hits;
};
Result Estimate(const char* solution, const char* guess){
Result res;
res.hits = 0;
res.pseudo_hits = 0;
int solution_mask = 0;
for(int i=0; i<4; ++i){
solution_mask |= 1 << (solution[i] - 'A');
}
for(int i=0; i<4; ++i){
if(guess[i] == solution[i])
++res.hits;
else if(solution_mask & ( 1<<(guess[i] - 'A')))
++res.pseudo_hits;
}
return res;
}
int Min(int a, int b){
return a < b ? a : b;
}
Result Estimate1(const char* solution, const char* guess){
Result res;
res.hits = 0;
res.pseudo_hits = 0;
int num = 26 + 5;
int guess_count[num], solution_count[num];
memset(guess_count, 0, sizeof(guess_count));
memset(solution_count, 0, sizeof(solution_count));
for(int i=0; i<4; ++i){
if(guess[i] == solution[i])
++res.hits;
++guess_count[(int)(guess[i]-'A')];
++solution_count[(int)(solution[i]-'A')];
}
char color[] = "RGBY";
for(int i=0; i<4; ++i){
int idx = (int)(color[i] - 'A');
res.pseudo_hits += Min(guess_count[idx], solution_count[idx]);
}
res.pseudo_hits -= res.hits;
return res;
}
int main(){
char solution[] = "RYGB";
char guess[] = "YRRR";
Result res = Estimate(solution, guess);
cout<<res.hits<<" "<<res.pseudo_hits<<endl;
Result res1 = Estimate1(solution, guess);
cout<<res1.hits<<" "<<res1.pseudo_hits<<endl;
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/02/21/19.5/
