Anonymous

#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>
#include <map>
#include <string>


using namespace std;

float closest = 0;
vector<pair<int,int>> wordCandidates;
vector<vector<string>> integersP;
vector<vector<map<string,int>>> bigrams;

string charToNumberString(char letter)
{
	switch(letter)
	{
	case 'a':
	case 'b':
	case 'c':
		return "1";
		break;
	case 'd':
	case 'e':
	case 'f':
		return "2";
		break;
	case 'g':
	case 'h':
	case 'i':
		return "3";
		break;
	case 'j':
	case 'k':
	case 'l':
		return "4";
		break;
	case 'm':
	case 'n':
	case 'o':
		return "5";
		break;
	case 'p':
	case 'q':
	case 'r':
		return "6";
		break;
	case 's':
	case 't':
	case 'u':
		return "7";
		break;
	case 'v':
	case 'w':
	case 'x':
		return "8";
		break;
	case 'y':
	case 'z':
		return "9";
		break;
	}
	return "0";
}

string convertInt(int number)
{
   stringstream ss;//create a stringstream
   ss << number%10;//add number to the stream
   return ss.str();//return a string with the contents of the stream
}

void partitionString(string currentString, int numberLeft, int numberToAdd)
{
	if(numberLeft == 0)
		integersP[numberToAdd].push_back(currentString);
	
	for(int i = numberLeft; i > 0; --i)
		partitionString(currentString + convertInt(i), numberLeft-i, numberToAdd);
}

map<string, int> getBigramMap(string str)
{
	map<string, int> m;
	
	for(int index = 0 ; index < (int)str.length()-1 ; ++index)
	{
		string temp = str.substr(index, 2);
		if (!m.count(temp))
		{
			m[temp] = 1;
		}
		else
		{
			++m[temp];
		}
	}

	return m;
}

void buildOrder()
{
	vector<string> temp;
	integersP.push_back(temp);

	for(int i = 1; i <= 10; ++i)
	{
		vector<string> t;
		integersP.push_back(t);
		partitionString("", i, i);
	}

	for(int i = 0; i <= 10; ++i)
	{
		vector<map<string, int>> m;
		bigrams.push_back(m);
		for(int j = 0; j < (int)integersP[i].size(); ++j)
		{
			bigrams[i].push_back(getBigramMap(integersP[i][j]));
		}
	}
}

map<string, int> getConvertedWordMap(string word)
{
	string temp = "";

	for(int i = 0; i < (int)word.length(); ++i)
		temp.append(charToNumberString(word[i]));

	return getBigramMap(temp);
}

float diceFunction(map<string, int> m1, map<string, int> m2)
{
	float sum = 0;
	float intersection = 0;
	
	for(map<string, int>::iterator it = m1.begin(); it != m1.end(); ++it)
	{
		if(m2.count(it->first) > 0)
			intersection += min(m1[it->first], m2[it->first])*2;

		sum += it->second;
	}

	for(map<string, int>::iterator it = m2.begin(); it != m2.end(); ++it)
	{
		sum += it->second;
	}

	return intersection/sum;
}

void generatStringsFromNumber(vector<string>& list, string currentStr, string choices)
{
	if(choices.length() == 0)
	{
		list.push_back(currentStr);
		return;
	}

	char first = choices[0];
	choices = choices.substr(1);

	switch(first)
	{
	case '0':
		break;
	case '1':
		generatStringsFromNumber(list, currentStr + "a", choices);
		generatStringsFromNumber(list, currentStr + "b", choices);
		generatStringsFromNumber(list, currentStr + "c", choices);
		break;
	case '2':
		generatStringsFromNumber(list, currentStr + "d", choices);
		generatStringsFromNumber(list, currentStr + "e", choices);
		generatStringsFromNumber(list, currentStr + "f", choices);
		break;
	case '3':
		generatStringsFromNumber(list, currentStr + "g", choices);
		generatStringsFromNumber(list, currentStr + "h", choices);
		generatStringsFromNumber(list, currentStr + "i", choices);
		break;
	case '4':
		generatStringsFromNumber(list, currentStr + "j", choices);
		generatStringsFromNumber(list, currentStr + "k", choices);
		generatStringsFromNumber(list, currentStr + "l", choices);
		break;
	case '5':
		generatStringsFromNumber(list, currentStr + "m", choices);
		generatStringsFromNumber(list, currentStr + "n", choices);
		generatStringsFromNumber(list, currentStr + "o", choices);
		break;
	case '6':
		generatStringsFromNumber(list, currentStr + "p", choices);
		generatStringsFromNumber(list, currentStr + "q", choices);
		generatStringsFromNumber(list, currentStr + "r", choices);
		break;
	case '7':
		generatStringsFromNumber(list, currentStr + "s", choices);
		generatStringsFromNumber(list, currentStr + "t", choices);
		generatStringsFromNumber(list, currentStr + "u", choices);
		break;
	case '8':
		generatStringsFromNumber(list, currentStr + "v", choices);
		generatStringsFromNumber(list, currentStr + "w", choices);
		generatStringsFromNumber(list, currentStr + "x", choices);
		break;
	case '9':
		generatStringsFromNumber(list, currentStr + "y", choices);
		generatStringsFromNumber(list, currentStr + "z", choices);
		break;
	}
}

void outputAnswer(int integer, string word, float value, string composition)
{
	cout.precision(3);

	cout << "Integer:" << integer << " (Word:" << word << " Dice Coeff.Value:" << value << " from Composition:[";

	for(int i = 0; i < (int)composition.size()-1; ++i)
		cout << composition[i] << ", ";

	cout << composition[composition.length()-1] << "])";
}

int main()
{
	buildOrder();
	string word;

	cin >> word;

	map<string, int> m = getConvertedWordMap(word);
	
	for(int length = 10; length > 0; --length)
	{
		for(int part = 0; part < (int)integersP[length].size(); ++part)
		{
			float dice = diceFunction(m, bigrams[length][part]);
			if(dice > closest)
			{
				wordCandidates.clear();
				closest = dice;
			}

			if(fabs(dice - closest) < 0.0000001)
			{
				wordCandidates.push_back(make_pair(length, part));
			}
		}
	}

	map<string, int> mOriginal = getBigramMap(word);

	cout << "The integers closer to the word: " << word << " are the following:" << endl;

	bool firstAnswer = true;

	for(int i = wordCandidates.size() - 1; i >= 0; --i)
	{
		vector<string> candidates;
		generatStringsFromNumber(candidates,"",integersP[wordCandidates[i].first][wordCandidates[i].second]);
		for(int j = 0; j < (int)candidates.size(); ++j)
		{
			if(fabs(diceFunction(mOriginal, getBigramMap(candidates[j]))- closest) < 0.000001)
			{
				if(firstAnswer)
					firstAnswer = false;
				else
					cout << endl;
				
				outputAnswer(wordCandidates[i].first, candidates[j], closest, integersP[wordCandidates[i].first][wordCandidates[i].second]);
			}
		}
	}
	/*
	cout << closest << endl;
	for(int i = 0; i < (int) wordCandidates.size(); ++i)
	{
		cout << integersP[wordCandidates[i].first][wordCandidates[i].second] << endl;
	}
	*/
	return 0;
}