Laboratorio di Algoritmi e Strutture Dati
Marco Tarini
“Fiat Lux”
Consegna Progetto: entro Dom 20 Giu 2010 - ore 24.00
Il problema
Come noto, per creare un nuovo mondo a partire dal caos primordiale, bisogna innanzitutto dividere la terra dalle acque. In questo progetto si fa proprio questo. Il mondo appena creato viene poi diviso in habitat al fine di essere popolato.
Divisione terra/acqua
Il caos primordiale `e costitutito da una griglia N × N di caselle. Ad ogni casella `e associato un valore di Vitalit`a Primordiale (numeri interi, cio`e positivi o anche negativi). Ogni casella `e adiacente ad altre 8 (2 in verticale, 2 in orizzontale, e 4 in diagonale – chiaramente le caselle di bordo sono adiacenti solo ad altre 5 caselle, e le quattro caselle di spigolo solo ad altre 3). Ogni coppia di caselle adiacenti possono essere direttamente connesse, oppure possono essere reciprocamente separate da una apposita barriera.
Inizialmente tutte le coppie di caselle adiacenti sono separate da una barriera. La creazione del mondo consiste nella rimozione progressiva di queste barriere, una ad una. Notare che le barriere che separano coppie di caselle in diagonale sono indipendenti fra loro: date 4 caselle adiacenti
AB CD
la rimozione della barriera fra A e D non implica (n`e impedisce) quella della barriera fra B e C.
Due caselle sono dette comunicanti se `e possible raggiungere la prima dalla seconda attraverso una sequenza di caselle ciascuna direttamente connessa alla successiva.
Dai quattro angoli del caos primordiale viene immessa di continuo acqua e terra (in effetti, sabbia), che da qui si espande in tutte le caselle comunicanti. Dall’angolo Nord-Ovest e da quello diametralmente opposto viene immessa acqua; dagli altri due, terra. In ogni momento, una casella pu`o essere gi`a riempita o da terra o da acqua, proveniente da uno dei quattro angoli, oppure pu`o essere ancora vuota. Inizialmente, solo i quattro angoli sono riempiti (da acqua o terra).
Come noto acqua e terra vanno separate! Una barriera non viene mai tolta se ci`o causasse un mesco- lamento di acqua e terra. Cioe’ non viene mai rimossa una barriera che separa due caselle attualmente invase rispettivamente da acqua e da terra. Di tutte le altre barriere, viene rimossa ogni volta quella che separa le due caselle adiacenti la cui vitalit`a sommata sia maggiore. In caso di pareggio, si rimuova la barriera che connette la casella pi`u settentrionale, e in caso di ulteriore pareggio, quella pi`u ad oriente.
Nota: la rimozione di una barriera non implica sempre un travaso di acqua o sabbia in una zona non ancora occupata. Pu`o succedere ad esempio che si rimuovano barriere fra zone ancora senza ancora n`e acqua n`e sabbia, oppure fra zone entrambe gi`a occupate da acqua, etc.
La crazione del mondo termina quando sono rimaste solo barriere necessarie a separare acqua da terra.
Nota: a questo punto, ogni casella sar`a necessariamente riempita di acqua oppure di sabbia.
Inoltre, l’acqua immessa da Nord e quella immessa da Sud sono diverse per salinit`a, composizione chimica, etc, e distinguibili; lo stesso vale per la sabbia. Alla termine della creazione del mondo, pu`o succedere
1
che l’acqua immessa dai due angoli opposti si sia miscelata, oppure che sia rimasta separata da barriere, e lo stesso per la sabbia: quando una casella di acqua (o sabbia) `e cumunicante con entrambe le fonti di acqua (o sabbia), queste si amalgano e si ottine acqua (o sabbia) “mista”, distinguibile da ciascuna delle due originali “pure”.
Suddivisione in Habitat
Una volta separate terra e acqua, il passaggio successivo `e il popolamento con animali e piante. Genie diverse (ancora senza nome) vengono create per habitat diversi. Al fine di creare in serie esseri viventi nelle giuste quantit`a, bisogner`a misurare quanto sono diffusi ciascuno dei diversi habitat che si sono formati (oceani, coste, fiordi, pianure, etc).
Ogni casella ha infatti un habitat, definito dal pezzetto di mondo 7 × 7 centrato intorno a quella casella.
Ogni configurazione diversa corrisponde ad un habitat diverso. Dunque due caselle, a qualunque distanza, hanno lo stesso habitat, se sono entrambe invase della stessa acqua (o sabbia), e se sono circondate dalla stessa configurazione di terra e acqua (distinguendole inoltre fra mista e pura, e, se pura, per origine). In altre parole due caselle hanno lo stesso habitat se e solo se i loro due intorni corrispondono esattamente nel contenuto, casella per casella, orientamento compreso. In altre parole ancora, un animale che viva in una casella non avrebbe modo di distinguere quella casella da altre caselle con lo stesso habitat guardandosi intorno entro tre caselle in ogni direzione, nemmeno con l’ausilio di una bussola.
Caselle vicine al bordo (o sul bordo) sono circondate da meno caselle di mondo: il loro habitat avr`a dunque alcune caselle mancanti. Questi habitat “di bordo” possono essere identici solo ad habitat dello stesso tipo.
Lo scopo di questa fase `e determinare, per ogni casella di mondo, quante altre caselle condividano lo stesso identico habitat.
Il progetto
Il progetto dovr`a prendere da riga di comando il nome di un file in Input da leggere. Dovr`a scrivere in risposta una coppia di file di testo, come specificato.
Dati in Input
Il file di input e’ un file di testo in ASCII cos`ı formattato: inizialmente, compare il numero di righe (che `e anche quello di colonne) che compone il Caos Primordiale. Poi, di fila, il valore di Vitalit`a Primordiale di ciascuna casella, riga per riga, a partire dall’angolo a Nord-Ovest (finendo dunque nell’angolo a Sud-Est).
Output 1/2: divisione terra e acqua
La divisione finale fra terra e acqua deve essere scritta in un file di testo ASCII, con lo stesso nome del file di input, ma terminato dal postfisso “ b.ppm”. La prima riga deve contenere i caratteri P3 (una lettera P e il numero 3, attaccati). La seconda riga di testo deve contenere il numero di righe del mondo, ripetuto due volte (altezza e larghezza della griglia dunque), seguito dal valore 7 (questi tre numeri vanno separati da spazi).
Dalla terza riga in poi deve comparire una serie di numeri separati da spazi, tre per casella, che specificano se quella casella `e invasa da acqua, da terra, e, in entrambi i casi, se l’acqua o la terra provengono dalla fonte nell’angolo a Nord o a Sud (o se si tratta di commistioni).
2
Si faccia riferimento alla seguente tabella:
Semantica: Tripletta:
Acqua “pura” da fonte a N-O 2 0 5 Acqua “pura” da fonte a S-E 0 2 5 Acqua miscelata 1 1 5 Sabbia “pura” da fonte a N-E 2 5 0 Sabbia “pura” da fonte a S-O 0 5 2 Sabbia miscelata 1 5 1
L’ordine delle caselle `e lo stesso di quello del file in input: dalla riga pi`u a Nord a quella pi`u a Sud, e, in ogni riga, dalla casella pi`u a Ovest a quella pi`u a Est. Si possono aggiungere liberamente caratteri di spazio, accapo o tabulazione fra i numeri o le triplette.
Output 2/2: separazione e conteggio habitat
Anche in questo caso, deve essere prodotto un file di testo ASCII, con lo stesso nome del file di input, ma aggiunto dell’estensione “ a.ppm”. La prima riga deve contenere i caratteri P2. La seconda riga `e identica a quella del primo file prodotto.
Dalla terza riga in poi deve comparire una serie di numeri separati da spazi, uno per casella, nello stesso ordine descritto sopra. Per ogni casella, deve comparire il numero 0 se l’habitat di quella casella compare pi`u di altre 7 volte, altrimenti il numero (7 − i), se l’habitat di quella casella compare identico altre i volte nella scacchiera (caselle che hanno un habitat unico nella mappa appaino dunque col numero 7).
Altri vincoli
Il progetto deve risolvere i problemi dell’ordine di quelli forniti (vedi sotto) in tempi nell’ordine di una decina di secondi al massimo.
Esempi di istanze del problema
In una griglia 3 × 3 come la seguente:
6 1 7
2 20 4
5 3 8
La prima barriera ad essere abbattuta `e quella fra 20 e 8. Come conseguenza, la casella di valore 20 si riempie di acqua proveniente dall’angolo Sud-Est. La seconda barriera a saltare sarebbe quella fra 20 e 7, ma questo causerebbe un miscelamento di acqua e terra. Quindi viene invece rimossa la barriera fra 20 e 6: l’acqua proveniente da Sud-Est e quella proveniente da Nord-Ovest si miscelano. Dopo tutte le rimozioni, la situazione finale vede tutte le caselle riempite di acqua mista, meno i due angoli di valore 7 e 5, che saranno rimasti di sabbia “pura” del rispettivo tipo.
In una griglia cos`ı piccola ogni casella ha un habitat reso diverso dalle condizioni di bordo (ad es, la casella di valore 6 `e l’unica con prosecuzioni di mondo a E, S e SE).
Altri esempi di varia grandezza sono disponibili nella pagina del corso. Se le specifiche vengono rispettate, i file in uscita possono essere visualizzati come immagini da viewer standard (in ambiente windows, per esempio, il programma Free “FastStone-Image Viewer”). I vari tipi di terra e acqua vengono visualizzati come tonalit`a diverse di verde e azzurro. La rarit`a dei vari habitat viene visualizzata con toni di grigio dal
3
nero (molto comune) al bianco (molto raro). Il risulato corretto del probelma input17.txt pu`o essere confrontato con la coppia di immagini presenti nella pagina del corso.
Suggerimenti
1. Per leggere l’input e scrivere l’output si possono usare le funzioni standard ANSI C fscanf() e fprintf().
2. Domanda: `e possibile, secondo il candidato, che gli algoritmi e le strutture dati imparate durante il corso non abbiano nessuna relazione col progetto assegnato?
3. SEMPRE: pensare bene sulla carta prima di cominciare a scrivere codice! Il problema potrebbe essere riformulato in modi pi`u semplici. Strutture dati adeguate vanno identificate correttamente.
Mezz’ora in pi`u di ragionamento possono far risparmiare giornate di implementazione fuori rotta.
Presentazione del progetto
Il progetto va implementato in C (si faccia riferimento allo standard ANSI). Vi `e piena libert`a sulla scelta dell’ambiente di sviluppo, ma il codice deve poter essere compilato con gcc e funzionare correttamente se eseguito da linea di comando.
L’elaborato deve essere inviato per posta elettronica all’indirizzo marco.tarini@isti.cnr.it entro e non oltre la data indicata. L’avvenuta ricezione del progetto sar`a confermata da un mio messaggio. Per favore, il soggetto della mail includa la stringa “algo2009d”.
I progetti che non hanno ricevuto un mio messaggio di conferma non saranno considerati validi.
Occorre presentare, oltre al il codice sorgente, una sintetica relazione (formato pdf o ps) che illustri le strutture dati utilizzate e analizza il costo delle diverse operazioni richieste dalla specifica.
Tutti i file spediti dal sorgente devono chiamarsi col proprio nome e cognome, per es ‘francorossi’. Solo l’estensione cambia: ‘.c’ per il file sorgente, se unico, ‘.zip’ se il progetto comprende pi`u di un file sorgente (e allora tale zip conterr`a solo alcuni file ‘.h’ ‘.c’), ‘.pdf’ o ‘.ps’ per la relazione.
Non inviare file eseguibili, neanche in cartelle compattate.
Il progetto deve essere discusso nella sessione di consegna. Si ricorda di presentarsi alla prova orale con una copia stampata della relazione e del codice.
La versione aggiornata del progetto `e pubblicata sul sito del corso (cercare la mia pagina con google – “Marco Tarini”, seguire “teaching” in fondo, seguire “lab di algoritmi 2009/2010”). Si consiglia di consultare periodicamente il sito per eventuali correzioni e/o precisazioni relative al testo del progetto.
La realizzazione del progetto `e una prova d’esame da svolgersi individualmente. Progetti che saranno ritenuti semplici varianti uno dell’altro non verranno corretti, a prescindere di quale sia stato l’originale e quale la copia derivata.
Per ogni ulteriore chiarimento, e-mail: marco.tarini@isti.cnr.it
4
