diff --git a/ReProjet/Sane_Granma.cc b/ReProjet/Sane_Granma.cc index 6319fa0..9a8af33 100644 --- a/ReProjet/Sane_Granma.cc +++ b/ReProjet/Sane_Granma.cc @@ -1,463 +1,463 @@ // Sane_Granma.cc // Auteur : Quentin Berling // Version : 1.0 #include #include #include #include #include using namespace std; struct StringPlus{ string str; unsigned nbT; unsigned nbD=0; string alpha; array mat={0}; }; const string NOT_IN_CAPITAL_LETTERS("The word is not purely in capital letters"); const string DOUBLE_WORD("Each word can be present only once"); const string EMPTY_DICO("The dictionnary cannot be empty"); const string NO_ANAGRAM("There is no anagram for this message and this dictionary"); const vector operator+(vector u, vector const &v); const array operator-(array u, array const &v); void operator+=(vector &u, vector const &v); void operator-=(array &u, array const &v); StringPlus str_to_StrPlus(const string &str); void read_input(vector &dico, vector &allmessages); void sort1234(vector &dico); void sort234(vector &dico); void sort3(vector &dico); void sort4(vector &dico); void find_anagrams(vector dico, StringPlus message, vector> &anagrams, vector anagram, array letters); void clean_anagrams(vector> &anagrams); void print_anagrams(const vector> &anagrams, const StringPlus &message); +bool check_word(const string &str); void check_dico(const vector &dico); bool enough_letters(const array &letters, const StringPlus &message); bool is_included(const vector anagram, const vector> &anagrams); void permutation(vector anagram, vector permuted_anagram, vector> &permuted_anagrams); bool check_message(const string &message); const vector operator+(vector u, vector const &v) { vector w; for (auto& wordplus : u) { w.push_back(wordplus); } for (auto& wordplus : v) { w.push_back(wordplus); } return w; } const array operator-(array u, array const &v) { array w; for (int i=0; i < 26; i++) { w[i]=u[i]-v[i]; } return w; } void operator+=(vector &u, vector const &v) { u=u+v; } void operator-=(array &u, array const &v) { u=u-v; } int main() { vector dico, allmessages; vector> anagrams; vector anagram; array letters; read_input(dico, allmessages); // Affichage du dictionnaire for (auto& wordplus : dico) { cout << wordplus.str << endl; } for (auto& message : allmessages) { letters=message.mat; find_anagrams(dico, message, anagrams, anagram, letters); clean_anagrams(anagrams); print_anagrams(anagrams, message); anagrams.clear(); } return 0; } void read_input(vector &dico, vector &allmessages) { string str, message; StringPlus strplus, messageplus; while(cin >> str) { if (str != ".") { - strplus=str_to_StrPlus(str); - dico.push_back(strplus); + if (check_word(str)) { + strplus=str_to_StrPlus(str); + dico.push_back(strplus); + } else { + exit(0); + } } else /*if (str == ".")*/ { break; } } while(cin >> str) { if (str != "." && str != "*") { message+=str+" "; } else if (str == ".") { str.pop_back(); messageplus=str_to_StrPlus(message); allmessages.push_back(messageplus); message.clear(); } } check_dico(dico); sort1234(dico); } +bool check_word(const string &str) { + for (auto& c : str) { + if (c != toupper(c) || c == '.') { + cout << NOT_IN_CAPITAL_LETTERS << endl; + return false; + } + } + + return true; +} + StringPlus str_to_StrPlus(const string &str) { StringPlus strplus; unsigned iter; strplus.str=str; strplus.nbT=str.size(); for (auto& c : str) { if (c != ' ') { iter=toupper(c)-'A'; strplus.mat[iter]+=1; } else { strplus.nbT--; } } for (unsigned n=0; n < 26; n++) { if (strplus.mat[n] > 0) { strplus.nbD++; iter=strplus.mat[n]; while (iter > 0) { strplus.alpha+='a'+n; iter--; } } } for (auto& letterbool : strplus.mat) { strplus.nbD+=letterbool; } return strplus; } void check_dico(const vector &dico) { if (dico.empty()) { cout << EMPTY_DICO << endl; exit(0); } for (unsigned i=0; i < dico.size(); i++) { for (unsigned j=i+1; j < dico.size(); j++) { if (dico[i].str == dico[j].str) { cout << DOUBLE_WORD << endl; exit(0); } } - - for (auto& c : dico[i].str) { - if (c != toupper(c)) { - cout << NOT_IN_CAPITAL_LETTERS << endl; - exit(0); - } - } } } void sort1234(vector &dico) { unsigned nbTmax(0); vector sorted_dico, nbt_sorted_dico; for (auto& wordplus : dico) { if (wordplus.nbT > nbTmax) { nbTmax=wordplus.nbT; } } for (unsigned i=1; i <= nbTmax; i++) { for (auto& wordplus : dico) { if (wordplus.nbT == i) { nbt_sorted_dico.push_back(wordplus); } } sort234(nbt_sorted_dico); // sorted_dico.insert(sorted_dico.end(), nbt_sorted_dico.begin(), nbt_sorted_dico.end() ); sorted_dico+=nbt_sorted_dico; nbt_sorted_dico.clear(); } swap(dico, sorted_dico); } void sort234(vector &dico) { unsigned nbDmax(0); vector sorted_dico, nbd_sorted_dico; for (auto& wordplus : dico) { if (wordplus.nbD > nbDmax) { nbDmax=wordplus.nbD; } } for (unsigned i=1; i <= nbDmax; i++) { for (auto& wordplus : dico) { if (wordplus.nbD == i) { nbd_sorted_dico.push_back(wordplus); } } if (nbd_sorted_dico.size() > 0) { sort3(nbd_sorted_dico); sort4(nbd_sorted_dico); } sorted_dico+=nbd_sorted_dico; nbd_sorted_dico.clear(); } swap(dico, sorted_dico); } void sort3(vector &dico) { string alpha_min=dico[0].str; unsigned alpha_min_index(0); vector unsorted_dico, alpha_sorted_dico; // for (auto& wordplus : dico) { // if (wordplus.alpha > alpha_max) { // alpha_max=wordplus.alpha; // } // } // alpha_max+="a"; while (dico.size() > 0) { // alpha_min=alpha_max; for (unsigned i=0; i < dico.size(); i++) { if (dico[i].alpha <= alpha_min) { alpha_min=dico[i].alpha; alpha_min_index=i; } } for (unsigned j=0; j < dico.size(); j++) { if (j==alpha_min_index) { alpha_sorted_dico.push_back(dico[j]); } else { unsorted_dico.push_back(dico[j]); } } swap(dico, unsorted_dico); unsorted_dico.clear(); } swap(dico, alpha_sorted_dico); } void sort4(vector &dico) { string alphabet_min, alphabet_max; unsigned alphabet_min_index(0); vector unsorted_dico, alphabet_sorted_dico; for (auto& wordplus : dico) { if (wordplus.str > alphabet_max) { alphabet_max=wordplus.str; } } while (dico.size() > 0) { alphabet_min=alphabet_max; for (unsigned i=0; i < dico.size(); i++) { if (dico[i].str <= alphabet_min) { alphabet_min=dico[i].str; alphabet_min_index=i; } } for (unsigned j=0; j < dico.size(); j++) { if (j==alphabet_min_index) { alphabet_sorted_dico.push_back(dico[j]); } else { unsorted_dico.push_back(dico[j]); } } swap(dico,unsorted_dico); unsorted_dico.clear(); } swap(dico, alphabet_sorted_dico); } void find_anagrams(vector dico, StringPlus message, vector> &anagrams, vector anagram, array letters) { StringPlus wordplus; while (! dico.empty()) { wordplus=dico.back(); dico.pop_back(); if (enough_letters(letters, wordplus)) { anagram.push_back(wordplus.str); letters-=wordplus.mat; find_anagrams(dico, message, anagrams, anagram, letters); } if (dico.empty()) { anagrams.push_back(anagram); } } } bool enough_letters(const array &letters, const StringPlus &wordplus) { for (unsigned n=0; n < 26; n++) { if (letters[n] < wordplus.mat[n]) { return false; } } return true; } void clean_anagrams(vector> &anagrams) { vector anagram; vector> cleaned_anagrams; while (anagrams.size() > 0) { anagram=anagrams.back(); anagrams.pop_back(); if (! is_included(anagram, anagrams)) { vector> permuted_anagrams; permutation(anagram, vector(), permuted_anagrams); for (auto& anagram_permuted : permuted_anagrams) { cleaned_anagrams.push_back(anagram_permuted); } } } anagrams=cleaned_anagrams; } bool is_included(const vector anagram, const vector> &anagrams) { vector anagram_part; if (anagram.empty()) { return true; } for (auto& anagram_test : anagrams) { anagram_part=anagram; // À optimiser. Sortir de boucle ASAP. for (unsigned i=0; i < anagram.size(); i++) { for (auto& word : anagram_test) { if (anagram_part.back() == word) { anagram_part.pop_back(); } } } if (anagram_part.empty()) { return true; } } return false; } void permutation(vector anagram, vector permuted_anagram, vector> &permuted_anagrams) { unsigned anagram_size=anagram.size(); if (anagram_size == 1) { permuted_anagram.push_back(anagram[0]); permuted_anagrams.push_back(permuted_anagram); } else { vector new_anagram, permuted_anagram_ori=permuted_anagram; for (unsigned i=0; i < anagram_size; i++) { for (unsigned j=0; j < anagram_size; j++) { if (i == j) { permuted_anagram.push_back(anagram[j]); } else { new_anagram.push_back(anagram[j]); } } permutation(new_anagram, permuted_anagram, permuted_anagrams); new_anagram.clear(); permuted_anagram=permuted_anagram_ori; } } } void print_anagrams(const vector> &anagrams, const StringPlus &message) { cout << endl; if (check_message(message.str)) { if (anagrams.empty()) { cout << NO_ANAGRAM << endl; } else { for (auto& anagram : anagrams) { for (unsigned i=0; i < anagram.size()-1; i++) { cout << anagram[i] << " "; } cout << anagram[anagram.size()-1] << endl; } } } } bool check_message(const string &message) { stringstream ss(message); string word; - bool capital(true), while_capital; + bool capital(true); while (ss >> word) { - while_capital=true; - - for (auto& c : word) { - if (c != toupper(c)) { - while_capital=false; - } - } - - if(! while_capital) { - cout << NOT_IN_CAPITAL_LETTERS << endl; + if (! check_word(word)) { capital=false; } } return capital; }