OK, this is the revised algorithm, verified with several examples from that site:
#include <ostream>
#include <istream>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
class Word;
class Sentence;
class LetterMap;
class Word
{
std::string sWord;
public:
Word():sWord("") {}
Word(std::string word):sWord(word) {}
operator std::string() {return sWord;}
operator [](int index) {return sWord[index];}
size_t length() const {return sWord.length();}
friend std::ostream& operator << (std::ostream& os, const Word& word);
friend std::istream& operator >> (std::istream& is, Word& word);
};
std::ostream& operator << (std::ostream& os, const Word& word)
{
return os << word.sWord;
}
std::istream& operator >> (std::istream& is, Word& word)
{
return is >> word.sWord;
}
class Sentence
{
std::vector<Word> Addings;
Word Result;
public:
Sentence() {}
Sentence(std::vector<Word> &adds, Word& res):Addings(adds), Result(res) {}
void Check(LetterMap& letterMap);
};
class LetterMap
{
std::map<char, int> LetterToNumber;
bool AreDifferent();
public:
void FromInput(std::vector<Word>& words);
void Reset();
bool HasNewConfiguration();
void MoveToNextConfiguration();
int GetNumericValue(char value) const;
friend std::ostream& operator << (std::ostream& os, const LetterMap& lmap);
};
void LetterMap::FromInput(std::vector<Word>& words)
{
for(std::vector<Word>::iterator it1 = words.begin(); it1 != words.end(); ++it1)
{
std::string word = (*it1);
for(std::string::iterator it2 = word.begin(); it2 != word.end(); ++it2)
LetterToNumber[*it2] = 0;
}
}
void LetterMap::Reset()
{
for(std::map<char, int>::iterator it = LetterToNumber.begin(); it != LetterToNumber.end(); ++it)
{
LetterToNumber[(*it).first] = 0;
}
}
bool LetterMap::HasNewConfiguration()
{
bool isend = true;
for(std::map<char, int>::iterator it = LetterToNumber.begin(); it != LetterToNumber.end() && isend; ++it)
{
isend = isend && (LetterToNumber[(*it).first] == 9);
}
return !isend;
}
bool LetterMap::AreDifferent()
{
for(std::map<char, int>::iterator it = LetterToNumber.begin(); it != LetterToNumber.end(); ++it)
{
std::map<char, int>::iterator start = it;
for(std::map<char, int>::iterator pos = ++start; pos != LetterToNumber.end(); ++pos)
{
if((*it).second == (*pos).second)
return false;
}
}
return true;
}
void LetterMap::MoveToNextConfiguration()
{
do
{
int transport = 1;
for(std::map<char, int>::reverse_iterator it = LetterToNumber.rbegin(); it != LetterToNumber.rend(); ++it)
{
char key = (*it).first;
int value = (*it).second;
value = value + transport;
if(value < 10)
{
LetterToNumber[key] = value;
break;
}
else
{
LetterToNumber[key] = 0;
transport = 1;
}
}
}
while(HasNewConfiguration() && !AreDifferent());
}
int LetterMap::GetNumericValue(char value) const
{
std::map<char, int>::const_iterator pos = LetterToNumber.find(value);
if(pos == LetterToNumber.end())
return 0;
return (*pos).second;
}
std::ostream& operator << (std::ostream& os, const LetterMap& lmap)
{
for(std::map<char, int>::const_iterator it = lmap.LetterToNumber.begin();
it != lmap.LetterToNumber.end(); ++it)
{
os << (*it).first << " : " << (*it).second << ", ";
}
os << '\n';
return os;
}
void Sentence::Check(LetterMap& letterMap)
{
size_t maxLength = 0;
for(std::vector<Word>::iterator ctit = Addings.begin(); ctit != Addings.end(); ++ctit)
{
std::string word = *ctit;
if( word.length() > maxLength)
maxLength = word.length();
}
size_t lengthResults = Result.length();
if(maxLength > lengthResults)
return;
if(maxLength < lengthResults)
maxLength = lengthResults;
letterMap.Reset();
int t = 1;
while(letterMap.HasNewConfiguration())
{
letterMap.MoveToNextConfiguration();
bool isOK = true;
int transport = 0;
for(int i=0; i<maxLength; i++)
{
int total = transport;
for(std::vector<Word>::reverse_iterator ctit = Addings.rbegin(); ctit != Addings.rend(); ++ctit)
{
std::string word = (*ctit);
if(word.length()-1 >= i)
total += letterMap.GetNumericValue(word[word.length() - 1 - i]);
}
int result = letterMap.GetNumericValue(Result[Result.length() - 1 - i]);
if(total%10 != result)
{
isOK = false;
break;
}
else
{
transport = total / 10;
}
}
if(isOK)
{
std::cout << letterMap;
}
}
}
int main(int argc, char* argv[])
{
Word word1("SHE");
Word word2("THE");
Word word3("BEST");
// std::cin >> word1;
// std::cin >> word2;
// std::cin >> word3;
std::vector<Word> words;
words.push_back(word1);
words.push_back(word2);
Sentence sentence(words, word3);
words.push_back(word3);
LetterMap themap;
themap.FromInput(words);
sentence.Check(themap);
return 0;
}
I know that fore some examples is slow, but I don't have time to optimize it.