[C] Progetto algoritmi tasselli e malta

[matteo.pata]

Ciao ragazzi sono di nuovo qui alle prese con il progetto di algoritmi per l'università.
Avrei bisogno di una grossa mano nello scegliere la struttura + adatta per il progetto che devo implementare in C.

Specifiche:

1 Il problema

Si vuole rivestire un pavimento rettangolare con un mosaico di tasselli e di malta a presa rapida. Ogni tassello ha la stessa grandezza ma `e delimitato da quattro bordi frastagliati di forma (in generale) diversa. I bordi di un tassello possono collimare pi`u o meno bene con i bordi degli altri tasselli. I tasselli
hanno un orientamento predefinito e devono essere collocati con quell’orientamento, a causa della fantasia disegnata nella parte superiore. Quindi ogni tassello ha un bordo Nord, uno Sud, uno Ovest e uno Est. I tasselli inizialmente sono dentro a delle scatole dall’identico contenuto. Queste scatole sono sempre
disponibili in numero sufficiente per terminare il lavoro. Ciascuna scatola contiene un numero prefissato k di tasselli numerati da 1 a k, sempre gli stessi in ogni scatola. Ad esempio, il tassello con numero di serie 3 della prima scatola ha la stessa forma (gli stessi bordi) del tassello numero 3 di tutte le altre scatole. Il numero di ordinamento `e scritto sul retro di ogni tassello, in piccolo. I tasselli possono essere estratti dalle scatole solo in tal ordine, da quello con numero di serie 1 a quello con numero di serie k.
Il pavimento, delimitato dalle quattro pareti, si pu`o immaginare come una griglia regolare di caselle quadrate, ciascuna delle quali dovr`a alla fine del lavoro contenere un tassello o essere riempita di malta. All’inizio del lavoro, ogni casella della griglia `e vuota.

2 Costruzione del mosaico

Ecco come si procede alla costruzione del pavimento. Per cominciare, si apre la prima scatola, e si mette il suo primo tassello nel mezzo del pavimento, nell’orientamento prescritto (i pavimenti hanno una numero dispari di caselle per lato, quindi esiste una casella centrale). Si rovescia il resto del contenuto della scatola in una apposita cesta di lavoro. Si apre
una scatola di riserva, se ne estrae il primo tassello e lo si pone nella cesta, in modo che questa contenga ora tanti tasselli quanti ce ne sono in una scatola. A questo punto, si procede sempre nello stesso modo, fino a quando l’intero pavimento sia completato,
cio`e non vi siano pi`u caselle vuote: si incolla un tassello alla volta sul pavimento, e talvolta, dopo averlo
fatto, si usa la malta liquida per riempire alcune zone del pavimento delimitate da tasselli gi`a posizionati. Ad ogni passaggio, si deve prendere un tassello dalla cesta per incollarlo sul pavimento, sempre accanto ad un tassello gi`a posizionato, in una casella ancora libera adiacente lato a lato a quest’ultimo. La scelta del tassello e della casella viene effettuata in modo da far collimare il pi`u possible il bordo del nuovo tassello con quello del tassello gi`a posizionato (vedi sotto).
Nell’estrarre il tassello dalla cesta di lavoro, lo si rimpiazza immediatamente col prossimo tassello preso dalla scatola di riserva, in modo che durante l’intero lavoro la cesta contenga sempre lo stesso numero di tasselli (tanti quanti ce ne sono in una scatola). Se la scatola di riserva rimane vuota, si apre semplicemente la scatola successiva, che servir`a da nuova scatola di riserva.
Dopo aver posto un tassello, si controlla se il pavimento presenta delle zone completamente delimitate da tasselli gi`a incollati: queste zone vengono subito riempite con la malta a presa rapida. Per “zona completamente delimitata” si intende un qualunque sottoinsieme di caselle vuote ciascuna delle quali sia adiacente lato a lato solo ad altre caselle di questo sottoinsieme oppure a tasselli gi`a incollati (ma non alle pareti che delimitano la stanza). La malta viene versata nella zona (o le zone) fino a riempirla, dopodich`e si indurisce. Le caselle piene di malta indurita non possono pi`u accogliere alcun tassello.

2.1 Bordi che collimano e bordi che non collimano

Come detto, i bordi dei tasselli sono frastagliati. Ognuno dei quattro bordi `e infatti caratterizzato da un certo numero n di dentellature in sequenza (n `e lo stesso per tutti i bordi di tutti i tasselli di un dato problema). Ciascuna dentellatura pu`o essere piatta, oppure rientrante, oppure sporgente. Rientranze (e sporgenze) possono essere profonde (o estroflesse) di una lunghezza variabile. Le rientranze sono descritte da numeri negativi, le sporgenze da numeri positivi: tanto maggiore il modulo del numero tanto pi`u profonda o estroflessa `e la rientranza o la sporgenza; una dentellatura piatta `e descritta dal numero zero.
Le rientranze rappresentate dal numero −k (con k naturale) collimano perfettamente con sporgenze della stessa entit`a, rappresentate dal numero opposto +k, e viceversa. In generale, il mismatch fra due dentellature k1 k2 `e un numero che rappresenta quanto quelle due dentellature sono lontane dal collimare perfettamente. E’ calcolato semplicemente con (k1 + k2)2 . Il mismatch fra un intero bordo e un altro `e la somma dei mismatch delle rispettive dentellature, in ordine.
Un tassello viene descritto da tutte le dentellature che si trovano sui suoi bordi, in ordine orario (n per lato cio`e 4n), a partire da quelle pi`u a Ovest del bordo Nord.

ESEMPIO



2.1.2 Scelta del tassello e della casella

Quando si deve scegliere il tassello fra quelli contenuti nella cesta, e il bordo libero a cui attaccarlo, bisogner`a preferire quel tassello e quel bordo libero che ottengano fra di loro un mismatch minore, fra tutte le scelte valide possibili di questo tipo (per “bordo libero” si intende il bordo di un tassello gi`a posizionato adiacente ad una casella ancora vuota). In caso di parit`a fra due o pi`u alternative, si sceglier`a di posizionare il tassello che presenti il numero di serie minore. Se il tassello scelto pu`o essere messo in due caselle diverse con lo stesso valore di mismatch, si scelga la posizione pi`u a Nord delle due, e in caso di ulteriore parit`a, quella pi`u a Est.
Nota: puo succedere che alcune caselle vuote saranno adiacenti a pi`u di un tassello gi`a incollato, cio`e che pi`u bordi liberi siano adiacenti ad una stessa casella vuota. Il criterio di scelta per`o valuta sempre ogni bordo separatamente, e nel sceglierne uno non conta quanto bene o quanto male gli altri bordi liberi collimino col tassello che viene eventualmente posto accanto ad essi. Ad esempio, si consideri la seguente situazione, dove in un minuscolo pavimento 2 × 2 siano stati collocati i tasselli A, B e C in questo modo:
AB
C. Un nuovo tassello D sar`a posizionato nella casella vuota rappresentata dal puntino a condizione che il bordo Ovest di D abbia un mismatch col bordo Est di C minore di quello ottenuto con qualunque altra scelta – e se questo si verifica non conta il mismatch fra il bordo Nord di D e il bordo Sud di B (se il mismatch minore possibile si trovasse fra il bordo Sud di B e il bordo Nord di D, ugualmente il tassello D sar`a posizionato nella casella vuota
– indipendentemente dal valore di mismatch fra il bordo Ovest di D e quello Est di C.)

3 Input e Output

Il file deve prendere dalla riga di comando il nome del file di input. Deve produrre in risposta un file di output, con un nome uguale a quello del file di input, giustapposto alla stringa .pnm. (ad esempio, se prende in input il file test.txt dovr`a produrre in output il file: test.txt.pnm

3.1 Dati in input

L’input consiste in file di testo, in cui il problema viene descritto con una serie di numeri interi (separati da spazi,
caratteri di accapo, etc). Per prima cosa compare la dimensione orizzontale e verticale del pavimento (sempre due numeri dispari). Segue il numero di tasselli contenuti in ogni scatola, e il numero di dentellature che compaiono in ognuno dei quattro lati di ogni tassello. Dopodiche’ compare la descrizione di ciascun tassello, uno dopo l’altro. La descrizione di un tassello consiste nella sequenza dei i valori numerici che rappresentano ciascuna dentellatura di ciascun lato (nell’ordine sopra descritto).

3.2 Dati in output

Il file di output deve consistere in un file di testo. All’inizio di questo file, nella sua prima riga, deve comparire la stringa di due caratteri “P1”. Nella seconda riga, devono comparire la larghezza e la lunghezza del pavimento, separate da uno spazio.
Di seguito, deve comparire la descrizione di come appare il pavimento alla fine del lavoro, a partire dalla fila pi`u a Nord del pavimento, fino alla riga piu’ a Sud, con una riga di testo per ogni fila. Ogni fila viene descritta da un numero binario per ogni casella, separati da uno spazio: 0 se la casella contiene un tassello, 1 se contiene malta.

3.3 Altri vincoli

La correttezza delle soluzioni `e un requisito necessario. Un progetto sar`a considerato pi`u o meno valido rispetto all’efficienza (tempo di calcolo) nel risolvere le istanze del problema di dimensioni via via crescenti (non solo le istanze fornite, ovviamente, ma anche altre del tipo di quelle fornite).
La sfida consiste nel fornire una soluzione che riesca a risolvere in tempi ragionevoli le istanze pi`u complesse possibili. Quali delle istanze proposte sar`a possibile risolvere?

4 Dimensioni e natura delle tipiche istanze del problema

I pavimenti possono essere molto grandi (o equivalentemente, i tasselli molto piccoli). Pavimenti composti di migliaia di tasselli per lato non sono incomuni. Anche il numero di tasselli diversi presenti nelle scatole pu`o essere
assai grande. Il numero di dentellature per ogni lato di tassello e’ di solito contenuto.


Grazia a tutti in anticipo.
Spero che qualcuno mi dia una mano....

[matteo.pata]

UP dai ragazzi una mano please

[tacchinox]

Io farei una struct "tassello" fatto da 4 array int "nord - sud - est - ovest", ti crei un tot di scatole di tasselli, che saranno altrettanti array, e poi man mano li svuoti nella cesta con un ciclo.

Per partire comunque crea una scatola costituita da 2 tasselli, fai un metodo per posizionarli, che tipo confronta se tassello[0].est >= tassello[1].est, con la tua formula ovviamente, poi fai un metodo che li stampa a video (e qua verra' un gran schifo immagino), e man mano provi a incrementare la scatole guardi se il risultato è giusto e i tempi sono rispettati.

Poi ci sono varie soluzioni, tipo una è che ogni tassello della cesta cerca la sua posizione all'interno del mosaico(ma all'aumentare della dimensione del mosaico è un macello perche' fa una marea di iterazioni), oppure fai che è il mosaico che "cerca" il tassello nella cesta, che consiste nel mettere il tassello[0] nel mosaico, poi prendere il lato nord del tassello[0] e cercare nella cesta un lato sud compatibile, poi prendere il lato est del tassello[0] e prendere nella cesta un lato est compatibile, fino a fare la croce, tipo
o
ooo
o
Poi quando hai una croce devi trovare il tassello con due lati compatibili e torni a fare un quadrato, etc...
ooo
ooo
ooo

Praticamente fai un ciclo dove controlli se c'e' una croce o un quadrato e a seconda cerchi uno o due lati compatibili, poi il mosaico si completa da solo.

Anche qua poi ordinarti l'array "cesta" prima di fare la scelta, magari facendo 4 copie ordinate tutte a seconda del lato piu' corto.
Tipo cestaEst[] - cestaOvest[] - cestaSud[] - cestaNord[] e man mano che riempi la cesta li riordini.
Cosi' sai sempre che se cerchi il tassello sul lato sud prendi l'elemento[0] di cestaSud, idem per gli altri lati.
Ovviamente devi riordinare i 4 array-copia ogni volta che riempi la cesta.
Poi dipende da te, se ti vengono in mente idee o se ci sono librerie potenti per gestire sta roba.

Spero comunque di averti dato un paio di spunti.

Dimenticavo, ovviamente il mosaico è una matrice di tasselli.

[matteo.pata]

up qualche altro spunto ragazzi...

[matteo.pata]

UP......

[matteo.pata]

[goldorak]

Beh in un problema del genere la prima cosa da fare e' scegliere le strutture dati piu' appropriate. Una indicazione il testo te la da

4 Dimensioni e natura delle tipiche istanze del problema

I pavimenti possono essere molto grandi (o equivalentemente, i tasselli molto piccoli). Pavimenti composti di migliaia di tasselli per lato non sono incomuni. Anche il numero di tasselli diversi presenti nelle scatole pu`o essere
assai grande. Il numero di dentellature per ogni lato di tassello e’ di solito contenuto.

Questo esclude strutture dati le cui operazioni hanno complessita' n^2 o peggio. Quindi ti servono strutture dati efficienti con complessita' O(n) oppure O(n * log n) .
Array statici sono out, devi usare alberi bilanciati, magari alberi binari red black o b-alberi etc... Sta a te la scelta.

Puoi usare un albero bilanciato per mantenere l'insieme dei tasselli gia' predisposti sul mosaico.
Questo e' gia' un punto di partenza, poi vedi tu che tipo di struttura usare per rappresentare il mosaico.

[matteo.pata]

UP......

[goldorak]

Originariamente inviato da matteo.pata

UP......

Ma cosa ti aspetti, che la gente ti scriva il codice al posto tuo ?

[matteo.pata]

Originariamente inviato da goldorak

Ma cosa ti aspetti, che la gente ti scriva il codice al posto tuo ?

un piccolo aiuto magari con qualche schema con qualche parola in più su come usare gli alberi su come ordinare gli elementi all'interno.
Non ho scritto per avere la pappa pronta ma un aiuto tutto qua.Dai post precedenti non ho molto ben capito come implementare e che strutture dati utilizzare.Tutto qui non sono un fenomeno a programmare e lo ammetto senza ombra di dubbio quindi più roba riesco ad avere e più roba mi viene suggerita magari anche con esempi e meglio è per me programmare.

Anzi chiedo direttamente a te se magari con qualche schema o qualcosa mi riesci a dare un aiuto un input per poter poi partire a programmare il tutto.
Ho scritto un po ma sono abbastanza bloccato su come implementare le strutture dati su cui si appoggia l'intero progetto.Tipo che struttura uso per tener i tasselli che ho inserito e in che posizione?


So che il tempo delle persone è denaro e di certo si ha di meglio da fare che stare a pensare e scrivere e fare schemi per un progetto (anche abbastanza compicato....o sbaglio).

ringrazio in anticipo tutti per il tempo che dedicherete a questo post.

[banryu79]

Originariamente inviato da matteo.pata

Ho scritto un po ma sono abbastanza bloccato su come implementare le strutture dati su cui si appoggia l'intero progetto.Tipo che struttura uso per tener i tasselli che ho inserito e in che posizione?

Sono passati 10 gg dal tuo primo post, non credo che tu non abbia fatto proprio nulla: postaci quello che hai fatto fin'ora e i tuoi dubbi, così vediamo dove ti blocchi e ti possiamo dare una mano.

[goldorak]

Se hai problemi a capire le differenze tra le varie strutture dati e
gli appunti che hai preso a lezione non sono sufficienti, ti consiglio di andare in biblioteca
e prendere in prestito il Cormen Leiserson Rivest "Introduction to Algorithms" che e'
la bibbia per quello che riguarda le strutture dati. Tutto quello che vuoi sapere sugli alberi, grafi, heaps, etc...
e' tutto li' dentro. Un altro libro forse piu' facile da leggere e' Algorithms in C++ di Sedgewick.
Il CLR contiene pseudo codice per tantissime strutture, mentre quello di Sedgewick contiene molte spiegazioni,
alcuni frammenti di codice ma poi tocca a te metterci mano per renderlo qualcosa di usabile.
Quindi dal punto di vista didattico e' meglio il Cormen.

[banryu79]

Originariamente inviato da goldorak

Quindi dal punto di vista didattico e' meglio il Cormen.

Testo eccellente, ma dubito che potrà essere veramente di aiuto per il compito in esame all'utente, se non è già abbastanza pratico: una seria consultazione (oserei dire, di questo testo, che non lo si può consultare, lo si può solo studiare) richiederebbe un certo lasso di tempo.

Se invece "è pratico" (sa cosa cercare) può trovare rapidamente valide soluzioni.
Comunque è utile sapere che c'è.

[matteo.pata]

UP.
Che struttura dati potrei utilizzare per tener traccia dei tasselli inseriti.
Io ho pensato alberi BST ma con che chiave li ordino??

Grazie

[goldorak]

Originariamente inviato da matteo.pata

UP.
Che struttura dati potrei utilizzare per tener traccia dei tasselli inseriti.
Io ho pensato alberi BST ma con che chiave li ordino??

Grazie

Beh ogni posizione del mosaico avra' al piu' un tassello.
Non puoi avere due tasselli che si sovrappongono (nel senso che occupano la stessa identica posizione) quindi....
potresti usare la posizione in cui viene inserito il tassello come chiave di ricerca.