#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <cstdlib>
#include <limits>
#include <sstream>

using namespace std;

class Word
{
public:
	int complexity; 	// The number of ways that this word can be matched
	int letters[27]; 	// Stores the number of each letter that this word 
						// contains, used for fast match computations
	string word;		// The word, as it was in the dictionary

	/* Constructor: fills out the complexity and letters variables */
	Word(string input)
	{
		word = input;

		for(int i = 0; i < 27; i++)
			letters[i] = 0;

		for(int i = 0; i < word.length(); i++)
		{
			char character = word.at(i);
			int offset;
		    if(character == '\'')
				offset = 26;
			else
				offset = character - 'A';

			if(offset < 0 || offset > 26) //Dictionary is not spec compliant
			{
				cout << "Unexpected character in input file" << endl << flush;
				exit(EXIT_FAILURE);
			}

			letters[offset]++;
		}

		complexity = 1;
		for(int i = 0; i < 27; i++)
			complexity *= letters[i] + 1;
	}

	/* Returns the number of letters that the two words have in common */
	inline int match(const Word& other)
	{
		int matches = 0;
		for(int i = 0; i < 27; i++)
		{
			matches += min(letters[i], other.letters[i]);
		}
		return matches;
	}

	/* This compares two words based on their complexity. It is used to 
	 * implement heuristic two. Note that we want the most complex words at the 
	 * front of the list, so we reverse the operator. */
	bool operator < (const Word other)
	{
		return complexity > other.complexity;
	}
};

/* Parse the dictionary stored in the file whose path is stored in the null 
 * terminated string "dictionary".
 */
list<Word>* parse(char* dictionary)
{
	ifstream in(dictionary);

	list<Word>* ret = new list<Word>();

	if(!in.is_open())
	{
		cout << "Cannot find file: " << dictionary << endl;
		exit(EXIT_FAILURE);
	}

	while(!in.eof())
	{
		string input;
		in >> input;

		//ignore whitespace
		if(input.length() == 0)
			continue;

		Word word(input);
		ret->push_back(word);
	}
	return ret;
}

/* Picks the guess from the first "limit" items in the list  "dictionary" which 
 * scores the highest according to heuristic one (see the README) */
list<Word>::iterator guess(list<Word>* dictionary, list<Word>* candidates, int limit)
{
	double best = numeric_limits<double>::max();
	list<Word>::iterator best_word;
	int current[64];

	list<Word>::iterator iter = dictionary->begin();
	int count = 0;
	while(count < limit && iter != dictionary->end())
	{
		Word current_word = *iter;

		for(int i = 0; i < 64; i++)
			current[i] = 0;

		for(list<Word>::iterator cand = candidates->begin(); cand != candidates->end(); cand++)
		{
			int matches = current_word.match(*cand);
			// We don't really want to do string comparisons in the inner loop
			// so we use the complexity to eliminate the need for most of them.
			// This accounts for the possibility that we guess the word exactly.
			if((*cand).complexity != (*iter).complexity || (*cand).word != (*iter).word)
				if(matches < 64)
					current[matches]++;
		}

		// Calculate the expected size of the match set. To get a proper 
		// expectation we should divide the result by candidates->size(), but 
		// since all the expectations should be divided by it and floating 
		// point division is slow we can compare the sum of squares instead and
		// get the same result. We use doubles since squaring set sizes could
		// lead to integer overflows.
		double expected_size = 0;
		for(int i = 0; i < 64; i++)
		{
			double setsize = (double)current[i];
			expected_size += setsize * setsize;
		}

		if(expected_size < best)
		{
			best = expected_size;
			best_word = iter; 
		}
		
		iter++;
		count++;
	}

	return best_word;
}

/* Eliminates words which do not match have a match score of "matches" against
 * the word "word". "word" must not be an iterator from the candidates list.
 * Returns the number of words removed from the candidates list.
 */
int eliminate(list<Word>* candidates, list<Word>::iterator word, int matches)
{
	int removed = 0;

	list<Word>::iterator iter = candidates->begin();
	while(iter != candidates->end())
	{
		if((*iter).match(*word) != matches || (*iter).word == (*word).word)
		{
			iter = candidates->erase(iter);
			removed++;
		}
		else 
			iter++;
	}

	return removed;
}

int main(int argc, char** argv)
{
	if(argc != 2)
	{
		cout << "Usage: " << argv[0] << " <dictionary>" << endl;
		return 1;
	}

	list<Word>* dictionary = parse(argv[1]);

	// Implements heuristic one (see README)
	list<Word>* candidates = new list<Word>(*dictionary);
	dictionary->sort();

	// The following allows for a higher starting guess size for smaller
	// dictionaries. We always want a decent number of guesses no matter how
	// large the dictionary is, however. The constant is chosen to get a 64 
	// starting size on the sample dictionary, for which the program is known
	// to terminate in a reasonable amount of time.
	int guess_size = max(96, 9273408 / (int)dictionary->size());
	while(true)
	{
		if(candidates->size() <= 3)
		{
			//In this situation we have a good chance of guessing directly
			//so we restrict ourselves to the candidates list	
			delete dictionary;
			dictionary = new list<Word>(*candidates);
		}

		list<Word>::iterator best = guess(dictionary, candidates, guess_size);

		cout << (*best).word << endl;

		string response;
		cin >> response;

		if(response == "YES")
			return 0;
		
		int matches;
		istringstream stream(response);
		stream >> matches;

		// Scale the sample size used to compute the next guess so that we 
		// have roughly the same number of comparisons in each round.
		int before = candidates->size();
		int after = before - eliminate(candidates, best, matches);
		double decrease = (double)before / (double)after;
		guess_size = (int)((double)guess_size * decrease);

		// Guard against integer overflows
		if(guess_size > dictionary->size() || guess_size < 0)
			guess_size = dictionary->size();

		// Ensures termination
		dictionary->erase(best);

		// Ensure that our opponent is telling the truth
		if(candidates->size() == 0)
		{
			cout << "Cheater!" << endl;
			return 1;
		}
	}
	return 0;
}