Laboratorio di Algoritmi e Strutture Dati
Marco Tarini
“New New New York”
Consegna Progetto: entro Dom 26 sett 2010 - ore 24.00
Il problema
New New New York `e la citt`a pi`u popolata nell’anno 3500 D.C. (costruita sulle ceneri di New New York). A NNNY si costruiscono grattacieli quasi ogni giorno. I grattacieli non sono fatti per durare in eterno. Gi`a al momento della costruzione `e nota la data della demolizione, talvolta vicinissima a quella di costruzione.
Ogni grattacielo al momento della costruzione viene battezzato con un nome (univoco). Qualche volta, si decide di ristrutturare un grattacielo gi`a esistente e si proroga la data della sua demolizione.
New New New York si affaccia sul mare: la sua spiaggia si estende da Nord a Sud. Se la si osserva dal mare, di notte, sopra alla spiaggia appare un tipico skyline (la linea di confine fra cielo e grattacieli).
Infatti, ogni metro di spiaggia (ad una certa latitudine) `e sovrastato da un certo numero di grattacieli a longitudini diverse (talvolta uno o nessuno). Chiaramente, `e sempre il pi`u alto di questi a svettare sugli altri, e la sua altezza definisce l’altezza dello skyline su quel metro di spiaggia. In assenza di palazzi, lo skyline `e alto zero.
Il problema consiste nel registrare, un certo numero di volte durante la serie di costruzioni e abbattimenti, quante altre volte lo skyline si `e presentato esattamente nella stessa forma in passato (per fini turistici e storici).
Dati in input
L’input consiste in una serie di righe. Nella prima riga compare un numero, che corrisponde alla lunghezza totale della spiaggia in metri (per esempio, se vale 5, la spiaggia comincia nel punto 0 e si estende fino al punto 5).
Ciascuna riga successiva descrive un evento quotidiano, oppure una query. Ogni giorno avviene soltanto un evento. Un evento pu`o corrispondere alla costruzione di un nuovo palazzo, oppure alla ristrutturazione di un palazzo gi`a esistente (con conseguente procrastinamento della sua demolizione), oppure ancora al semplice passaggio di una giornata (evento vuoto). Costruzioni e ristrutturazioni avvengono sempre nel primo mattino. La sera, quando `e necessario, uno (o anche pi`u) palazzi (arrivati alla fine della loro vita) possono essere abbattuti. Se nella riga successiva all’evento compare una query, allora il programma deve rispondere ad una domanda relativa alla notte successiva all’ultimo evento trascorso.
• Le righe che descrivono una query consistono nel solo carattere “punto interrogativo”. Nel leggere questa riga, il programma dovr`a stampare a schermo il numero di notti precedenti nelle quasi lo skyline si `e presentato identico a quello della notte corrente . Ad esempio, se durante la notte relativa alla richiesta siamo in presenza di uno skyline inedito, si dovr`a stampare il numero 0. Se lo skyline `e identico a quello della notte di una settimana prima (ma diverso da quello di tutte le altre notti) si dovr`a stampare il numero 1.
1
• Gli eventi di tipo costruzione cominciano con la stringa “new” (senza le virgolette), seguita dal nome del palazzo costruito, seguito da una tripletta di misure del grattacielo, seguito dalla durata prevista, cio`e dal numero di giorni che il grattacielo deve durare prima di essere abbattuto. Le tre misure rappresentano, rispettivamente: da quale metro di spiaggia comincia e a quale metro finisce il grattacielo, e la sua altezza, in centimetri. Si tratta di tre numeri naturali. Ad esempio, se com- paiono i numeri 4 6 1000, significa che il grattacielo si estende nell’intervallo che comincia a 4 metri esatti, finisce al sesto metro (sar`a dunque lungo due metri), ed `e alto 1000 centimetri (10 metri). La durata `e espressa in giorni, ed e’ un numero naturale strettamente maggiore di 0 che rappresenta il numero di giornate che devono trascorrere prima dell’abbattimento (salvo rimandi). Il grattacielo viene abbattuto la sera della sua ultima giornata, prima della notte successiva. Quindi, ad esempio, se la durata valesse 1, il grattacielo verrebbe abbattuto ancor prima della notte successiva.
• Gli eventi di tipo ristrutturazione cominciano con la stringa “renew” (senza le virgolette), seguita dal nome del palazzo in questione, seguito dal numero di giorni di durata ulteriore da attribuire al grattacielo.
• Gli eventi vuoti consistono nella lettera “v” (senza le virgolette).
La serie di righe `e terminata da una riga composta da un solo punto esclamativo, che segnala la fine del problema.
L’input viene fornito al programma sotto forma di file di testo, il cui nome viene specificato dal primo argomento passato al programma. Se non ne viene specificato alcuno, l’input deve venir letto direttamente dallo stdin.
Altri vincoli
E’ richiesto che programma funzioni in modalit`a “on-line”: cio`e l’input pu`o essere letto una sola volta, e, nel leggere una richiesta, la risposta deve essere stampata sul video senza che sia necessario leggere nessuna delle righe successive. Insomma il programma deve funzionare anche se ipoteticamente l’input fosse fornito solo una riga alla volta, e se le risposte fossero necessarie prima di fornire la riga successiva.
La correttezza `e un requisito necessario. Un progetto sar`a considerato pi`u o meno valido rispetto all’ef- ficienza (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).
Esempi
Facciamo ad esempio il seguente caso di file di input.
15
new aaa 7 10 2500 3 new bbb 5 10 1500 100
?
new ccc 7 9 2500 100 new ddd 9 10 2500 100
?
!
Il primo giorno viene costruito aaa, e il secondo bbb.
2
Al momento della la prima query, la seconda notte, saranno presenti entrambi i grattacieli aaa e bbb. Dal metro 7 al metro 10 (dunque per tre metri) avremo uno skyline alto esattamente 25 metri (l’altezza del palazzo aaa). Dal metro 5 al 7, alto 15 (per il palazzo bbb, che in effetti prosegue anche fino al metro 10, ma dal metro 7 al 10 la sua silhouette viene coperta da quella di aaa). Visto che questa configurazione non ha avuto precedenti, alla query si risponder`a con uno 0.
La mattina del terzo giorno viene costruito ccc. Alla sera dello stesso giorno, aaa viene abbattuto. Il quarto giorno viene costruito ddd. Al momento della seconda query, cioe la quarta notte, lo skyline `e lo stesso della seconda notte (pur essendo in piedi un numero diverso di palazzi). Dunque alla query si risponder`a con un 1.
So noti che e’ alla seconda query si sarebbe dovuto rispondere nello stesso modo anche se la prima query non fosse stata effettuata. Infatti, conta il numero di notti, indipendentemente dal numero di queries.
Dimensioni e natura delle tipiche istanze del problema
E’ difficile prevedere la configurazione di New New New York in un tempo cosi’ remoto nel futuro. I grattacieli potrebbero anche essere essere molto numerosi. Tuttavia, la lunghezza della spiaggia diffi- cilmente potr`a cambiare, dato che si parla di tempi non certo geologici. Nelle istanze del problema, le spiagge saranno sempre relativamente poco estese, dell’ordine di alcune centinaia di metri al massimo.
Nessuna ipotesi pu`o invece essere fatta sull’altezza media dei grattacieli del futuro. Potrebbero misurare anche migliaia di metri! Non si sa molto neanche circa lo stile architettonico del futuro. Ad esempio, non si sa i grattacieli saranno o meno alti un numero intero di metri, o di piani, etc.
Le durate previste dei grattacieli possono essere anch’esse molto variabili. In alcune istanze del problema, alcuni grattacieli potrebbero avere una durata prevista di anche solo di pochi giorni, ma non e’ da escludere che alcuni grattacieli adottino delle tecnologie che consentano durate molto superiori (o chiss`a forse quasi indefinite! Millenni?).
I nomi dei grattacieli non sono mai scelti pi`u lunghi di qualche centinaio di caratteri, e contengono solo lettere (mai numeri o spazi).
Nel sito del corso sono presenti alcuni esempi di istanza di problema, che non esauriscono tutta la casistica qui descritta. Molte altre istanze sono infatti possibili. Progetti che risolvano correttamente un numero maggiore di istanze saranno ritenuti maggiormente validi. Si pu`o sempre assumere, comunque, che il file di input del problema sia conforme alle specifiche.
Suggerimenti
1. Per leggere l’input e scrivere l’output si possono usare le funzioni standard ANSI C fscanf() e fprintf().
2. Domanda-trucchetto: `e possibile, secondo il candidato, che gli algoritmi e le strutture dati insegnati durante il corso non abbiano alcuna 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 pu`o far risparmiare giornate di implementazione fuori rotta.
3
Cosa, come, quando consengare
Occorre presentare, oltre al codice sorgente, una sintetica relazione (formato pdf o ps) che illustri le strutture dati utilizzate e analizzi il costo della propria soluzione.
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.
Note sul Codice
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. Puo’ consistere in un solo file sorgente .c oppure in un piccolo insieme di files .c e .h.
Il codice deve essere ben documentato: per esempio, laddove non sia immediatamente chiaro dal contesto, ogni funzione deve essere preceduta da una breve descrizione del suo scopo, del significato dei suoi parametri, etc.
Note sulla Relazione
La relazione deve essere sintetica, ma deve descrivere le strutture dati adoperate, e quali algoritmi noti sono stati utilizzati su di esse (per risolvere quale sottoproblema). Si pu`o includere una breve analisi della complessit`a delle principali sottofunzioni implementate, ma e’ importante includere una stima asintotica della complessit`a totale (spaziale e temporale) della soluzione proposta (ricordandosi anche di specificare cosa si intende con gli argomenti delle funzioni).
La relazione non deve invece includere una ripetizione della descrizione del problema. A cosa servirebbe?
Modalit` a di consegna
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 con un mio messaggio. Per favore, il soggetto della mail includa la stringa “algo2009f”.
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.
I progetti che non hanno ricevuto un mio messaggio di conferma non saranno considerati validi.
Discussione
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.
Per ogni ulteriore chiarimento, e-mail: marco.tarini@isti.cnr.it
4
