server/wordscapes/wordscapes.cc

   1 #include "wordscapes.h"
   2
   3 #include <fstream>
   4 #include <map>
   5 #include <queue>
   6 #include <string>
   7
   8 Dictionary::Node::Node() {}
   9
  10 Dictionary::Dictionary(const char* filename)
  11 {
  12     header = new Node();
  13     std::ifstream dictfile(filename);
  14     std::string word;
  15     while (dictfile >> word)
  16     {
  17         Node* tmp = header;
  18         for (char ch : word)
  19         {
  20             if (tmp->next[ch - 'a'] == nullptr)
  21                 tmp->next[ch - 'a'] = new Node();
  22             tmp = tmp->next[ch - 'a'];
  23         }
  24         tmp->isWord = true;
  25     }
  26     dictfile.close();
  27 }
  28
  29 Dictionary::Node::~Node()
  30 {
  31     for (int i = 0; i < 26; i++)
  32         if (next[i] != nullptr) delete next[i];
  33 }
  34
  35 Dictionary::~Dictionary() { delete header; }
  36
  37 bool Dictionary::findWord(std::string& word)
  38 {
  39     Node* tmp = header;
  40     for (char ch : word)
  41     {
  42         if (tmp->next[ch - 'a'] == nullptr) return false;
  43         tmp = tmp->next[ch - 'a'];
  44     }
  45     return tmp->isWord;
  46 }
  47
  48 //TODO: get filename from config file
  49 Wordscapes::Wordscapes() { dict = new Dictionary("myDictionary"); }
  50
  51 Wordscapes::~Wordscapes() {}
  52
  53 void Wordscapes::stripInput(std::string& given, std::string& search)
  54 {
  55     for (auto i = given.begin(); i != given.end(); i++)
  56     {
  57         if (*i >= 'a' && *i <= 'z')
  58             continue;
  59         else if (*i >= 'A' && *i <= 'Z')
  60             *i += 'a' - 'A';
  61         else
  62             given.erase(i--);
  63     }
  64     for (auto i = search.begin(); i != search.end(); i++)
  65     {
  66         if ((*i >= 'a' && *i <= 'z') || *i == '*')
  67             continue;
  68         else if (*i >= 'A' && *i <= 'Z')
  69             *i += 'a' - 'A';
  70         else
  71             given.erase(i--);
  72     }
  73 }
  74
  75 std::vector<std::string> Wordscapes::solve(std::string& given,
  76                                            std::string& search)
  77 {
  78     // strip input string, remove unexpected characters
  79     stripInput(given, search);
  80
  81     std::vector<std::string> result;
  82     std::map<char, int> mp;
  83     std::queue<std::pair<std::string, std::map<char, int>>> qu;
  84
  85     for (char ch : given) mp[ch]++;
  86     for (char ch : search)
  87     {
  88         if (ch >= 'a' && ch <= 'z') mp[ch]--;
  89         if (mp[ch] < 0) return {};
  90     }
  91     qu.push({search, mp});
  92
  93     while (!qu.empty())
  94     {
  95         std::string word = qu.front().first;
  96         auto wmp         = qu.front().second;
  97         qu.pop();
  98         std::size_t found = word.find('*');
  99         if (found == std::string::npos)
 100         {
 101             if (dict->findWord(word)) result.push_back(word);
 102         }
 103         else
 104         {
 105             for (auto& m : wmp)
 106             {
 107                 if (m.second != 0)
 108                 {
 109                     auto tmp_word = word;
 110                     auto tmp_wmp  = wmp;
 111                     tmp_word.replace(found, 1, 1, m.first);
 112                     tmp_wmp[m.first]--;
 113                     qu.push({tmp_word, tmp_wmp});
 114                 }
 115             }
 116         }
 117     }
 118     return result;
 119 }