Domanda Risolto Programma Pyhon Progetto gioco - unione parole compatibili

[FrancyTheon]

Buonasera ragazzi sto svolgendo un progetto in Python purtroppo però mi sono veramente bloccato su una parte di codice da svolgere in maniera ricorsiva probabilmente attraverso l’uso di alberi, non saprei. Chiedo gentilmente un aiuto qui sul forum se vi va di vedervi il testo ve lo allego qua sotto:


Viene data una lista di stringhe che, opportunamente combinate, formano un testo.

Le stringhe sono costruite in modo che un suffisso di una sia compatibile col

prefisso di una o più altre, ovvero abbiano una sottostringa in comune nelle

estremità opposte, di lunghezza imprecisata.

Esempio: "cavallo" è compatibile sia con "allora" ('allo') che con "logica"

('lo' ma anche 'ca' scambiando l'ordine delle due parole) e combinate possono

produrre rispettivamente "cavallora", "cavallogica" oppure "logicavallo".

In caso ci fossero più sottostringhe comuni per la stessa coppia di parole,

si prenda la più lunga.

Esempio: "patata" è compatibile con "atalanta" sia per la sottostringa 'a'

che per 'ata', si consideri 'ata'.



Esite un'unica sequenza delle stringhe in modo che ciascuna coppia di parole

consecutive sia compatibile per costruire il testo.

Si deve costruire un programma che fa uso di almeno una funzione ricorsiva

per trovare l'unica sequenza e, quindi, il testo originario.



Nello specifico, si costruisca una funzione es(fparole,ftesto) che prende

come argomenti:

- fparole: il percorso di un file di testo che contiene, su righe successive, le stringhe,

- ftesto: il percorso di un file in cui dovete scrivere il testo ricostruito

e che ritorna la lista degli indici delle stringhe in input nell'ordine

corretto per ottenere il testo originale (sconosciuto).



ES: se le stringhe nel file sono 'ottuso' 'iodato' 'coniglio'

l'unica sequenza corretta da scrivere nel file ftesto è conigliodatottuso

e la funzione deve tornare la lista di indici [2,1,0]

Non è ammesso importare librerie!

 

[St3ve]

Scrivi una funzione che permuta le stringhe in tutti i modi possibili, lo si può implementare ricorsivamente con un generatore. Poi modifichi il codice per skippare la chiamata ricorsiva nel caso in cui l'ultima l'ultima lettera della parola corrente non coincide con la prima lettera della parola successiva (i.e., non c'è alcun suffisso della parola attuale che è un prefisso per la parola successiva). Infine, unisci ogni lista di parole tenendo conto che devi "mangiare" più lettere possibili (un semplice for).

 

[FrancyTheon]

Scrivi una funzione che permuta le stringhe in tutti i modi possibili, lo si può implementare ricorsivamente con un generatore. Poi modifichi il codice per skippare la chiamata ricorsiva nel caso in cui l'ultima l'ultima lettera della parola corrente non coincide con la prima lettera della parola successiva (i.e., non c'è alcun suffisso della parola attuale che è un prefisso per la parola successiva). Infine, unisci ogni lista di parole tenendo conto che devi "mangiare" più lettere possibili (un semplice for).

Putroppo la cosa che mi mette in difficoltà è proprio il confronto poiché non basta che l’ultima parola sia la prima di un altra parola; nel caso di coniglio - iodato, le due parole sono compatibili poiché le ultime due lettere di conigl-io sono compatibili con le prime due di io-dato. Inoltre devo confrontare la compatibilità e prendere la sequenza più lunga di lettere compatibile: es. “coniglio” può avere come seguito “ottuso” per la compatibilità conigli-o o-ttuso e “iodato” per la compatibilità conigl-io io-dato. In questo caso viene scelto iodato poiché ha una sequenza di lettere compatibili più lunga.

 

[St3ve]

Oh, hai ragione non ci avevo riflettuto abbastanza. Anche per il controllo devi usare il "semplice ciclo for" che ti avevo accennato alla fine, una roba del genere:

def max_suffixprefix(a, b):
    i = 0
    while not b.startswith(a[i:]): i += 1
    return len(a) - i

 

[FrancyTheon]

Oh, hai ragione non ci avevo riflettuto abbastanza. Anche per il controllo devi usare il "semplice ciclo for" che ti avevo accennato alla fine, una roba del genere:

def max_suffixprefix(a, b):
    i = 0
    while not b.startswith(a[i:]): i += 1
    return len(a) - i

Grazie mille sto procedendo mi è stato molto utile il suo consiglio