HW8 di recupero.... qualche consiglio??

Question

Ciao, volevo sapere se potrei avere qualche consiglio che mi faccia riflettere (se possibile) per quanto riguarda l'hw8 di recupero... visto che è ormai più o meno 17 giorni che ci sto su ed ho guardato le altre domande relative all'hw8rec qui su q2a.. ho provato ad individuare la prima frase e poi concatenare partendo da li ma passo solo 5 test e nessun test segreto.. ho pensato anche di prendere tutte le combinazioni e provare a fare tutti i casi possibili ma ancora non mi raccapezzo su come implementarlo.. per questo ho perso il primo appello.. e non vorrei perdere il secondo..

Answer 1

La tua impostazione iniziale è corretta, intanto fai in modo che il programma provi tutte le combinazioni di parole, perciò tutte quelle che stanno bene insieme le attacca.

Quindi l'idea sarebbe che ad ogni chiamata della funzione ricorsiva, ogni volta che scendi sempre di più di "livello" di ricorsione, ti avvicinerai sempre più a quella che sarà l'ultima parola, quella che chiude la frase insomma.

Se il programma riesce in questo intento, cioè arrivi all'ultima parola, avendo usato tutte le altre, BENE! Questo vuol dire che tutte le parole sono state concatenate nel modo più corretto, come definito dalla consegna. Ovviamente per fare ciò nel mezzo dovrai controllare le parole che "appiccichi" tra loro, se arrivi ad un punto che ti ritrovi a dover appendere una parola che hai già usato, sicuramente quella non era la combinazione giusta e perciò provi le altre oppure risali di "livello".

E siccome la consegna richiede che al ritorno la funzione restituisca una lista di interi corrispondenti alle posizioni delle parole nel file, mentre attacchi le parole tieni conto anche di questo fatto.

Intanto fallo funzionare, all'ottimizzazione ci pensi dopo e non ti demoralizzare che non sei l'unico ad aver saltato il primo appello

Comments

pure io uso tutte le combinazione inerente ad una parola cosi da velocizzare il processo però arrivo all'ultima parola con ancora delle parole da attaccare

---

Se vi rimangono delle parole da attaccare oppure la soluzione non è unica vuol dire che in precedenza è stata fatta una scelta sbagliata (ad esempio la prima parola è un'altra oppure in un certo momento della vostra costruzione esisteva un'altra parola da attaccare alla vostra soluzione parziale)

Provate a costruire l'albero di gioco della soluzione come abbiamo fatto a lezione

---

dove posso trovare la video lezione?

---

in aula                 .

L'idea è di costruire un "albero di gioco" che ha come nodi le posizioni del gioco mano a mano che evolve.
Ciascun nodo/posizione (nel nostro caso ad esempio un certo gruppo di parole concatenate e il resto da concatenare ) ha come figli tutte le posizioni che si possono ottenere applicando una mossa (concatenare un'altra parola).
Si esplora l'albero cercando la soluzione vincente (nel nostro caso tutte le parole concatenate) e ogni volta che una foglia si rivela "sbagliata" (parole rimanenti che non possono essere concatenate, oppure nessuno dei nodi figli è una soluzione) si ignora quel percorso e si prova un'altro nodo dell'albero.

Aggiungo che per passare tutti i test il meccanismo deve essere reso efficiente per evitare di ripetere più volte le stesse operazioni.

Answer 2

Mi aggrego anche io, sono ancora in alto mare, non riesco a trovare un algoritmo efficiente.

Answer 3

Due consigli ovvi :
- non ripetere le stesse operazioni
- sfruttare il fatto che solo certe coppie di parole si concatenano e non altre

Answer 4

Buonasera,

anche io sto riscontrando dei problemi, l'algoritmo mi restituisce la frase corretta nei primi tre test, per il quarto invece vengono contatenate due parole nell'ordine non corretto; queste sono le parole in input:

ntato)èdettoh
equestocamminoe
Determinareseq
ncamminoinungr
lgrafounaeuna
oseessotoccatu
oriadeigrafi,un
esistaèunprobl
grafo(orienta
uttiiverticidel
atoononorient
Nelcampomatema
maticodellateor
blemaNP-complet
hamiltonianos
asolavolta.De
eto.

Iniziando dalla prima ( ntato)èdettoh ), il mio algoritmo concatena grafo(orienta perché individua tre caratteri uguali, la parola da concatenare sarebbe invece: atoononorient.

C'è un ordine preferenziale in cui procedere?

Grazie Matteo.

Comments

Il fatto che passa i primi 3 test e dal quarto in poi no, è il seguente:

Nei primi 3 test ogni parola può essere concatenata alla successiva mediante il semplice controllo dell'UNICA sottostringa più lunga, esempio:

{

pezzi_0.txt: ottuso iodato coniglio

ottuso -> None  [0 sottostringhe]

iodato ->  o -> ottuso [1 sottostringa]

coniglio -> o -> ottuso | coniglio -> io -> iodato [2 sottostringhe ]

}

Se il programma dovesse scegliere quale stringa concatenare alla parola coniglio, sceglierebbe sicuramente (iodato) perchè (-io-) sarebbe la sottostringa più lunga tra le due di coniglio. (come definito nella consegna)

Questo criterio di scelta funziona fino al terzo test, dal quarto in poi dovrai rendere più "intelligente" il programma, perchè le parole avranno più sottostringhe di lunghezza uguale e quindi se mantieni il criterio detto prima, il programma sceglierà sempre quella sbagliata (o quella giusta per CASO!).

Il consiglio che ti do' è lo stesso che ho già dato in precedenza sempre su questa domanda, leggi le risposte precedenti.

---

Grazie Alexei,

proverò a creare una sorta di "ramificazione" dell'esecuzione, se non ho capito male quello che intendi.

Answer 5

Anche io sto avendo problemi, infatti mi ha fatto saltare l'appello del 29 gennaio, comunque io riesco ad attaccare le parole però va in crisi quando arrivo all'ultima parola( perchè parto da una parola presa arbitrariamente dalla lista) ed ho ancora parole da attaccare