Progetto di informatica

di
PhiL99
il
73 risposte
P
PhiL99
Pochi posts
Iscritto da
set, 2022
Messaggi:
45

Progetto di informatica

Salve a tutti, ho bisogno che mi aiutiate con il mio programma. Devo assolutamente completarlo entro il 9/9.
Devo trovare un modo per rendere più veloce la sua esecuzione. Ho provato a cambiare le strutture dati, ma l'esito del test è ancora negativo. Mi serve il vostro aiuto per trovare un algoritmo più efficiente. Di seguito trovate il codice che ho scritto.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct node_s {
char *key;
int color; // 0 = red, 1 = black
struct node_s *left;
struct node_s *right;
struct node_s *father;
} node_t;

typedef struct node_m {
char *key;
struct node_m *next;
struct node_m *prev;
} node_n;

typedef struct node_a {
char *key;
char *cmp;
struct node_a *next;
} node_b;

typedef struct node_x {
node_t *root;
node_t *nil;
} node_y;

int search(char word[], node_t *n, node_y *t);
node_n * calculate_compatibility(char cmp[], char word[], node_n *n);
node_n * check(char word[], char ref[], char res[], node_n *n);
int is_compatible(char *word, node_b *n);
node_n * build_compatibility_list(node_y *r, node_t *t, node_n *n, int length);
void right_rotate(node_y *t, node_t *x);
void left_rotate(node_y *t, node_t *x);
void rb_insert_fixup(node_y *t, node_t *z);
void rb_insert(node_y *t, node_t *z);

int
main(void)
{
int length, max_cmp, found, new_match, inserted;
char *word = NULL, *ref = NULL;
node_b *compare_list = NULL, *last_compare = NULL, *new_nodeb = NULL;
node_n *compatibility_list = NULL, *new_noden = NULL, *currn = NULL;
node_t *new_nodet = NULL;
node_y *rb_root = NULL;

if ((1 != scanf("%d", &length)) || (length <= 0)) {
return (0);
}
length += 1; /* carattere terminatore */
if (length > 18) {
word = (char *)calloc(length, sizeof (char));
} else {
word = (char *)calloc(18, sizeof (char));
}
if (scanf("%s", word) != 1) {
return (0);
}
rb_root = (node_y *)malloc(sizeof (node_y));
rb_root->nil = (node_t *) malloc(sizeof (node_t));
rb_root->nil->color = 1;
rb_root->root = rb_root->nil;
while (strcmp(word, "+nuova_partita") != 0) {
new_nodet = (node_t *)malloc(sizeof (node_t));
new_nodet->key = (char *)calloc(length, sizeof (char));
strcpy(new_nodet->key, word);
new_nodet->left = rb_root->nil;
new_nodet->right = rb_root->nil;
new_nodet->father = rb_root->nil;
rb_insert(rb_root, new_nodet);
if (scanf("%s", word) != 1) {
return (0);
}
}
compatibility_list = build_compatibility_list(rb_root, rb_root->root, compatibility_list, length);
ref = (char *)calloc(length, sizeof (char));
while (1) {
if (scanf("%s", ref) != 1) {
return (0);
}
if (1 != scanf("%d", &max_cmp)) {
return (0);
}
found = -1;
while ((found == -1) && (max_cmp > 0)) {
if (scanf("%s", word) != 1) {
return (0);
}
if (strcmp(word, "+inserisci_inizio") == 0) {
if (scanf("%s", word) != 1) {
return (0);
}
while (strcmp(word, "+inserisci_fine") != 0) {
new_nodet = (node_t *)malloc(sizeof (node_t));
new_nodet->key = (char *)calloc(length, sizeof (char));
strcpy(new_nodet->key, word);
new_nodet->left = rb_root->nil;
new_nodet->right = rb_root->nil;
new_nodet->father = rb_root->nil;
rb_insert(rb_root, new_nodet);
if (is_compatible(word, compare_list) == 1) {
new_noden = (node_n *)malloc(sizeof (node_n));
new_noden->key = (char *)calloc(length, sizeof (char));
strcpy(new_noden->key, word);
new_noden->next = NULL;
new_noden->prev = NULL;
if (compatibility_list != NULL) {
currn = compatibility_list;
inserted = -1;
while (inserted == -1) {
if (strcmp(new_noden->key, currn->key) < 0) {
new_noden->next = currn;
if (currn->prev != NULL) {
new_noden->prev = currn->prev;
currn->prev->next = new_noden;
} else {compatibility_list = new_noden;}
currn->prev = new_noden;
inserted = 1;
} else if (!(currn->next != NULL)) {
new_noden->prev = currn;
currn->next = new_noden;
inserted = 1;
}
currn = currn->next;
}
} else {
compatibility_list = new_noden;
}
}
if (scanf("%s", word) != 1) {
return (0);
}
}
} else if (strcmp(word, "+stampa_filtrate") == 0) {
currn = compatibility_list;
while (currn != NULL) {
printf("%s", currn->key);
currn = currn->next;
if (currn != NULL) {
printf(",\n");
} else {
printf("\n");
}
}
} else if (strcmp(word, "+nuova_partita") == 0) {
new_match = 1;
break;
} else if (search(word, rb_root->root, rb_root) == -1) {
printf("not_exists\n");
} else if (strcmp(word, ref) == 0) {
printf("ok\n");
found = 1;
} else {
new_nodeb = (node_b *)malloc(sizeof (node_b));
new_nodeb->key = (char *)calloc(length, sizeof (char));
strcpy(new_nodeb->key, word);
new_nodeb->next = NULL;
new_nodeb->cmp = (char *)calloc(length, sizeof (char));
compatibility_list = check(word, ref, new_nodeb->cmp, compatibility_list);
if (compare_list != NULL) {
last_compare->next = new_nodeb;
last_compare = new_nodeb;
} else {
compare_list = new_nodeb;
last_compare = compare_list;
}
max_cmp -= 1;
if (max_cmp == 0) {printf("ko\n");}
}
}
if (new_match != 1) {
if (scanf("%s", word) != 1) {
return (0);
}
while (strcmp(word, "+nuova_partita") != 0) {
if (strcmp(word, "+inserisci_inizio") == 0) {
if (scanf("%s", word) != 1) {
return (0);
}
while (strcmp(word, "+inserisci_fine") != 0) {
new_nodet = (node_t *)malloc(sizeof (node_t));
new_nodet->key = (char *)calloc(length, sizeof (char));
strcpy(new_nodet->key, word);
new_nodet->left = rb_root->nil;
new_nodet->right = rb_root->nil;
new_nodet->father = rb_root->nil;
rb_insert(rb_root, new_nodet);
if (1 != scanf("%s", word)) {
return (0);
}
}
} else {
return (0);
}
if (scanf("%s", word) != 1) {
return (0);
}
}
}
new_match = 0;
while (compatibility_list != NULL) {
currn = compatibility_list;
compatibility_list = compatibility_list->next;
free(currn);
}
compatibility_list = build_compatibility_list(rb_root, rb_root->root, compatibility_list, length);
while (compare_list != NULL) {
last_compare = compare_list;
compare_list = compare_list->next;
free(last_compare);
}
last_compare = NULL;
}
return (0);
}

int
search(char word[], node_t *n, node_y *t)
{
if (n == t->nil) {
return (-1);
} else if (strcmp(n->key, word) == 0) {
return (1);
} else {
if (strcmp(word, n->key) < 0) {
return (search(word, n->left, t));
} else {
return (search(word, n->right, t));
}
}
}

node_n *
calculate_compatibility(char cmp[], char word[], node_n *n)
{
int count;
int count1;
int wpos;
int rpos;
int reps;
int length;
int deleted;
node_n *curr, *del;
length = strlen(cmp);
curr = n;
while (curr != NULL) {
deleted = -1;
for (count = 0; count < length; ++count) {
if (cmp[count] == '+') {
if (word[count] != curr->key[count]) {
if ((curr->prev != NULL) && (curr->next != NULL)) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
} else if (!(curr->prev != NULL) && (curr->next != NULL)) {
curr->next->prev = NULL;
n = curr->next;
} else if ((curr->prev != NULL) && !(curr->next != NULL)) {
curr->prev->next = NULL;
} else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
n = NULL;
}
del = curr;
curr = curr->next;
free(del);
deleted = 1;
break;
}
} else if (cmp[count] == '|') {
if (word[count] == curr->key[count]) {
if ((curr->prev != NULL) && (curr->next != NULL)) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
} else if (!(curr->prev != NULL) && (curr->next != NULL)) {
curr->next->prev = NULL;
n = curr->next;
} else if ((curr->prev != NULL) && !(curr->next != NULL)) {
curr->prev->next = NULL;
} else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
n = NULL;
}
del = curr;
curr = curr->next;
free(del);
deleted = 1;
break;
} else {
wpos = 0;
rpos = 0;
reps = 0;
for (count1 = 0; count1 < length; ++count1) {
if (word[count] == word[count1]) {
if (cmp[count1] == '|') {
++wpos;
} else if (cmp[count1] == '+') {
++rpos;
}
}
if (word[count] == curr->key[count1]) {
++reps;
}
}
if (reps < (wpos + rpos)) {
if ((curr->prev != NULL) && (curr->next != NULL)) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
} else if (!(curr->prev != NULL) && (curr->next != NULL)) {
curr->next->prev = NULL;
n = curr->next;
} else if ((curr->prev != NULL) && !(curr->next != NULL)) {
curr->prev->next = NULL;
} else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
n = NULL;
}
del = curr;
curr = curr->next;
free(del);
deleted = 1;
break;
}
}
} else {
if (word[count] == curr->key[count]) {
if ((curr->prev != NULL) && (curr->next != NULL)) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
} else if (!(curr->prev != NULL) && (curr->next != NULL)) {
curr->next->prev = NULL;
n = curr->next;
} else if ((curr->prev != NULL) && !(curr->next != NULL)) {
curr->prev->next = NULL;
} else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
n = NULL;
}
del = curr;
curr = curr->next;
free(del);
deleted = 1;
break;
} else {
wpos = 0;
rpos = 0;
reps = 0;
for (count1 = 0; count1 < length; ++count1) {
if (word[count] == word[count1]) {
if (cmp[count1] == '|') {
++wpos;
} else if (cmp[count1] == '+') {
++rpos;
}
}
if (curr->key[count1] == word[count]) {
++reps;
}
}
if ((wpos + rpos) != reps) {
if ((curr->prev != NULL) && (curr->next != NULL)) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
} else if (!(curr->prev != NULL) && (curr->next != NULL)) {
curr->next->prev = NULL;
n = curr->next;
} else if ((curr->prev != NULL) && !(curr->next != NULL)) {
curr->prev->next = NULL;
} else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
n = NULL;
}
del = curr;
curr = curr->next;
free(del);
deleted = 1;
break;
}
}
}
}
if (deleted == -1) {
curr = curr->next;
}
}
return (n);
}

node_n *
check(char word[], char ref[], char res[], node_n *n)
{
int count;
int count1;
int exist;
int reps;
int rpos;
int wpos;
int length;
node_n *curr;
length = strlen(word);
for (count = 0; count < length; ++count) {
if (word[count] == ref[count]) {
res[count] = '+';
} else {
reps = 0;
rpos = 0;
wpos = 0;
exist = -1;
for (count1 = 0; count1 < length; ++count1) {
if (word[count] == ref[count1]) {
exist = 1;
++reps;
if (word[count1] == ref[count1]) {
++rpos;
}
}
else if ((count1 < count) && (word[count1] == word[count])) {
++wpos;
}
}
if ((exist == -1) || (wpos >= (reps - rpos))) {
res[count] = '/';
} else {res[count] = '|';}
}
}
res[length] = '\0';
printf("%s,\n", res);
n = calculate_compatibility(res, word, n);
curr = n;
count = 0;
while (curr != NULL) {
++count;
curr = curr->next;
}
printf("%d\n", count);
return (n);
}

int
is_compatible(char *word, node_b *n)
{
int wpos, rpos, reps;
int count;
int count1;
int length;
node_b *curr;
length = strlen(word);
curr = n;
while (curr != NULL) {
for (count = 0; count < length; ++count) {
if (curr->cmp[count] == '+') {
if (word[count] != curr->key[count]) {
return (-1);
}
} else if (curr->cmp[count] == '|') {
if (word[count] == curr->key[count]) {
return (-1);
}
wpos = 0;
rpos = 0;
reps = 0;
for (count1 = 0; count1 < length; ++count1) {
if (curr->key[count] == curr->key[count1]) {
if (curr->cmp[count1] == '|') {
++wpos;
} else if (curr->cmp[count1] == '+') {
++rpos;
}
}
if (word[count1] == curr->key[count]) {
++reps;
}
}
if (reps < (wpos + rpos)) {
return (-1);
}
} else {
if (word[count] == curr->key[count]) {
return (-1);
}
wpos = 0;
rpos = 0;
reps = 0;
for (count1 = 0; count1 < length; ++count1) {
if (curr->key[count] == curr->key[count1]) {
if (curr->cmp[count1] == '|') {
++wpos;
} else if (curr->cmp[count1] == '+') {
++rpos;
}
}
if (curr->key[count] == word[count1]) {
++reps;
}
}
if ((wpos + rpos) != reps) {
return (-1);
}
}
}
curr = curr->next;
}
return (1);
}

node_n *
build_compatibility_list(node_y *r, node_t *t, node_n *n, int length) {
node_n *new_noden, *currn;
int inserted;
if (t != r->nil) {
new_noden = (node_n *) malloc(sizeof(node_n));
new_noden->key = (char *) calloc(length, sizeof(char));
strcpy(new_noden->key, t->key);
new_noden->next = NULL;
new_noden->prev = NULL;
if (n != NULL) {
currn = n;
inserted = -1;
while (inserted == -1) {
if (strcmp(new_noden->key, currn->key) < 0) {
new_noden->next = currn;
if (currn->prev != NULL) {
new_noden->prev = currn->prev;
currn->prev->next = new_noden;
} else { n = new_noden; }
currn->prev = new_noden;
inserted = 1;
} else if (!(currn->next != NULL)) {
new_noden->prev = currn;
currn->next = new_noden;
inserted = 1;
}
currn = currn->next;
}
} else {
n = new_noden;
}
n = build_compatibility_list(r, t->left, n, length);
n = build_compatibility_list(r, t->right, n, length);
}
return (n);
}

void
left_rotate(node_y *t, node_t *x) {
node_t *y;
y = x->right;
x->right = y->left;
if (y->left != t->nil) {
y->left->father = x;
}
y->father = x->father;
if (x->father == t->nil) {
t->root = y;
} else if (x == x->father->left) {
x->father->left = y;
} else {
x->father->right = y;
}
y->left = x;
x->father = y;
return;
}

void
right_rotate(node_y *t, node_t *x) {
node_t *y;
y = x->left;
x->left = y->right;
if (y->right != t->nil) {
y->right->father = x;
}
y->father = x->father;
if (x->father == t->nil) {
t->root = y;
} else if (x == x->father->left) {
x->father->left = y;
} else {
x->father->right = y;
}
y->right = x;
x->father = y;
return;
}

void
rb_insert(node_y *t, node_t *z) {
node_t *y, *x;
y = t->nil;
x = t->root;
while (x != t->nil) {
y = x;
if (strcmp(z->key, x->key) < 0) {
x = x->left;
} else {
x = x->right;
}
}
z->father = y;
if (y == t->nil) {
t->root = z;
} else if (strcmp(z->key, y->key) < 0) {
y->left = z;
} else {
y->right = z;
}
z->left = t->nil;
z->right = t->nil;
z->color = 0;
rb_insert_fixup(t, z);
return;
}

void
rb_insert_fixup(node_y *t, node_t *z) {
node_t *x, *y;
if (z == t->root) {
t->root->color = 1;
} else {
x = z->father;
if (x->color == 0) {
if (x == x->father->left) {
y = x->father->right;
if (y->color == 0) {
x->color = 1;
y->color = 1;
x->father->color = 0;
rb_insert_fixup(t, x->father);
} else {
if (z == x->right) {
z = x;
left_rotate(t, z);
x = z->father;
}
x->color = 1;
x->father->color = 0;
right_rotate(t, x->father);
}
} else {
y = x->father->left;
if (y->color == 0) {
x->color = 1;
y->color = 1;
x->father->color = 0;
rb_insert_fixup(t, x->father);
} else {
if (z == x->left) {
z = x;
right_rotate(t, z);
x = z->father;
}
x->color = 1;
x->father->color = 0;
left_rotate(t, x->father);
}
}
}
}
return;
}
Allegati:
32479_a2a49b87df32fdefddefbaa513ae00f9.jpg
32479_a2a49b87df32fdefddefbaa513ae00f9.jpg

32479_3a00ffaae0e1273cdc58be6ef8b710f5.jpg
32479_3a00ffaae0e1273cdc58be6ef8b710f5.jpg

32479_e4c5ad39681e54e1f15d7460ee615d24.jpg
32479_e4c5ad39681e54e1f15d7460ee615d24.jpg

32479_433d53f447a2c9282d0205dfa99f1c9a.jpg
32479_433d53f447a2c9282d0205dfa99f1c9a.jpg

32479_3fc4276e96141aeb98f4ff7666e3ea41.jpg
32479_3fc4276e96141aeb98f4ff7666e3ea41.jpg

73 Risposte

  • P
    PhiL99
    Pochi posts
    Iscritto da
    set, 2022
    Messaggi:
    45

    Re: Progetto di informatica

    In allegato il continuo della specifica.
    Allegati:
    32479_b804c0dd6275851fdedc10ff65e75c47.jpg
    32479_b804c0dd6275851fdedc10ff65e75c47.jpg

    32479_a149e5d70687cd2a66ad143850e5b5e1.jpg
    32479_a149e5d70687cd2a66ad143850e5b5e1.jpg

    32479_a56b094efcf21fdbb736411430e0ce18.jpg
    32479_a56b094efcf21fdbb736411430e0ce18.jpg

    32479_19c875b1931f19b21f3708e01bc6efa9.jpg
    32479_19c875b1931f19b21f3708e01bc6efa9.jpg

    32479_5167725a6457579d4dcff6547e61dfe5.jpg
    32479_5167725a6457579d4dcff6547e61dfe5.jpg
  • P
    PhiL99
    Pochi posts
    Iscritto da
    set, 2022
    Messaggi:
    45

    Re: Progetto di informatica

    In allegato le ultime pagine della specifica.
    Allegati:
    32479_db8471d0e334d8467e55fc0327d04caf.jpg
    32479_db8471d0e334d8467e55fc0327d04caf.jpg

    32479_b601b168429c75e97b7c7be4bd142819.jpg
    32479_b601b168429c75e97b7c7be4bd142819.jpg
  • Andrea Quaglia
    Andrea Quaglia
    Molto attivo
    Iscritto da
    giu, 2017
    Messaggi:
    603

    Re: Progetto di informatica

    Incomincia a mettere il codice tra i tag CODE (vedi "Editor completo & Anteprima").
    Poi ne riparliamo.
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Progetto di informatica

    Ciao, ma è solo una questione di efficienza? Nel senso che il codice che hai scritto, anche se lento, funziona correttamente?
  • P
    PhiL99
    Pochi posts
    Iscritto da
    set, 2022
    Messaggi:
    45

    Re: Progetto di informatica

    Nippolo ha scritto:

    Ciao, ma è solo una questione di efficienza? Nel senso che il codice che hai scritto, anche se lento, funziona correttamente?
    Sì, è solo una questione di efficienza. Il programma funziona correttamente.
  • P
    PhiL99
    Pochi posts
    Iscritto da
    set, 2022
    Messaggi:
    45

    Re: Progetto di informatica

    
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct node_s {
char *key;
int color; // 0 = red, 1 = black
struct node_s *left;
struct node_s *right;
struct node_s *father;
} node_t;

typedef struct node_m {
char *key;
struct node_m *next;
struct node_m *prev;
} node_n;

typedef struct node_a {
char *key;
char *cmp;
struct node_a *next;
} node_b;

typedef struct node_x {
node_t *root;
node_t *nil;
} node_y;

int search(char word[], node_t *n, node_y *t);
node_n * calculate_compatibility(char cmp[], char word[], node_n *n);
node_n * check(char word[], char ref[], char res[], node_n *n);
int is_compatible(char *word, node_b *n);
node_n * build_compatibility_list(node_y *r, node_t *t, node_n *n, int length);
void right_rotate(node_y *t, node_t *x);
void left_rotate(node_y *t, node_t *x);
void rb_insert_fixup(node_y *t, node_t *z);
void rb_insert(node_y *t, node_t *z);

int
main(void)
{
int length, max_cmp, found, new_match, inserted;
char *word = NULL, *ref = NULL;
node_b *compare_list = NULL, *last_compare = NULL, *new_nodeb = NULL;
node_n *compatibility_list = NULL, *new_noden = NULL, *currn = NULL;
node_t *new_nodet = NULL;
node_y *rb_root = NULL;

if ((1 != scanf("%d", &length)) || (length <= 0)) {
return (0);
}
length += 1; /* carattere terminatore */
if (length > 18) {
word = (char *)calloc(length, sizeof (char));
} else {
word = (char *)calloc(18, sizeof (char));
}
if (scanf("%s", word) != 1) {
return (0);
}
rb_root = (node_y *)malloc(sizeof (node_y));
rb_root->nil = (node_t *) malloc(sizeof (node_t));
rb_root->nil->color = 1;
rb_root->root = rb_root->nil;
while (strcmp(word, "+nuova_partita") != 0) {
new_nodet = (node_t *)malloc(sizeof (node_t));
new_nodet->key = (char *)calloc(length, sizeof (char));
strcpy(new_nodet->key, word);
new_nodet->left = rb_root->nil;
new_nodet->right = rb_root->nil;
new_nodet->father = rb_root->nil;
rb_insert(rb_root, new_nodet);
if (scanf("%s", word) != 1) {
return (0);
}
}
compatibility_list = build_compatibility_list(rb_root, rb_root->root, compatibility_list, length);
ref = (char *)calloc(length, sizeof (char));
while (1) {
if (scanf("%s", ref) != 1) {
return (0);
}
if (1 != scanf("%d", &max_cmp)) {
return (0);
}
found = -1;
while ((found == -1) && (max_cmp > 0)) {
if (scanf("%s", word) != 1) {
return (0);
}
if (strcmp(word, "+inserisci_inizio") == 0) {
if (scanf("%s", word) != 1) {
return (0);
}
while (strcmp(word, "+inserisci_fine") != 0) {
new_nodet = (node_t *)malloc(sizeof (node_t));
new_nodet->key = (char *)calloc(length, sizeof (char));
strcpy(new_nodet->key, word);
new_nodet->left = rb_root->nil;
new_nodet->right = rb_root->nil;
new_nodet->father = rb_root->nil;
rb_insert(rb_root, new_nodet);
if (is_compatible(word, compare_list) == 1) {
new_noden = (node_n *)malloc(sizeof (node_n));
new_noden->key = (char *)calloc(length, sizeof (char));
strcpy(new_noden->key, word);
new_noden->next = NULL;
new_noden->prev = NULL;
if (compatibility_list != NULL) {
currn = compatibility_list;
inserted = -1;
while (inserted == -1) {
if (strcmp(new_noden->key, currn->key) < 0) {
new_noden->next = currn;
if (currn->prev != NULL) {
new_noden->prev = currn->prev;
currn->prev->next = new_noden;
} else {compatibility_list = new_noden;}
currn->prev = new_noden;
inserted = 1;
} else if (!(currn->next != NULL)) {
new_noden->prev = currn;
currn->next = new_noden;
inserted = 1;
}
currn = currn->next;
}
} else {
compatibility_list = new_noden;
}
}
if (scanf("%s", word) != 1) {
return (0);
}
}
} else if (strcmp(word, "+stampa_filtrate") == 0) {
currn = compatibility_list;
while (currn != NULL) {
printf("%s", currn->key);
currn = currn->next;
if (currn != NULL) {
printf(",\n");
} else {
printf("\n");
}
}
} else if (strcmp(word, "+nuova_partita") == 0) {
new_match = 1;
break;
} else if (search(word, rb_root->root, rb_root) == -1) {
printf("not_exists\n");
} else if (strcmp(word, ref) == 0) {
printf("ok\n");
found = 1;
} else {
new_nodeb = (node_b *)malloc(sizeof (node_b));
new_nodeb->key = (char *)calloc(length, sizeof (char));
strcpy(new_nodeb->key, word);
new_nodeb->next = NULL;
new_nodeb->cmp = (char *)calloc(length, sizeof (char));
compatibility_list = check(word, ref, new_nodeb->cmp, compatibility_list);
if (compare_list != NULL) {
last_compare->next = new_nodeb;
last_compare = new_nodeb;
} else {
compare_list = new_nodeb;
last_compare = compare_list;
}
max_cmp -= 1;
if (max_cmp == 0) {printf("ko\n");}
}
}
if (new_match != 1) {
if (scanf("%s", word) != 1) {
return (0);
}
while (strcmp(word, "+nuova_partita") != 0) {
if (strcmp(word, "+inserisci_inizio") == 0) {
if (scanf("%s", word) != 1) {
return (0);
}
while (strcmp(word, "+inserisci_fine") != 0) {
new_nodet = (node_t *)malloc(sizeof (node_t));
new_nodet->key = (char *)calloc(length, sizeof (char));
strcpy(new_nodet->key, word);
new_nodet->left = rb_root->nil;
new_nodet->right = rb_root->nil;
new_nodet->father = rb_root->nil;
rb_insert(rb_root, new_nodet);
if (1 != scanf("%s", word)) {
return (0);
}
}
} else {
return (0);
}
if (scanf("%s", word) != 1) {
return (0);
}
}
}
new_match = 0;
while (compatibility_list != NULL) {
currn = compatibility_list;
compatibility_list = compatibility_list->next;
free(currn);
}
compatibility_list = build_compatibility_list(rb_root, rb_root->root, compatibility_list, length);
while (compare_list != NULL) {
last_compare = compare_list;
compare_list = compare_list->next;
free(last_compare);
}
last_compare = NULL;
}
return (0);
}

int
search(char word[], node_t *n, node_y *t)
{
if (n == t->nil) {
return (-1);
} else if (strcmp(n->key, word) == 0) {
return (1);
} else {
if (strcmp(word, n->key) < 0) {
return (search(word, n->left, t));
} else {
return (search(word, n->right, t));
}
}
}

node_n *
calculate_compatibility(char cmp[], char word[], node_n *n)
{
int count;
int count1;
int wpos;
int rpos;
int reps;
int length;
int deleted;
node_n *curr, *del;
length = strlen(cmp);
curr = n;
while (curr != NULL) {
deleted = -1;
for (count = 0; count < length; ++count) {
if (cmp[count] == '+') {
if (word[count] != curr->key[count]) {
if ((curr->prev != NULL) && (curr->next != NULL)) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
} else if (!(curr->prev != NULL) && (curr->next != NULL)) {
curr->next->prev = NULL;
n = curr->next;
} else if ((curr->prev != NULL) && !(curr->next != NULL)) {
curr->prev->next = NULL;
} else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
n = NULL;
}
del = curr;
curr = curr->next;
free(del);
deleted = 1;
break;
}
} else if (cmp[count] == '|') {
if (word[count] == curr->key[count]) {
if ((curr->prev != NULL) && (curr->next != NULL)) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
} else if (!(curr->prev != NULL) && (curr->next != NULL)) {
curr->next->prev = NULL;
n = curr->next;
} else if ((curr->prev != NULL) && !(curr->next != NULL)) {
curr->prev->next = NULL;
} else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
n = NULL;
}
del = curr;
curr = curr->next;
free(del);
deleted = 1;
break;
} else {
wpos = 0;
rpos = 0;
reps = 0;
for (count1 = 0; count1 < length; ++count1) {
if (word[count] == word[count1]) {
if (cmp[count1] == '|') {
++wpos;
} else if (cmp[count1] == '+') {
++rpos;
}
}
if (word[count] == curr->key[count1]) {
++reps;
}
}
if (reps < (wpos + rpos)) {
if ((curr->prev != NULL) && (curr->next != NULL)) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
} else if (!(curr->prev != NULL) && (curr->next != NULL)) {
curr->next->prev = NULL;
n = curr->next;
} else if ((curr->prev != NULL) && !(curr->next != NULL)) {
curr->prev->next = NULL;
} else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
n = NULL;
}
del = curr;
curr = curr->next;
free(del);
deleted = 1;
break;
}
}
} else {
if (word[count] == curr->key[count]) {
if ((curr->prev != NULL) && (curr->next != NULL)) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
} else if (!(curr->prev != NULL) && (curr->next != NULL)) {
curr->next->prev = NULL;
n = curr->next;
} else if ((curr->prev != NULL) && !(curr->next != NULL)) {
curr->prev->next = NULL;
} else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
n = NULL;
}
del = curr;
curr = curr->next;
free(del);
deleted = 1;
break;
} else {
wpos = 0;
rpos = 0;
reps = 0;
for (count1 = 0; count1 < length; ++count1) {
if (word[count] == word[count1]) {
if (cmp[count1] == '|') {
++wpos;
} else if (cmp[count1] == '+') {
++rpos;
}
}
if (curr->key[count1] == word[count]) {
++reps;
}
}
if ((wpos + rpos) != reps) {
if ((curr->prev != NULL) && (curr->next != NULL)) {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
} else if (!(curr->prev != NULL) && (curr->next != NULL)) {
curr->next->prev = NULL;
n = curr->next;
} else if ((curr->prev != NULL) && !(curr->next != NULL)) {
curr->prev->next = NULL;
} else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
n = NULL;
}
del = curr;
curr = curr->next;
free(del);
deleted = 1;
break;
}
}
}
}
if (deleted == -1) {
curr = curr->next;
}
}
return (n);
}

node_n *
check(char word[], char ref[], char res[], node_n *n)
{
int count;
int count1;
int exist;
int reps;
int rpos;
int wpos;
int length;
node_n *curr;
length = strlen(word);
for (count = 0; count < length; ++count) {
if (word[count] == ref[count]) {
res[count] = '+';
} else {
reps = 0;
rpos = 0;
wpos = 0;
exist = -1;
for (count1 = 0; count1 < length; ++count1) {
if (word[count] == ref[count1]) {
exist = 1;
++reps;
if (word[count1] == ref[count1]) {
++rpos;
}
}
else if ((count1 < count) && (word[count1] == word[count])) {
++wpos;
}
}
if ((exist == -1) || (wpos >= (reps - rpos))) {
res[count] = '/';
} else {res[count] = '|';}
}
}
res[length] = '\0';
printf("%s,\n", res);
n = calculate_compatibility(res, word, n);
curr = n;
count = 0;
while (curr != NULL) {
++count;
curr = curr->next;
}
printf("%d\n", count);
return (n);
}

int
is_compatible(char *word, node_b *n)
{
int wpos, rpos, reps;
int count;
int count1;
int length;
node_b *curr;
length = strlen(word);
curr = n;
while (curr != NULL) {
for (count = 0; count < length; ++count) {
if (curr->cmp[count] == '+') {
if (word[count] != curr->key[count]) {
return (-1);
}
} else if (curr->cmp[count] == '|') {
if (word[count] == curr->key[count]) {
return (-1);
}
wpos = 0;
rpos = 0;
reps = 0;
for (count1 = 0; count1 < length; ++count1) {
if (curr->key[count] == curr->key[count1]) {
if (curr->cmp[count1] == '|') {
++wpos;
} else if (curr->cmp[count1] == '+') {
++rpos;
}
}
if (word[count1] == curr->key[count]) {
++reps;
}
}
if (reps < (wpos + rpos)) {
return (-1);
}
} else {
if (word[count] == curr->key[count]) {
return (-1);
}
wpos = 0;
rpos = 0;
reps = 0;
for (count1 = 0; count1 < length; ++count1) {
if (curr->key[count] == curr->key[count1]) {
if (curr->cmp[count1] == '|') {
++wpos;
} else if (curr->cmp[count1] == '+') {
++rpos;
}
}
if (curr->key[count] == word[count1]) {
++reps;
}
}
if ((wpos + rpos) != reps) {
return (-1);
}
}
}
curr = curr->next;
}
return (1);
}

node_n *
build_compatibility_list(node_y *r, node_t *t, node_n *n, int length) {
node_n *new_noden, *currn;
int inserted;
if (t != r->nil) {
new_noden = (node_n *) malloc(sizeof(node_n));
new_noden->key = (char *) calloc(length, sizeof(char));
strcpy(new_noden->key, t->key);
new_noden->next = NULL;
new_noden->prev = NULL;
if (n != NULL) {
currn = n;
inserted = -1;
while (inserted == -1) {
if (strcmp(new_noden->key, currn->key) < 0) {
new_noden->next = currn;
if (currn->prev != NULL) {
new_noden->prev = currn->prev;
currn->prev->next = new_noden;
} else { n = new_noden; }
currn->prev = new_noden;
inserted = 1;
} else if (!(currn->next != NULL)) {
new_noden->prev = currn;
currn->next = new_noden;
inserted = 1;
}
currn = currn->next;
}
} else {
n = new_noden;
}
n = build_compatibility_list(r, t->left, n, length);
n = build_compatibility_list(r, t->right, n, length);
}
return (n);
}

void
left_rotate(node_y *t, node_t *x) {
node_t *y;
y = x->right;
x->right = y->left;
if (y->left != t->nil) {
y->left->father = x;
}
y->father = x->father;
if (x->father == t->nil) {
t->root = y;
} else if (x == x->father->left) {
x->father->left = y;
} else {
x->father->right = y;
}
y->left = x;
x->father = y;
return;
}

void
right_rotate(node_y *t, node_t *x) {
node_t *y;
y = x->left;
x->left = y->right;
if (y->right != t->nil) {
y->right->father = x;
}
y->father = x->father;
if (x->father == t->nil) {
t->root = y;
} else if (x == x->father->left) {
x->father->left = y;
} else {
x->father->right = y;
}
y->right = x;
x->father = y;
return;
}

void
rb_insert(node_y *t, node_t *z) {
node_t *y, *x;
y = t->nil;
x = t->root;
while (x != t->nil) {
y = x;
if (strcmp(z->key, x->key) < 0) {
x = x->left;
} else {
x = x->right;
}
}
z->father = y;
if (y == t->nil) {
t->root = z;
} else if (strcmp(z->key, y->key) < 0) {
y->left = z;
} else {
y->right = z;
}
z->left = t->nil;
z->right = t->nil;
z->color = 0;
rb_insert_fixup(t, z);
return;
}

void
rb_insert_fixup(node_y *t, node_t *z) {
node_t *x, *y;
if (z == t->root) {
t->root->color = 1;
} else {
x = z->father;
if (x->color == 0) {
if (x == x->father->left) {
y = x->father->right;
if (y->color == 0) {
x->color = 1;
y->color = 1;
x->father->color = 0;
rb_insert_fixup(t, x->father);
} else {
if (z == x->right) {
z = x;
left_rotate(t, z);
x = z->father;
}
x->color = 1;
x->father->color = 0;
right_rotate(t, x->father);
}
} else {
y = x->father->left;
if (y->color == 0) {
x->color = 1;
y->color = 1;
x->father->color = 0;
rb_insert_fixup(t, x->father);
} else {
if (z == x->left) {
z = x;
right_rotate(t, z);
x = z->father;
}
x->color = 1;
x->father->color = 0;
left_rotate(t, x->father);
}
}
}
}
return;
}
  • P
    PhiL99
    Pochi posts
    Iscritto da
    set, 2022
    Messaggi:
    45

    Re: Progetto di informatica

    Il problema dovrebbe essere l'algoritmo che calcola il confronto con la parola di riferimento e che individua le parole compatibili con il risultato di quest'ultima operazione tra quelle compatibili con i precedenti confronti.
  • P
    PhiL99
    Pochi posts
    Iscritto da
    set, 2022
    Messaggi:
    45

    Re: Progetto di informatica

    Ho fatto in modo che si esca da ogni ciclo appena possibile, evitando che venga eseguito del codice inutilmente.
    Ho usato un albero rosso-nero per memorizzare le parole ammissibili, una lista doppiamente concatenata per le compatibilità e, infine, una lista concatenata per i confronti effettuati. A parer mio, e in base alle mie conoscenze, sono le strutture dati più appropriate per rappresentare i vari insiemi.
  • P
    PhiL99
    Pochi posts
    Iscritto da
    set, 2022
    Messaggi:
    45

    Re: Progetto di informatica

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

typedef struct node_s {
    char *key;
    int color; // 0 = red, 1 = black
    struct node_s *left;
    struct node_s *right;
    struct node_s *father;
} node_t;

typedef struct node_m {
    char *key;
    struct node_m *next;
    struct node_m *prev;
} node_n;

typedef struct node_a {
    char *key;
    char *cmp;
    struct node_a *next;
} node_b;

typedef struct node_x {
    node_t *root;
    node_t *nil;
} node_y;

int search(char word[], node_t *n, node_y *t);
node_n * calculate_compatibility(char cmp[], char word[], node_n *n);
node_n * check(char word[], char ref[], char res[], node_n *n);
int is_compatible(char *word, node_b *n);
node_n * build_compatibility_list(node_y *r, node_t *t, node_n *n, int length);
void right_rotate(node_y *t, node_t *x);
void left_rotate(node_y *t, node_t *x);
void rb_insert_fixup(node_y *t, node_t *z);
void rb_insert(node_y *t, node_t *z);

int
main(void)
{
    int length, max_cmp, found, new_match, inserted;
    char *word = NULL, *ref = NULL;
    node_b *compare_list = NULL, *last_compare = NULL, *new_nodeb = NULL;
    node_n *compatibility_list = NULL, *new_noden = NULL, *currn = NULL;
    node_t *new_nodet = NULL;
    node_y *rb_root = NULL;
    clock_t time;
    float float_time;

    if ((1 != scanf("%d", &length)) || (length <= 0)) {
        return (0);
    }
    length += 1; /* carattere terminatore */
    if (length > 18) {
        word = (char *)calloc(length, sizeof (char));
    } else {
        word = (char *)calloc(18, sizeof (char));
    }
    if (scanf("%s", word) != 1) {
        return (0);
    }
    rb_root = (node_y *)malloc(sizeof (node_y));
    rb_root->nil = (node_t *) malloc(sizeof (node_t));
    rb_root->nil->color = 1;
    rb_root->root = rb_root->nil;
    while (strcmp(word, "+nuova_partita") != 0) {
        time = clock();
        new_nodet = (node_t *)malloc(sizeof (node_t));
        new_nodet->key = (char *)calloc(length, sizeof (char));
        strcpy(new_nodet->key, word);
        new_nodet->left = rb_root->nil;
        new_nodet->right = rb_root->nil;
        new_nodet->father = rb_root->nil;
        rb_insert(rb_root, new_nodet);
        time = clock() - time;
        float_time = time / CLOCKS_PER_SEC;
        printf("tempo impiegato dalla cpu per la rb_insert: %f\n", &float_time);
        if (scanf("%s", word) != 1) {
            return (0);
        }
    }
    compatibility_list = build_compatibility_list(rb_root, rb_root->root, compatibility_list, length);
    ref = (char *)calloc(length, sizeof (char));
    while (1) {
        if (scanf("%s", ref) != 1) {
            return (0);
        }
        if (1 != scanf("%d", &max_cmp)) {
            return (0);
        }
        found = -1;
        while ((found == -1) && (max_cmp > 0)) {
            if (scanf("%s", word) != 1) {
                return (0);
            }
            if (strcmp(word, "+inserisci_inizio") == 0) {
                if (scanf("%s", word) != 1) {
                    return (0);
                }
                while (strcmp(word, "+inserisci_fine") != 0) {
                    time = clock();
                    new_nodet = (node_t *)malloc(sizeof (node_t));
                    new_nodet->key = (char *)calloc(length, sizeof (char));
                    strcpy(new_nodet->key, word);
                    new_nodet->left = rb_root->nil;
                    new_nodet->right = rb_root->nil;
                    new_nodet->father = rb_root->nil;
                    rb_insert(rb_root, new_nodet);
                    if (is_compatible(word, compare_list) == 1) {
                        new_noden = (node_n *)malloc(sizeof (node_n));
                        new_noden->key = (char *)calloc(length, sizeof (char));
                        strcpy(new_noden->key, word);
                        new_noden->next = NULL;
                        new_noden->prev = NULL;
                        if (compatibility_list != NULL) {
                            currn = compatibility_list;
                            inserted = -1;
                            while (inserted == -1) {
                                if (strcmp(new_noden->key, currn->key) < 0) {
                                    new_noden->next = currn;
                                    if (currn->prev != NULL) {
                                        new_noden->prev = currn->prev;
                                        currn->prev->next = new_noden;
                                    } else {compatibility_list = new_noden;}
                                    currn->prev = new_noden;
                                    inserted = 1;
                                } else if (!(currn->next != NULL)) {
                                    new_noden->prev = currn;
                                    currn->next = new_noden;
                                    inserted = 1;
                                }
                                currn = currn->next;
                            }
                        } else {
                            compatibility_list = new_noden;
                        }
                    }
                    time = clock() - time;
                    float_time = time / CLOCKS_PER_SEC;
                    printf("tempo impiegato dalla cpu per l'inserimento in lista: %f\n", &float_time);
                    if (scanf("%s", word) != 1) {
                        return (0);
                    }
                }
            } else if (strcmp(word, "+stampa_filtrate") == 0) {
                currn = compatibility_list;
                while (currn != NULL) {
                    printf("%s", currn->key);
                    currn = currn->next;
                    if (currn != NULL) {
                        printf(",\n");
                    } else {
                        printf("\n");
                    }
                }
            } else if (strcmp(word, "+nuova_partita") == 0) {
                new_match = 1;
                break;
            } else if (search(word, rb_root->root, rb_root) == -1) {
                printf("not_exists\n");
            } else if (strcmp(word, ref) == 0) {
                printf("ok\n");
                found = 1;
            } else {
                new_nodeb = (node_b *)malloc(sizeof (node_b));
                new_nodeb->key = (char *)calloc(length, sizeof (char));
                strcpy(new_nodeb->key, word);
                new_nodeb->next = NULL;
                new_nodeb->cmp = (char *)calloc(length, sizeof (char));
                time = clock();
                compatibility_list = check(word, ref, new_nodeb->cmp, compatibility_list);
                time = clock() - time;
                float_time = time / CLOCKS_PER_SEC;
                printf("tempo impiegato dalla cpu per la check: %f\n", &float_time);
                if (compare_list != NULL) {
                    last_compare->next = new_nodeb;
                    last_compare = new_nodeb;
                } else {
                    compare_list = new_nodeb;
                    last_compare = compare_list;
                }
                max_cmp -= 1;
                if (max_cmp == 0) {printf("ko\n");}
            }
        }
        if (new_match != 1) {
            if (scanf("%s", word) != 1) {
                return (0);
            }
            while (strcmp(word, "+nuova_partita") != 0) {
                if (strcmp(word, "+inserisci_inizio") == 0) {
                    if (scanf("%s", word) != 1) {
                        return (0);
                    }
                    while (strcmp(word, "+inserisci_fine") != 0) {
                        new_nodet = (node_t *)malloc(sizeof (node_t));
                        new_nodet->key = (char *)calloc(length, sizeof (char));
                        strcpy(new_nodet->key, word);
                        new_nodet->left = rb_root->nil;
                        new_nodet->right = rb_root->nil;
                        new_nodet->father = rb_root->nil;
                        rb_insert(rb_root, new_nodet);
                        if (1 != scanf("%s", word)) {
                            return (0);
                        }
                    }
                } else {
                    return (0);
                }
                if (scanf("%s", word) != 1) {
                    return (0);
                }
            }
        }
        new_match = 0;
        while (compatibility_list != NULL) {
            currn = compatibility_list;
            compatibility_list = compatibility_list->next;
            free(currn);
        }
        compatibility_list = build_compatibility_list(rb_root, rb_root->root, compatibility_list, length);
        while (compare_list != NULL) {
            last_compare = compare_list;
            compare_list = compare_list->next;
            free(last_compare);
        }
        last_compare = NULL;
    }
    return (0);
}

int
search(char word[], node_t *n, node_y *t)
{
    if (n == t->nil) {
        return (-1);
    } else if (strcmp(n->key, word) == 0) {
        return (1);
    } else {
        if (strcmp(word, n->key) < 0) {
            return (search(word, n->left, t));
        } else {
            return (search(word, n->right, t));
        }
    }
}

node_n *
calculate_compatibility(char cmp[], char word[], node_n *n)
{
    int count;
    int count1;
    int wpos;
    int rpos;
    int reps;
    int length;
    int deleted;
    node_n *curr, *del;
    length = strlen(cmp);
    curr = n;
    while (curr != NULL) {
        deleted = -1;
        for (count = 0; count < length; ++count) {
            if (cmp[count] == '+') {
                if (word[count] != curr->key[count]) {
                    if ((curr->prev != NULL) && (curr->next != NULL)) {
                        curr->prev->next = curr->next;
                        curr->next->prev = curr->prev;
                    } else if (!(curr->prev != NULL) && (curr->next != NULL)) {
                        curr->next->prev = NULL;
                        n = curr->next;
                    } else if ((curr->prev != NULL) && !(curr->next != NULL)) {
                        curr->prev->next = NULL;
                    } else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
                        n = NULL;
                    }
                    del = curr;
                    curr = curr->next;
                    free(del);
                    deleted = 1;
                    break;
                }
            } else if (cmp[count] == '|') {
                if (word[count] == curr->key[count]) {
                    if ((curr->prev != NULL) && (curr->next != NULL)) {
                        curr->prev->next = curr->next;
                        curr->next->prev = curr->prev;
                    } else if (!(curr->prev != NULL) && (curr->next != NULL)) {
                        curr->next->prev = NULL;
                        n = curr->next;
                    } else if ((curr->prev != NULL) && !(curr->next != NULL)) {
                        curr->prev->next = NULL;
                    } else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
                        n = NULL;
                    }
                    del = curr;
                    curr = curr->next;
                    free(del);
                    deleted = 1;
                    break;
                } else {
                    wpos = 0;
                    rpos = 0;
                    reps = 0;
                    for (count1 = 0; count1 < length; ++count1) {
                        if (word[count] == word[count1]) {
                            if (cmp[count1] == '|') {
                                ++wpos;
                            } else if (cmp[count1] == '+') {
                                ++rpos;
                            }
                        }
                        if (word[count] == curr->key[count1]) {
                            ++reps;
                        }
                    }
                    if (reps < (wpos + rpos)) {
                        if ((curr->prev != NULL) && (curr->next != NULL)) {
                            curr->prev->next = curr->next;
                            curr->next->prev = curr->prev;
                        } else if (!(curr->prev != NULL) && (curr->next != NULL)) {
                            curr->next->prev = NULL;
                            n = curr->next;
                        } else if ((curr->prev != NULL) && !(curr->next != NULL)) {
                            curr->prev->next = NULL;
                        } else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
                            n = NULL;
                        }
                        del = curr;
                        curr = curr->next;
                        free(del);
                        deleted = 1;
                        break;
                    }
                }
            } else {
                if (word[count] == curr->key[count]) {
                    if ((curr->prev != NULL) && (curr->next != NULL)) {
                        curr->prev->next = curr->next;
                        curr->next->prev = curr->prev;
                    } else if (!(curr->prev != NULL) && (curr->next != NULL)) {
                        curr->next->prev = NULL;
                        n = curr->next;
                    } else if ((curr->prev != NULL) && !(curr->next != NULL)) {
                        curr->prev->next = NULL;
                    } else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
                        n = NULL;
                    }
                    del = curr;
                    curr = curr->next;
                    free(del);
                    deleted = 1;
                    break;
                } else {
                    wpos = 0;
                    rpos = 0;
                    reps = 0;
                    for (count1 = 0; count1 < length; ++count1) {
                        if (word[count] == word[count1]) {
                            if (cmp[count1] == '|') {
                                ++wpos;
                            } else if (cmp[count1] == '+') {
                                ++rpos;
                            }
                        }
                        if (curr->key[count1] == word[count]) {
                            ++reps;
                        }
                    }
                    if ((wpos + rpos) != reps) {
                        if ((curr->prev != NULL) && (curr->next != NULL)) {
                            curr->prev->next = curr->next;
                            curr->next->prev = curr->prev;
                        } else if (!(curr->prev != NULL) && (curr->next != NULL)) {
                            curr->next->prev = NULL;
                            n = curr->next;
                        } else if ((curr->prev != NULL) && !(curr->next != NULL)) {
                            curr->prev->next = NULL;
                        } else if (!(curr->prev != NULL) && !(curr->next != NULL)) {
                            n = NULL;
                        }
                        del = curr;
                        curr = curr->next;
                        free(del);
                        deleted = 1;
                        break;
                    }
                }
            }
        }
        if (deleted == -1) {
            curr = curr->next;
        }
    }
    return (n);
}

node_n *
check(char word[], char ref[], char res[], node_n *n)
{
    int count;
    int count1;
    int exist;
    int reps;
    int rpos;
    int wpos;
    int length;
    node_n *curr;
    length = strlen(word);
    for (count = 0; count < length; ++count) {
        if (word[count] == ref[count]) {
            res[count] = '+';
        } else {
            reps = 0;
            rpos = 0;
            wpos = 0;
            exist = -1;
            for (count1 = 0; count1 < length; ++count1) {
                if (word[count] == ref[count1]) {
                    exist = 1;
                    ++reps;
                    if (word[count1] == ref[count1]) {
                        ++rpos;
                    }
                }
                else if ((count1 < count) && (word[count1] == word[count])) {
                    ++wpos;
                }
            }
            if ((exist == -1) || (wpos >= (reps - rpos))) {
                res[count] = '/';
            } else {res[count] = '|';}
        }
    }
    res[length] = '\0';
    printf("%s,\n", res);
    n = calculate_compatibility(res, word, n);
    curr = n;
    count = 0;
    while (curr != NULL) {
        ++count;
        curr = curr->next;
    }
    printf("%d\n", count);
    return (n);
}

int
is_compatible(char *word, node_b *n)
{
    int wpos, rpos, reps;
    int count;
    int count1;
    int length;
    node_b *curr;
    length = strlen(word);
    curr = n;
    while (curr != NULL) {
        for (count = 0; count < length; ++count) {
            if (curr->cmp[count] == '+') {
                if (word[count] != curr->key[count]) {
                    return (-1);
                }
            } else if (curr->cmp[count] == '|') {
                if (word[count] == curr->key[count]) {
                    return (-1);
                }
                wpos = 0;
                rpos = 0;
                reps = 0;
                for (count1 = 0; count1 < length; ++count1) {
                    if (curr->key[count] == curr->key[count1]) {
                        if (curr->cmp[count1] == '|') {
                            ++wpos;
                        } else if (curr->cmp[count1] == '+') {
                            ++rpos;
                        }
                    }
                    if (word[count1] == curr->key[count]) {
                        ++reps;
                    }
                }
                if (reps < (wpos + rpos)) {
                    return (-1);
                }
            } else {
                if (word[count] == curr->key[count]) {
                    return (-1);
                }
                wpos = 0;
                rpos = 0;
                reps = 0;
                for (count1 = 0; count1 < length; ++count1) {
                    if (curr->key[count] == curr->key[count1]) {
                        if (curr->cmp[count1] == '|') {
                            ++wpos;
                        } else if (curr->cmp[count1] == '+') {
                            ++rpos;
                        }
                    }
                    if (curr->key[count] == word[count1]) {
                        ++reps;
                    }
                }
                if ((wpos + rpos) != reps) {
                    return (-1);
                }
            }
        }
        curr = curr->next;
    }
    return (1);
}

node_n *
build_compatibility_list(node_y *r, node_t *t, node_n *n, int length) {
    node_n *new_noden, *currn;
    int inserted;
    if (t != r->nil) {
        new_noden = (node_n *) malloc(sizeof(node_n));
        new_noden->key = (char *) calloc(length, sizeof(char));
        strcpy(new_noden->key, t->key);
        new_noden->next = NULL;
        new_noden->prev = NULL;
        if (n != NULL) {
            currn = n;
            inserted = -1;
            while (inserted == -1) {
                if (strcmp(new_noden->key, currn->key) < 0) {
                    new_noden->next = currn;
                    if (currn->prev != NULL) {
                        new_noden->prev = currn->prev;
                        currn->prev->next = new_noden;
                    } else { n = new_noden; }
                    currn->prev = new_noden;
                    inserted = 1;
                } else if (!(currn->next != NULL)) {
                    new_noden->prev = currn;
                    currn->next = new_noden;
                    inserted = 1;
                }
                currn = currn->next;
            }
        } else {
            n = new_noden;
        }
        n = build_compatibility_list(r, t->left, n, length);
        n = build_compatibility_list(r, t->right, n, length);
    }
    return (n);
}

void
left_rotate(node_y *t, node_t *x) {
    node_t *y;
    y = x->right;
    x->right = y->left;
    if (y->left != t->nil) {
        y->left->father = x;
    }
    y->father = x->father;
    if (x->father == t->nil) {
        t->root = y;
    } else if (x == x->father->left) {
        x->father->left = y;
    } else {
        x->father->right = y;
    }
    y->left = x;
    x->father = y;
    return;
}

void
right_rotate(node_y *t, node_t *x) {
    node_t *y;
    y = x->left;
    x->left = y->right;
    if (y->right != t->nil) {
        y->right->father = x;
    }
    y->father = x->father;
    if (x->father == t->nil) {
        t->root = y;
    } else if (x == x->father->left) {
        x->father->left = y;
    } else {
        x->father->right = y;
    }
    y->right = x;
    x->father = y;
    return;
}

void
rb_insert(node_y *t, node_t *z) {
    node_t *y, *x;
    y = t->nil;
    x = t->root;
    while (x != t->nil) {
        y = x;
        if (strcmp(z->key, x->key) < 0) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->father = y;
    if (y == t->nil) {
        t->root = z;
    } else if (strcmp(z->key, y->key) < 0) {
        y->left = z;
    } else {
        y->right = z;
    }
    z->left = t->nil;
    z->right = t->nil;
    z->color = 0;
    rb_insert_fixup(t, z);
    return;
}

void
rb_insert_fixup(node_y *t, node_t *z) {
    node_t *x, *y;
    if (z == t->root) {
        t->root->color = 1;
    } else {
        x = z->father;
        if (x->color == 0) {
            if (x == x->father->left) {
                y = x->father->right;
                if (y->color == 0) {
                    x->color = 1;
                    y->color = 1;
                    x->father->color = 0;
                    rb_insert_fixup(t, x->father);
                } else {
                    if (z == x->right) {
                        z = x;
                        left_rotate(t, z);
                        x = z->father;
                    }
                    x->color = 1;
                    x->father->color = 0;
                    right_rotate(t, x->father);
                }
            } else {
                y = x->father->left;
                if (y->color == 0) {
                    x->color = 1;
                    y->color = 1;
                    x->father->color = 0;
                    rb_insert_fixup(t, x->father);
                } else {
                    if (z == x->left) {
                        z = x;
                        right_rotate(t, z);
                        x = z->father;
                    }
                    x->color = 1;
                    x->father->color = 0;
                    left_rotate(t, x->father);
                }
            }
        }
    }
    return;
}
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Progetto di informatica

    Se la scadenza, come hai detto nel post iniziale, è il 9 settembre, per quanto mi riguarda non credo di poterti essere d'aiuto.
    Se invece hai più tempo a disposizione, allora con calma mi leggo meglio la traccia, ragiono sul problema e poi magari ne discutiamo.
  • P
    PhiL99
    Pochi posts
    Iscritto da
    set, 2022
    Messaggi:
    45

    Re: Progetto di informatica

    La scadenza è domani alle 23.59.
  • P
    PhiL99
    Pochi posts
    Iscritto da
    set, 2022
    Messaggi:
    45

    Re: Progetto di informatica

    Mi rendo conto che la mia è una richiesta "forzata", per via del poco tempo a disposizione.
    Ma come si suol dire, "mai dire mai".
  • Andrea Quaglia
    Andrea Quaglia
    Molto attivo
    Iscritto da
    giu, 2017
    Messaggi:
    603

    Re: Progetto di informatica

    Dunque, ho copiaincollato il tuo codice e fatto alcune prove.
    Io non vedo problemi, ho un PC a carbone del 2006, e anche compilando in debug le risposte attese sono pressoché immediate.
    Qualche perplessità sul numero (tentativi rimasti?) che compare dopo il confronto, a me viene diverso:
    /home/andrea/CLionProjects/untitled/cmake-build-debug/untitled
5
8adfs
tempo impiegato dalla cpu per la rb_insert: 0.000000
5sjaH
tempo impiegato dalla cpu per la rb_insert: 0.000000
KS061
tempo impiegato dalla cpu per la rb_insert: 0.000000
Hi23a
tempo impiegato dalla cpu per la rb_insert: 0.000000
laj74
tempo impiegato dalla cpu per la rb_insert: 0.000000
-s9k0
tempo impiegato dalla cpu per la rb_insert: 0.000000
sm_ks
tempo impiegato dalla cpu per la rb_insert: 0.000000
okauE
tempo impiegato dalla cpu per la rb_insert: 0.000000
+nuova_partita
5sjaH
4
KS061
/////,
6
tempo impiegato dalla cpu per la check: 0.000000
okauE
//|//,
4
  • P
    PhiL99
    Pochi posts
    Iscritto da
    set, 2022
    Messaggi:
    45

    Re: Progetto di informatica

    Il numero che compare alla destra del confronto indica il numero di parole compatibili rimaste.
    Vi comunico che la scadenza è stata posticipata di un paio di mesi. Per chiunque avesse intenzione di aiutarmi, c'è ancora tempo!
Devi accedere o registrarti per scrivere nel forum
73 risposte