[LeetCode]Bulls and Cows

这道题本身是没有什么好讲的，按照题目的要求来即可，代码如下：

	class Solution {
	public:
	string getHint(string secret, string guess) {
	int len = secret.size(), bull = 0, cow = 0;
	int map[10] = {0};
	for(int i = 0; i < len; ++i)
	{
	if(secret[i] == guess[i])bull++;
	else map[secret[i] - '0']++;
	}
	for(int i = 0; i < len; ++i)
	{
	if(secret[i] != guess[i])
	{
	if(map[guess[i] - '0'])
	{
	cow++;
	map[guess[i] - '0']--;
	}
	}
	}
	return to_string(bull) + "A" + to_string(cow) + "B";
	}
	};

view raw Bulls and Cows.cpp hosted with ❤ by GitHub

这道题有趣的部分是在于follow up，如果我们只准用1111-9999范围中的数，我们如何用最少的次数来猜出给定的数。这道题其实本质上就是和Guess the Word一样了，我们仍然是采用minimax的思路：

• 对于每一个数，计算所有的match可能{0A1B, 0A2B, 0A3B, 0A4B, 1A0B... 3A0B, 3A1B}情况下可以eliminate的数的数量，取最少的为score，即min。
• 对于所有在candidate里的数，我们取score最大的，即max。

由于计算量非常大，前几个数我们可以随机取，然后在用这个思路，我实现的时候第一个数取1234，之后在按照这个思路来，计算量依旧很大，第一个iteration耗时很久。实际跑了之后的输出如下：

代码如下：

	pair<int, int> GetHint(int s, int g)
	{
	string secret = to_string(s), guess = to_string(g);
	int len = secret.size(), bull = 0, cow = 0;
	int map[10] = { 0 };
	for (int i = 0; i < len; ++i)
	{
	if (secret[i] == guess[i])bull++;
	else map[secret[i] - '0']++;
	}
	for (int i = 0; i < len; ++i)
	{
	if (secret[i] != guess[i])
	{
	if (map[guess[i] - '0'])
	{
	cow++;
	map[guess[i] - '0']--;
	}
	}
	}
	return{ bull, cow };
	}
	class Master
	{
	public:
	Master()
	{
	//put the answer here
	secret = 2573;
	cout << "Game starts, answer is " << secret << endl;
	}
	pair<int, int> Guess(int guess)
	{
	auto res = GetHint(secret, guess);
	cout << to_string(res.first) << "Bulls" << to_string(res.second) << "Cows" << endl;
	return res;
	}
	private:
	int secret;
	};
	class Player
	{
	public:
	void guess(Master& master)
	{
	//start with 1234
	int start = 1234;
	cout << "Pick start number: " << start << endl;
	auto hint = master.Guess(start);
	if (hint.first == 4)
	{
	cout << "Correct, the number is " << start << endl;
	return;
	}
	vector<int> candidates;
	for (int i = 1111; i <= 9999; ++i)
	{
	auto bc = GetHint(i, start);
	if (hint.first == bc.first && hint.second == bc.second)
	candidates.push_back(i);
	}
	cout << candidates.size() << " numbers left" << endl;
	while (true)
	{
	int num = pick(candidates);
	cout << "Guessing number " << num << endl;
	hint = master.Guess(num);
	if(hint.first == 4)
	{
	cout << "Correct, the number is " << num << endl;
	getchar();
	return;
	}
	candidates = filter(candidates, num, hint.first, hint.second);
	cout << candidates.size() << " numbers left" << endl;
	}
	}
	private:
	int pick(vector<int>& candidates)
	{
	int num = -1, maxElim = -1;
	//get maximum eliminations among every possible pick
	for (const auto& cand : candidates)
	{
	int minElim = INT_MAX;
	//get minimum elinimations for each pattern
	for (int a = 0; a < 4; ++a)
	{
	for (int b = 0; a + b <= 4; ++b)
	{
	int cnt = 0;
	for (const auto& num : candidates)
	{
	auto hint = GetHint(num, cand);
	if (a != hint.first || b != hint.second)
	++cnt;
	}
	minElim = min(cnt, minElim);
	}
	}
	if (minElim > maxElim)
	{
	num = cand;
	maxElim = minElim;
	}
	}
	return num;
	}
	vector<int> filter(const vector<int>& candidates, int guess, int bulls, int cows)
	{
	vector<int> res;
	for (const auto& cand : candidates)
	{
	auto bc = GetHint(cand, guess);
	if (bc.first == bulls && bc.second == cows)
	res.push_back(cand);
	}
	return res;
	}
	};
	int main()
	{
	Master master;
	Player player;
	player.guess(master);
	}

view raw Bulls and Cows Game.cpp hosted with ❤ by GitHub