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

l
leonardo.brogi (170 points)
0 1 3
asked Feb 6, 2020 in Recupero HW4 by leonardo.brogi (170 points)
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

4 Answers

andrea.sterbini (172780 points)
513 935 1789
answered Feb 6, 2020 by andrea.sterbini (172,780 points)
I generatori hanno le stesse lettere oppure una di meno
EffeGi (1530 points)
0 1 5
answered May 7, 2020 by EffeGi (1,530 points)

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" heart)

Spero di essere d'aiuto!

andrea.sterbini (172780 points)
513 935 1789
answered May 10, 2020 by andrea.sterbini (172,780 points)
Non capisco perchè fai le permutazioni per capire se due parole sono uguali/simili, è il modo più inefficiente che esiste. Prova a canonicizzarle.
f
fpoldi (210 points)
0 1 3
answered Jul 1, 2020 by fpoldi (210 points)
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.
andrea.sterbini (172780 points)
513 935 1789
commented Jul 1, 2020 by andrea.sterbini (172,780 points)
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 .....