Page Menu
Home
c4science
Search
Configure Global Search
Log In
Files
F56496467
Sane_Granma.cc
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Thu, Mar 28, 16:17
Size
10 KB
Mime Type
text/x-c
Expires
Sat, Mar 30, 16:17 (2 d)
Engine
blob
Format
Raw Data
Handle
16724691
Attached To
R10932 CS-119
Sane_Granma.cc
View Options
// 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
Log In to Comment