Si parla di programmazione ‘in piccolo’ quando il punto centrale dell’attività è la ricerca di un algoritmo efficace per una data elaborazione dell’informazione, seguita da una sua opportuna codifica in un linguaggio di programmazione che ne permetta l’esecuzione tramite un interprete automatico.
0.1.1 Un esempio
Un tipico esempio di esercizio di programmazione ‘in piccolo’ è il seguente (tratto dal materiale di supporto al tutorato di “Programmazione”, autori Violetta Lonati e Anna Morpurgo).
Si scriva un programma che legga (dallo standard input) due interi r e c, seguiti da una matrice di r righe e c colonne contenente lettere maiuscole e asterischi, e che stampi (sullo standard output) la matrice che si ottiene da quella in input “schiacciando” verso il basso le lettere e facendo “galleggiare” gli asterischi. Ad esempio, se la matrice è data da
V * S
* * B K * *
* S *
il programma dovrà stampare la matrice seguente:
* * *
* * * V * S K S B
Per risolvere l’esercizio bisogna ideare una strategia: si tratta di un processo in buona
parte, ma non del tutto, indipendente dal linguaggio di programmazione. Ogni
linguag-gio mette a disposizione diversi modi di rappresentare i dati e di esprimere computazioni,
anche se nella famiglia “imperativa” la sovrapposizione fra i diversi linguaggi è general-mente molto ampia, una volta scontata la varietà della sintassi. La strategia, quindi, dovrà tener conto della famiglia linguistica (risolvere un problema con un paradigma “lo-gico”
1, per esempio, richiede spesso un’impostazione specializzata) e in qualche misura anche delle peculiarità del linguaggio (costrutti espressivi, strutture dati di base, librerie standard, forme idiomatiche) in cui se ne prevede l’implementazione.
Per esempio in Go esaminare (scorrere gli elementi) di una matrice per righe è più facile che per colonne; nulla vieta però di leggere l’input e scrivere l’output come richiesto dall’esercizio e manipolare internamente una struttura dati trasposta.
Per immaginare una strategia è fondamentale suddividere il problema in sottoparti quasi elementari, in modo da articolare correttamente il pensiero
2.
Nell’esempio, potrebbe essere utile considerare separatamente almeno tre parti: (1) schiac-ciamento di una singola serie, (2) composizione degli schiacciamenti e (3) I/O.
Innanzitutto, quindi, ci concentriamo sullo schiacciamento di una singola serie.
package main import (
"unicode"
)
// schiaccia prende una serie di lettere e asterischi e li ordina in modo // da avere all'inizio tutti gli asterischi
func schiaccia(s []rune) (result []rune) { result = make([]rune, len(s))
var i uint
for _, c := range s { if c == '*' {
result[i] = c } i++
}for _, c := range s {
1Se questo termine è completamente nuovo, ci si può fare un’idea consultando la pagina Wikipedia dedicata all’argomento: https://en.wikipedia.org/wiki/Logic_programming
2Cartesio nel suo “Discorso sul metodo”, dopo aver dichiarato di non prendere mai niente per vero, “se non ciò che io avessi chiaramente riconosciuto come tale”, si ripromette di procedere seguendo questi famosi princìpi:
1. Il secondo, di dividere ognuna delle difficoltà sotto esame nel maggior numero di parti possibile, e per quanto fosse necessario per un’adeguata soluzione.
2. Il terzo, di condurre i miei pensieri in un ordine tale che, cominciando con oggetti semplici e facili da conoscere, potessi salire poco alla volta, e come per gradini, alla conoscenza di oggetti più complessi; assegnando nel pensiero un certo ordine anche a quegli oggetti che nella loro natura non stanno in una relazione di antecedenza e conseguenza.
3. E per ultimo, di fare in ogni caso delle enumerazioni così complete, e delle sintesi così generali, da poter essere sicuro di non aver tralasciato nulla.
[Cartesio, “Discorso sul metodo” a cura di A. Carlini, Bari 1963]
0.1 Programmazione ‘in piccolo’
if unicode.IsLetter(c) { result[i] = c
} i++
}return result }
È utile cercare di convincerci che la soluzione di questo sotto problema è corretta:
i pezzi semplici sono più facili da controllare (ed eventualmente correggere) di quelli complessi. La parte di confronto fra due slice di rune è opportuno scorporarla: fra l’altro potrà essere utile anche in altri test.
package main import "testing"
func equal(a, b []rune) bool { if len(a) != len(b) {
return false }for i, v := range a {
if v != b[i] { return false }
}return true }
// TestSchiaccia tests the first example func TestSchiaccia(t *testing.T) {
actual := schiaccia([]rune{'V', '*', 'K', '*'}) expected := []rune{'*', '*', 'V', 'K'}
if !equal(actual, expected) {
t.Errorf("\nGot: %v\nExp: %v\n", actual, expected) }
}
Passiamo poi a comporre le schiacciatine.
// SchiacciaTutte Schiaccia ogni riga
func SchiacciaTutte(s [][]rune) (result [][]rune) { for _, line := range s {
result = append(result, schiaccia(line)) }
return result }
Anche in questo caso possiamo controllare che funzioni almeno nel caso d’esempio, cui aggiungiamo anche alcune linee particolari (solo asterischi e solo lettere).
// TestSchiacciaTutte tests the example func TestSchiacciaTutte(t *testing.T) {
data := [][]rune{{'V', '*', 'K', 'S'}, {'*', '*', '*', 'S'},
{'S', 'B', '*', '*'}, {'*', '*', '*', '*'}, {'S', 'B', 'S', 'B'}}
actual := SchiacciaTutte(data)
expected := [][]rune{{'*', 'V', 'K', 'S'}, {'*', '*', '*', 'S'},
{'*', '*', 'S', 'B'}, {'*', '*', '*', '*'}, {'S', 'B', 'S', 'B'}}
for i, line := range actual { if !equal(line, expected[i]) {
t.Errorf("\nGot: %v\nExp: %v\n", actual, expected) } }
}
A questo punto manca solo l’I/O che però richiede una trasposizione.
// trasponi traspone le righe con le colonne func trasponi(m [][]rune) (result [][]rune) {
result = make([][]rune, len(m[0])) for i := range result {
result[i] = make([]rune, len(m)) }for i := range result {
for j := range result[i] { result[i][j] = m[j][i]
}
}return result }
Con il relativo test.
// TestTrasponi tests the example func TestTrasponi(t *testing.T) {
data := [][]rune{{'V', '*', 'K', 'S'}, {'*', '*', '*', 'S'},
{'S', 'B', '*', '*'}}
actual := trasponi(data)
expected := [][]rune{{'V', '*', 'S'}, {'*', '*', 'B'},
{'K', '*', '*'}, {'S', 'S', '*'}}
for i, line := range actual { if !equal(line, expected[i]) {
t.Errorf("\nGot: %v\nExp: %v\n", actual, expected) } }
}
0.1 Programmazione ‘in piccolo’
Ora possiamo passare all’I/O.
func main() { var r, c int
scanner := bufio.NewScanner(os.Stdin) fmt.Print("Dammi il numero di righe: ") if scanner.Scan() {
r, _ = strconv.Atoi(scanner.Text()) }
fmt.Print("Dammi il numero di colonne: ") if scanner.Scan() {
c, _ = strconv.Atoi(scanner.Text()) }
matrice := make([][]rune, r) for i := 0; i<r; i++ {
fmt.Println("Dammi la riga ", i) matrice[i] = make([]rune, c) if scanner.Scan() {
matrice[i] = []rune(scanner.Text()) } }
result := trasponi(SchiacciaTutte(trasponi(matrice))) var output string
for _, line := range result { for _, x := range line {
output += string(x) + " "
}
output += "\n"
}
fmt.Print(output) }
Le parti di I/O possono essere più macchinose da verificare in modo sistematico, so-prattutto nel caso si abbia a che fare con interfacce grafiche, ma ne caso dello standard input e standard output ci si può aiutare con la redirezione dei flussi standard di dati che il sistema operativo associa a ogni processo cui è collegato un “terminale”.
Creiamo un file input.txt:
3 2Z Z
* *A A