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

[Giova411]

Volevo esercitarmi per diletto e per non perdere la "mano"...
Anche perché questi sono esercizi classici nelle prove d'assunzione alla google, amazon e compagnia bella..
Avevo visto un esercizio del forum (IN STILE STRINGHE DEL DNA da confrontare) e pensavo di farlo ma è rimasto bloccato lì.
Consideriamo un dizionario con delle stringhe date ad esempio di 4 come questo:
AB BA ABB BAB
Data poi una stringa casuale come questa:
ABBBABABAB
Bisogna trovare se quest'ultima data è composta dalle sole stringhe del dizionario (anche ripetute)
Nell'esempio dovrei ottenere 3 modi possibili
(ossia tre modi: ABB − BA − BA − BAB, oppure ABB − BA − BAB − AB e ABB − BAB − AB − AB )

Sempre con lo stesso dizionario, ma dando una stringa diversa tipo questa:
ABBAAAB
Ottengo 0 modi.

Un codice ricorsivo che funziona l'ho scritto ma volevo sfruttare la programmazione dinamica o, per strafare, la tecnica memoization che memorizza solo cio' che ci serve.

#include <iostream>
#include <vector>
using namespace std;
string X;
vector < string > P;
int modi = 0;

void dfs (string s){
  if (s.length () >= X.length ()){
      if (s == X) modi++;
      return;
    }
  for (int i = 0; i < P.size (); i++){
      dfs (s + P[i]);
    }
}
int main (){
  int N;//numero di primitive
  cout << "Inserisci il numero di primitive: \n";
  cin >> N;
  string temp;
  cout << "Inserisci le primitive (separate da uno spazio): \n";
  for (int i = 0; i < N; i++){
      cin >> temp;
      P.push_back (temp);
    }
  cout << "Inserisci la stringa: \n";
  cin >> X;
  dfs ("");
  cout << "Numero: " << modi << endl;
}

Sono tornato a rompere

[vict85]

Sono a Roma e in questi giorni non ho accesso ad un compilatore. Comunque provo a descrivertelo a parole. Il dizionario lo metto per semplicità in un vector D. La parola è in string P. Crei quindi un vector M(P.lenght()+1,0) e poni M[0]=1.
A questo punto fai un ciclo for(int i=1; i<= P.lenght(); ++i) e dentro questo calcoli M. Il calcolo lo fai con un ciclo sulle parole in D in cui controlli che M[i-D[j].lenght()]!=0 (e che l'indice non diventi negativo) e poi con un ciclo compari D[j][k] con P[i-1-D[j].lenght()+k]. Se il confronto ha successo aumenti M di uno e passi alla prossima parola del dizionario.
Calcolato M per tutte le i, restituisci al main M[P.lenght()].

[Giova411]

VIC TI PAGO IL BIGLIETTO ALLORA!!! TORNAAAAA

Gli indici mi incasinano MI SENTO STUPIDOOOOOOOOOOO
Forse ho capito male, così "a parole", ma fai 3 cicli per togliere la ricorsione "stupida" mia?
Col for lavori sulla stringa, con un while (immagino) scorri il vector delle primitive
K e J come le inizializzi? CHE PALLEEEEEEE

[vict85]

Io non ho eliminato la ricorsione dalla tua, ho proposto un algoritmo che usa la memoization (o era la programmazione dinamica non ricordo bene la differenza). L'eliminazione della tua ricorsione non è comunque semplicissima perché ogni funzione ricorsiva contiene un ciclo al suo interno.

Comunque ho usato un compilatore online e sembra che questo funzioni.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int dfs(vector<string> &D, string P);

int main()
{
  string X;
  vector<string> P;
  int N;//numero di primitive
  cout << "Inserisci il numero di primitive: \n";
  cin >> N;
  string temp;
  cout << "Inserisci le primitive (separate da uno spazio): \n";
  for (int i = 0; i < N; i++){
      cin >> temp;
      P.push_back(temp);
    }
  cout << "Inserisci la stringa: \n";
  cin >> X; 
  cout << "Numero: " << dfs(P, X) << endl;
}

int dfs(vector<string> &D, string P)
{
	int const Ps = P.length();
	vector<int> M(Ps+1, 0);
	M[0] = 1;
	
	for(int i=1; i<= Ps; ++i)
	{
		int const Ds = D.size();
		for(int j=0; j < Ds; ++j)
		{
			int const Djs = D[j].length();
			if(Djs <= i)
			{
				if(M[i - Djs] != 0)
				{
					int k = 0;
					for(; (k < Djs)&&(D[j][k] == P[i-Djs+k]); ++k);
					if(k == Djs)
						M[i] += M[i - Djs];
				}
			}
		}
	}
	return M[Ps];
} 

anche se immagino sarebbe necessario qualche test più serio per esserne sicuri (ho usato il tuo codice per il main).


Ripensando alle questioni relative all'ordinamento non sono sicuro che valga troppo la pena farlo. Per problemi semplici probabilmente non ci sono neanche così tanti vantaggi a non usare la ricorsione.

[Giova411]

Mi sento "CONFUSA E FELICE"
Vic scrivi il codice bene, davvero ti invidio!!!!!!!!
In questo caso non son riuscito a farlo "bene" su "carta e penna", figuriamoci a farlo efficente col codice.
Come dice APA bisogna allenarsi con queste "coding interview", ma anche avere la padronanza del linguaggio come Vic.
Ad esempio, solo ora, ho visto come usare bene un vector a tal punto da poter scrivere " D[j][k] "... GRAZIE VIC DAVVERO (una finezza, tipo quei doppi-passi di Ronaldo nel 1997/'98.. e non sono interista!).

"vict85":Io non ho eliminato la ricorsione dalla tua, ho proposto un algoritmo che usa la memoization (o era la programmazione dinamica non ricordo bene la differenza)

Da quel che ricordo, una è sottoinsieme dell'altra; ossia la memo è una PD "tirchia" perché "prende nota" solo dei dati che servono e non di tabelle piene riempite tutte senza badare al consumo di spazio. Se la memoized prende troppi appunti allora sfocia in una PD(credo)
Nel codice mio [size=50](che faceva andar di corpo anche la nonna mia stitica dal 1988)[/size] non c'era nessuna memo ed una ricorsione grande come l'Empire State Building...

Prima di chiudere con un "risolto" PENSATE si possa dire che la soluzione di VIC sia O( nm ) ?
Si può fare di meglio? [size=50]Dai aspettiamo che torni dalla Capitale!!!!![/size]

[vict85]

Se con m si intendi il numero di caratteri che compongono complessivamente D allora si. Altrimenti è più un O(mnp) dove p è la lunghezza massima delle primitive. Il metodo di apatriarca (che di c++ e programmazione ne sa sicuramente più di me[nota]Ed essendo mio fratello gemello posso dirlo con una certa sicurezza.[/nota]) è lineare su n ma richiede di trovare l'automa (a meno che non si conoscano le primitive in anticipo). Devo dire che essendo un matematico e non un informatico non ho mai esplorato gli algoritmi per la creazione di automi e la loro complessità. Se m e p sono piccoli rispetto a n probabilmente conviene, per m e p grandi dipenderà dall'algoritmo per farlo.

[Giova411]

AH DICEVO IO!!!!! GENI BUONI!!! CHE FORTUNA!!!!!!!
Per un attimo, all'inizio, ero sicuro che Apa mi sparasse un codice di 4 righe perfetto ma in Python

Sì è vero!!!!! E' O(nmp)!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Quindi meglio di quello che hai proposto te non è possibile!!!!!!!
GRAZIE A LOT!!!!!

Spero di trovare altri problemi simili!

[apatriarca]

Si può costruire un automa se si vuole ottenere qualcosa di meglio di quello che ho descritto in un mio precedente post, ma quella descrizione non conteneva alcun automa. Nota che in pratica l'idea viene dal fatto che il tuo problema originale (senza il conteggio del numero di combinazioni) è equivalente a chiedersi se la stringa rispetta la regex (AB|BA|ABB|BAB)*. Questa regex può ovviamente essere migliorata nella forma che avevo scritto. Siccome esiste un algoritmo per fare questo test in tempo lineare (non tutte le librerie regex usano questo algoritmo perché hanno funzionalità più avanzate per cui l'algoritmo non è applicabile), esiste un algoritmo in tempo lineare sulla lunghezza della stringa per risolvere anche il tuo problema.

[Giova411]

Quando scrivi faccio questo ->
Dopo vedo meglio di cosa parli
Quel simbolo " | " lo ricordo quando studiai Calcolo delle Prob (tipo 10 anni fa... )
Forse vedi una sorta di dag ed avanzi solo quando c'é una primitiva?


BUONGIORNO A TUTTI MITI MIEI!

[apatriarca]

No, parlo di Regular Expression.. Se non le conosci ti consiglio di darci un'occhiata perché sono utili in molti contesti. La barra verticale significa che devi prendere in considerazione l'espressione a sinistra oppure quella a destra. Quindi (AB|BA) significa "AB" oppure "BA". Nel link vedi anche altre operazioni. Se guardi la parte relativa all'implementazione, vedrai che si fa riferimento ad algoritmi lineari basati su automi (DFA o NFA) e poi un algoritmo basato sul backtracking. Per una descrizione più dettagliata dell'algoritmo che ho in mente puoi dare una occhiata a questo link. Discute l'implementazione (in C) di una funzione per il matching di espressioni regolari. È più generale e un po' diverso rispetto al tuo problema, ma è da dove ho preso l'idea.

[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.

\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?????????

(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 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++).

#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