Ordine Rettangoli

Question

Ciao a tutti,

per trovare l'ordinamento dei rettangoli vado a ritroso sapendo che il rettangolo che sta in cima a tutti non ha intersezioni, quindi tolgo il colore di tale rettangolo dalle intersezioni degli altri, prendo il secondo rettangolo che sta in cima e così via...in modo simile a quanto fatto da alcuni come in questo link:

https://q2a.di.uniroma1.it/19666/ordine-rettangoli?course=hw6-required/homeworks/fondamenti-di-programmazione-20-21

Tuttavia la matrice compressa che produco utilizzando il file 'random-25-831-643.png' produce un ordinamento differente da un certo indice in poi rispetto al file di encoding fornito.

Qualcuno sa per caso quale possa essere il motivo?

Molte grazie

Answer 1

Concordo, se non specifichi il tipo di errore che ricevi è difficile darti un suggerimento

Comments

Nessun errore, semplicemente dopo un certo indice l'ordinamento esce differente...quindi non comprendo se la logica che ho utilizzato sia alla fine errata e quindi non sto considerando alcuni casi che mi sfuggono. Quindi ad esempio gli ultimi K rettangoli che vengono disegnati (quelli in cima) vengono ordinati correttamente, ma poi mi ritrovo da K in poi un ordinamento dei colori differente da quello del professore (in sostanza il rettangolo alla base di tutti non corrisponde a quello che calcolo...).

Non è corretta la logica utilizzata?

---

magari se un particolare rettangolo ha solo un'intersezione con un rettangolo che sta sopra (ma che non è disegnato immediatamente dopo lui) e tu togli l'unica intersezione che ha, per il tuo algoritmo risulta essere quello disegnato erroneamente prima nella sequenza

---

però rimuovendo iterativamente il colore che sta in cima ad ogni passo non dovrebbe capitare il caso di cui parli. Infatti l'ordine di sovrapposizione è unico quindi non possono coesistere due rettangoli sullo stesso piano. O sbaglio?

---

Allora non è questo il problema. Come si comporta l'algoritmo quando togli il colore di un rettangolo che sta sopra a due rettangoli diversi e che hanno entrambi altre 2 intersezioni rimaste (tolta quella del rettangolo sopra in comune)?

---

Quando rimuovo il rettangolo che sta sopra, l'algoritmo va a cercare il rettangolo che non ha più intersezioni (che ci deve essere data l'unicità della disposizione delle immagini). Quindi i due rettangoli del tuo esempio perdono un'intersezione (perchè viene rimossa) e l'algoritmo seleziona ora il colore del rettangolo che non è più coperto da nessun altro.

Ad esempio immagina io ho 5 Rettangoli R0,R1,R2,R3,R4 (tra parentesi le loro intersezioni): R0 = ( ), R1 = (R0), R2 = (R1), R3 = (R0,R1,R2), R4 = (R0,R2,R3). Se rimuovo R0 ottengo R1 = (), R2 = (R1), R3 = (R1,R2), R4 = (R2,R3). Ora R3 e R4 hanno entrambi 2 intersezioni, ma l'algoritmo prende R1. Quindi toglie R1 da R2 che diventa R2 = (), R3 diventa R3 = (R2) etc...

Non comprendo perchè non possa funzionare.

---

La logica è giusta, ho completato poco fa l'algoritmo seguendo questo ragionamento e funziona su tutti i test. Probabilmente non l'hai sviluppata nel modo giusto.

---

Ok perfetto! Mi rincuora perlomeno saperlo! Allora sta in altro l'errore come immaginavo! Molte grazie ;)

---

Quando il procedimento ci sembra giusto, ma il computer non è d'accordo, secondo me in questi casi una bella sessione di debug è quello che ci vuole! Quando si scova il baco, lo si schiaccia senza pietà: è una bella soddisfazione!

Se ci fosse bisogno di un esempio pratico di debugging, c'è quello del Prof. Sterbini nella lezione n.15 di martedì scorso (24/11) al minuto 1:13

https://twiki.di.uniroma1.it/pub/Programmazione1/AA20_21/DiarioDelleLezioni-CanaleAL/lezione15-24-11-20.mp4

Spero di essere stato utile. Buon lavoro.

---

Grazie! Ci dò un'occhiata! :)

Answer 2

quale errore ti da?