solution.cc

   1 /**
   2  *
   3  * A solution for Wordscapes, an app in appstore game
   4  *
   5  */
   6
   7 #include <fstream>
   8 #include <iostream>
   9 #include <set>
  10 #include <string>
  11 #include <vector>
  12 using namespace std;
  13
  14 class lset {
  15    private:
  16     class letter {
  17        public:
  18         bool word;
  19         lset* next;
  20         letter() : word(false), next(nullptr){};
  21     };
  22     letter* ltr[26];
  23
  24    public:
  25     lset() {
  26         for (int i = 0; i < 26; i++) ltr[i] = new letter;
  27     }
  28     ~lset() {
  29         for (int i = 0; i < 26; i++) {
  30             if (ltr[i]->next != nullptr) delete ltr[i]->next;
  31             delete ltr[i];
  32         }
  33     }
  34
  35     void insert(const char* w) {
  36         int index;
  37         if (w[0] >= 97 && w[0] <= 122)
  38             index = w[0] - 97;
  39         else if (w[0] >= 65 && w[0] <= 90)
  40             index = w[0] - 65;
  41         else
  42             return;
  43         if (w[1] == '\0')
  44             ltr[index]->word = true;
  45         else {
  46             if (ltr[index]->next == nullptr) ltr[index]->next = new lset;
  47             ltr[index]->next->insert(w + 1);
  48         }
  49     }
  50     bool find(const char* w) {
  51         int index;
  52         if (w[0] >= 97 && w[0] <= 122)
  53             index = w[0] - 97;
  54         else if (w[0] >= 65 && w[0] <= 90)
  55             index = w[0] - 65;
  56         else
  57             return false;
  58         if (w[1] == '\0')
  59             return ltr[index]->word;
  60         else if (ltr[index]->next == nullptr)
  61             return false;
  62         else
  63             return ltr[index]->next->find(w + 1);
  64         return false;
  65     }
  66     bool prefix(const char* w) {
  67         int index;
  68         if (w[0] >= 97 && w[0] <= 122)
  69             index = w[0] - 97;
  70         else if (w[0] >= 65 && w[0] <= 90)
  71             index = w[0] - 65;
  72         else
  73             return false;
  74         if (ltr[index]->next == nullptr) return false;
  75         if (w[1] == '\0')
  76             return true;
  77         else
  78             return ltr[index]->next->prefix(w + 1);
  79         return false;
  80     }
  81 };
  82
  83 void loadDictionary(lset* dic, string filename) {
  84     cout << "Loading dictionary..." << endl;
  85     ifstream f(filename);
  86     string str;
  87     while (f >> str) {
  88         dic->insert(&str[0]);
  89     }
  90     cout << "Load completed!" << endl;
  91     f.close();
  92 }
  93
  94 class scape {
  95    private:
  96     lset& dic;
  97     int numLetters;
  98     vector<char> letters;
  99     int findWords() {
 100         cout << "Find words: blank as '*' || back new scape: 0 \n->";
 101         string str;
 102         cin >> str;
 103         if (str[0] == '0') return 1;
 104         vector<char> word;
 105         vector<bool> lstat(letters.size(), false);
 106         for (int i = 0; i < str.length(); i++) {
 107             if (str[i] == '*')
 108                 word.push_back('*');
 109             else {
 110                 char ch;
 111                 if (str[i] >= 'a' && str[i] <= 'z')
 112                     ch = str[i];
 113                 else if (str[i] >= 'A' && str[i] <= 'Z')
 114                     ch = str[i] - 'A' + 'a';
 115                 for (int k = 0; k < letters.size(); k++) {
 116                     if (letters[k] == ch && lstat[k] == false) {
 117                         lstat[k] = true;
 118                         word.push_back(ch);
 119                         break;
 120                     }
 121                 }
 122             }
 123         }
 124         int sizeW = word.size();
 125         set<string> ans;
 126         finding(word, lstat, 0, sizeW, "", ans);
 127         for (auto& w : ans) cout << w << endl;
 128         return 0;
 129     }
 130     void finding(vector<char> w, vector<bool> lst, int pos, int ws, string str,
 131                  set<string>& ans) {
 132         if (pos == ws) {
 133             if (dic.find(&(str)[0]))
 134                 // cout << str << endl;
 135                 ans.insert(str);
 136             return;
 137         }
 138         if (pos != 0 && !dic.prefix(&(str + '\0')[0])) return;
 139         if (w[pos] == '*') {
 140             for (int i = 0; i < lst.size(); i++) {
 141                 if (lst[i] == false) {
 142                     string st = str + letters[i];  // cout <<'-'<<st<<endl;
 143                     vector<bool> lst_(lst);
 144                     lst_[i] = true;
 145                     finding(w, lst_, pos + 1, ws, st, ans);
 146                 }
 147             }
 148         } else {
 149             str += w[pos];
 150             finding(w, lst, pos + 1, ws, str, ans);
 151         }
 152     }
 153
 154    public:
 155     scape(lset& dic) : dic(dic) {
 156         cout << "add letters || back new scape: 0 \n->";
 157         string str;
 158         cin >> str;
 159         if (str[0] == '0') return;
 160         for (int i = 0; i < str.length(); i++) {
 161             if (str[i] >= 'a' && str[i] <= 'z')
 162                 letters.push_back(str[i]);
 163             else if (str[i] >= 'A' && str[i] <= 'Z')
 164                 letters.push_back(str[i] - 'A' + 'a');
 165         }
 166         numLetters = letters.size();
 167         while (findWords() == 0)
 168             ;
 169     }
 170 };
 171
 172 int main() {
 173     lset dic;
 174     loadDictionary(&dic, "words_alpha.txt");
 175
 176     cout << "Dictionary loaded!" << endl;
 177
 178     while (1) {
 179         cout << "Command: New scape: 1 || exit: 0 \n->";
 180         int cmd;
 181         cin >> cmd;
 182         if (cmd == 1) {
 183             scape sc(dic);
 184         } else if (cmd == 0)
 185             break;
 186     }
 187     cout << "Releasing memory for dictionary..." << endl;
 188     return 0;
 189 }