[Note (per gli studenti meno avvertiti):
 1) i testi fra parentesi quadre sono note esplicative che non fanno parte dello schema di relazione;
 2) i testi fuori dalle parentesi quadre costituiscono uno SCHEMA, non una relazione. ]

TRACCIA DI RELAZIONE DEL PROGETTO "OTHELLO"

CAPITOLO 1: IL PROBLEMA

Riassunto della descrizione nel file PDF
[I FORMATI DI INGRESSO E USCITA SONO OVVI DETTAGLI INFORMATICI, DA NON RIPORTARE]


CAPITOLO 2: L'algoritmo [riflette la progettazione top-down]

Il problema si puo' decomporre in:
1 Costruisce la configurazione iniziale della scacchiera:
  dettagli utili (2 pedine N e 2 pedine B al centro)
2 Esegue le mosse indicate nel file:
  dettagli utili (scorre il file e per ogni mossa valuta se e' lecita,
                  e in caso positivo la esegue; altrimenti segnala l'errore e termina)
3 Stampa la scacchiera finale:
  dettagli utili (stampa anche una riga e una colonna aggiuntive
                  con gli indici delle colonne e righe)
4 Stampa l'esito del gioco:
  dettagli utili (stampa il numero di caselle nere e bianche e il vincitore)

La scacchiera e' una matrice di char quadrata statica, ecc... perche':
- spazio minimo strettamente necessario
- lettura e scrittura in tempo costante

  Sezione 2.1: configurazione iniziale:

  - Ripulisce l'intera scacchiera
  - Inserire nelle posizioni centrali due pedine nere e due bianche

  Quindi [AGGIUNGERE LE SPIEGAZIONI] il costo e' T \in O(n^2) e S \in O(n^2)
  dove n e' il numero di righe e colonne della scacchiera
  [A rigore, n e' costante, ma l'analisi diventerebbe banale, quindi lo considero variabile]


  Sezione 2.2: esecuzione e controllo delle mosse

  - Definisce il giocatore che muove per primo
    [Apre il file delle mosse: QUESTO E' UN OVVIO DETTAGLIO INFORMATICO, DA NON RIPORTARE]
  - Finche' ci sono mosse da valutare nel file
    * Se e' una mossa, valuta se e' lecita: se lo e', la esegue; altrimenti, segnala l'errore e termina
      (vedi Sezione 2.2.1)
    * Se e' una sospensione, valuta se e' lecita: se non lo e', segnala l'errore e termina
      (vedi Sezione 2.2.2)
  - Passa la mano all'altro giocatore
    [Chiude il file delle mosse: QUESTO E' UN OVVIO DETTAGLIO INFORMATICO, DA NON RIPORTARE]


  Sezione 2.2.1: valuta ed esegue una mossa

  - Estrae gli indici di riga e colonna della mossa
  - Verifica se la mossa e' lecita, cioe':
    * la casella non e' occupata
      Allora, per ogni direzione possibile
        Le direzioni sono rappresentate da vettori [dr,dc] con dr,dc in {-1,0,1} escludendo [0,0]
      valuta ed esegue la mossa nella direzione corrente
      Se nessuna direzione e' lecita, segnala l'errore e termina
      Altrimenti, posiziona la pedina nuova nella casella

  Quindi [AGGIUNGERE LE SPIEGAZIONI] il costo e' T \in O(1) piu' 8 cicli di EsegueDirezione
  che e' O(n), dunque O(n); S \in O(n^2) perche' usa la scacchiera

  Sezione 2.2.2: valuta una sospensione

  - Per ogni cella libera della scacchiera
    per ogni direzione, EsegueDirezione, la quale...

  Quindi [AGGIUNGERE LE SPIEGAZIONI] il costo e' S = O(n^2) per la scacchiera
  T deriva dallo scorrere n^2 celle, 8 direzioni e chiamare EsegueDirezione, che costa O(n)
  Quindi T \in O(n^3)


Riassumendo il costo [Sez 2] e':
  S \in O(n^2) per la scacchiera
  T deriva dall'eseguire per ogni mossa EsegueMossa o VerificaSospensione,
  quindi T \in O(m max(O(n),O(n^3)) = O(mn^3) dove m sono le mosse piu' le sospensioni.
  Oppure T \in O(m O(n) + s O(n^3)) = O(mn+sn^3) dove m sono le mosse e s le sospensioni


Sezione 2.3: stampa della scacchiera

  - Stampa la riga 0 con gli indici delle colonne
  - Stampa la scacchiera con la colonna 0 (indici delle righe)

  Quindi [AGGIUNGERE LE SPIEGAZIONI] il costo e' S \in O(n^2) per la scacchiera
  T \in O(n^2) per lo scorrimento delle celle della scacchiera nella stampa


Sezione 2.4: stampa dell'esito

  - Conta le pedine bianche e nere
  - Stampa il numero di pedine bianche e nere e l'esito della partita

  Quindi [AGGIUNGERE LE SPIEGAZIONI] il costo e' S \in O(n^2) per la scacchiera
  T \in O(n^2) per lo scorrimento delle celle della scacchiera nel conteggio
  [SI POTREBBE CONSERVARE IL NUMERO E AGGIORNARLO VIA VIA]

[LE SEZIONI 2.3 E 2.4 POTREBBERO ESSERE RACCOLTE PER EVITARE SEZIONI INUTILMENTE CORTE]

Costo complessivo:
S \in O(n^2)
T \in O(n^2+mn+sn^3)