#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 256
typedef struct node_ {
char *word;
char *comparison;
struct node_ *next;
int Yes[N];
int No[N];
int not_equal[N];
int dimension;
} node;
typedef struct nodo_ {
char *word;
struct nodo_ *next;
} nodo;
typedef struct tree_node_ {
char *word;
struct tree_node_ *left;
struct tree_node_ *right;
} tree_node;
void define_alphabet2(int *alp)
{
for(char c = '0'; c <= '9'; ++alp[(int)c++]);
for(char c = 'A'; c <= 'Z'; ++alp[(int)c++]);
for(char c = 'a'; c <= 'z'; ++alp[(int)c++]);
++alp['-'];
++alp['_'];
}
int check_validity2(const char *p, const int *alp, int k)
{
unsigned int i;
for(i = 0; i < k && alp[(int)p[i]]; ++i);
return(i == k && !p[i]);
}
node* add_node2(char *i, node **p2, int l) {
node *new;
new = (node*)malloc(sizeof(node));
new->word = (char*)malloc(sizeof(char) * (l + 1));
strcpy(new->word, i);
new->comparison = (char*)malloc(sizeof(char) * (l + 1));
new->comparison[l] = '\0';
new->dimension = 0;
new->next = *p2;
*p2 = new;
return(*p2);
}
void add_eligible_word(char *i, tree_node **p, int l) {
if(*p == NULL) {
*p = (tree_node*)malloc(sizeof(tree_node));
(*p)->word = (char*)malloc(sizeof(char) * (l + 1));
strcpy((*p)->word, i);
(*p)->left = NULL;
(*p)->right = NULL;
} else if(strcmp((*p)->word, i) < 0) {
add_eligible_word(i, &(*p)->right, l);
} else {
add_eligible_word(i, &(*p)->left, l);
}
}
nodo* add_compatible_word2(char *i, nodo **p1, int l) {
nodo *new;
while((*p1 != NULL) && (strcmp((*p1)->word, i) <= 0)) {
p1 = &(*p1)->next;
}
new = (nodo*)malloc(sizeof(nodo));
new->word = (char*)malloc(sizeof(char) * (l + 1));
strcpy(new->word, i);
new->next = *p1;
*p1 = new;
return(*p1);
}
int calculate_compatibility2(const char *i, node *p2) {
int v[N] = {0};
unsigned int count;
for(count = 0; p2->word[count] && (p2->comparison[count] == '+' ? i[count] == p2->word[count] : i[count] != p2->word[count] && ++v[(int)i[count]] && (!p2->No[(int)i[count]] || p2->Yes[(int)i[count]] - v[(int)i[count]] >= 0)); ++count);
for(count = !p2->word[count] ? 0 : p2->dimension + 1; count < p2->dimension && v[p2->not_equal[count]] - p2->Yes[p2->not_equal[count]] >= 0; ++count);
return(count == p2->dimension);
}
int calculate_compatibilities2(char *i, node **p2) {
while(*p2 != NULL) {
if(calculate_compatibility2(i, *p2) != 1) {
return(-1);
}
p2 = &(*p2)->next;
}
return(1);
}
void add_words2(char *i, tree_node **p, nodo **p1, node **p2, int l, int *alp) {
while(1) {
//printf("inserire una nuova parola o il comando +inserisci_fine\n");
if(scanf("%s", i) == 1) {
if(strcmp("+inserisci_fine", i) == 0) {
break;
} else {
if(check_validity2(i, alp, l) == 1) {
add_eligible_word(i, p, l);
if(calculate_compatibilities2(i, p2) == 1) {
add_compatible_word2(i, p1, l);
}
}
}
}
}
}
int find_word2(char *i, tree_node **p) {
int val;
if(*p != NULL) {
if((val = strcmp((*p)->word, i)) == 0) {
return(1);
} else if(val < 0) {
return(find_word2(i, &(*p)->right));
} else {
return(find_word2(i, &(*p)->left));
}
} else {
return(-1);
}
}
void print_filtered_words2(nodo **p1) {
while(*p1 != NULL) {
printf("%s\n", (*p1)->word);
p1 = &(*p1)->next;
}
}
void calculate_comparison2(const char *k, node *p2) {
memset(p2->Yes, p2->dimension = 0, sizeof(*p2->Yes) * N);
memset(p2->No, 0, sizeof(*p2->No) * N);
int v[N] = {0};
for(unsigned int i = 0; k[i]; ++i)
{
if(p2->word[i] == k[i])
{
p2->comparison[i] = '+';
}
else
{
p2->comparison[i] = '/';
++v[(int)k[i]];
}
}
for(unsigned int i = 0; k[i]; ++i)
{
if(p2->comparison[i] == '/')
{
if(v[(int)p2->word[i]])
{
p2->comparison[i] = '|';
--v[(int)p2->word[i]];
if(!p2->Yes[(int)p2->word[i]]++)
{
p2->not_equal[(p2->dimension)++] = (unsigned char ) p2->word[i];
}
}
else
{
++p2->No[(int)p2->word[i]];
}
}
}
}
int list_length2(nodo **p1) {
int i = 0;
while(*p1 != NULL) {
++i;
p1 = &(*p1)->next;
}
return(i);
}
void compare2(nodo **p1, node *p2, char *k) {
nodo **pp1 = p1;
nodo *del1;
calculate_comparison2(k, p2);
while(*p1 != NULL) {
if(calculate_compatibility2((*p1)->word, p2) != 1) {
del1 = *p1;
*p1 = (*p1)->next;
free(del1);
} else {
p1 = &(*p1)->next;
}
}
printf("%s\n%d\n", p2->comparison, list_length2(pp1));
}
void start2(char *i, tree_node **p, nodo **p1, int *l, int *alp) {
int temp;
do {
//printf("inserire la lunghezza delle parole\n");
temp = scanf("%d", l);
} while((temp != 1) || (*l <= 0));
do {
do {
//printf("inserire una nuova parola o il comando +nuova_partita\n");
temp = scanf("%s", i);
} while(temp != 1);
if(check_validity2(i, alp, *l) == 1) {
add_eligible_word(i, p, *l);
add_compatible_word2(i, p1, *l);
}
} while(strcmp(i, "+nuova_partita") != 0);
}
void build_compatible_list(tree_node **p, nodo **p1, int l) {
if(*p != NULL) {
build_compatible_list(&(*p)->left, p1, l);
add_compatible_word2((*p)->word, p1, l);
build_compatible_list(&(*p)->right, p1, l);
}
}
void reset2(tree_node **p, nodo **p1, node **p2, int l) {
nodo *del1;
node *del2;
while(*p1 != NULL) {
del1 = *p1;
*p1 = (*p1)->next;
free(del1);
}
while(*p2 != NULL) {
del2 = *p2;
*p2 = (*p2)->next;
free(del2);
}
build_compatible_list(p, p1, l);
}
int end_game2(char *i, tree_node **p, nodo **p1, node **p2, int l, int *alp) {
int temp;
while(1) {
do {
//printf("inserire un comando di end-game\n");
temp = scanf("%s", i);
} while(temp != 1);
if(strcmp("+inserisci_inizio", i) == 0) {
while(1) {
do {
//printf("inserire una nuova parola oppure il comando +inserisci_fine\n");
temp = scanf("%s", i);
} while(temp != 1);
if(strcmp("+inserisci_fine", i) == 0) {
break;
} else {
if(check_validity2(i, alp, l) == 1) {
add_eligible_word(i, p, l);
}
}
}
} else if(strcmp("+nuova_partita", i) == 0) {
reset2(p, p1, p2, l);
return(1);
} else if(strcmp("+exit", i) == 0) {
return(-1);
} else {
printf("error\n");
}
}
}
int new_game2(char *i, tree_node **p, nodo **p1, node **p2, int l, int *alp) {
char *key;
int rounds;
int val;
key = (char*)malloc(sizeof(char) * (l + 1));
do {
//printf("inserire la parola di riferimento\n");
val = scanf("%s", key);
} while((val != 1) || !find_word2(key, p));
do {
//printf("inserire il numero di tentativi a disposizione\n");
val = scanf("%d", &rounds);
} while(val != 1);
while(1) {
do {
//printf("inserire una parola ammissibile da confrontare oppure un comando di game\n");
val = scanf("%s", i);
} while(val != 1);
if(strcmp(key, i) == 0) {
printf("ok\n");
return(end_game2(i, p, p1, p2, l, alp));
} else if(strcmp("+nuova_partita", i) == 0) {
reset2(p, p1, p2, l);
return(1);
} else if(strcmp("+stampa_filtrate", i) == 0) {
print_filtered_words2(p1);
} else if(strcmp("+inserisci_inizio", i) == 0) {
add_words2(i, p, p1, p2, l, alp);
} else if(strcmp("+exit", i) == 0) {
return(-1);
} else if(find_word2(i, p) == 1) {
compare2(p1, add_node2(i, p2, l), key);
if((--rounds) == 0) {
printf("ko\n");
return(end_game2(i, p, p1, p2, l, alp));
}
} else {
printf("not_exists\n");
}
}
}
int main() {
int word_length;
int close;
int alphabet[N] = {0};
char input[500];
tree_node *eligible_words = NULL;
nodo *compatible_words = NULL;
node *compared_words = NULL;
define_alphabet2(alphabet);
start2(input, &eligible_words, &compatible_words, &word_length, alphabet);
do {
close = new_game2(input, &eligible_words, &compatible_words, &compared_words, word_length, alphabet);
} while(close != -1);
return(0);
}