Advent of Code 2019 – Day 2

I due problemi del Day 2 proposti da Eric Wastl su Advent of Code cominciano ad essere veramente impegnativi.

Per risolverli ho utilizzato diversi strumenti messi a disposizione da FreeBASIC:

Il codice sorgente relativo alle due soluzioni è disponibile su GitHub:

Attenzione però!

L’algoritmo utilizzato per scrivere il codice contenuto nel file sorgente 02b.bas contiene una parte che lo rende altamente inefficiente.

Lascio a voi trovarla. 😉

Quando progettiamo i nostri algoritmi non dobbiamo mai dimenticarci di curare la fase di ottimizzazione.

Ed ora… Day 03!

Advent of Code 2019 – Day 1

Il testo completo in inglese lo trovate qui.

Puzzle n.1

In questo primo puzzle Eric, l’ideatore di Advent of Code, ci chiede di calcolare la quantità di carburante necessario per lanciare nello spazio dei moduli spaziali.

Il puzzle è molto semplice: ci viene detto che per calcolare la quantità di carburante per ciascun modulo occorre basarsi sulla sua massa e applicare questa formula:

Dividi la massa per 3, approssima il risultato per difetto e quindi sottrai il valore 2.

I valori delle masse dei moduli ci vengono forniti sotto forma di lista numerica.

Definizione dell’algoritmo

In questo caso i passi del nostro algoritmo sono praticamente già descritti in chiaro nel testo:

  1. Leggi il valore della massa (m) del primo modulo.
  2. Applica la formula data per ricavare la quantità di carburante necessario (f) per il lancio di un singolo modulo.
  3. Somma tutti i valori ottenuti per ottenere il totale del carburante (f_tot) necessario per tutti i moduli.

Scrittura del codice

Prima di iniziare a scrivere il codice, salviamo la lista delle masse in un file di testo che nomineremo input.txt e che salveremo per semplicità nella stessa cartella dove andremo a salvare il nostro file sorgente che possiamo nominare per esempio 01a.bas.

''nome file: 01a.bas

dim m as string ''variabile per la lettura della massa
dim as integer f, f_tot ''variabili per il carburante

''reset variabili
m = ""
f = 0
f_tot = 0

''apertura del file
open "input.txt" for input as #1

  line input #1, m ''lettura della prima massa

  ''ciclo per la lettura di tutte le masse e
  ''calcolo del carburante necessario
  do until m = ""
    f = int(val(m) / 3) - 2 ''carburante per un modulo
    f_tot = f_tot + f ''carburante totale
    line input #1, m ''lettura di un'altra massa
  loop

''stampa il risultato del puzzle n.1
print "Totale carburante necessario = "; f_tot

close #1 ''chiusura del file

Ovviamente questo è soltanto un esempio di possibile risoluzione: potremmo infatti decidere di creare un array per memorizzare tutti i valori delle masse, oppure potremmo creare una funzione ad hoc per il calcolo del carburante necessario.

Insomma, nella programmazione esistono sempre più modi di risolvere un problema. E questa è proprio una delle cose che la rendono così interessante.

Puzzle n.2

Il secondo puzzle del Day 1 comincia ad essere un po’ più impegnativo.

Eric ci fa notare che anche il carburante di un modulo è a sua volta una massa, e quindi anche questa massa per essere lanciata nello spazio ha bisogno di carburante. Ma, attenzione! Anche il carburante necessario per la massa del carburante è a sua volta una massa…

Insomma, lo avete capito, qui bisogna escogitare un algoritmo iterativo un po’ più raffinato.

Come tutte le iterazioni, anche questa deve avere una fine, altrimenti sono guai. Nel testo del puzzle n.2 ci viene detto che, applicando la stessa formula che abbiamo visto per il puzzle n.1, una volta che otteniamo una quantità di carburante negativa, allora dobbiamo fermarci.

Definizione dell’algoritmo

L’idea è quella di utilizzare un altro ciclo do-loop all’interno del ciclo principale che itera le masse dei moduli.

In questo nuovo clico interno il valore del carburante necessario dovrà rientrare come input alla formula di calcolo. Nella condizione di controllo del ciclo andremo quindi a verificare per ogni iterazione che il carburante necessario non sia negativo. Infine la variabile del carburante necessario al carburante dovrà incrementarsi soltanto se i valori del carburante calcolato sono positivi.

Scrittura del codice

Riprandendo il codice del puzzle n.1, andiamo ad aggiungere, nella parte dedicata alla dichiarazione delle variabili, una nuova variabile che conterrà la somma del carburante necessario al carburante.

dim as integer f, f_tot, f_tot2 ''variabili per il carburante

Poi andremo ad inserire all’interno del primo ciclo un secondo ciclo dedicato proprio al calcolo del carburante necessario al carburante.

  do until m = ""
    f = int(val(m) / 3) - 2 ''carburante per un modulo
    f_tot = f_tot + f ''carburante totale

    ''puzzle n.2
    do until f <= 0
      f = int(f / 3) - 2
      if f > 0 then f_tot2 = f_tot2 + f
    loop

    line input #1, m ''lettura di un'altra massa
  loop

Ed infine possiamo inserire una riga per la stampa del risultato.

''stampa il risultato del puzzle n.1
print "Puzzle n.1 - Totale carburante necessario = "; f_tot

''stampa il risultato del puzzle n.2
print "Puzzle n.2 - Totale carburante necessario = "; f_tot + f_tot2

Bene. Il Day 1 è fatto! 🙂

Il problema delle tre monete

Cominciamo la nostra avventura nel mondo degli algoritmi con questo primo problema che potete trovare a pagina 13 del testo Il pensiero computazionale – Dagli algoritmi al coding di Paolo Ferragina e Fabrizio Luccio.

Tra tre monete di identico aspetto una potrebbe essere falsa e di peso differente. Disponendo di una bilancia a due piatti per confrontare le monete tra loro si vuole individuare la moneta falsa se c’è, e in questo caso stabilire se pesa più o meno delle altre, mediante non più di due pesate.

Prima di partire a testa bassa immaginando un ipotetico algoritmo o, peggio ancora, cominciando a scrivere direttamente del codice, fermiamoci e leggiamo lentamente, più volte, e con molta attenzione l’enunciato del problema.

Cerchiamo quindi di individuare e ordinare le informazioni essenziali che rappresenteranno i nostri dati.

Poi sforziamoci di capire cosa ci viene chiesto, in modo tale da essere in grado di formulare con precisione le giuste domande a cui dovremo cercare di dare risposta con il nostro algoritmo tradotto in codice FreeBASIC.

Le giuste domande ci guidano nella definizione del nostro obiettivo.

Raccolta delle informazioni essenziali (dati)

Suddividiamo e ordiniamo le informazioni in punti:

  • «tre monete di identico aspetto»;
  • «una potrebbe essere falsa e di peso differente»;
  • «bilancia a due piatti per confrontare le monete»;
  • «non più di due pesate».

Una volta raccolte le informazioni essenziali che, come già detto, non sono altro che i dati su cui potremo operare, analizziamo i nostri punti.

Il primo, il terzo e il quarto non sembrano presentare ambiguità. Concentriamoci quindi sul secondo punto. Questo punto, se letto in maniera poco attenta, potrebbe crearci dei problemi nel momento in cui inizieremo a progettare l’algoritmo risolutivo: il testo, infatti, riferendosi alle monete ci dice che «una potrebbe essere falsa».

Stiamo bene attenti…

Cosa ci dice questa frase?

Che ci sono delle monete false?

No!

La frase semplicemente asserisce due cose:

  1. la prima è che non ci possono essere più monete false;
  2. la seconda è che potrebbero anche non essercene.

Quindi i casi sono soltanto due:

  1. o c’è una moneta falsa;
  2. oppure non ci sono monete false.

Il secondo punto rappresenta quindi una informazione chiave per la definizione del nostro obiettivo.

Dobbiamo quindi stare sempre attenti non soltanto a ciò che di esplicito ci dicono le informazioni in nostro possesso, ma anche a ciò che ci viene suggerito in modo implicito. Molto spesso sono proprio le informazioni implicite a sfuggirci con più facilità.

Ecco allora che è bene seguire questa regola:

È bene trasformare sempre le informazioni implicite in esplicite.

Proviamo quindi a farlo con il nostro secondo punto:

  • frase implicita: «una potrebbe essere falsa e di peso differente»;
  • frase esplicita: se esiste una moneta tra le tre date che ha un peso differente dalle altre due che per definizione devono avere in questo caso pari peso, allora questa è falsa.

Definizione precisa delle domande (obiettivo)

Torniamo all’enunciato del problema per cercare di scoprire qual è il nostro obiettivo: ovvero a quali domande dobbiamo rispondere.

Ecco le frasi che ci interessano:

  • «individuare la moneta falsa se c’è»;
  • «in questo caso stabilire se pesa più o meno delle altre».

Che possiamo tradurre in queste due domande:

  1. Esiste una moneta falsa?
  2. Se esiste, pesa di più o di meno delle altre due?

Progettazione di un algoritmo risolutivo (pensiero computazionale)

Bene, ora che abbiamo raccolto i dati e definito le domande a cui dobbiamo rispondere, proviamo ad immaginare il cuore del nostro algoritmo procedendo per passi.

  • la prima cosa da fare che dovrebbe venirci in mente è quella di identificare in qualche modo le nostre tre monete per poterle riconoscere senza ambiguità: diamo quindi i nomi di prima, seconda e terza moneta;
  • a questo punto possiamo procedere con la prima pesata (#1) tra la prima e la seconda moneta;
  • da questa prima operazione potremo ricavare esclusivamente due possibili soluzioni:
    1. le due monete hanno lo stesso peso;
    2. le due monete hanno peso differente.
  • a questo punto procediamo con la seconda pesata (#2) tra la prima moneta e la terza moneta;
  • ovviamente anche da questa operazione non potremo che ottenere le due possibili soluzioni che abbiamo visto in precedenza, ovvero:
    1. le due monete hanno lo stesso peso;
    2. le due monete hanno peso differente.

E adesso viene il bello: che ce ne facciamo con questi risultati?

Proviamo a spremere le meningi…

Tabella associativa

La cosa migliore da fare sembra essere quella di costruire una Tabella associativa che metta in relazione tutti i possibili risultati delle due pesate ottenendo quindi le diverse soluzioni possibili:

'Tabella associativa risultati pesate/soluzioni possibili
'             pesata #2
'  pesata #1 |  1  |  2
'      1     |  A  |  B
'      2     |  C  |  D

Analizziamo ora il significato delle soluzioni:

  • A: pesata #1 risultato 1, pesata #2 risultato 1 → la moneta falsa non esiste
  • B: pesata #1 risultato 1, pesata #2 risultato 2 → la terza moneta è falsa
  • C: pesata #1 risultato 2, pesata #2 risultato 1 → la seconda moneta è falsa
  • D: pesata #1 risultato 2, pesata #2 risultato 2 → la prima moneta è falsa

Se siamo abbastanza confidenti – ancora non possiamo infatti dirci sicuri al 100% – che il nostro algoritmo funzioni, allora possiamo a ragion veduta cominciare a scrivere il nostro codice sorgente. Farlo prima ci avrebbe fatto perdere soltanto del tempo. Provare per credere. 😉

Scrittura del codice (coding)

Bene. Riprendiamo in mano il nostro algoritmo e cominciamo a scrivere:

'identificazione delle monete attraverso la loro dichiarazione
dim as integer m1, m2, m3

'definisci il caso di test assegnando
'i pesi delle monete
input "quanto pesa la prima moneta"; m1
input "quanto pesa la seconda moneta"; m2
input "quanto pesa la terza moneta"; m3

'verifica correttezza specifica
if m1 <> m2 and m1 <> m3 and m2 <> m3 then
  print "Attenzione! Non stai rispettando la"
  print "specifica che prevede che al massimo"
  print "ci possa essere una sola moneta falsa"
  print "con peso differente."
  end 'esci dal programma
end if

'pesata #1 tra la prima e la seconda moneta
if m1 = m2 then
  'procediamo con la seconda pesata
  if m1 = m3 then
    'Soluzione A
    print "la moneta falsa non esiste"
  elseif m1 < m3 then
    'Soluzione B
    print "la terza moneta è falsa e pesa di più"
  else 'm1 > m3
    'Soluzione B
    print "la terza moneta è falsa e pesa di meno"
  end if
elseif m1 < m2 then
  'procediamo con la seconda pesata
  if m1 = m3 then
    'Soluzione C
    print "la seconda moneta è falsa e pesa di più"
  else 'm1 < m3
    'Soluzione D
    print "la prima moneta è falsa e pesa di meno"
  end if
else 'm1 > m2
  'procediamo con la seconda pesata
  if m1 = m3 then
    'Soluzione C
    print "la seconda moneta è falsa e pesa di meno"
  else 'm1 > m3
    'Soluzione D
    print "la prima moneta è falsa e pesa di più"
  end if
end if

Rivediamo più volte il codice prima di compilarlo. Se la compilazione dovesse fallire leggiamo bene il tipo di errore che il compilatore FreeBASIC ci segnala e operiamo le opportune correzioni al codice. Una volta che la compilazione ha successo possiamo finalmente eseguire il nostro codice e passare alla fase di collaudo del software.

Test

Per collaudare il nostro software dobbiamo testare tutte le diverse combinazioni dei risultati delle due pesate (caso di test) e confrontare quindi i risultati (i nostri print a video) con le possibili soluzioni (oracolo).

Per fare questo non dobbiamo inventarci nulla, ma semplicemente riprendere la nostra Tabella associativa e giocare con i pesi rispettando le specifiche date: ovvero stando attenti a non inserire pesi diversi per tutte e tre le monete.

Potete testare il codice anche su JDoodle cliccando qui.

Buon divertimento e a presto. 😉

Introduzione al pensiero computazionale

Comincia con questo primo articolo una nuova categoria del blog dedicata al pensiero computazionale.

Il pensiero computazionale è un processo mentale per la creazione di un algoritmo, ovvero di una sequenza finita di passi elementari (istruzioni), traducibili poi in un linguaggio di programmazione (codice sorgente) in grado di permettere ad un computer di risolvere un problema.

Gli articoli che andranno a comporre questa categoria prenderanno spunto dal testo Il pensiero computazionale – Dagli algoritmi al coding di Paolo Ferragina e Fabrizio Luccio.

Cercheremo quindi di risolvere alcuni problemi proposti nel libro per sviluppare le nostre capacità creative nella elaborazione degli algoritmi che poi andremo a tradurre in codice FreeBASIC.

Inoltre proveremo anche a risolvere i rompicapo proposti su Advent of Code. Le soluzioni potrete trovarle su GitHub, sia sullo spazio di JJFlash che sul mio.

Per testare il codice offline direttamente sulla propria macchina si rimanda all’articolo  FreeBASIC – esecuzione.

Per chi invece preferisce lavorare online, lo stesso codice verrà comunque messo a disposizione su JDoodle.