Partager via

Another entry to the phraser programming contest

  • Article

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

      }

}

Comments