HW4 di recupero, come trovare il generatore non presente nella lista di parole date

Question

Salve a tutti,

Sono bloccato sul hw4 di recupero da un bel pò di tempo, il mio problema principale è che non riesco a trovare il generatore quando questo non è presente nella lista di parole.

Ad esempio nel test con 9900 parole non riesco a capire come trovare il generatore 'n', come faccio a capire che il generatore è esterno? E soprattutto come riesco a farlo in tempi brevi senza fare le permutazioni di ogni singola parola all'interno del file?

passo 6 test su 10, di cui 2 vanno in timeout

Grazie per l'aiuto

Answer 1

I generatori hanno le stesse lettere oppure una di meno

Answer 2

Ciao!

infatti se il generatore è più piccolo (al max di 1) non lo troverai tra le parole...

quindi consiglio di cercare direttamente generatori più piccoli, partendo dalle parole.

Inoltre consiglio l'utilizzo di insiemi per ottimizzare i tempi 

PS. (ricordati di inserire la parola stessa come generata dai "generatori figli" )

Spero di essere d'aiuto!

Answer 3

Non capisco perchè fai le permutazioni per capire se due parole sono uguali/simili, è il modo più inefficiente che esiste. Prova a canonicizzarle.

Answer 4

Ciao.
Io ho standardizzato le parole creando insiemi di lettere ma i tempi sono biblici. Pensando a quelle ripetute che set avrebbe eliminato, con una list comprehension ho creato gruppi del tipo "cassa" = "c", "a", "s", "ss", "aa".
Il tempo però arriva a centinaia di secondi.
Ho provato a scandire ogni parola e verificarla in base alla lunghezza con tutte le altre
Oppure
a raggrupparle in un dizionario di lunghezze per paragonare solo quelle di dimensioni "giuste" ma il tempo varia poco.

Comments

ci sono modi molto più semplici di standardizzare una parola in modo da poterla confrontare con un suo anagramma e capire se sono uguali. Basta pensare che contengono le stesse lettere ma .....