Progettazione di algoritmi a.a. 2012-2013

Progetto

Si richiede di scrivere un programma che a partire dalle tabelle orarie di una rete ferroviaria calcola i migliori percorsi da una stazione ad un'altra. Il programma deve leggere i dati di input da un file di testo di nome input.txt e scrivere i risultati in un altro file di testo di nome output.txt. Ogni stazione è identificata da un codice numerico (intero positivo) e anche ogni treno è identificato da un codice numerico (intero positivo). Una stazione può avere lo stesso codice di un treno. Questo non causa nessun problema perchè il formato dei dati permette sempre di distinguere se si tratta di stazione o treno.

La tabella oraria di una stazione riporta il codice S della stazione e un elenco di fermate. Ogni fermata specifica il codice T di un treno, l'orario di arrivo del treno T nella stazione S e l'orario di partenza del treno T dalla stazione S. Gli orari sono espressi in minuti dalla mezzanotte. Ad esempio, gli orari 9:00 e 23:59 sono espressi, rispettivamente, con i valori 540 e 1439. Quindi, un qualsiasi orario è espresso con un valore compreso tra 0 e 1439 (0 rappresenta la mezzanotte). Se la Fermata è relativa ad un treno che inizia il suo tragitto, l'orario di arrivo è per convenzione -1. Se invece è relativa ad un treno che termina il suo tragitto, l'orario di partenza è -1. Solamente se la Fermata è di passaggio entrambi i valori della fermata rappresentano orari. Si tenga presente che in questo caso l’orario di partenza è sempre successivo a quello di arrivo. Questo, però, non significa che il valore di arrivo sia sempre minore di quello di partenza. Ad esempio, il treno potrebbe arrivare in stazione alle 23:35, valore 1415, e ripartire alle 00:15, valore 15. È assicurato che ogni treno ha esattamente una fermata d'inizio e una fermata di fine. Si fanno inoltre le seguenti assunzioni: (1) il codice di un treno compare al più una sola volta in una tabella oraria; (2) l'intero tragitto di un treno ha una durata inferiore alle 24 ore. Queste assunzioni rendono possibile risalire al tragitto di un treno dai dati delle tabelle orarie. Per tragitto di un treno si intende la sequenza in ordine temporale di tutte le fermate fatte dal treno dalla fermata d'inizio a quella di fine.

In relazione a una rete ferroviaria specificata dalle tabelle orarie di un insieme di stazioni il programma deve rispondere a delle richieste di tre tipi. Il primo tipo è denominata MINTEMPO e chiede date due stazioni S1 e S2 (cioè i loro codici) di trovare, se esiste, un percorso di minimo tempo da S1 a S2. Il percorso può essere composto da tratte effettuate da più treni. Il secondo tipo è denominata MINORARIO e chiede date due stazioni S1 e S2 e un orario O di trovare, se esiste, un percorso da S1 a S2 che minimizza il tempo che passa tra l'orario O e quello di arrivo nella stazione di destinazione S2. Il terzo tipo, denominato MINCAMBI, chiede date due stazioni S1 e S2 di trovare, se esiste, un percorso da S1 a S2 che minimizza il numero di cambi di treno. Quest'ultimo tipo di richieste devono essere esaudite solamente da progetti consegnati da gruppi con 2 o 3 membri (vedere più avanti).

Il programma quando eseguito deve leggere il file input.txt e scrivere i risultati nel file output.txt, entrambi i file devono essere nella stessa directory in cui si trova l'eseguibile. Non deve fare nient'altro, in particolare non deve chiedere input o stampare alcunché.

Formato del file di input

Il file input.txt contiene i dati relativi a uno o più casi di test. Ogni caso di test comprende la specifica delle tabelle orarie e un elenco di richieste.

La prima linea del file contiene il numero N dei casi di test. Poi c'è la prima linea del primo caso di test. Ogni caso di test inizia con una linea contenente

TESTCASE K

dove K è il numero progressivo del caso di test a iniziare da 1. La seconda linea contiene il numero B di tabelle, poi per ogni tabella un gruppo di linee. La prima linea di ogni gruppo contiene il codice S della stazione e il numero F di fermate, poi F linee e in ognuna il codice treno T, l'orario di arrivo A e l'orario di partenza P (se è la fermata d'inizio del treno T, A è -1; se è la fermata di fine, P è -1). Quindi una linea che specifica una fermata ha il formato:

T A P

Dopo le linee che specificano le B tabelle c'è una linea contenente il numero R di richieste e poi R linee. Ognuna di queste può essere di uno dei seguenti tre tipi:

MINTEMPO S1 S2

MINORARIO S1 S2 O

MINCAMBI S1 S2

dove S1 e S2 sono codici di stazioni e O è un orario. Questo completa un caso di test.

Formato del file di output

Il file output.txt deve contenere per ogni caso di test del file input.txt le risposte alle richieste nell'ordine in cui appaiono nel file di input. Per ogni caso di test la prima linea deve contenere:

TESTCASE K

dove K è il numero del caso di test. Tutte le richieste chiedono di calcolare un percorso che minimizza qualche parametro. Un percorso è determinato da una sequenza di tratte. Una tratta è la parte del tragitto di un treno che va da una stazione alla stazione immediatamente successiva. È specificata da cinque numeri T, P, OP, A, OA, dove T è il codice di un treno, P è il codice di una stazione in cui il treno T si ferma e riparte nell'orario OP, A è il codice della prossima stazione in cui il treno T arriva in orario OA. Quindi una tratta è specificata da una linea con il formato:

T P OP A OA

La risposta ad ogni richiesta inizia con una linea che riporta la richiesta, poi delle linee che dipendono dal tipo di richiesta:

In tutti i casi se non c'è nessun percorso da S1 a S2, una singola linea con il valore -1. Le tratte di un percorso devono essere elencate nell'ordine temporale e quindi per ogni coppia di tratte consecutive: (1) la stazione di arrivo della prima tratta è la stessa di quella di partenza della seconda; (2) l'orario di arrivo della prima tratta deve precedere quello di partenza della seconda.

Esempi

Esempi di file di input e output: input.txt e il relativo output.txt

Si tenga presente che potrebbero esserci più percorsi ottimali relativamente a una data richiesta. Il programma deve restituire uno qualsiasi di questi.

Valutazione

Per la valutazione del progetto si terrà conto non solo della correttezza ma anche dell'efficienza in termini di memoria usata e di tempi di esecuzione. A questo proposito si fa presente che i dati delle tabelle orarie possono riguardare anche migliaia di stazioni e di treni e le tabelle orarie possono contenere anche centinaia di fermate (si pensi, ad esempio, alla rete ferroviaria europea).

Gruppi

Il progetto può essere consegnato da un gruppo di al massimo tre membri. Il progetto consegnato da un gruppo 2 o 3 membri deve rispondere anche alle richieste di tipo MINCAMBI, mentre un progetto presentato da un singolo membro non è obbligato a rispondere a tali tipi di richieste e le può ignorare.

Linguaggi e modalità di consegna

Il progetto può essere realizzato o in linguaggio C o in Java. Devono essere consegnati tutti i sorgenti e un file in testo semplice chiamato info.txt (o in pdf chiamato info.pdf). Quest'ultimo file deve contenere i nomi dei membri del gruppo che ha realizzato il progetto ed altre informazioni specificate di seguito.

I file sorgenti devono essere ben commentati. Il file info deve contenere una relazione scritta che spieghi le scelte effettuate: le strutture di dati e gli algoritmi usati. In particolare, dovrà essere specificato il contenuto di ogni file. La relazione deve anche contenere una discussione dell'efficienza dell'implementazione in funzione della dimensione dei dati forniti in ingresso (cioe, le tabelle orarie). Se si vogliono aggiungere i risultati di sperimentazioni questi sono, ovviamente, benvenuti.

La consegna del progetto deve avvenire in concomitanza con gli appelli della sessione estiva 2012-2013. Più precisamente, se si vuole fare la discussione orale del progetto in un dato appello è necessario consegnare il progetto entro una data prestabilita che precede di qualche giorno la data dello scritto dell'appello prescelto. Ecco l'elenco delle date entro le quali si può consegnare il progetto relativamente ad ogni appello:

Il progetto deve essere consegnato all'indirizzo:

X@gmail.com      (sostituire X con mp.progetti)