301 lines
10 KiB
Markdown
301 lines
10 KiB
Markdown
# brusegan_samuele_VETF04000T_secondaprova
|
||
|
||
Elaborato per la **Gara Nazionale di Informatica (GNI) 2026** — ITIS Pininfarina, Moncalieri (TO).
|
||
|
||
- Autore: **Brusegan Samuele**
|
||
- Codice meccanografico: `VETF04000T`
|
||
- Prova: **Seconda prova**
|
||
|
||
---
|
||
|
||
## Indice
|
||
|
||
1. [Traccia](#traccia)
|
||
2. [Modello del problema](#modello-del-problema)
|
||
3. [Algoritmo](#algoritmo)
|
||
4. [Struttura del progetto](#struttura-del-progetto)
|
||
5. [Requisiti](#requisiti)
|
||
6. [Build & Run](#build--run)
|
||
7. [Dataset](#dataset)
|
||
|
||
---
|
||
|
||
## Traccia
|
||
|
||
Il testo ufficiale della prova è un PDF di 5–6 pagine fornito dalla commissione GNI 2026 e **non è ancora incluso in questo repository**. Verrà aggiunto in `docs/traccia.pdf` appena disponibile.
|
||
|
||
### Sintesi inferita dal codice
|
||
|
||
Dato un insieme di **Punti di Interesse (POI)**, ciascuno caratterizzato da:
|
||
|
||
- un **nome**,
|
||
- un valore di **prestigio** (numero reale),
|
||
- un **tipo** (`0` = culturale, `1` = panoramico — convenzione inferita dal dataset),
|
||
|
||
va costruito un **itinerario turistico** che:
|
||
|
||
1. parte dall'ultimo POI del dataset, il **Castello di Moncalieri** (nodo fisso di partenza);
|
||
2. visita un sottoinsieme degli altri POI in un certo ordine;
|
||
3. massimizza il **prestigio totale** accumulato lungo il percorso.
|
||
|
||
Sul singolo passaggio fra due POI consecutivi viene applicato un **bonus di varietà**: se i due POI sono di tipo diverso (uno culturale e uno panoramico), il prestigio del POI di arrivo viene moltiplicato per un coefficiente `MULTIPLIER = 1.5`. Il primo POI del percorso contribuisce con il proprio prestigio "nudo".
|
||
|
||
Nel codice attuale sono fissati anche:
|
||
|
||
- `K = 4` — numero di nodi che vengono lasciati "fuori" dall'esplorazione ricorsiva sul fondo dello stack (vedi [Algoritmo](#algoritmo));
|
||
- partenza dal `Castello di Moncalieri`, che viene rimosso dalla lista e ri-aggiunto in coda a tutti i path generati.
|
||
|
||
> Quando avrò a disposizione il PDF della traccia, questa sezione verrà sostituita con il testo esatto e i vincoli ufficiali.
|
||
|
||
---
|
||
|
||
## Modello del problema
|
||
|
||
Il problema è modellabile come **ricerca della permutazione di massimo "prestigio"** su un insieme di nodi etichettati, con una funzione di costo che dipende dall'**ordine** (per via del bonus di tipo) — è quindi una variante di problema NP-hard sullo spazio delle permutazioni, risolto qui per via esatta sfruttando la dimensione contenuta dell'istanza (≤ 20 POI nei dataset forniti).
|
||
|
||
### Classi del dominio
|
||
|
||
- **`Node`** (`org.example.models.Node`)
|
||
POI immutabile. Campi: `name : String`, `prestigio : double`, `type : boolean` (true ↔ "panoramico"). Implementa `equals`/`hashCode` su tutti i campi: è quindi usabile come chiave/elemento di `HashSet` / `HashMap`, sfruttato per la memoization.
|
||
|
||
- **`Path`** (`org.example.models.Path`)
|
||
Sequenza ordinata di `Node` con il proprio `prestigioTotale` cumulato. Espone:
|
||
- `add(Node)` — append in coda, aggiorna il prestigio in O(1) usando l'ultimo nodo come "predecessore";
|
||
- `addAsFirstNode(Node)` — insert in testa, **ricalcola** il prestigio scorrendo tutto il path (perché cambia il vicino sinistro di ciò che prima era in testa) — O(n);
|
||
- `getPrestigio()` — getter del prestigio cumulato;
|
||
- copy-constructor `Path(Path other)` — usato per copie difensive nella cache.
|
||
|
||
- **`MainLogic`** (`org.example.models.MainLogic`)
|
||
Orchestratore: importa i dati, lancia la ricorsione, sceglie il path migliore. Espone anche `needBonus(Node s, Node e)` come predicato del bonus di varietà.
|
||
|
||
- **`Importer`** (`org.example.models.Importer`)
|
||
Lettore CSV "manuale" (split su `,`). Path hard-coded su `./src/main/resources/punti_interesse.csv`.
|
||
|
||
### Diagramma classi
|
||
|
||
```mermaid
|
||
classDiagram
|
||
class Node {
|
||
-String name
|
||
-double prestigio
|
||
-boolean type
|
||
+Node(String, double, boolean)
|
||
+Node(String, double, int)
|
||
+getType() boolean
|
||
+getPrestigio() double
|
||
+equals(Object) boolean
|
||
+hashCode() int
|
||
+toString() String
|
||
}
|
||
|
||
class Path {
|
||
-ArrayList~Node~ nodes
|
||
-double prestigioTotale
|
||
+Path()
|
||
+Path(Path other)
|
||
+add(Node) void
|
||
+addAsFirstNode(Node) void
|
||
+getPrestigio() double
|
||
-calculateDeltaPrestigio(Node, Node) double
|
||
-updatePrestigio() void
|
||
}
|
||
|
||
class MainLogic {
|
||
+double MULTIPLIER$
|
||
+int K$
|
||
+double LENGHT$
|
||
-HashMap~Set~Node~,List~Path~~ cache$
|
||
+main(String[])$ void
|
||
+importData()$ ArrayList~Node~
|
||
+getPaths(List~Node~)$ ArrayList~Path~
|
||
+needBonus(Node, Node)$ boolean
|
||
}
|
||
|
||
class Importer {
|
||
-String FILENAME_CSV_DATA$
|
||
+importData()$ ArrayList~Node~
|
||
}
|
||
|
||
class PathBuilder {
|
||
+run() void
|
||
}
|
||
<<Runnable>> PathBuilder
|
||
|
||
class App {
|
||
+start(Stage) void
|
||
+main(String[])$ void
|
||
}
|
||
|
||
class MainUI {
|
||
+start(Stage)$ void
|
||
}
|
||
|
||
class Controller
|
||
|
||
Path "1" o-- "*" Node : contiene
|
||
MainLogic ..> Importer : usa
|
||
MainLogic ..> Path : crea/elabora
|
||
MainLogic ..> Node : usa
|
||
Importer ..> Node : istanzia
|
||
App --> MainUI : avvia
|
||
MainUI ..> Controller : (previsto)
|
||
Controller ..> MainLogic : (previsto)
|
||
PathBuilder ..> MainLogic : (previsto)
|
||
```
|
||
|
||
---
|
||
|
||
## Algoritmo
|
||
|
||
### Idea
|
||
|
||
Enumerazione delle permutazioni della lista dei POI con due ottimizzazioni:
|
||
|
||
1. **Memoization** su sotto-istanze: due rami di ricorsione che arrivano allo stesso *insieme* (non sequenza!) di nodi rimanenti producono lo stesso insieme di sotto-path. La chiave della cache è quindi un `Set<Node>` e non una lista ordinata.
|
||
2. **Pruning sul fondo**: la ricorsione si ferma quando restano `K` nodi (con `K = 4`), restituendo un path vuoto. I `K` nodi residui non vengono permutati a quel livello — la logica completa di chi gestisce gli ultimi `K` nodi è parte dei [TODO](#todo) (vedi anche [Note di correttezza](#note-di-correttezza)).
|
||
|
||
Pseudocodice (vedi <ref_snippet file="/home/samuele/IdeaProjects/brusegan_samuele_VETF04000T_secondaprova/src/main/java/org/example/models/MainLogic.java" lines="46-83" />):
|
||
|
||
```
|
||
getPaths(nl):
|
||
key = set(nl)
|
||
if key in cache:
|
||
return deep_copy(cache[key])
|
||
|
||
if |nl| == LENGHT - K - 1:
|
||
return [ Path() ] # caso base
|
||
|
||
result = []
|
||
for n in nl:
|
||
sub = getPaths(nl \ {n}) # ricorsione su lista priva di n
|
||
for p in sub: p.addAsFirstNode(n) # n diventa la testa
|
||
result += sub
|
||
|
||
cache[key] = deep_copy(result) # copia difensiva
|
||
return result
|
||
```
|
||
|
||
`main()` poi:
|
||
|
||
```
|
||
nl = importData()
|
||
moncalieri = nl.removeLast()
|
||
paths = getPaths(nl)
|
||
for p in paths: p.add(moncalieri) # Moncalieri in coda a tutti i path
|
||
best = argmax(paths, key = p.getPrestigio())
|
||
```
|
||
|
||
### Funzione obiettivo
|
||
|
||
Per un path `p = [n₁, n₂, …, nₖ]`:
|
||
|
||
```
|
||
prestigio(p) = prestigio(n₁)
|
||
+ Σ_{i=2..k} ( needBonus(n_{i-1}, n_i)
|
||
? MULTIPLIER · prestigio(n_i)
|
||
: prestigio(n_i) )
|
||
```
|
||
|
||
dove `needBonus(a, b) ↔ a.type ≠ b.type` e `MULTIPLIER = 1.5`.
|
||
|
||
### Complessità
|
||
|
||
- Senza memoization: `O(n!)` in tempo, `O(n)` in spazio di stack.
|
||
- Con memoization su `Set<Node>`: gli stati distinti sono `2^n`, ma per ciascuno serve costruire `O(n)` path → spazio `O(n · 2^n)`, tempo dominato da costruzione e copia delle liste. Con `n ≤ ~20` resta tranquillamente gestibile.
|
||
- `addAsFirstNode` è `O(n)` per via dell'aggiornamento del prestigio: il costo per path è quindi `O(n²)`.
|
||
|
||
### Note di correttezza
|
||
|
||
- La cache **deve** restituire copie difensive perché i chiamanti mutano i path tramite `addAsFirstNode` / `add`. Vedi <ref_snippet file="/home/samuele/IdeaProjects/brusegan_samuele_VETF04000T_secondaprova/src/main/java/org/example/models/MainLogic.java" lines="51-58" /> e <ref_snippet file="/home/samuele/IdeaProjects/brusegan_samuele_VETF04000T_secondaprova/src/main/java/org/example/models/MainLogic.java" lines="76-79" />.
|
||
- Il caso base `|nl| == LENGHT - K - 1` taglia gli ultimi `K` livelli di ricorsione restituendo path vuoti: occorre verificare che questo sia il comportamento voluto dalla traccia (probabilmente la traccia richiede esattamente un percorso lungo `K+1` nodi, partenza inclusa). Da chiarire/refinire una volta letto il PDF.
|
||
|
||
---
|
||
|
||
## Struttura del progetto
|
||
|
||
```
|
||
.
|
||
├── pom.xml
|
||
├── nbactions.xml
|
||
├── src/
|
||
│ └── main/
|
||
│ ├── java/
|
||
│ │ ├── module-info.java
|
||
│ │ └── org/example/
|
||
│ │ ├── App.java # entry point JavaFX
|
||
│ │ ├── SystemInfo.java
|
||
│ │ ├── controller/
|
||
│ │ │ └── Controller.java # stub
|
||
│ │ ├── models/
|
||
│ │ │ ├── Importer.java # parser CSV
|
||
│ │ │ ├── Node.java
|
||
│ │ │ ├── Path.java
|
||
│ │ │ ├── PathBuilder.java # stub Runnable
|
||
│ │ │ └── MainLogic.java # ricorsione + cache + main CLI
|
||
│ │ └── views/
|
||
│ │ └── MainUI.java # stub UI
|
||
│ └── resources/
|
||
│ ├── punti_interesse.csv # dataset principale (14 POI)
|
||
│ └── punti_interesse_b.csv # dataset secondario (20 POI)
|
||
└── target/
|
||
```
|
||
|
||
---
|
||
|
||
## Requisiti
|
||
|
||
- **JDK 25** (vedi `<release>25</release>` nel `pom.xml`)
|
||
- **Maven 3.9+** (incluso wrapper `.mvn/`)
|
||
- **JavaFX 21.0.2** — risolto da Maven via `org.openjfx:javafx-controls`
|
||
|
||
---
|
||
|
||
## Build & Run
|
||
|
||
### Compilazione
|
||
|
||
```bash
|
||
./mvnw clean compile
|
||
```
|
||
|
||
### Esecuzione della logica (CLI)
|
||
|
||
Per ora il `main` di `MainLogic` stampa direttamente il miglior path su stdout:
|
||
|
||
```bash
|
||
./mvnw exec:java -Dexec.mainClass="org.example.models.MainLogic"
|
||
```
|
||
|
||
oppure, da IDE, eseguire la classe `org.example.models.MainLogic`.
|
||
|
||
### Esecuzione dell'app JavaFX (stub)
|
||
|
||
```bash
|
||
./mvnw javafx:run
|
||
```
|
||
|
||
Apre una finestra placeholder.
|
||
|
||
> Nota: l'`Importer` usa un path **relativo** (`./src/main/resources/punti_interesse.csv`), quindi va lanciato dalla root del progetto.
|
||
|
||
---
|
||
|
||
## Dataset
|
||
|
||
Due file CSV in `src/main/resources/`, stesso schema (senza header):
|
||
|
||
```
|
||
<nome>,<prestigio>,<tipo>
|
||
```
|
||
|
||
- `<nome>`: stringa libera (no virgole)
|
||
- `<prestigio>`: numero (parsato come `double`)
|
||
- `<tipo>`: `0` (culturale) o `1` (panoramico)
|
||
|
||
L'**ultima riga** è sempre il punto di partenza (`Castello di Moncalieri`).
|
||
|
||
| File | Righe |
|
||
|---|---|
|
||
| `punti_interesse.csv` | 14 |
|
||
| `punti_interesse_b.csv` | 20 |
|