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