Progetto di informatica

PhiL99

il 07 set 2022, 15:09

73 risposte

73 Risposte - Pagina 5

Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1237
Re: Progetto di informatica
06 feb 2023, 02:53
04/02/2023 - Weierstrass ha scritto:
Perché Windows vuole il Carriage Return + Line Feed, loro usano Linux.
Ah ok, non lo sapevo.
Ho provato a scorrere il testo dal blocco note con i tasti freccia, ed effettivamente quando incontro il carattere \n il cursore resta fermo.
04/02/2023 - Weierstrass ha scritto:
Direi che basta così: gli hai già fatto la parte più difficile del progetto… :-)
Aspettiamo allora aggiornamenti da parte dell'OP alla luce dei consigli che gli hai dato.
Qualcosa si può sicuramente limare, ma se il limite è quello dei 3 secondi, la vedo dura…

PhiL99

Pochi posts

Iscritto da: set, 2022

Messaggi:: 45

Re: Progetto di informatica

08 feb 2023, 19:08

Adesso il programma esegue il test intorno ai 0,055 s. Il problema è che sforo con la memoria. Allora ho provato ad allocare nodo e stringa con una singola malloc e qualcosina ho guadagnato. Per risparmiare ancora più memoria, ho pensato di allocare a blocchi di 4096 (nodo + stringa), ma incorro in segmentation fault. Mi potreste spiegare perché?

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

typedef struct node_ {
    char* key;
    struct node_* left;
    struct node_* right;
} node;

int main() {
    node *blocco, *nodo;

    blocco = malloc(sizeof(node) * 100 + sizeof(char) * 6 * 100);

    for (int i = 0; i < 100; ++i) {
        nodo = blocco + i * sizeof(nodo);
        nodo->key = (char*) blocco + sizeof(nodo) * 100 + i * sizeof(char) * 6;
        strcpy(nodo->key, "aabbc");
    }

    for (int i = 0; i < 100; ++i) {
        nodo = blocco + i * sizeof(nodo);
        printf("%s\n", nodo->key);
    }

    return 0;
}

PhiL99

Pochi posts

Iscritto da: set, 2022

Messaggi:: 45

Re: Progetto di informatica

08 feb 2023, 19:18

Vi lascio il codice aggiornato, qualora voleste ancora aiutarmi.

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

#define N 128

typedef struct node_ {
    char* key;
    struct node_* left;
    struct node_* right;
} node;

typedef struct nodo_ {
    node *n;
    char *res;
    uint8_t SI[N];
    uint8_t NO[N];
    uint8_t *u;
    uint8_t u_dim;
    struct nodo_ *next;
} nodo;

typedef struct pnode_ {
    node *n;
    struct pnode_ *next;
} pnode;

int strcmp(const char *s1, const char *s2) {
    while (*s1 && (*s1 == *s2)) {
        s1++;
        s2++;
    }
    return (*(const unsigned char*)s1 - *(const unsigned char*)s2);
}

node* tree_search(node **root, char *word) {
    int val;

    while (*root != NULL) {
        if (!(val = strcmp((*root)->key, word))) {
            return (*root);
        } else if (val < 0) {
            root = &(*root)->right;
        } else {
            root = &(*root)->left;
        }
    }
    return (NULL);
}

void tree_insert(node **root, node *n) {
    while (*root != NULL) {
        if (strcmp((*root)->key, n->key) < 0) {
            root = &(*root)->right;
        } else {
            root = &(*root)->left;
        }
    }
    *root = n;
}

void print_filtered(pnode **comp_w) {
    while (*comp_w != NULL) {
        printf("%s\n", (*comp_w)->n->key);
        comp_w = &(*comp_w)->next;
    }
}

int end_game(node **root, unsigned int l, node *n, char *i) {
    while (1) {
        if (EOF == scanf("%s", i)) {
            return (0);
        }
        if (!strcmp(i, "+nuova_partita")) {
            return (1);
        } else {
            while (1) {
                if (EOF == scanf("%s", i)) {
                    return (0);
                }
                if (!strcmp(i, "+inserisci_fine")) {
                    break;
                } else {
                    n = malloc(sizeof(node) + sizeof(char) * (l + 1));
                    n->key = (char*) n + sizeof(node);
                    strcpy(n->key, i);
                    n->left = NULL;
                    n->right = NULL;
                    tree_insert(root, n);
                }
            }
        }
    }
}

void pnode_insert(pnode **pn, node *n, pnode *new) {
    new = (pnode*)malloc(sizeof(pnode));
    new->n = n;
    new->next = *pn;
    *pn = new;
}

void comp_free(pnode **comp_w) {
    pnode *del;

    while (*comp_w != NULL) {
        del = *comp_w;
        *comp_w = (*comp_w)->next;
        free(del);
    }
}

void comp_reset(node **root, pnode **comp_w, pnode *new, unsigned int *m) {
    if (*root != NULL) {
        ++*m;
        comp_reset(&(*root)->right, comp_w, new, m);
        pnode_insert(comp_w, *root, new);
        comp_reset(&(*root)->left, comp_w, new,  m);
    }
}

void list_reset(nodo **c_list) {
    nodo *del;

    while (*c_list != NULL) {
        del = *c_list;
        *c_list = (*c_list)->next;
        free(del);
    }
}

nodo* add_comparison(nodo **c_list, node *a, uint8_t l) {
    while (*c_list != NULL) {
        c_list = &(*c_list)->next;
    }
    *c_list = malloc(sizeof(nodo) + sizeof(char) * (l + 1) + sizeof(uint8_t) * l);
    (*c_list)->n = a;
    (*c_list)->next = NULL;
    (*c_list)->res = (char*) *c_list + sizeof(nodo);
    (*c_list)->u = (uint8_t*) *c_list + sizeof(nodo) + sizeof(char) * (l + 1);
    (*c_list)->res[l] = '\0';
    return (*c_list);
}

nodo* calculate_comparison(nodo *n, const char *k) {
    memset(n->SI, (int)(n->u_dim = 0), sizeof(*n->SI) * N);
    memset(n->NO, 0, sizeof(*n->NO) * N);
    uint8_t v[N] = {0};
    for(unsigned int i = 0; k[i]; ++i)
    {
        if(n->n->key[i] == k[i])
        {
            n->res[i] = '+';
        }
        else
        {
            n->res[i] = '/';
            ++v[(int)k[i]];
        }
    }
    for(unsigned int i = 0; k[i]; ++i)
    {
        if(n->res[i] == '/')
        {
            if(v[(int)n->n->key[i]])
            {
                n->res[i] = '|';
                --v[(int)n->n->key[i]];
                if(!n->SI[(int)n->n->key[i]]++)
                {
                    n->u[(n->u_dim)++] = n->n->key[i];
                }
            }
            else
            {
                ++n->NO[(int)n->n->key[i]];
            }
        }
    }
    return (n);
}

int is_compatible(const char *p, nodo *n) {
    uint8_t v[N] = {0};

    unsigned int i;
    for(i = 0; n->n->key[i] && (n->res[i] == '+' ? p[i] == n->n->key[i] : p[i] != n->n->key[i] && ++v[(int)p[i]] && (!n->NO[(int)p[i]] || n->SI[(int)p[i]] - v[(int)p[i]] >= 0)); ++i);
    for(i = !n->n->key[i] ? 0 : n->u_dim + 1; i < n->u_dim && v[n->u[i]] - n->SI[n->u[i]] >= 0; ++i);
    return(i == n->u_dim);
}

void update_compatibilities(pnode **comp_w, nodo *n1, unsigned int *m) {
    pnode *del;

    while (*comp_w != NULL) {
        if (!is_compatible((*comp_w)->n->key, n1)) {
            del = *comp_w;
            *comp_w = (*comp_w)->next;
            free(del);
            --*m;
        } else {
            comp_w = &(*comp_w)->next;
        }
    }
}

int respect_constraints(nodo **p, char *i) {
    while (*p != NULL) {
        if (!is_compatible(i, *p)) {
            return (0);
        }
        p = &(*p)->next;
    }
    return (1);
}

void pnode_insert_in_order(pnode **comp_w, node *n) {
    pnode *new;

    while (*comp_w != NULL && strcmp((*comp_w)->n->key, n->key) < 0) {
        comp_w = &(*comp_w)->next;
    }
    new = (pnode*)malloc(sizeof(pnode));
    new->n = n;
    new->next = *comp_w;
    *comp_w = new;
}

void build_compatible_words(node **el_w, pnode **comp_w, pnode *new) {
    if (*el_w != NULL) {
        build_compatible_words(&(*el_w)->right, comp_w, new);
        pnode_insert(comp_w, *el_w, new);
        build_compatible_words(&(*el_w)->left, comp_w, new);
    }
}

int main() {
    node *eligible_words = NULL;
    nodo *comparison_list = NULL, *temp;
    node *new_node = NULL;
    pnode *compatible_words = NULL, *new = NULL;
    char input[100], *key;
    uint8_t length;
    unsigned int num_comp = 0, rounds;

    if (EOF == scanf("%s", &length)) {
        return (0);
    }

    while (1) {
        if (EOF == scanf("%s", input)) {
            delete_tree(&eligible_words);
            return (0);
        }
        if (!strcmp(input, "+nuova_partita")) {
            break;
        } else {
            new_node = malloc(sizeof(node) + sizeof(char) * (length + 1));
            new_node->key = (char*) new_node + sizeof(node);
            new_node->left = NULL;
            new_node->right = NULL;
            strcpy(new_node->key, input);
            ++num_comp;
            tree_insert(&eligible_words, new_node);
        }
    }
    build_compatible_words(&eligible_words, &compatible_words, new);

    key = (char*)malloc(sizeof(char) * (length + 1));
    while (1) {
        if (EOF == scanf("%s", key) || EOF == scanf("%d", &rounds)) {
            break;
        }
        while (1) {
            if (EOF == scanf("%s", input)) {
                return (0);
            }
            if (input[0] != '+') {
                if (!strcmp(input, key)) {
                    printf("ok\n");
                    if (!end_game(&eligible_words, length, new_node, input)) {
                        return (0);
                    }
                    num_comp = 0;
                    comp_free(&compatible_words);
                    comp_reset(&eligible_words, &compatible_words, new,  &num_comp);
                    list_reset(&comparison_list);
                    break;
                } else if ((new_node = tree_search(&eligible_words, input)) != NULL) {
                    update_compatibilities(&compatible_words, calculate_comparison(temp = add_comparison(&comparison_list, new_node, length), key), &num_comp);
                    printf("%s\n%d\n", temp->res, num_comp);
                    if (!(--rounds)) {
                        printf("ko\n");
                        if (!end_game(&eligible_words, length, new_node, input)) {
                            return (0);
                        }
                        num_comp = 0;
                        comp_free(&compatible_words);
                        comp_reset(&eligible_words, &compatible_words, new, &num_comp);
                        list_reset(&comparison_list);
                        break;
                    }
                } else {
                    printf("not_exists\n");
                }
            } else if (!strcmp(input, "+stampa_filtrate")) {
                print_filtered(&compatible_words);
            } else if (!strcmp(input, "+inserisci_inizio")) {
                while (1) {
                    if (EOF == scanf("%s", input)) {
                        return (0);
                    }
                    if (!strcmp(input, "+inserisci_fine")) {
                        break;
                    } else {
                        new_node = malloc(sizeof(node) + sizeof(char) * (length + 1));
                        new_node->key = (char*) new_node + sizeof(node);
                        new_node->left = NULL;
                        new_node->right = NULL;
                        strcpy(new_node->key, input);
                        if (respect_constraints(&comparison_list, input)) {
                            ++num_comp;
                            pnode_insert_in_order(&compatible_words, new_node);
                        }
                        tree_insert(&eligible_words, new_node);
                    }
                }
            } else if (!strcmp(input, "+nuova_partita")) {
                num_comp = 0;
                comp_free(&compatible_words);
                comp_reset(&eligible_words, &compatible_words, new, &num_comp);
                list_reset(&comparison_list);
                break;
            } else {
                return (0);
            }
        }
    }
    return (0);
}

P
PhiL99
Pochi posts
Iscritto da
set, 2022
Messaggi:
45
Re: Progetto di informatica
08 feb 2023, 19:28
Allocazione a blocchi a parte, se avete consigli per diminuire il consumo di memoria, sono tutto orecchi…
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1237
Re: Progetto di informatica
08 feb 2023, 19:51
Puoi spiegare in linea di massima quali cambiamenti hai apportato?
In ogni caso non compila, manca la definizione della funzione delete_tree().
Inoltre hai rimosso la lettura da file, quindi non ho la possibilità di effettuare il test.
Weierstrass
Utente Famoso
Iscritto da
feb, 2019
Messaggi:
2245
Re: Progetto di informatica
08 feb 2023, 22:07
Sicuramente puoi ridurre N da 128 a 78:
invece di passargli un indice i, gli passi un indice j = i - '-' che quindi andrà da 0 (= '-' - '-') a 77 (= 'z’ - 'i')
Con un po' più di lavoro puoi ridurre N a 64 (il numero totale di caratteri ammissibili)

PhiL99

Pochi posts

Iscritto da: set, 2022

Messaggi:: 45

Re: Progetto di informatica

09 feb 2023, 09:49

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

#define N 128

typedef struct node_ {
    char* key;
    struct node_* left;
    struct node_* right;
} node;

typedef struct nodo_ {
    node *n;
    char *res;
    uint8_t SI[N];
    uint8_t NO[N];
    uint8_t *u;
    uint8_t u_dim;
    struct nodo_ *next;
} nodo;

typedef struct pnode_ {
    node *n;
    struct pnode_ *next;
} pnode;

int strcmp(const char *s1, const char *s2) {
    while (*s1 && (*s1 == *s2)) {
        s1++;
        s2++;
    }
    return (*(const unsigned char*)s1 - *(const unsigned char*)s2);
}

node* tree_search(node **root, char *word) {
    int val;

    while (*root != NULL) {
        if (!(val = strcmp((*root)->key, word))) {
            return (*root);
        } else if (val < 0) {
            root = &(*root)->right;
        } else {
            root = &(*root)->left;
        }
    }
    return (NULL);
}

void tree_insert(node **root, node *n) {
    while (*root != NULL) {
        if (strcmp((*root)->key, n->key) < 0) {
            root = &(*root)->right;
        } else {
            root = &(*root)->left;
        }
    }
    *root = n;
}

void print_filtered(pnode **comp_w) {
    while (*comp_w != NULL) {
        printf("%s\n", (*comp_w)->n->key);
        comp_w = &(*comp_w)->next;
    }
}

int end_game(node **root, unsigned int l, node *n, char *i) {
    while (1) {
        if (EOF == scanf("%s", i)) {
            return (0);
        }
        if (!strcmp(i, "+nuova_partita")) {
            return (1);
        } else {
            while (1) {
                if (EOF == scanf("%s", i)) {
                    return (0);
                }
                if (!strcmp(i, "+inserisci_fine")) {
                    break;
                } else {
                    n = malloc(sizeof(node) + sizeof(char) * (l + 1));
                    n->key = (char*) n + sizeof(node);
                    strcpy(n->key, i);
                    n->left = NULL;
                    n->right = NULL;
                    tree_insert(root, n);
                }
            }
        }
    }
}

void pnode_insert(pnode **pn, node *n, pnode *new) {
    new = (pnode*)malloc(sizeof(pnode));
    new->n = n;
    new->next = *pn;
    *pn = new;
}

void comp_free(pnode **comp_w) {
    pnode *del;

    while (*comp_w != NULL) {
        del = *comp_w;
        *comp_w = (*comp_w)->next;
        free(del);
    }
}

void comp_reset(node **root, pnode **comp_w, pnode *new, unsigned int *m) {
    if (*root != NULL) {
        ++*m;
        comp_reset(&(*root)->right, comp_w, new, m);
        pnode_insert(comp_w, *root, new);
        comp_reset(&(*root)->left, comp_w, new,  m);
    }
}

void list_reset(nodo **c_list) {
    nodo *del;

    while (*c_list != NULL) {
        del = *c_list;
        *c_list = (*c_list)->next;
        free(del);
    }
}

nodo* add_comparison(nodo **c_list, node *a, uint8_t l) {
    while (*c_list != NULL) {
        c_list = &(*c_list)->next;
    }
    *c_list = malloc(sizeof(nodo) + sizeof(char) * (l + 1) + sizeof(uint8_t) * l);
    (*c_list)->n = a;
    (*c_list)->next = NULL;
    (*c_list)->res = (char*) *c_list + sizeof(nodo);
    (*c_list)->u = (uint8_t*) *c_list + sizeof(nodo) + sizeof(char) * (l + 1);
    (*c_list)->res[l] = '\0';
    return (*c_list);
}

nodo* calculate_comparison(nodo *n, const char *k) {
    memset(n->SI, (int)(n->u_dim = 0), sizeof(*n->SI) * N);
    memset(n->NO, 0, sizeof(*n->NO) * N);
    uint8_t v[N] = {0};
    for(unsigned int i = 0; k[i]; ++i)
    {
        if(n->n->key[i] == k[i])
        {
            n->res[i] = '+';
        }
        else
        {
            n->res[i] = '/';
            ++v[(int)k[i]];
        }
    }
    for(unsigned int i = 0; k[i]; ++i)
    {
        if(n->res[i] == '/')
        {
            if(v[(int)n->n->key[i]])
            {
                n->res[i] = '|';
                --v[(int)n->n->key[i]];
                if(!n->SI[(int)n->n->key[i]]++)
                {
                    n->u[(n->u_dim)++] = n->n->key[i];
                }
            }
            else
            {
                ++n->NO[(int)n->n->key[i]];
            }
        }
    }
    return (n);
}

int is_compatible(const char *p, nodo *n) {
    uint8_t v[N] = {0};

    unsigned int i;
    for(i = 0; n->n->key[i] && (n->res[i] == '+' ? p[i] == n->n->key[i] : p[i] != n->n->key[i] && ++v[(int)p[i]] && (!n->NO[(int)p[i]] || n->SI[(int)p[i]] - v[(int)p[i]] >= 0)); ++i);
    for(i = !n->n->key[i] ? 0 : n->u_dim + 1; i < n->u_dim && v[n->u[i]] - n->SI[n->u[i]] >= 0; ++i);
    return(i == n->u_dim);
}

void update_compatibilities(pnode **comp_w, nodo *n1, unsigned int *m) {
    pnode *del;

    while (*comp_w != NULL) {
        if (!is_compatible((*comp_w)->n->key, n1)) {
            del = *comp_w;
            *comp_w = (*comp_w)->next;
            free(del);
            --*m;
        } else {
            comp_w = &(*comp_w)->next;
        }
    }
}

int respect_constraints(nodo **p, char *i) {
    while (*p != NULL) {
        if (!is_compatible(i, *p)) {
            return (0);
        }
        p = &(*p)->next;
    }
    return (1);
}

void pnode_insert_in_order(pnode **comp_w, node *n) {
    pnode *new;

    while (*comp_w != NULL && strcmp((*comp_w)->n->key, n->key) < 0) {
        comp_w = &(*comp_w)->next;
    }
    new = (pnode*)malloc(sizeof(pnode));
    new->n = n;
    new->next = *comp_w;
    *comp_w = new;
}

void build_compatible_words(node **el_w, pnode **comp_w, pnode *new) {
    if (*el_w != NULL) {
        build_compatible_words(&(*el_w)->right, comp_w, new);
        pnode_insert(comp_w, *el_w, new);
        build_compatible_words(&(*el_w)->left, comp_w, new);
    }
}

int main() {
    node *eligible_words = NULL;
    nodo *comparison_list = NULL, *temp;
    node *new_node = NULL;
    pnode *compatible_words = NULL, *new = NULL;
    char input[100], *key;
    uint8_t length;
    unsigned int num_comp = 0, rounds;

    if (EOF == scanf("%s", &length)) {
        return (0);
    }

    while (1) {
        if (EOF == scanf("%s", input)) {
            return (0);
        }
        if (!strcmp(input, "+nuova_partita")) {
            break;
        } else {
            new_node = malloc(sizeof(node) + sizeof(char) * (length + 1));
            new_node->key = (char*) new_node + sizeof(node);
            new_node->left = NULL;
            new_node->right = NULL;
            strcpy(new_node->key, input);
            ++num_comp;
            tree_insert(&eligible_words, new_node);
        }
    }
    build_compatible_words(&eligible_words, &compatible_words, new);

    key = (char*)malloc(sizeof(char) * (length + 1));
    while (1) {
        if (EOF == scanf("%s", key) || EOF == scanf("%d", &rounds)) {
            break;
        }
        while (1) {
            if (EOF == scanf("%s", input)) {
                return (0);
            }
            if (input[0] != '+') {
                if (!strcmp(input, key)) {
                    printf("ok\n");
                    if (!end_game(&eligible_words, length, new_node, input)) {
                        return (0);
                    }
                    num_comp = 0;
                    comp_free(&compatible_words);
                    comp_reset(&eligible_words, &compatible_words, new,  &num_comp);
                    list_reset(&comparison_list);
                    break;
                } else if ((new_node = tree_search(&eligible_words, input)) != NULL) {
                    update_compatibilities(&compatible_words, calculate_comparison(temp = add_comparison(&comparison_list, new_node, length), key), &num_comp);
                    printf("%s\n%d\n", temp->res, num_comp);
                    if (!(--rounds)) {
                        printf("ko\n");
                        if (!end_game(&eligible_words, length, new_node, input)) {
                            return (0);
                        }
                        num_comp = 0;
                        comp_free(&compatible_words);
                        comp_reset(&eligible_words, &compatible_words, new, &num_comp);
                        list_reset(&comparison_list);
                        break;
                    }
                } else {
                    printf("not_exists\n");
                }
            } else if (!strcmp(input, "+stampa_filtrate")) {
                print_filtered(&compatible_words);
            } else if (!strcmp(input, "+inserisci_inizio")) {
                while (1) {
                    if (EOF == scanf("%s", input)) {
                        return (0);
                    }
                    if (!strcmp(input, "+inserisci_fine")) {
                        break;
                    } else {
                        new_node = malloc(sizeof(node) + sizeof(char) * (length + 1));
                        new_node->key = (char*) new_node + sizeof(node);
                        new_node->left = NULL;
                        new_node->right = NULL;
                        strcpy(new_node->key, input);
                        if (respect_constraints(&comparison_list, input)) {
                            ++num_comp;
                            pnode_insert_in_order(&compatible_words, new_node);
                        }
                        tree_insert(&eligible_words, new_node);
                    }
                }
            } else if (!strcmp(input, "+nuova_partita")) {
                num_comp = 0;
                comp_free(&compatible_words);
                comp_reset(&eligible_words, &compatible_words, new, &num_comp);
                list_reset(&comparison_list);
                break;
            } else {
                return (0);
            }
        }
    }
    return (0);
}

P
PhiL99
Pochi posts
Iscritto da
set, 2022
Messaggi:
45
Re: Progetto di informatica
09 feb 2023, 09:53
Ho rimosso delete_tree(). 0,055 è il tempo d'esecuzione del verificatore che compila con questi flag
gcc -Wall -Werror -O2 -g3 sorgente.c -o eseguibile
P
PhiL99
Pochi posts
Iscritto da
set, 2022
Messaggi:
45
Re: Progetto di informatica
09 feb 2023, 09:58
Test ? https://easyupload.io/8tjbop
output ? https://easyupload.io/hi0blf
P
PhiL99
Pochi posts
Iscritto da
set, 2022
Messaggi:
45
Re: Progetto di informatica
09 feb 2023, 10:05
08/02/2023 - Weierstrass ha scritto:
Sicuramente puoi ridurre N da 128 a 78:
invece di passargli un indice i, gli passi un indice j = i - '-' che quindi andrà da 0 (= '-' - '-') a 77 (= 'z’ - 'i')
Con un po' più di lavoro puoi ridurre N a 64 (il numero totale di caratteri ammissibili)
Grazie, provo a vedere se funziona.
P
PhiL99
Pochi posts
Iscritto da
set, 2022
Messaggi:
45
Re: Progetto di informatica
09 feb 2023, 10:23
Per quanto riguarda l'allocazione dinamica a blocchi, sapreste darmi una mano? Così alleggerirei ulteriormente il carico dell'extra heap.
P
PhiL99
Pochi posts
Iscritto da
set, 2022
Messaggi:
45
Re: Progetto di informatica
09 feb 2023, 10:41
08/02/2023 - Weierstrass ha scritto:
Sicuramente puoi ridurre N da 128 a 78:
invece di passargli un indice i, gli passi un indice j = i - '-' che quindi andrà da 0 (= '-' - '-') a 77 (= 'z’ - 'i')
Con un po' più di lavoro puoi ridurre N a 64 (il numero totale di caratteri ammissibili)
Purtroppo non è bastato.

Weierstrass

Utente Famoso

Iscritto da: feb, 2019

Messaggi:: 2245

Re: Progetto di informatica

09 feb 2023, 12:20

Quanto è il limite? Quanto hai usato finora?

Poi rimetti il codice aggiornato nella versione che serve a nippolo, altrimenti non può aiutarti…

Tipo così

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

#define N 123

FILE * fp, * out;
    
typedef struct node_ {
    char* key;
    struct node_* left;
    struct node_* right;
} node;

typedef struct nodo_ {
    node *n;
    char *res;
    uint8_t SI[N];
    uint8_t NO[N];
    uint8_t *u;
    uint8_t u_dim;
    struct nodo_ *next;
} nodo;

typedef struct pnode_ {
    node *n;
    struct pnode_ *next;
} pnode;

int strcmp(const char *s1, const char *s2) {
    while (*s1 && (*s1 == *s2)) {
        s1++;
        s2++;
    }
    return (*(const unsigned char*)s1 - *(const unsigned char*)s2);
}

node* tree_search(node **root, char *word) {
    int val;

    while (*root != NULL) {
        if (!(val = strcmp((*root)->key, word))) {
            return (*root);
        } else if (val < 0) {
            root = &(*root)->right;
        } else {
            root = &(*root)->left;
        }
    }
    return (NULL);
}

void tree_insert(node **root, node *n) {
    while (*root != NULL) {
        if (strcmp((*root)->key, n->key) < 0) {
            root = &(*root)->right;
        } else {
            root = &(*root)->left;
        }
    }
    *root = n;
}

void print_filtered(pnode **comp_w) {
    while (*comp_w != NULL) {
        fprintf(out, "%s\n", (*comp_w)->n->key);
        comp_w = &(*comp_w)->next;
    }
}

int end_game(node **root, unsigned int l, node *n, char *i) {
    while (1) {
        if (EOF == fscanf(fp, "%s", i)) {
            return (0);
        }
        if (!strcmp(i, "+nuova_partita")) {
            return (1);
        } else {
            while (1) {
                if (EOF == fscanf(fp, "%s", i)) {
                    return (0);
                }
                if (!strcmp(i, "+inserisci_fine")) {
                    break;
                } else {
                    n = calloc(1, sizeof(node) + sizeof(char) * (l + 1));
                    n->key = (char*) n + sizeof(node);
                    strcpy(n->key, i);
                    n->left = NULL;
                    n->right = NULL;
                    tree_insert(root, n);
                }
            }
        }
    }
}

void pnode_insert(pnode **pn, node *n, pnode *new) {
    new = (pnode*)calloc(1, sizeof(pnode));
    new->n = n;
    new->next = *pn;
    *pn = new;
}

void comp_free(pnode **comp_w) {
    pnode *del;

    while (*comp_w != NULL) {
        del = *comp_w;
        *comp_w = (*comp_w)->next;
        free(del);
    }
}

void comp_reset(node **root, pnode **comp_w, pnode *new, unsigned int *m) {
    if (*root != NULL) {
        ++*m;
        comp_reset(&(*root)->right, comp_w, new, m);
        pnode_insert(comp_w, *root, new);
        comp_reset(&(*root)->left, comp_w, new,  m);
    }
}

void list_reset(nodo **c_list) {
    nodo *del;

    while (*c_list != NULL) {
        del = *c_list;
        *c_list = (*c_list)->next;
        free(del);
    }
}

nodo* add_comparison(nodo **c_list, node *a, uint8_t l) {
    while (*c_list != NULL) {
        c_list = &(*c_list)->next;
    }
    *c_list = calloc(1, sizeof(nodo) + sizeof(char) * (l + 1) + sizeof(uint8_t) * l);
    (*c_list)->n = a;
    (*c_list)->next = NULL;
    (*c_list)->res = (char*) *c_list + sizeof(nodo);
    (*c_list)->u = (uint8_t*) *c_list + sizeof(nodo) + sizeof(char) * (l + 1);
    (*c_list)->res[l] = '\0';
    return (*c_list);
}

nodo* calculate_comparison(nodo *n, const char *k) {
    memset(n->SI, (int)(n->u_dim = 0), sizeof(*n->SI) * N);
    memset(n->NO, 0, sizeof(*n->NO) * N);
    uint8_t v[N] = {0};
    for(unsigned int i = 0; k[i]; ++i)
    {
        if(n->n->key[i] == k[i])
        {
            n->res[i] = '+';
        }
        else
        {
            n->res[i] = '/';
            ++v[(int)k[i]];
        }
    }
    for(unsigned int i = 0; k[i]; ++i)
    {
        if(n->res[i] == '/')
        {
            if(v[(int)n->n->key[i]])
            {
                n->res[i] = '|';
                --v[(int)n->n->key[i]];
                if(!n->SI[(int)n->n->key[i]]++)
                {
                    n->u[(n->u_dim)++] = n->n->key[i];
                }
            }
            else
            {
                ++n->NO[(int)n->n->key[i]];
            }
        }
    }
    return (n);
}

int is_compatible(const char *p, nodo *n) {
    uint8_t v[N] = {0};

    unsigned int i;
    for(i = 0; n->n->key[i] && (n->res[i] == '+' ? p[i] == n->n->key[i] : p[i] != n->n->key[i] && ++v[(int)p[i]] && (!n->NO[(int)(p[i])] || n->SI[(int)(p[i])] - v[(int)(p[i])] >= 0)); ++i);
    for(i = !n->n->key[i] ? 0 : n->u_dim + 1; i < n->u_dim && v[n->u[i]] - n->SI[n->u[i]] >= 0; ++i);
    return(i == n->u_dim);
}

void update_compatibilities(pnode **comp_w, nodo *n1, unsigned int *m) {
    pnode *del;

    while (*comp_w != NULL) {
        if (!is_compatible((*comp_w)->n->key, n1)) {
            del = *comp_w;
            *comp_w = (*comp_w)->next;
            free(del);
            --*m;
        } else {
            comp_w = &(*comp_w)->next;
        }
    }
}

int respect_constraints(nodo **p, char *i) {
    while (*p != NULL) {
        if (!is_compatible(i, *p)) {
            return (0);
        }
        p = &(*p)->next;
    }
    return (1);
}

void pnode_insert_in_order(pnode **comp_w, node *n) {
    pnode *new;

    while (*comp_w != NULL && strcmp((*comp_w)->n->key, n->key) < 0) {
        comp_w = &(*comp_w)->next;
    }
    new = (pnode*)calloc(1, sizeof(pnode));
    new->n = n;
    new->next = *comp_w;
    *comp_w = new;
}

void build_compatible_words(node **el_w, pnode **comp_w, pnode *new) {
    if (*el_w != NULL) {
        build_compatible_words(&(*el_w)->right, comp_w, new);
        pnode_insert(comp_w, *el_w, new);
        build_compatible_words(&(*el_w)->left, comp_w, new);
    }
}

int main() {
    node *eligible_words = NULL;
    nodo *comparison_list = NULL, *temp;
    node *new_node = NULL;
    pnode *compatible_words = NULL, *new = NULL;
    char input[100], *key;
    uint8_t length;
    unsigned int num_comp = 0, rounds;
            
    if ((fp=fopen("test3.txt", "r"))==NULL)
        return -1;
    
    if ((out=fopen("out.txt", "w"))==NULL)
        return -2;    

    if (EOF == fscanf(fp, "%s", &length)) {
        return (0);
    }

    while (1) {
        if (EOF == fscanf(fp, "%s", input)) {
            return (0);
        }
        if (!strcmp(input, "+nuova_partita")) {
            break;
        } else {
            new_node = calloc(1, sizeof(node) + sizeof(char) * (length + 1));
            new_node->key = (char*) new_node + sizeof(node);
            new_node->left = NULL;
            new_node->right = NULL;
            strcpy(new_node->key, input);
            ++num_comp;
            tree_insert(&eligible_words, new_node);
        }
    }
    build_compatible_words(&eligible_words, &compatible_words, new);

    key = (char*)calloc(1, sizeof(char) * (length + 1));
    while (1) {
        if (EOF == fscanf(fp,"%s", key) || EOF == fscanf(fp,"%d", &rounds)) {
            break;
        }
        while (1) {
            if (EOF == fscanf(fp, "%s", input)) {
                return (0);
            }
            if (input[0] != '+') {
                if (!strcmp(input, key)) {
                    fprintf(out, "ok\n");
                    if (!end_game(&eligible_words, length, new_node, input)) {
                        fclose(out);
                        fclose(fp);
                        return (0);
                    }
                    num_comp = 0;
                    comp_free(&compatible_words);
                    comp_reset(&eligible_words, &compatible_words, new,  &num_comp);
                    list_reset(&comparison_list);
                    break;
                } else if ((new_node = tree_search(&eligible_words, input)) != NULL) {
                    update_compatibilities(&compatible_words, calculate_comparison(temp = add_comparison(&comparison_list, new_node, length), key), &num_comp);
                    fprintf(out, "%s\n%u\n", temp->res, num_comp);
                    if (!(--rounds)) {
                        fprintf(out, "ko\n");
                        if (!end_game(&eligible_words, length, new_node, input)) {
                            return (0);
                        }
                        num_comp = 0;
                        comp_free(&compatible_words);
                        comp_reset(&eligible_words, &compatible_words, new, &num_comp);
                        list_reset(&comparison_list);
                        break;
                    }
                } else {
                    fprintf(out, "not_exists\n");
                }
            } else if (!strcmp(input, "+stampa_filtrate")) {
                print_filtered(&compatible_words);
            } else if (!strcmp(input, "+inserisci_inizio")) {
                while (1) {
                    if (EOF == fscanf(fp, "%s", input)) {
                        return (0);
                    }
                    if (!strcmp(input, "+inserisci_fine")) {
                        break;
                    } else {
                        new_node = calloc(1, sizeof(node) + sizeof(char) * (length + 1));
                        new_node->key = (char*) new_node + sizeof(node);
                        new_node->left = NULL;
                        new_node->right = NULL;
                        strcpy(new_node->key, input);
                        if (respect_constraints(&comparison_list, input)) {
                            ++num_comp;
                            pnode_insert_in_order(&compatible_words, new_node);
                        }
                        tree_insert(&eligible_words, new_node);
                    }
                }
            } else if (!strcmp(input, "+nuova_partita")) {
                num_comp = 0;
                comp_free(&compatible_words);
                comp_reset(&eligible_words, &compatible_words, new, &num_comp);
                list_reset(&comparison_list);
                break;
            } else {
                fclose(out);
                fclose(fp);                
                return (0);
            }
        }
    }
    fclose(out);
    fclose(fp);
    return (0);
}

Weierstrass

Utente Famoso

Iscritto da: feb, 2019

Messaggi:: 2245

Re: Progetto di informatica

09 feb 2023, 12:45

Prova così. Su quel file funziona, sugli altri devi controllare che non si generi qualche confronto su puntatori nulli

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

#define N 123

FILE * fp, * out;
    
typedef struct node_ {
    char* key;
    struct node_* left;
    struct node_* right;
} node;

typedef struct nodo_ {
    node *n;
    char *res;
    uint8_t *SI;
    uint8_t *NO;
    uint8_t *u;
    uint8_t u_dim;
    struct nodo_ *next;
} nodo;

typedef struct pnode_ {
    node *n;
    struct pnode_ *next;
} pnode;

int strcmp(const char *s1, const char *s2) {
    while (*s1 && (*s1 == *s2)) {
        s1++;
        s2++;
    }
    return (*(const unsigned char*)s1 - *(const unsigned char*)s2);
}

node* tree_search(node **root, char *word) {
    int val;

    while (*root != NULL) {
        if (!(val = strcmp((*root)->key, word))) {
            return (*root);
        } else if (val < 0) {
            root = &(*root)->right;
        } else {
            root = &(*root)->left;
        }
    }
    return (NULL);
}

void tree_insert(node **root, node *n) {
    while (*root != NULL) {
        if (strcmp((*root)->key, n->key) < 0) {
            root = &(*root)->right;
        } else {
            root = &(*root)->left;
        }
    }
    *root = n;
}

void print_filtered(pnode **comp_w) {
    while (*comp_w != NULL) {
        fprintf(out, "%s\n", (*comp_w)->n->key);
        comp_w = &(*comp_w)->next;
    }
}

int end_game(node **root, unsigned int l, node *n, char *i) {
    while (1) {
        if (EOF == fscanf(fp, "%s", i)) {
            return (0);
        }
        if (!strcmp(i, "+nuova_partita")) {
            return (1);
        } else {
            while (1) {
                if (EOF == fscanf(fp, "%s", i)) {
                    return (0);
                }
                if (!strcmp(i, "+inserisci_fine")) {
                    break;
                } else {
                    n = calloc(1, sizeof(node) + sizeof(char) * (l + 1));
                    n->key = (char*) n + sizeof(node);
                    strcpy(n->key, i);
                    n->left = NULL;
                    n->right = NULL;
                    tree_insert(root, n);
                }
            }
        }
    }
}

void pnode_insert(pnode **pn, node *n, pnode *new) {
    new = (pnode*)calloc(1, sizeof(pnode));
    new->n = n;
    new->next = *pn;
    *pn = new;
}

void comp_free(pnode **comp_w) {
    pnode *del;

    while (*comp_w != NULL) {
        del = *comp_w;
        *comp_w = (*comp_w)->next;
        free(del);
    }
}

void comp_reset(node **root, pnode **comp_w, pnode *new, unsigned int *m) {
    if (*root != NULL) {
        ++*m;
        comp_reset(&(*root)->right, comp_w, new, m);
        pnode_insert(comp_w, *root, new);
        comp_reset(&(*root)->left, comp_w, new,  m);
    }
}

void list_reset(nodo **c_list) {
    nodo *del;

    while (*c_list != NULL) {
        del = *c_list;
        *c_list = (*c_list)->next;
        free(del);
    }
}

nodo* add_comparison(nodo **c_list, node *a, uint8_t l) {
    while (*c_list != NULL) {
        c_list = &(*c_list)->next;
    }
    *c_list = calloc(1, sizeof(nodo) + sizeof(char) * (l + 1) + sizeof(uint8_t) * l);
    (*c_list)->n = a;
    (*c_list)->next = NULL;
    (*c_list)->res = (char*) *c_list + sizeof(nodo);
    (*c_list)->u = (uint8_t*) *c_list + sizeof(nodo) + sizeof(char) * (l + 1);
    (*c_list)->res[l] = '\0';
    return (*c_list);
}

nodo* calculate_comparison(nodo *n, const char *k) {
    n->SI = calloc(1, N); 
    n->NO = calloc(1, N);    
    n->u_dim = 0;
    uint8_t v[N] = {0};
    for(unsigned int i = 0; k[i]; ++i)
    {
        if(n->n->key[i] == k[i])
        {
            n->res[i] = '+';
        }
        else
        {
            n->res[i] = '/';
            ++v[(int)k[i]];
        }
    }
    for(unsigned int i = 0; k[i]; ++i)
    {
        if(n->res[i] == '/')
        {
            if(v[(int)n->n->key[i]])
            {
                n->res[i] = '|';
                --v[(int)n->n->key[i]];
                if(!n->SI[(int)n->n->key[i]]++)
                {
                    n->u[(n->u_dim)++] = n->n->key[i];
                }
            }
            else
            {
                ++n->NO[(int)n->n->key[i]];
            }
        }
    }
    return (n);
}

int is_compatible(const char *p, nodo *n) {
    uint8_t v[N] = {0};

    unsigned int i;
    for(i = 0; n->n->key[i] && (n->res[i] == '+' ? p[i] == n->n->key[i] : p[i] != n->n->key[i] && ++v[(int)p[i]] && (!n->NO[(int)(p[i])] || n->SI[(int)(p[i])] - v[(int)(p[i])] >= 0)); ++i);
    for(i = !n->n->key[i] ? 0 : n->u_dim + 1; i < n->u_dim && v[n->u[i]] - n->SI[n->u[i]] >= 0; ++i);
    return(i == n->u_dim);
}

void update_compatibilities(pnode **comp_w, nodo *n1, unsigned int *m) {
    pnode *del;

    while (*comp_w != NULL) {
        if (!is_compatible((*comp_w)->n->key, n1)) {
            del = *comp_w;
            *comp_w = (*comp_w)->next;
            free(del);
            --*m;
        } else {
            comp_w = &(*comp_w)->next;
        }
    }
}

int respect_constraints(nodo **p, char *i) {
    while (*p != NULL) {
        if (!is_compatible(i, *p)) {
            return (0);
        }
        p = &(*p)->next;
    }
    return (1);
}

void pnode_insert_in_order(pnode **comp_w, node *n) {
    pnode *new;

    while (*comp_w != NULL && strcmp((*comp_w)->n->key, n->key) < 0) {
        comp_w = &(*comp_w)->next;
    }
    new = (pnode*)calloc(1, sizeof(pnode));
    new->n = n;
    new->next = *comp_w;
    *comp_w = new;
}

void build_compatible_words(node **el_w, pnode **comp_w, pnode *new) {
    if (*el_w != NULL) {
        build_compatible_words(&(*el_w)->right, comp_w, new);
        pnode_insert(comp_w, *el_w, new);
        build_compatible_words(&(*el_w)->left, comp_w, new);
    }
}

int main() {
    node *eligible_words = NULL;
    nodo *comparison_list = NULL, *temp;
    node *new_node = NULL;
    pnode *compatible_words = NULL, *new = NULL;
    char input[100], *key;
    uint8_t length;
    unsigned int num_comp = 0, rounds;
            
    if ((fp=fopen("test3.txt", "r"))==NULL)
        return -1;
    
    if ((out=fopen("out.txt", "w"))==NULL)
        return -2;    

    if (EOF == fscanf(fp, "%s", &length)) {
        fclose(out);
        fclose(fp);
        return (0);
    }

    while (1) {
        if (EOF == fscanf(fp, "%s", input)) {
            fclose(out);
            fclose(fp);
            return (0);
        }
        if (!strcmp(input, "+nuova_partita")) {
            break;
        } else {
            new_node = calloc(1, sizeof(node) + sizeof(char) * (length + 1));
            new_node->key = (char*) new_node + sizeof(node);
            new_node->left = NULL;
            new_node->right = NULL;
            strcpy(new_node->key, input);
            ++num_comp;
            tree_insert(&eligible_words, new_node);
        }
    }
    build_compatible_words(&eligible_words, &compatible_words, new);

    key = (char*)calloc(1, sizeof(char) * (length + 1));
    while (1) {
        if (EOF == fscanf(fp,"%s", key) || EOF == fscanf(fp,"%d", &rounds)) {
            break;
        }
        while (1) {
            if (EOF == fscanf(fp, "%s", input)) {
                fclose(out);
                fclose(fp);             
                return (0);
            }
            if (input[0] != '+') {
                if (!strcmp(input, key)) {
                    fprintf(out, "ok\n");
                    if (!end_game(&eligible_words, length, new_node, input)) {
                        fclose(out);
                        fclose(fp);
                        return (0);
                    }
                    num_comp = 0;
                    comp_free(&compatible_words);
                    comp_reset(&eligible_words, &compatible_words, new,  &num_comp);
                    list_reset(&comparison_list);
                    break;
                } else if ((new_node = tree_search(&eligible_words, input)) != NULL) {
                    update_compatibilities(&compatible_words, calculate_comparison(temp = add_comparison(&comparison_list, new_node, length), key), &num_comp);
                    fprintf(out, "%s\n%u\n", temp->res, num_comp);
                    if (!(--rounds)) {
                        fprintf(out, "ko\n");
                        if (!end_game(&eligible_words, length, new_node, input)) {
                            fclose(out);
                            fclose(fp);
                            return (0);
                        }
                        num_comp = 0;
                        comp_free(&compatible_words);
                        comp_reset(&eligible_words, &compatible_words, new, &num_comp);
                        list_reset(&comparison_list);
                        break;
                    }
                } else {
                    fprintf(out, "not_exists\n");
                }
            } else if (!strcmp(input, "+stampa_filtrate")) {
                print_filtered(&compatible_words);
            } else if (!strcmp(input, "+inserisci_inizio")) {
                while (1) {
                    if (EOF == fscanf(fp, "%s", input)) {
                        fclose(out);
                        fclose(fp);                       
                        return (0);
                    }
                    if (!strcmp(input, "+inserisci_fine")) {
                        break;
                    } else {
                        new_node = calloc(1, sizeof(node) + sizeof(char) * (length + 1));
                        new_node->key = (char*) new_node + sizeof(node);
                        new_node->left = NULL;
                        new_node->right = NULL;
                        strcpy(new_node->key, input);
                        if (respect_constraints(&comparison_list, input)) {
                            ++num_comp;
                            pnode_insert_in_order(&compatible_words, new_node);
                        }
                        tree_insert(&eligible_words, new_node);
                    }
                }
            } else if (!strcmp(input, "+nuova_partita")) {
                num_comp = 0;
                comp_free(&compatible_words);
                comp_reset(&eligible_words, &compatible_words, new, &num_comp);
                list_reset(&comparison_list);
                break;
            } else {
                fclose(out);
                fclose(fp);
                return (0);
            }
        }
    }
    fclose(out);
    fclose(fp);
    return (0);
}

Devi accedere o registrarti per scrivere nel forum

73 risposte