diff --git a/ReProjet/Sane_Granma.cc b/ReProjet/Sane_Granma.cc index e7121d7..eadac82 100644 --- a/ReProjet/Sane_Granma.cc +++ b/ReProjet/Sane_Granma.cc @@ -1,420 +1,418 @@ // 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; Alphabet mat={0}; }; const vector operator+(vector u, vector const &v); const Alphabet operator-(Alphabet u, Alphabet const &v); void operator+=(vector &u, vector 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, const vector &anagram, const Alphabet &letters); void print_anagrams(const vector> &anagrams, const StringPlus &message); 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 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 Alphabet operator-(Alphabet u, Alphabet const &v) { Alphabet w; 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-=(Alphabet &u, Alphabet const &v) { u=u-v; } int main() { vector dico, allmessages; vector> anagrams; - Alphabet letters; read_input(dico, allmessages); for (auto& wordplus : dico) { cout << wordplus.str << endl; } for (auto& message : allmessages) { - letters=message.mat; - find_anagrams(dico, anagrams, vector(), letters); + find_anagrams(dico, anagrams, vector(), message.mat); 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& letter : str) { if (letter != toupper(letter) || letter == '.') { 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& letter : str) { if (letter != ' ') { iter=toupper(letter)-'A'; strplus.mat[iter]+=1; } else { strplus.nbT--; } } 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 (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+=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; + string alpha_max, alpha_min; 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& wordplus : dico) { if (wordplus.alpha <= alpha_min) { alpha_min=wordplus.alpha; } } for (auto& wordplus : dico) { if (wordplus.alpha==alpha_min) { alpha_sorted_dico.push_back(wordplus); } else { unsorted_dico.push_back(wordplus); } } 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; + string alphabet_max, alphabet_min; 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 (size_t i=0; i < dico.size(); i++) { if (dico[i].str <= alphabet_min) { alphabet_min=dico[i].str; alphabet_min_index=i; } } 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, const vector &anagram, const Alphabet &letters) { StringPlus wordplus; vector anagram_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 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) { add_permutations(anagram, string(), permuted_anagrams); } cout << 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 (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]); } } 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; }