Blocco nell'hw8

A
Andrea.D'Archivio (270 points)
2 4 5
asked Jan 18, 2020 in Recupero HW8 by Andrea.D'Archivio (270 points)
Non so se ho capito bene fino in fondo la traccia, comunque sto svolgendo il problema trovando prima la parola iniziale e successivamente le altre.

Come altri hanno già detto, più parole sono concatenabili, anche se poi soltanto una sola concatenazione porta alla chiusura della parola.

Inizialmente pensavo che fra tutte quelle in comune dovevo prendere quella parola con la sottostringa in comune più lunga, invece poi ho capito che non è detto ciò. Quindi magari mi ritrovo a scegliere una parola concatenabile, e alla fine non riesco a chiudere la parola.

Il mio problema sta proprio nel non riuscire a formulare un algoritmo in modo da seguire questi cambiamenti di percorso.
613 views

4 Answers

andrea.sterbini (172780 points)
513 935 1789
answered Jan 18, 2020 by andrea.sterbini (172,780 points)
Quando tenti una parola ed il seguito non si sistema devi provare un'altra parola
A
Andrea.D'Archivio (270 points)
2 4 5
commented Jan 19, 2020 by Andrea.D'Archivio (270 points)
Non so, molto probabilmente me lo sto complicando io.

La ringrazio lo stesso.
DGreat (1210 points)
7 11 23
answered May 26, 2020 by DGreat (1,210 points)
Non so se hai risolto, ma considera ho accantonato l'hw per mesi finché oggi preso da un lampo di genio ho deciso di implementare questa soluzione.

Non so se il prof. Sterbini lo ha inserito come easter egg o è puramente casuale, ma a me è risultato molto utile leggere pezzi4.

Indica secondo me la struttura dati più adatta per risolvere il problema, e con un po' di lavoro sono sicuro riuscirai ad implementare ciò che chiede pezzi4.

L'idea che personalmente ho utilizzato è:

- trovare tutte le possibili combinazioni (ossia ogni parola con quale potenzialmente si può connettere), andando a creare una sorta di "guida" con il grafo

- tracciare un percorso per ogni parola seguendo la guida

Va da sè che se tutte le parole sono connesse tra di loro, dovresti avere un problema solo sull'ultima parola.

Infatti, facendo in questa maniera non serve lavorare veramente sulle parole, basta lavorare solamente sulla guida: è più veloce e non richiede perdite in termini di risorse.

Spero di esserti stato utile!
EffeGi (1530 points)
0 1 5
answered May 26, 2020 by EffeGi (1,530 points)

Ciao,

anche io sto lavorando sull'HW8 e sono rimasto bloccato solamente sull'ultimo test che va in timeout, ma l'algoritmo funziona.

Io ho catalogato le parole in un dizionario ed associato tutte le parole che possono essere successive a quella analizzata (solamente la sovrapposizione più lunga).

Creato il dizionario si parte alla ricerca di tutte le sequenze possibili sulla base della successiva parola nel dizionario, in quella chiave.

La funzione ricorsiva prende una sequenza inizialmente vuota ed aggiunge le parole (che sono numeri per semplicità di calcolo), se la sequenza è lunga come il dizionario (quindi con tutte le parole) la restituisce, mentre se la parola successiva è presente nella sequenza, viene scartata.

Pertanto la funzione ricorsiva ritornerà soltanto la sequenza che contiene tutte le parole concatenate.

Il problema resta sull'ultimo test... deve esserci un modo per semplificare nettamente la ricorsione, perchè nei primi 8 test sono sotto i 10 ms, il nono 0.8 sec ed il decimo 3.5 sec 

Ho pensato di non "scartare" le sequenze non valide in modo da evitare una chiamata alla ricorsione qualora le parole restanti fossero le stesse di una delle sequenze eliminate (quindi riutilizzare il calcolo già effettuato), tuttavia la lista di tutte le combinazioni possibili non valide è talmente grande che il programma risulta ancora più lento rispetto alla forza bruta....

Sono a corto di altre idee!

EffeGi (1530 points)
0 1 5
answered Jun 6, 2020 by EffeGi (1,530 points)

Una possibile soluzione è trovare le parole che necessariamente devono essere una la successiva dell'altra, ossia solo e solamente una parola più essere seguente ad un'altra. Dopo questa semplificazione, le possibili combinazioni che troverai con la funzione ricorsiva sono notevolmente diminuite, così da non avere problemi di timeout.

Non è detto che sia possibile individuare la prima parola (o l'ultima) della sequenza, l'unica soluzione è provare tutte le combinazioni possibili (con elementi ridotti secondo quanto detto prima) e ritornare la sequenza solo se comprende tutti quegli elementi!

Successivamente, inserisci nella sequenza trovata i percorsi semplificati che hai trovato, per ottenere infine la sequenza completa.

Un consiglio è quello di capire come trovare tutti i percorsi possibili in un grafo heart