Artifact 3e66f13d80d37e147736bc5c909bff5cbe85a52e

• File SRM/146/1B.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <iterator>
using namespace std;

struct Masterbrain
{
	int possibleSecrets(vector<string> guesses, vector<string> results)
	{
		int N = guesses.size();
		int cnt = 0;
		for(int n=0; n<7*7*7*7; ++n)
		{
			int x[] = {n/7/7/7%7+1,n/7/7%7+1,n/7%7+1,n%7+1};

			bool possible = false;
			for(int lie=0; lie<N && !possible; ++lie)
			{
				bool possible_by_the_lie = true;
				for(int i=0; i<N && possible_by_the_lie; ++i)
				{
					int g[] = {guesses[i][0]-'0',guesses[i][1]-'0',guesses[i][2]-'0',guesses[i][3]-'0'};
					int b = results[i][0]-'0';
					int w = results[i][3]-'0';

					if( (i==lie) == match(x,g,b,w) )
						possible_by_the_lie = false;
				}
				possible |= possible_by_the_lie;
			}
			if( possible )
				++cnt;
		}
		return cnt;
	}

	bool match(int x[], int g[], int b, int w)
	{
		int true_b = 0;
		multiset<int> xs, gs;
		for(int i=0; i<4; ++i)
			if( g[i] == x[i] )
				true_b++;
			else
				xs.insert(x[i]), gs.insert(g[i]);
		vector<int> p;
		set_intersection(xs.begin(), xs.end(), gs.begin(), gs.end(), back_inserter(p));
		return true_b==b && w==p.size();
	}
};