solution.cc

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