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);


      }


}