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

Do you need help?

HW1bis - esercizio 2

f.cocci (650 points)
3 13 17
in HW1bis by (650 points)
Salve a tutti, volevo qualche dritta su come ottimizzare le performance relativamente alla soluzione da me sviluppata per l'esercizio 2 dell' HW1 di recupero.

In pratica:

#inizializzo un contatore a 0

#creo na lista di appoggio uguale ad ls

#finche' il contatore e' minore dell'intero k:

 # inizializzo una variabilire risultato di tipo lista

 # in una range pari alla lunghezza della lista:

  #appendo al risultato l'elemento della lista di appoggio (inizialmente uguale a ls) il cui indice corrisponde all'indice estratto dalla lista lmosse per l'indice i del range di lmosse che stiamo scorrendo.

 #pongo appo uguale al risultato

#incremento il contatore.

Alla fine la funzione una volta arrivato a k-1 esce dal ciclo e ritorna il risultato che e' la lista dopo le k combinazioni.

Il codice funziona perfettamente solo che a partire dal 5 test becco il time-out e non so davvero come ottimizzare.

il problema penso sia ndovuto al fatto che l'operazione venga ripetuta per k volte e dal quinto test k e' davvero grande.

Sto provando a fare ragionamenti su ena eventuale periodicita' del risultato, infatti per la prima coppia di ls e lmosse in pratica a partire dal sesto tentativo che in pratica restituisce il risultato immutato per poi ricominciare a reiterare le stesse combinazioni da 1 a 5.

Grazie, F.
831 views
closed

1 Answer

Best answer
_andrea_ (45670 points)
11 42 297
by (45.7k points)
selected by
Si devi usare la periodicità. Se la lista si ripete dopo 10 volte, e tu devi farlo 1037 volte, ti basta farlo solo 7 volte per ottenere il vero risultato. Ovviamente in realtà devi farlo prima 10 volte (per capire che dopo 10 si ripete) e poi altre 7, quindi 17 in totale, che è diverso sicuramente da 1037. Ovviamente questo è un esempio ma se lo fai il programma ti gira anche il meno di mezzo secondo
f.cocci (650 points)
3 13 17
by (650 points)
Finche il risultato generato e' una combinazione diversa di elementi (quindi la sequenza non e' presente tra quelle viste in precedenza) significa che deve continuare a fare il ciclo per generare altri risultati.

Nel momento in cui viene generata una sequenza gia vista, metto il alzo il flag delle variabile STOP e quindi smette di produrre nuovi risultati che da quel momente sarebbere periodici.

Il risultato diventa di volta in volta la tua nuova ls su cui generarne uno nuovo e cosi via.

Facendo un assegnamento non modifichi la lista ls, ma crei una nuova variabili di nome ls.

Alla fine cosi facendo il programma inpiega 0,3 secondi sulla mia macchina a fare tutti i test.
_andrea_ (45670 points)
11 42 297
by (45.7k points)
Non serve un insieme di sequenze, basta vedere se la lista nuova dopo le permutazioni è uguale a quella iniziale per sapere se si è arrivati alla periodicità
f.cocci (650 points)
3 13 17
by (650 points)
si anche, perche tornando all'esempio si nota che dopo il sesto tentativo il risultato e' uguale a ls.

Sinceramente, ho visto che funzionava egregiamente e ho chiuso la.
A
AFulvio (220 points)
2 2 5
by (220 points)

Scusami F.Cocci ma non capisco ancora un passaggio, una volta controllato se la lista generata è nella lista degli elementi visti, come faccio in caso contrario a continuare ad iterare per le restanti volte ? (Non capisco il passaggio in cui parli di Y, flag e N laugh)

_andrea_ (45670 points)
11 42 297
by (45.7k points)
Esegui gli scambi che rimangono da fare sapendo che dopo n volte la lista torna a posto. Se hai 99 scambi da fare e n=10, devi fare i restanti 9 scambi, che ottieni con modulo