4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: #include <iterator>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: struct Masterbrain
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	int possibleSecrets(vector<string> guesses, vector<string> results)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int N = guesses.size();
4fd800b3a8 2011-02-23        kinaba: 		int cnt = 0;
4fd800b3a8 2011-02-23        kinaba: 		for(int n=0; n<7*7*7*7; ++n)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int x[] = {n/7/7/7%7+1,n/7/7%7+1,n/7%7+1,n%7+1};
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			bool possible = false;
4fd800b3a8 2011-02-23        kinaba: 			for(int lie=0; lie<N && !possible; ++lie)
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				bool possible_by_the_lie = true;
4fd800b3a8 2011-02-23        kinaba: 				for(int i=0; i<N && possible_by_the_lie; ++i)
4fd800b3a8 2011-02-23        kinaba: 				{
4fd800b3a8 2011-02-23        kinaba: 					int g[] = {guesses[i][0]-'0',guesses[i][1]-'0',guesses[i][2]-'0',guesses[i][3]-'0'};
4fd800b3a8 2011-02-23        kinaba: 					int b = results[i][0]-'0';
4fd800b3a8 2011-02-23        kinaba: 					int w = results[i][3]-'0';
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 					if( (i==lie) == match(x,g,b,w) )
4fd800b3a8 2011-02-23        kinaba: 						possible_by_the_lie = false;
4fd800b3a8 2011-02-23        kinaba: 				}
4fd800b3a8 2011-02-23        kinaba: 				possible |= possible_by_the_lie;
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 			if( possible )
4fd800b3a8 2011-02-23        kinaba: 				++cnt;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return cnt;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	bool match(int x[], int g[], int b, int w)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int true_b = 0;
4fd800b3a8 2011-02-23        kinaba: 		multiset<int> xs, gs;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<4; ++i)
4fd800b3a8 2011-02-23        kinaba: 			if( g[i] == x[i] )
4fd800b3a8 2011-02-23        kinaba: 				true_b++;
4fd800b3a8 2011-02-23        kinaba: 			else
4fd800b3a8 2011-02-23        kinaba: 				xs.insert(x[i]), gs.insert(g[i]);
4fd800b3a8 2011-02-23        kinaba: 		vector<int> p;
4fd800b3a8 2011-02-23        kinaba: 		set_intersection(xs.begin(), xs.end(), gs.begin(), gs.end(), back_inserter(p));
4fd800b3a8 2011-02-23        kinaba: 		return true_b==b && w==p.size();
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };