Un Pitone nel labirinto: prima fitta

english

Un puzzle può essere un esercizio divertente per migliorare le tecniche e le conoscenze matematiche. Quando uno poi prende l’abitudine di mischiare programmazione e argomenti matematici o scientifici viene piuttosto naturale usare un approccio ibrido. Dal momento che questo è un blog sulla Matematica e sulla didattica in questo momento mi interessa enfatizzare in che modo è possibile convertire un puzzle in una opportunità per allenare sia le abilità matematiche che quelle di programmazione allo stesso tempo, e come ognuno dei due set di competenze può indurre l’altro ad entrare in funzione. Il puzzle seguente mi è stato proposto da uno studente a lezione.

Ogni lettera sta per una e una sola cifra (possiamo supporre che le cifre/lettere più significative siano diverse da zero, cioè F, O e T non sono uguali a 0):


FIVE -
FOUR =
------
 ONE +
 ONE =
------
 TWO

Risolvere questo problema implica effettuare un certo numero di deduzioni basate sul testo del problema e sulla meccanica di base dell’addizione e della sottrazione (cioè le regole di riporto/prestito).
Di certo per trovare le soluzioni c’è bisogno di utilizzare una certa quantità di logica, ma l’impiego di ciò che viene spesso chiamato il “pensiero computazionale” probabilmente permette di arrivare alle soluzioni in una maniera che sia più conveniente del concatenare una sequenza interminabile (o almeno molto lunga) di proposizioni logiche.

Ma come farebbe una macchina a risolvere questo problema? Una possibilità sarebbe di trovare la strada per uscire dal labirinto tramite forza bruta. Per esempio si potrebbero generare tutte le permutazioni possibili dei valori delle lettere, e vedere per ognuno di loro se i vincoli sono soddisfatti. Una soluzione molto facile potrebbe essere questo script Python molto elementare

from itertools import permutations


def tonum(*a): # convert tuple in numeri interi
    l = len(a)
    res = 0
    for i in xrange(l):
         res += a[i]*10**(l-i-1)
    return res


solutions = [
    (
        tonum(f,i,v,e), 
        tonum(f,o,u,r), 
        tonum(o,n,e), 
        tonum(t, w, o)
    ) for (f, i, v, e, o, u, r, n, t, w) in permutations(range(10)) 
        if tonum(f,i,v,e)-tonum(f,o,u,r)==tonum(o,n,e) and 
            tonum(o, n, e)*2 == tonum(t, w, o)]


# rapporto

print "%d soluzioni trovate:" % (len(solutions), )
print
for five, four, one, two in solutions:
    print "%4d -" % (five,)
    print "%4d =" % (four,)
    print "------"
    print "%4d +" % (one,)
    print "%4d =" % (one,)
    print "------"
    print "%4d" % (two, )
    print

Chiaramente questo programma non è particolarmente veloce o efficiente, dato che genera tutte le 10! permutazioni mantenendo solo “quelle buone“. Ma ci mostra uno schema per risolvere un puzzle combinatorio di questo tipo. Dobbiamo ora solo sviluppare una strategia che ci permetta di tenere manualmente traccia delle possibili soluzioni risparmiando gli sforzi non necessari.

Permutazioni

Procediamo con ordine: come si generano tutte le permutazioni (per esempio) dei numeri 0, 1, 2?
Partiamo dal primo numero (0), in questo modo

livello 0     *
              |
livello 1     0 (1,2) 

Dai numeri che rimangono (quelli nelle parentesi) estraiamo ogni volta il prossimo della serie, continuando in questo modo

livello 0     *
              |
livello 1     0 (1,2)
              |
livello 2     1 (2) 
              |
livello 3     2 ()

Quando consumiamo tutti i numeri allora saliamo di un livello (“backtrack“): torniamo indietro sui nostri passi, tenendo traccia di quello che abbiamo scritto finora, e proviamo tutte le alternative possibili lungo il percorso

livello 0         *
                  |
livello 1         0 (1,2)
               /--'--\
livello 2     1 (2)   2 (1)
              |       |
livello 3     2       1

Continuiamo così

livello 0                        *
                   /-------------|-------------\
livello 1         0 (1,2)        1 (0,2)        2 (0,1)
               /--'--\        /--'--\        /--'--\
livello 2     1 (2)   2 (1)  0 (2)   2 (0)  0 (1)   1 (0)
              |       |      |       |      |       |
livello 3     2       1      2       0      1       0

permutaz.:   012     021    102     120    201     210

Spero che il disegno sia abbastanza chiaro, sostanzialmente costruiamo un albero, usandolo per tenere traccia delle possibilità.

Dall’albero alle tavole (matematica per carpentieri?)

L’albero ha una struttura molto bella e sintetica, ma può essere scomodo da disegnare. Possiamo a questo punto farlo diventare una tabella, come segue:

livello 0 livello 1 livello 2 livello 3 permutazione
* 0 1 2 012
2 1 021
1 0 2 102
2 0 120
2 0 1 201
1 0 210

Ancora una volta spero che la tabella parli da sola: riesci a vedere perché questa tabella è equivalente all’albero disegnato sopra? Useremo tabelle come questa per tenere traccia delle soluzioni candidate, ma cercheremo di evitare tabelle troppo grandi per essere maneggiate con carta e penna, per evitare di perdere il controllo delle cose.

Continueremo il discorso in un post futuro, ma nel frattempo con un po’ di buona volontà consiglio di provare ad andare avanti per conto proprio a partire dal punto in cui siamo arrivati, così da fare un pò di esercizio.

Advertisements

One thought on “Un Pitone nel labirinto: prima fitta

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s