[Algoritmi] Togliere la ricorsione [c++] [RISOLTO VIC+APA!]

[Giova411]

Apa tu sei laureato in Fisica Quantistica (tesi sulla teoria delle stringhe?! )
Per me è troppo complicato da capire, figurati a "stendere" del codice
Devo ancora capire bene (e simulare meglio!) quello di VIC io !!!!!!!!!

[apatriarca]

Ma cosa hai trovato complicato? Il link sull'algoritmo? Le regular expression sono abbastanza facili. Non hai mai usato grep (o programmi simili) su linux? Si tratta di espressioni che permettono di rappresentare un insieme di stringhe in modo sintetico. Per esempio, la seguente espressione rappresenta un indirizzo email.

Codice:

\b[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,4}\b

Utilizzandola è possibile scrivere un codice molto sintetico che ti permette per esempio di estrarre gli indirizzi email da una pagina web (se vuoi estrarre anche indirizzi nascosti devi fare qualcosa di più complicato). Le espressioni non sono particolarmente semplici da leggere, ma sono molto utili quando devi lavorare con delle stringhe. Sono anche la risposta da dare in alcune domande ai colloqui. Per esempio, se ti venisse chiesto di estrarre tutte le righe da un file che rispettano una particolare struttura, programmi come grep o script in linguaggi come python/perl/lua/ruby.. sono la risposta probabilmente "corretta". Non sempre scrivere un programma in C++ complicato è la soluzione corretta. Anzi, non lo è quasi mai.

P.S. Ho una laurea triennale in Ingegneria del Cinema e dei Mezzi di Comunicazione e una laurea specialistica in Matematica.. Ma nulla di tutto questo l'ho imparato durante il mio percorso di studi.

[Giova411]

SEI SU UN LIVELLO SUPERIORE, volevo dire quello. Ma proprio nella classificazione degli esseri umani
Tipo Sapiens Sapiens Sapiens.
Lo so che ti faccio alterare! Ormai mi conosci!!!!!!
Sì grep lo conosco pochino! Il comando che confronta file di caratteri se non sbaglio.
(Non so che algoritmo usi boh.. pensavo una sorta di LCS modificata o String Matching..)

Trovo complicato implementarlo proprio. Forse Python per le stringhe è ideale.. Magari impararlo un giorno!
Sì volevo farlo in C++, ma metterci mano per me è un dramma!!!!
Te dici di chiamare librerie che fanno tutto? By the way, Vic è tornato da Roma?????????

Testo nascosto, fai click qui per vederlo

(Come farsi odiare... Chiedere a Giova!!!!)

[apatriarca]

No, credo tornerà la settimana prossima..

La ragione per cui l'uso di linguaggi come Python è meglio in alcuni problemi non riguarda la capacità di gestire stringhe, ma piuttosto nella maggiore velocità di sviluppo e nell'ampiezza della sua libreria standard.

grep è un programma che estrae le righe da un file che rispettano alcune condizioni. Queste condizioni possono essere descritte tramite semplici stringhe, ma anche con espressioni regolari. È quindi un po' più complicato di una ricerca di stringhe all'interno del file. L'algoritmo che usa è esattamente quello che è descritto in quel link (in effetti il Thompson di cui si parla è l'autore di Grep). Ci sono però varianti di grep che usano algoritmi diversi. Il vantaggio dell'algoritmo di Thompson è la complessità lineare rispetto a quella potenzialmente esponenziale dell'algoritmo basato sul backtracking. Ma è anche più limitato nelle funzionalità.

[Giova411]

Si sto guardando il link.
(Il backtracking già poteva bene a livello teorico.... Ma chi l'ha mai usato?! Solo a parole... Almeno io.)
Quindi, già in C++11, si potrebbe fare tutto con un ciclo solo (grazie a Thompson) con espressioni regolari che verificano le primitive date. Te dici che si può fare facilmente, un codice ancor più semplice e corto di quello scritto da VIC... Avevo letto la struct che consigliavi... Ma, se non vedo un esempio, sono ancora sul confuso andante. Eppure nel link che hai messo vedo del codice "familiare" : | libreria <regex> serve? (Mi servirà un mese per leggermi la documentazione!!! )

[apatriarca]

Non l'ho testato a fondo, ma il seguente codice dovrebbe fare quello che dicevo. L'ho scritto in C (e in realtà non è compatibile con il C++).

Codice:

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

typedef struct state state;
struct state {
    int word;
    int index;
    int count;
};

typedef struct state_array state_array;
struct state_array {
    size_t capacity;
    size_t size;
    state states[];
};

static inline state_array *new_state_array(size_t capacity) {
    size_t size = sizeof(state_array) + capacity*sizeof(state);
    state_array *ret = malloc(size);
    if (!ret) { return NULL; }

    ret->capacity = capacity;
    ret->size = 0;
    return ret;
}

static inline state_array *grow(state_array **arr, size_t new_capacity)
{
    if (!arr) { return new_state_array(new_capacity); }

    if (*arr && (*arr)->capacity >= new_capacity) { return *arr; }

    state_array *ret = new_state_array(new_capacity);
    if (!ret) { return NULL; }

    if (!memcpy(ret->states, (*arr)->states, (*arr)->size*sizeof(state))) {
        free(ret);
        return NULL;
    }

    free(*arr);
    *arr = ret;
    return ret;
}

static inline state_array *push_back(state_array *arr, state s)
{
    if (!arr) { return arr; }

    if (arr->capacity == arr->size) {
        if (!grow(&arr, arr->capacity*2)) { return NULL; }
    }

    arr->states[arr->size++] = s;
    return arr;
}

int combinations(const int dictionary_size, const char * dictionary[dictionary_size], const char *text)
{
    state_array *states = NULL, *states_next = NULL;

    states = new_state_array(dictionary_size);
    if (!states) { return -1; }

    push_back(states, (state){ -1, -1, 1 });

    states_next = new_state_array(dictionary_size);
    if (!states) { free(states); return -1; }

    push_back(states_next, (state){-1, -1, 0});

    int i = 0;
    while (text[i]) {
        if (states->states[0].count > 0) {
            for (int d = 0; d < dictionary_size; ++d) {
                if (!dictionary[d][0]) { // size 0 strings in dictionary
                    states_next->states[0].count += states->states[0].count;
                }
                if (text[i] == dictionary[d][0]) {
                    if (!dictionary[d][1]) { // size 1 strings in dictionary
                        states_next->states[0].count += states->states[0].count;
                    } else {
                        push_back(states_next, (state){ d, 0, states->states[0].count });
                    }
                }
            }
        }

        for (size_t j = 1; j < states->size; ++j) {
            const char *word = dictionary[ states->states[j].word ];
            if (text[i] == word[ states->states[j].index + 1 ]) {
                if (!word[ states->states[j].index + 2 ]) {
                    states_next->states[0].count += states->states[j].count;
                } else {
                    push_back(states_next, (state){ states->states[j].word, states->states[j].index+1, states->states[j].count });
                }
            }
        }

        state_array *tmp = states;
        states = states_next;
        states_next = tmp;

        states_next->size = 1;
        states_next->states[0] = (state){-1, -1, 0};

        ++i;
    }

    int ret = states->states[0].count;

    free(states);
    free(states_next);

    return ret;
}

int main(void)
{
    const char * dictionary[] = {
        "AB", "BA", "ABB", "BAB"
    };
    const size_t dictionary_size = sizeof(dictionary)/sizeof(const char *);

    const char *str1 = "ABBBABABAB";
    printf("Stringa: %s. Modi: %d.\n", str1, combinations(dictionary_size, dictionary, str1));

    const char *str2 = "ABBAAAB";
    printf("Stringa: %s. Modi: %d.\n", str2, combinations(dictionary_size, dictionary, str2));

    return 0;
}


[Giova411]

Mi sei mancato tutti sti mesi