Another entry to the phraser programming contest
I received another entry to my programming contest in email:
From: "Michael Scholz"
Sent: Thursday, April 01, 2004 5:34 PM
I started working on your programming contest, but I quickly tired of optimizing for how-clear-the-code-is. But then, when you posted some clear code with the slow algorithm, I figured I'd finish what I'd started; to at least provide an algorithmic alternative. Fixing up the performance by pre-allocating buffers, etc, would arguably be less clear. So I'll just submit a first draft (i.e. sans comments). And final draft, actually, I should go back to my regularly scheduled coding... :)
-Michael Scholz
THQ, Inc.
p.s. I'm kind of learn as I go on STL, so probably the blog-o-sphere would have much feedback about STL correctness. But at least I learned something new! (equal_range())
I’m including the source code at the end of the message. Basically, this one is a 120-line C++ program. Unlike the previous entries, it uses recursion rather than pure iteration. I actually like this better. What do you think?
This solution is close to mine, which I shall disclose fairly soon (I’m writing up the docs). FYI, my program is in yet another language. :-)
#include <assert.h>
#include <fstream>
#include <map>
#include <set>
// why did I have to do this? Couldn't a simple std::string have compiled correctly?
class stlstring : public std::string
{
public:
stlstring() : std::string()
{}
stlstring(const std::string& arg) : std::string(arg)
{}
std::string& operator=(const std::string& _Right)
{
return (this->std::string::operator=(_Right));
}
bool operator<(const stlstring& _Right) const
{
return (this->compare(_Right) < 0);
}
};
typedef std::multimap<stlstring,stlstring> tWordList;
typedef std::pair<stlstring,stlstring> tWordValue;
typedef std::set<stlstring> tStringSet;
char GetKeypadMapping(char characterToMap)
{
if (characterToMap >= 'a' && characterToMap <= 'c')
return '2';
else if (characterToMap >= 'd' && characterToMap <= 'f')
return '3';
else if (characterToMap >= 'g' && characterToMap <= 'i')
return '4';
else if (characterToMap >= 'j' && characterToMap <= 'l')
return '5';
else if (characterToMap >= 'm' && characterToMap <= 'o')
return '6';
else if (characterToMap >= 'p' && characterToMap <= 's')
return '7';
else if (characterToMap >= 't' && characterToMap <= 'v')
return '8';
else if (characterToMap >= 'w' && characterToMap <= 'z')
return '9';
assert(0); // input wasn't valid, Although I'm putting a filter on the wordlist to guarantee it.
return '0';
}
void InitWordList(tWordList& rWordList, const char* pszFileName)
{
const int MAX_STRING_LENGTH =48;
char tempbuffer[MAX_STRING_LENGTH];
std::ifstream iffile( pszFileName );
tWordValue tempval;
if( iffile )
{
while ( iffile.good() ) // EOF or failure stops the reading
{
iffile.getline(tempbuffer,MAX_STRING_LENGTH);
if (*tempbuffer)
{
tempval.first = tempbuffer;
tempval.second = tempbuffer;
for (unsigned int mapIndex = 0;mapIndex<tempval.second.length();mapIndex++)
{
tempval.first[mapIndex] = GetKeypadMapping(tolower(tempval.second[mapIndex]));
}
rWordList.insert(tempval);
}
}
}
else {
// cout << "ERROR: Cannot open file 'pszFileName'." << endl;
}
}
void FindMatchesRecursive(tStringSet& destSet,const tWordList& rWordList, const stlstring& input,const stlstring& prefix)
{
stlstring saveString = prefix;
saveString.append(input);
destSet.insert(saveString);
size_t inputStringLength = input.length();
for (unsigned int i=0;inputStringLength && i<=(inputStringLength);i++)
{
for (unsigned int j=0;j<=i;j++)
{
stlstring prefixString = prefix;
prefixString.append(input.substr(0,j));
stlstring testString = input.substr(j,i);
stlstring remainderString = "";
if (j+i < inputStringLength)
remainderString = input.substr(j+i,inputStringLength-j-i);
std::pair<tWordList::const_iterator,tWordList::const_iterator> rangeMatch=rWordList.equal_range(testString);
for (tWordList::const_iterator it = rangeMatch.first;it!=rangeMatch.second;++it)
{
saveString = prefixString;
saveString.append(it->second);
FindMatchesRecursive(destSet,rWordList,remainderString,saveString);
}
}
}
}
void main(void)
{
tWordList wordlistMap;
tStringSet answer;
InitWordList(wordlistMap,"wordlist.txt");
stlstring inputString = "6423946369";
answer.insert(inputString);
stlstring nullString = "";
FindMatchesRecursive(answer,wordlistMap,inputString,nullString);
for(tStringSet::iterator it = answer.begin();it!=answer.end();it++)
{
char buff[20];
sprintf(buff, "%s\n", it->c_str());
OutputDebugString(buff);
}
}