Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

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

l
leonardo.brogi (170 points)
1 1 3
in Recupero HW4 by (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 (207920 points)
749 1267 2373
by (208k points)
I generatori hanno le stesse lettere oppure una di meno
EffeGi (1530 points)
0 1 5
by (1.5k 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 (207920 points)
749 1267 2373
by (208k 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)
1 1 3
by (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 (207920 points)
749 1267 2373
by (208k 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 .....