diff --git a/ReProjet/Sane_Granma.cc b/ReProjet/Sane_Granma.cc index 72bf3f9..4401c06 100644 --- a/ReProjet/Sane_Granma.cc +++ b/ReProjet/Sane_Granma.cc @@ -1,422 +1,421 @@ // Sane_Granma.cc // Auteur : Quentin Berling // Version : 1.0 #include #include #include #include #include using namespace std; +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"); + +constexpr size_t alphabet_size = 26; + +typedef array Alphabet; + struct StringPlus{ string str; unsigned nbT; unsigned nbD=0; string alpha; - array mat={0}; + Alphabet 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); +const Alphabet operator-(Alphabet u, Alphabet const &v); void operator+=(vector &u, vector const &v); -void operator-=(array &u, array const &v); +void operator-=(Alphabet &u, Alphabet 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 sort34(vector &dico); void sort4(vector &dico); -void find_anagrams(vector dico, - vector> &anagrams, vector anagram, - array letters); +void find_anagrams(vector dico, vector> &anagrams, + const vector &anagram, const Alphabet &letters); void print_anagrams(const vector> &anagrams, const StringPlus &message); -void print_permutations(const vector &anagram_vec, string permuted_anagram, string &permuted_anagrams); +void add_permutations(const vector &anagram_vec, string permuted_anagram, + string &permuted_anagrams); bool check_word(const string &str); void check_dico(const vector &dico); -bool enough_letters(const array &letters, - const array &word_letters); +bool enough_letters(const Alphabet &letters, const Alphabet &word_letters); 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; +const Alphabet operator-(Alphabet u, Alphabet const &v) { + Alphabet w; - for (int i=0; i < 26; i++) { + for (size_t i=0; i < alphabet_size; 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) { +void operator-=(Alphabet &u, Alphabet const &v) { u=u-v; } int main() { vector dico, allmessages; vector> anagrams; - array letters; + Alphabet 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, anagrams, vector(), letters); 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 != ".") { if (check_word(str)) { strplus=str_to_StrPlus(str); dico.push_back(strplus); } else { exit(0); } } else { 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++) { + for (size_t n=0; n < alphabet_size; 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++) { + for (size_t i=0; i < dico.size(); i++) { + for (size_t j=i+1; j < dico.size(); j++) { if (dico[i].str == dico[j].str) { cout << DOUBLE_WORD << 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) { sort34(nbd_sorted_dico); } sorted_dico+=nbd_sorted_dico; nbd_sorted_dico.clear(); } swap(dico, sorted_dico); } void sort34(vector &dico) { string alpha_max, alpha_min=dico[0].str; vector unsorted_dico, sorted_dico, alpha_sorted_dico; for (auto& wordplus : dico) { if (wordplus.alpha > alpha_max) { alpha_max=wordplus.alpha; } } while (dico.size() > 0) { alpha_min=alpha_max; for (auto& strplus : dico) { if (strplus.alpha <= alpha_min) { alpha_min=strplus.alpha; } } for (auto& strplus : dico) { if (strplus.alpha==alpha_min) { alpha_sorted_dico.push_back(strplus); } else { unsorted_dico.push_back(strplus); } } sort4(alpha_sorted_dico); sorted_dico+=alpha_sorted_dico; alpha_sorted_dico.clear(); swap(dico, unsorted_dico); unsorted_dico.clear(); } swap(dico, 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++) { + for (size_t 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++) { + for (size_t 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, - vector> &anagrams, vector anagram, - array letters) { +void find_anagrams(vector dico, vector> &anagrams, + const vector &anagram, const Alphabet &letters) { StringPlus wordplus; vector anagram_loop; - array letters_loop; + Alphabet letters_loop; unsigned letters_counter(0); while (! dico.empty()) { wordplus=dico.back(); dico.pop_back(); anagram_loop=anagram; letters_loop=letters; if (enough_letters(letters, wordplus.mat)) { anagram_loop.push_back(wordplus.str); letters_loop-=wordplus.mat; find_anagrams(dico, anagrams, anagram_loop, letters_loop); } if (dico.empty()) { for (auto& counter : letters_loop) { letters_counter+=counter; } if (letters_counter == 0) { anagrams.push_back(anagram_loop); } } } } -bool enough_letters(const array &letters, - const array &word_letters) { - for (unsigned n=0; n < 26; n++) { +bool enough_letters(const Alphabet &letters, const Alphabet &word_letters) { + for (size_t n=0; n < alphabet_size; n++) { if (letters[n] < word_letters[n]) { return false; } } return true; } void print_anagrams(const vector> &anagrams, const StringPlus &message) { string permuted_anagrams; cout << endl; if (check_message(message.str)) { if (anagrams.empty()) { cout << NO_ANAGRAM << endl; } else { for (auto& anagram : anagrams) { - print_permutations(anagram, string(), permuted_anagrams); + add_permutations(anagram, string(), permuted_anagrams); } cout << permuted_anagrams; } } } -void print_permutations(const vector &anagram_vec, string permuted_anagram, string &permuted_anagrams) { +void add_permutations(const vector &anagram_vec, string permuted_anagram, + string &permuted_anagrams) { unsigned anagram_size=anagram_vec.size(); if (anagram_size == 1) { permuted_anagram+=anagram_vec[0]; permuted_anagrams+=permuted_anagram+"\n"; } else { vector new_anagram; string permuted_anagram_ori=permuted_anagram; - for (unsigned i=0; i < anagram_size; i++) { - for (unsigned j=0; j < anagram_size; j++) { + for (size_t i=0; i < anagram_size; i++) { + for (size_t j=0; j < anagram_size; j++) { if (i == j) { permuted_anagram+=anagram_vec[j]+" "; } else { new_anagram.push_back(anagram_vec[j]); } } - print_permutations(new_anagram, permuted_anagram, permuted_anagrams); + add_permutations(new_anagram, permuted_anagram, permuted_anagrams); new_anagram.clear(); permuted_anagram=permuted_anagram_ori; } } } bool check_message(const string &message) { stringstream ss(message); string word; bool capital(true); while (ss >> word) { if (! check_word(word)) { capital=false; } } return capital; }