Tag: Advent of Code 2019

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:

Più sotto il codice relativo alle due soluzioni.

File 02a.bas

''programma: Quiz 1 del Day 2 di Advent of Code 2019
''autore:    ciuco informatico
''data:      12 dicembre 2019
''web:       https://ciucoinformatico.home.blog/

dim as integer array() ''array vuoto
dim as integer position
dim as integer value

position = 0
value = 0

''lettura del file e creazione del contenitore indicizzato (array)
open "02_input.txt" for input as #1

  do until eof(1)
  
    input #1, value ''lettura di un singolo valore
    redim preserve array (0 to position) ''ridimensionamento array
    array(position) = value

    position += 1

  loop

close #1

''restore the gravity assist program
array(1) = 12
array(2) = 2

''intcode program
position = 0
do

  value = array(position)
  
  select case value

    case 1 ''somma
      
      array(array(position +3)) = array(array(position + 1)) + array(array(position + 2))
    
    case 2 ''moltiplica
    
      array(array(position +3)) = array(array(position + 1)) * array(array(position + 2))
      
    case 99 ''esce dal programma intcode
      exit do
      
    case else ''caso non previsto
      print "opcode non previsto"
      
  end select

  position += 4
  
loop until position >= ubound(array)

''risposta del quiz 1 del Day 2
print "Il valore in posizione zero e':"; array(0)

File 02b.bas

''programma: Quiz 2 del Day 2 di Advent of Code 2019
''autore:    ciuco informatico
''data:      12 dicembre 2019
''web:       https://ciucoinformatico.home.blog/

dim shared array() as integer ''array vuoto
dim shared address as integer
dim shared value as integer
dim as integer opcode

''dichiarazione procedura intcode
declare sub reset_intcode

address = 0
opcode = 0
value = 0

''ciclo per il parametro "verbo" (verb)
for i as integer = 0 to 99

  ''ciclo per il parametro "sostantivo" (noon)
  for j as integer = 0 to 99

    ''chiamata della procedura intcode reset input)
    reset_intcode

    array(2) = i ''verb
    array(1) = j ''noon

    address = 0
    do
      opcode = array(address)
      select case opcode
        case 1 ''somma
          array(array(address +3)) = array(array(address + 1)) + array(array(address + 2))
        case 2 ''moltiplica
          array(array(address +3)) = array(array(address + 1)) * array(array(address + 2))
        case 99 ''esce dal programma intcode
          exit do
        case else ''caso non previsto
          print "opcode non previsto"
      end select
      address += 4
    loop until address > ubound(array)
    
    if array(0) = 19690720 then
      ''domanda del quiz 2 del Day 2
      print "What is 100 * noun + verb?"; 100 * array(1) + array(2)
    else
      ''non fare nulla
    end if
    
  next j

next i

''definizione procedura intcode
sub reset_intcode
  address = 0
  ''lettura del file e creazione del contenitore indicizzato (array)
  open "02_input.txt" for input as #1
    do until eof(1)    
      input #1, value ''lettura di un singolo valore
      redim preserve array (0 to address) ''ridimensionamento array
      array(address) = value
      address += 1
    loop
  close #1
end sub

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.

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! 🙂