Progetto 2025/26

Questa pagina descrive il progetto per il corso di Informatica della Laurea in Matematica per gli appelli dell'anno accademico 2025/2026.

Esercizio: un labirinto da esplorare

Descrizione generale

L'esercizio consiste nel determinare l'esito di un'esplorazione in un labirinto da parte di un gruppo di avventurieri.

In questo labirinto, gli avventurieri si muovono in stanze collegate tra loro e rappresentate come celle di una griglia bidimensionale.

Data una griglia rettangolare N x M che rappresenta la mappa del labirinto in cui gli avventurieri si muovono e data una sequenza di mosse, vogliamo calcolare se, partendo dalla cella (0, 0), gli avventurieri riescono a raggiungere la cella contenente l'uscita del labirinto.

Le coordinate delle celle/stanze seguono le stesse convenzioni delle matrici, e con gli indici che partono da 0. In altre parole, la stanza (0, 0) è quella in alto a sinistra, ha sotto di lei la stanza (1, 0), mentre ha alla sua destra la stanza (0, 1), e così via. In generale, una stanza ha coordinate (numRiga, numColonna).

La sequenza di mosse contiene zero o più delle seguenti mosse, che modificano la posizione degli avventurieri (in modo relativo alla posizione corrente) come segue:

• A: spostamento verso l'alto (riga -1, colonna =)
• B: spostamento verso il basso (riga +1, colonna =)
• S: spostamento verso sinistra (riga =, colonna -1)
• D: spostamento verso destra (riga =, colonna +1)

Quando entrano in una stanza, gli avventurieri possono opzionalmente trovare ostacoli o aiuti. Più precisamente, una stanza può essere di uno dei seguenti tipi:

• '_': la stanza è vuota.
• 'P': la stanza contiene una pozione, che gli avventurieri bevono immediatamente all'ingresso. Questa pozione garantisce a loro l'immunità dalle bombe per le successive tre mosse. La pozione viene consumata al primo uso: se gli avventurieri nel loro percorso rientrano nella stessa stanza, la trovano vuota.
• 'b': la stanza contiene una bomba. La bomba esplode uccidendo gli avventurieri, a meno che non siano immuni grazie alla pozione. La bomba viene consumata nell'esplosione: se gli avventurieri sopravvivono alla bomba e dopo nel loro percorso rientrano nella stessa stanza, la trovano vuota.
• 'I': la stanza è quella iniziale. Solo la stanza di coordinate (0, 0) è di questo tipo. Non ha nessun effetto particolare, come le stanze vuote.
• 'U': la stanza contiene l'uscita dal labirinto. Gli avventurieri hanno avuto successo nella loro esplorazione.

Se si bevono più pozioni, l'immunità delle pozioni non si accumula. Più precisamente, se si beve una pozione mentre si è ancora immuni a causa di un'altra pozione bevuta precedentemente, l'immunità dura comunque solo per le tre mosse successive. In altre parole, ai fini dell'immunità, conta solo l'ultima pozione bevuta.

Esempio di immunità

Data una sequenza di mosse che esplora le celle |P|_|_|b| da sinistra a destra, gli avventurieri possono proseguire lungo il percorso senza subire danni, in quanto la bomba esplode durante il periodo di immunità.
Data invece una sequenza di mosse sulle celle |P|_|_|_|b|, gli avventurieri perderanno l'immunità prima di calpestare la bomba, e l'esplorazione terminerà con il fallimento.
Infine, data una sequenza di mosse sulle celle |P|_|_|P|_|_|b|, gli avventurieri potranno proseguire senza subire danni, in quanto la seconda pozione resetta l'immunità a tre mosse.

Risultato dell'esplorazione e punteggio

Gli avventurieri possono fallire la loro esplorazione per i seguenti motivi.

• Il percorso non raggiunge mai l'uscita.
• Una bomba esplode mentre non sono immuni.
• Il loro percorso li porta fuori dalla mappa (coordinate fuori dalle dimensioni della matrice mappa).

In caso di fallimento, definiamo il punteggio dell'esplorazione come -1000000 (meno un milione).

In caso di successo, invece, il punteggio dell'esplorazione viene calcolato come

    punti = (numero di mosse) + 3 * (numero di pozioni bevute) - 2 * (numero di bombe esplose)

Esempi

Mosse generate: DBBSDSABDDBSDBBDDDSDDDBDBDDDB
Lunghezza mosse: 29
Risultato atteso: FALLIMENTO (uscita non raggiunta)
Punteggio = -1000000 punti

Mosse generate: BDDSDBDSDABSBABDBDBB
Lunghezza mosse: 20
Risultato atteso: FALLIMENTO (per una bomba)
Punteggio = -1000000 punti

Mosse generate: BBDDBBDDABDDDABDDBDSADDSDDDDDDDDDD
Lunghezza mosse: 34
Risultato atteso: VITTORIA
Punteggio = 34+ 3 * 2 (pozioni) - 2 * 2 (bombe) = 36 punti

Implementazione in Java

Dati in input e funzione richiesta

Per poter determinare il risultato dell'esplorazione, si ricevono in input i seguenti dati:

• char[][] mappa: una matrice di caratteri che rappresenta la mappa del labirinto. I caratteri sono quelli elencati sopra come tipi di stanze ('_', 'P', eccetera).
• String mosse: una stringa contenente la sequenza di mosse. Le mosse sono rappresentate come descritto sopra (ABSD).

Il programma Java che dovete sviluppare dovrà contenere una funzione

   public static int percorriLabirinto(char[][] mappa, String percorso)

che calcola il punteggio totale ottenuto dagli avventurieri seguendo la sequenza di mosse passata come parametro.

Se vi serve, all'interno di questa funzione potete modificare la matrice mappa durante il calcolo del punteggio. In ogni caso, il punteggio calcolato deve essere quello riferito al valore iniziale della mappa.

Consigli

Si consiglia di usare una variabile int immunita per tenere traccia della durata dell'immunità dovuta all'effetto della pozione.

Si ricorda che in Java le matrici si accedono con mappa[riga][colonna], come si fa di solito per le matrici. In questo esercizio si segue questa convenzione.
Questo è diverso da usare coordinate cartesiane, che invece richiederebbe l'uso di mappa[x][y] dove x indica la colonna, e y la riga, quindi invertendo i due indici. Fate attenzione a non invertirli per errore.
Inoltre, a indice di riga maggiore nelle matrici si scende verso il basso, mentre in coordinate cartesiane una y maggiore indica un punto più in alto.

Come scrivere il progetto

Per sviluppare il codice, è obbligatorio creare un progetto Eclipse senza module-info.java e senza package, che contiene una classe Progetto, seguendo lo scheletro di codice che vi forniamo:

• scheletro

La classe scheletro va posizionata in un progetto Eclipse come segue. Create un progetto Eclipse chiamato cognome_matricola (usate i vostri dati, per esempio tramaglino_000001 o de_paperoni_000002), e create la classe Progetto al suo interno nella cartella src. Dovete ottenere un file come segue:

• zunino_555555/src/Progetto.java

È obbligatorio rispettare la posizione del file della classe come descritto sopra. Dentro quel file potete quindi inserire il codice dello scheletro fornito.

È tassativamente proibito modificare lo scheletro nelle parti segnate al suo interno come da non modificare. In particolare, non si può modificare il tipo o il nome delle procedure / funzioni già presenti all'interno. In nessun caso il file consegnato dovrà contenere una dichiarazione package.

È invece consentito (e consigliabile) definire delle procedure/funzioni addizionali all'interno della classe Progetto. È consentito aggiungere import per usare librerie di Java. È in ogni caso vietato usare funzioni di libreria (incluse in Java o esterne) che rendano banale lo svolgimento del compito.

È consentito modificare il metodo main della classe nello scheletro. Si noti, tuttavia, che tale metodo potrà essere cancellato e sovrascritto, o comunque non eseguito, da chi corregge. Di conseguenza, se si decidono di usare variabili globali, queste devono essere inizializzate dentro la funzione percorriLabirinto(), e non dentro il main, in quanto quest'ultimo non verrà eseguito.

Noi testeremo la funzione percorriLabirinto() su vari input, chiamandola ripetutamente anche in modo automatizzato, e senza eseguire il main() della vostra classe Progetto.

Un aiuto per testare il vostro codice

Per aiutarvi nel testare il vostro codice, vi mettiamo a disposizione una piccola libreria helper.

• helper versione 1.1
• tiles versione 1.0 (opzionale)

Dopo avere scaricato il file helper di sopra in una qualunque cartella, potete inserire la libreria helper nel vostro progetto Eclipse, selezionando il vostro progetto, facendo clic destro, e selezionando dal menù la voce Build Path -> Add External Archives.... Comparirà una finestra dove potete selezionare il file jar fornito sopra.

Dopo avere aggiunto la libreria Helper al vostro progetto, all'interno del file Java Progetto.java potete usare le funzioni della libreria, che mostriamo sotto. Nello scheletro di progetto che vi forniamo, trovate già degli esempi su come usarle nel main(), dopo avere usato import helper2025.Helper; e import helper2025.TestCase; (come fa già lo scheletro di codice fornito).

Lo scheletro di codice fornito usa già la libreria Helper per testare il vostro codice. Nel caso voi vogliate fare modifiche ai test, qui sotto descriviamo le funzioni principali fornite dall'Helper.

La classe Helper fornisce le seguenti funzioni:

• TestCase generaTest()
  Genera un labirinto casuale di dimensione (N x M), minimo 5x5, e una sequenza di mosse anch'esse casuali. Restituisce un record TestCase che contiene: la mappa del labirinto, la sequenza di mosse.
• public void stampaLabirinto(char[][] mappa)
  Data in input la mappa del labirinto, la stampa in console in formato ASCII. Questo può essere utile per visualizzare il labirinto generato dalla funzione generaTest() in fase di debug. Rimuovere/commentare per velocizzare l'esecuzione dei test.
• void setSeed(long seed)
  Imposta il seed del generatore di numeri casuali. Impostare il seed a un numero prefissato fa sì che chiamare ripetutamente le funzioni genera...() descritte precedentemente generi deterministicamente sempre gli stessi valori. Non è necessario usare questa funzione, ma può essere comoda durante il debugging per potere ripetere esattamente gli stessi test.
• public boolean testSoluzione(int punti, TestCase test)
  Controlla che i punti calcolati dalla vostra funzione controllaMosse() corrispondano al risultato atteso dal TestCase generato. Restituisce true se la soluzione è corretta, false altrimenti.

La classe TestCase fornisce le funzioni necessarie a leggere la mappa, le mosse e verificare le soluzioni ed è definita come segue:

• public char[][] getMappa() Restituisce una copia della mappa del labirinto generata. Attenzione: ogni volta che si chiama questa funzione viene restituita una copia della mappa, non un riferimento alla mappa interna. Si consiglia di chiamarla una sola volta e salvare il risultato in una variabile locale.
• String getMosse() Restituisce la sequenza di mosse generata.

Le seguenti funzioni sono totalmente opzionali e servono solo per creare un'immagine PNG a colori del labirinto:

• public void inizializzaTiles(String tilesPath, int tileSize)
  Inizializza le immagini dei vari tipi di stanza del labirinto. tilesPath è il percorso della cartella che contiene le immagini PNG (fornite nella cartella png/tiles/ scaricabile da qui), mentre tileSize è la dimensione in pixel di ciascuna immagine (32x32).
• public void generaImmagineLabirinto(char[][] griglia, String outputPath)
  Crea un'immagine PNG del labirinto rappresentato dalla matrice di caratteri griglia, e la salva nel percorso specificato da outputPath. Attenzione! Questa funzione richiede che prima sia stata chiamata la funzione inizializzaTiles(). La funzione crea file sul disco, quindi è consigliabile utilizzarla solo quando i test case sono meno di 20-30, per evitare di creare troppi files.

Se lo desiderate, potete organizzarvi tra di voi e scambiarvi ulteriori test e relativi risultati. Potete usare il forum Moodle del corso per coordinarvi, o qualunque altro mezzo a vostra disposizione.

Requisiti e criteri di valutazione

Il progetto verrà valutato secondo i seguenti criteri, che descrivono un insieme di requisiti sul codice consegnato. Ogni requisito primario deve essere rispettato rigidamente: in caso di violazione, anche minima, di uno di questi requisiti la prova d'esame non è superata. I requisiti secondari devono essere generalmente rispettati. Violazioni minori saranno tollerate, ma violazioni gravi possono comunque causare il non superamento della prova.

Requisiti tecnici (primario). La soluzione consegnata deve seguire lo scheletro di progetto fornito sopra, modificato nel modo descritto sopra.

Devono inoltre essere rispettati questi requisiti:

1. Non modificate il nome della classe Progetto, i nomi o i tipi delle procedure/funzioni segnate come da non modificare. Non ci deve essere nessuna dichiarazione di package della classe. Non ci deve essere nessun module-info.java.
2. Posizionate la classe Progetto come descritto sopra nel vostro progetto Eclipse.
3. Le procedure/funzioni richieste non devono interagire con l'utente in nessun modo (ad es., chiedere di inserire dati da tastiera). I nostri test devono potere chiamare ripetutamente quelle funzioni in modo automatico, senza il nostro intervento manuale. Il main invece può interagire con l'utente, se desiderato (ma comunque come detto sopra il codice del main può essere ignorato da noi durante i test.)

Il non rispettare questi requisiti tecnici può causare il fallimento dei nostri test automatizzati, ed in tal caso la prova non sarà superata.

Correttezza (primario). Non ci devono essere errori a tempo di compilazione: il programma deve compilare. Non ci devono essere errori a tempo di esecuzione: il programma non deve generare eccezioni (per esempio, DivisionByZero oppure ArrayIndexOutOfBounds) quando eseguito su un input ben formato.

Il programma deve dare l'output desiderato su qualunque input compatibile con la specifica.

Nota bene: Nel caso il programma sia scorretto, non è compito di chi corregge fare il debugging, ovvero identificare la causa dell'errore e suggerire una modifica per rimuoverla. Anche quando tale causa fosse nota a chi corregge, non verrà comunicata allo studente, in quanto sarebbe come suggerire una parte non banale della soluzione della prova. Infatti, capita frequentemente che correggere l'errore dopo averlo individuato diventi banale ("devo usare x, e non x+1"), e che la prova di conseguenza consista prevalentemente nella ricerca dell'errore.
Corollario: se provando il programma su un insieme di input campione si riscontrano già errori di correttezza, chi corregge non è tenuto ad esaminare il codice del programma.

Leggibilità (secondario). Il codice deve essere scritto in modo tale da permettere ad un altro programmatore di comprenderne la logica. Non è sufficiente che il codice "funzioni", o che sia chiaro a chi lo ha scritto. Per aiutare la lettura del codice da parte di altri, si consiglia di usare dei nomi di variabile e di funzione appropriati, strutturare il codice adeguatamente (dove ha senso, meglio dividere una funzione lunga in più funzioni ausiliarie), e di inserire dei commenti se ritenuto utile.

Non commentate come state calcolando qualcosa, commentate piuttosto cosa state calcolando. Per esempio, il seguente commento è altamente inutile:

	// incremento i
	i++;

Al contrario, il seguente aiuta a comprendere il codice:

	// passo a coordinate polari
	rho = Math.sqrt(x*x + y*y);
	theta = Math.atan2(y, x);

Efficienza in tempo (secondario). Il vostro programma deve svolgere il suo compito in tempi ragionevoli. Noi dobbiamo essere in grado di svolgere agevolmente i nostri test chiamando la funzione percorriLabirinto() molte volte su input diversi.

Se il vostro programma è così lento da impedirci di eseguire tutti i test nel tempo di pochi minuti, riterremo tutti i test falliti.

Efficienza in spazio (secondario). Il vostro programma deve usare una quantità ragionevole di memoria. Noi dobbiamo essere in grado di svolgere i test senza avere problemi di memoria. In caso contrario riterremo i test falliti.

Si richiede più precisamente di non allocare memoria non davvero richiesta. Non allocate vettori o matrici di dimensioni prefissate a un valore "grande", ma regolate la loro dimensione secondo i valori dati in input.

Consegna del progetto

Per potere partecipare allo scritto di un appello di esame, il progetto deve essere consegnato entro le date indicate nell'elenco degli appelli d'esame. La consegna si svolge su Moodle, in modo simile a quanto fatto per il tutorato.

• Per ogni appello d'esame, su Moodle potrete consegnare il vostro progetto. Le scadenze per la consegna sono riportate sulla pagina principale del corso. Quando consegnate, Moodle verifica che la consegna venga fatta entro la scadenza, e impedisce la consegna se in ritardo.
• Per consegnare dovere preparare un singolo file in formato ".zip", che deve avere nome "cognome_matricola.zip" (per esempio, "zunino_555555.zip"). Altri formati (come rar o tar.gz) saranno rifiutati da Moodle.
• L'archivio ".zip" allegato deve contenere una sola cartella, chiamata "cognome_matricola" (secondo i vostri dati), il cui contenuto segue quanto detto sopra per lo scheletro di progetto. Se sentite il bisogno di aggiungere delle note per chi corregge, potete opzionalmente aggiungere nella stessa cartella un file di testo "README.txt". Per esempio, un file ".zip" del progetto potrebbe contenere i seguenti file:
  • zunino_555555/src/Progetto.java
  • zunino_555555/README.txt
  Se sono presenti anche altri file all'interno dello zip non è un problema, ma preferibilmente includete nello zip solo i file davvero richiesti. Per sicurezza, controllate di non consegnare uno zip vuoto o con solo file irrilevanti.

Procedure anti plagio

Il progetto non viene svolto in un ambiente "controllato" come per esempio avviene per un esame scritto, ma vi viene lasciata libertà di svolgerlo dove e quando preferite (compatibilmente con le scadenze). Per esempio, potete usare i laboratori quando liberi, o farlo su un vostro computer personale.

Il progetto è individuale, non di gruppo. Tuttavia, vi è consentito discutere del progetto con altre persone per scambiarsi opinioni a riguardo. Non è consentita, ovviamente, la copia di pezzi di codice inerenti al progetto da uno studente all'altro. Allo stesso modo, farsi fare il progetto da un'altra persona (o da strumenti software di qualunque tipo) è considerato equivalente a copiare.

Verranno usati dei software anti plagio per confrontare le diverse consegne anche in appelli distinti. Ci riserviamo la possibilità di convocarvi per un colloquio sul codice che avete consegnato, anche dopo l'esame scritto, sia nel caso ci siano dubbi sull'autenticità del progetto o per effettuare verifiche a campione.

In caso di plagio, manifesto o accertato, verranno presi provvedimenti, che potranno anche andare oltre il semplice annullamento della prova d'esame.

Si sottolinea che non è solo vietato copiare il codice da altri, ma anche condividere il proprio progetto con altri, anche dopo che l'esame è stato superato e verbalizzato. Anche dopo la verbalizzazione potranno essere presi provvedimenti.

Vi è consentito di "copiare" pezzi di codice che vi abbiamo fornito noi, o di "tradurre in Java" dei pezzi di codice che potreste trovare su qualche libro o tutorial online, e che non siano soluzioni degli esercizi proposti o di una loro parte significativa. Nei casi consentiti dovete obbligatoriamente citare la fonte in un commento nel codice.

Il discutere del progetto su forum di discussione su Internet o simili non è vietato a prescindere, ma è soggetto alle stesse regole della comunicazione tra altri studenti. Inoltre, se iniziate una discussione su un forum riguardo al progetto, dovete obbligatoriamente dichiarare 1) che l'esercizio in questione è un progetto di esame, e 2) che non desiderate che qualcuno vi scriva una soluzione al posto vostro. Se anche chiarendo ciò qualcuno vi risponde includendo del codice, voi non potete includerlo nel progetto.

Note Finali

Se ci sono parti del testo del progetto che ritenete non chiare, vi invitiamo a fare domande usando il forum che trovate su Moodle, in modo che tutti gli studenti possano leggere le nostre risposte.

Se preferite, potete usare anche caratteristiche di Java non viste a lezione (costrutti diversi come gli oggetti, librerie non viste a lezione purché incluse tra quelle standard di Java), anche se il progetto si può svolgere benissimo senza. Dovete però comprendere il codice che state usando: se venite chiamati ad un colloquio (vedi sopra) vi può essere chiesto di spiegarlo.

Informatica - Teaching - Home

Roberto Zunino, 2025