Page MenuHomec4science

Sane_Granma.cc
No OneTemporary

File Metadata

Created
Thu, Mar 28, 16:17

Sane_Granma.cc

// Sane_Granma.cc
// Auteur : Quentin Berling
// Version : 1.0
#include <array>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
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<unsigned, 26> Alphabet;
struct StringPlus{
string str;
unsigned nbT;
unsigned nbD=0;
string alpha;
Alphabet mat={0};
};
const vector<StringPlus> operator+(vector<StringPlus> u, vector<StringPlus> const &v);
const Alphabet operator-(Alphabet u, Alphabet const &v);
void operator+=(vector<StringPlus> &u, vector<StringPlus> const &v);
void operator-=(Alphabet &u, Alphabet const &v);
StringPlus str_to_strplus(const string &str);
void read_input(vector<StringPlus> &dico, vector<StringPlus> &allmessages);
void sort1234(vector<StringPlus> &dico);
void sort234(vector<StringPlus> &dico);
void sort34(vector<StringPlus> &dico);
void sort4(vector<StringPlus> &dico);
void find_anagrams(vector<StringPlus> dico, vector<vector<string>> &anagrams,
const vector<string> &anagram, const Alphabet &letters);
void print_anagrams(const vector<vector<string>> &anagrams, const StringPlus &message);
void add_permutations(const vector<string> &anagram_vec, string permuted_anagram,
string &permuted_anagrams);
bool check_word(const string &str);
void check_dico(const vector<StringPlus> &dico);
bool enough_letters(const Alphabet &letters, const Alphabet &word_letters);
bool check_message(const string &message);
const vector<StringPlus> operator+(vector<StringPlus> u, vector<StringPlus> const &v) {
vector<StringPlus> 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<StringPlus> &u, vector<StringPlus> const &v) {
u=u+v;
}
void operator-=(Alphabet &u, Alphabet const &v) {
u=u-v;
}
int main() {
vector<StringPlus> dico, allmessages;
vector<vector<string>> anagrams;
read_input(dico, allmessages);
for (auto& wordplus : dico) {
cout << wordplus.str << endl;
}
for (auto& message : allmessages) {
find_anagrams(dico, anagrams, vector<string>(), message.mat);
print_anagrams(anagrams, message);
anagrams.clear();
}
return 0;
}
void read_input(vector<StringPlus> &dico, vector<StringPlus> &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<StringPlus> &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<StringPlus> &dico) {
unsigned nbTmax(0);
vector<StringPlus> 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<StringPlus> &dico) {
unsigned nbDmax(0);
vector<StringPlus> 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<StringPlus> &dico) {
string alpha_max, alpha_min;
vector<StringPlus> 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<StringPlus> &dico) {
string alphabet_max, alphabet_min;
unsigned alphabet_min_index(0);
vector<StringPlus> 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<StringPlus> dico, vector<vector<string>> &anagrams,
const vector<string> &anagram, const Alphabet &letters) {
StringPlus wordplus;
vector<string> 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<vector<string>> &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<string> &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<string> 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;
}

Event Timeline