Es 3 Homework 2 - Ottimizzare Algoritmo

Question

Per risolvere l'esercizio 3, dopo aver memorizzato i dati nelle varie liste, mi creo una lista di movimento per i due robottini, nel senso che per ogni incremento, incremento appunto le coordinate del robottino e le inserisco in una lista movimenti, per esempio da questi incrementi [5,-2,-2,2,4] ottengo una lista (movimenti) [[1,6],[3,6],[5,6],[5,8],[9,8]] e poi successivamente vado a fare i vari confronti, eliminando le coordinate dalla lista movimenti ogni volta che la x è minore della x della tupla della lista delle coordinate dei quadratini(posso farlo perché ho ordinato la lista di tuple) , l'algoritmo funziona, ma non passa il test "mp4.txt", penso che ci metta più di un secondo perché creo questa lista di movimenti ma non riesco a trovare un altro modo per risolverlo

Answer 1

scusa non ho capito bene perche elimini le coordinate dalla lista movimenti..perche lo fai?

Comments

Perché quando poi passo alla tupla successiva non devo controllare le coordinate che ho giá controllato

---

ah si ci sta diciamo anche se non hai problemi perche se vedi gli esempi map vanno sempre avanti le coordinate ovvero passano sempre da (3,10) (3,100) (3,1000) non troverai mai coordinate piu piccole che devi controllare indietro...non so se puo aiutare questo fatto

---

Non lo date per scontato, nel test aggiuntivo tutte le assunzioni che fate saranno stravolte

Answer 2

Può essere utile ottimizzare la lista dei movimenti sommando tra loro i movimenti consecutivi omogenei. 

io ad esempio ho una lista movimenti di questo tipo:

[(1, 1), (1, 6), (5, 6), (5, 8), (9, 8)] come puoi vedere non ho la tupla (3, 6) perché è intermedia tra (1, 6) e (5, 6) quindi non mi serve.

Per quanto riguarda la cancellazione potresti ovviare "salvandoti" l'index della lista da cui vuoi ripartire al successivo confronto