Enigmes informatiques: la matematica ricreativa col pc

Enigmes informatiques è la sezione del sito Bibmath.net dedicata alla matematica ricreativa da affrontare con l’aiuto di un computer.
Il sito è uno dei tanti in lingua francese sul tema, molti più di quanti ne esistano in italiano. C’è da chiedersi se questa penuria sia effetto o causa del disagio italico a manovrare con i numeri.
Un po’ l’uno, un po’ l’altra. All’origine c’è forse un insegnamento della matematica che non entusiasma i ragazzi. Sta di fatto che un sito simile in Italia non avrebbe un grande appeal, e quindi non c’è particolare interesse a crearne e mantenerli in vita. Un’eccezione da segnalare: i Giochimatematici della Bocconi. Il sito val bene una visita.
Proviamo ad affrontare invece uno degli enigmes informatiques, aiutandoci con il linguaggio Ruby.

Un nombre à 9 chiffres

Il problema è il secondo della sezione degli Enigmes informatiques. Ripropongo qui il testo del problema:

On cherche un nombre de neuf chiffres différents de 0 tel que:
(1) le nombre formé par le premier chiffre soit divisible par 1
(2) le nombre formé par les deux premiers chiffres soit divisible par 2
(3) le nombre formé par les trois premiers chiffres soit divisible par 3
(4) le nombre formé par les quatre premiers chiffres soit divisible par 4
(5) le nombre formé par les cinq premiers chiffres soit divisible par 5
(6) le nombre formé par les six premiers chiffres soit divisible par 6
(7) le nombre formé par les sept premiers chiffres soit divisible par 7
(8) le nombre formé par les huit premiers chiffres soit divisible par 8
(9) le nombre formé par les neuf premiers chiffres soit divisible par 9

(on appelle par premier chiffre le chiffre de gauche).
Il y en a plusieurs comme 183252321 par exemple. Cependant, il y en a un unique où les neuf chiffres sont distincts, lequel?

Enigmes informatiques, quindi serve un algoritmo!

Beh, forse algoritmo è una parola grossa, però dobbiamo mettere insieme le righe di codice che arrivino alla soluzione (che è unica, ci informa il testo) e in modo efficiente.

Il numero cercato ha 9 cifre, tutte diverse tra loro. Quindi dovremo cercare tra 9! = 362.880 possibili disposizioni delle 9 cifre da 1 a 9.
La disposizione cercata dovrà essere tale che le prime due cifre da sinistra formino un numero divisibile per 2, le prime tre un numero divisibile per 3, e così via fino al numero composto da tutte le cifre da 1 a 9, che dovrà essere divisibile per 9.

Cominciamo a notare due cose:

se il numero composto dalle prime cinque cifre deve essere divisibile per 5, allora la quinta cifra da sinistra deve essere 0 o 5. Eliminato lo zero, che non è previsto, possiamo fissare già la quinta cifra al valore di 5;
comunque siano disposte le nove cifre, la loro somma sarà sempre pari a 45; quindi il numero sarà sempre multiplo di 9. L’ultima condizione posta dal problema è quindi inutile.

Ruby corre in aiuto degli enigmes informatiques

Come si generano le possibili disposizioni dei numeri da 1 a 9 con Ruby? Semplice:

[1,2,3,4,5,6,7,8,9].permutation.each do |p|
	...[ qui va il codice] ...
end

Vale a dire che del vettore con le 9 cifre [1,2,3,4,5,6,7,8,9] vanno generate tutte le possibili permutazioni delle cifre e, per ciascuna, chiamata p, vanno verificate le condizioni del problema, alla ricerca della soluzione.

Come tradurre in codice le condizioni del problema

Abbiamo visto che la quinta cifra deve essere 5. In Ruby scriveremo così:

next if p[4] != 5

Cioè: passa al prossimo candidato (next) se la quinta cifra non è uguale a 5. Perché la quinta cifra è identificata come p[4]? Semplicemente perché la numerazione degli elementi dei vettori parte da 0!

Per esprimere invece la condizione che il numero composto, ad esempio, dalle prime quattro cifre deve essere divisibile per 4, scriveremo:

next if p[0..3].join.to_i % 4 != 0

Cioè: passa al prossimo candidato (next) se, il numero intero (to_i) formato dalle prime quattro posizioni della permutazione (p[0..3].join ), dà un resto (%) diverso da zero quando diviso per 4.

Occhio all’efficienza!

Aggiungiamo ancora due elementi: una misura del tempo di elaborazione del programma e una misura dell’efficienza dei filtri che porremo in sequenza.

Per il primo punto il codice è molto semplice: si prende l’orario all’inizio dell’esecuzione dell’algoritmo, si rilegge l’orologio alla fine e per sottrazione si determina il tempo impiegato:

t0 = Time.now
... [qui va il codice dell'algoritmo] ...
t1 = Time.now
print "tempo impiegato: ",t1-t0," sec"

Per il secondo punto basterà contare i passaggi attraverso ciascun filtro e vedere come si riducono passaggio dopo passaggio.

La soluzione più semplice per il nostro primo incontro con gli enigmes informatiques

Mettiamo insieme gli elementi appena visti, e abbiamo l’algoritmo che più fedelmente traduce il testo del problema (Algo_A).

 conta = Hash.new(0)
t0 = Time.now
[1,2,3,4,5,6,7,8,9].permutation.each do |p|
	conta[1] += 1
	next if p[4] != 5
	conta[2] += 1
	next if p[0..1].join.to_i % 2 != 0
	conta[3] += 1
	next if p[0..2].join.to_i % 3 != 0
	conta[4] += 1
	next if p[0..3].join.to_i % 4 != 0
	conta[5] += 1
	next if p[0..5].join.to_i % 6 != 0
	conta[6] += 1
	next if p[0..6].join.to_i % 7 != 0
	conta[7] += 1
	next if p[0..7].join.to_i % 8 != 0
	print "soluzione: ", p, "\n"
end
t1 = Time.now
print "efficienza del filtraggio: ", conta, "\n"
print "tempo impiegato: ",t1-t0," sec"

Il controllo sulla quinta cifra, che presumibilmente opera un filtraggio efficiente, è in prima posizione, e non è stato inserito nessun filtraggio sul numero di 9 cifre, che si è visto essere superfluo. L’esecuzione del programma dà questo risultato:

soluzione: [3, 8, 1, 6, 5, 4, 7, 2, 9]
efficienza del filtraggio: {1=>362880, 2=>40320, 3=>20160, 4=>7680, 5=>1632, 6=>120, 7=>22}
tempo impiegato: 0.314495 sec

Il numero cercato è quindi 381654729 (provare per credere).
Le possibili permutazioni sono abbattute dalle iniziali 362.880 a 40.320 dal controllo sulla quinta cifra, poi il controllo della divisibilità per 2 riduce ulteriormente a 20.160, e così via.

Un primo miglioramento del filtraggio

Una prima idea può essere quella di non verificare semplicemente che la seconda cifra sia pari, ma, in un unico passaggio, verificare che siano pari la seconda, la quarta, la sesta, l’ottava. Questo perché i numeri con le prime 2, 4, 6 e 8 cifre da sinistra devono essere tutti pari.

Ne segue che le cinque posizioni rimanenti devono essere occupate dai cinque dispari rimanenti (1, 3, 5, 7, 9), e il loro prodotto deve essere dispari. Quindi

Sostituiamo:
	next if p[0..1].join.to_i % 2 != 0
con:
	next if p[0]*p[2]*p[4]*p[6]*p[8] % 2 == 0

Difficile dire come cambia il tempo di esecuzione del singolo filtro, ma certamente aumenta la sua efficienza. Vediamo cosa ci dice l’esecuzione del programma (Algo_B):

soluzione: [3, 8, 1, 6, 5, 4, 7, 2, 9]
efficienza del filtraggio: {1=>362880, 2=>40320, 3=>576, 4=>240, 5=>120, 6=>40, 7=>8}
tempo impiegato: 0.198961 sec

Esecuzione molto più veloce (da 0.314495 sec a 0.198961 sec), grazie a una eccellente efficienza del filtro (solo 576 permutazioni che superano il controllo su seconda, quarta, sesta e ottava cifra, contro le 20.160 rimanenti dopo il controllo limitato alla seconda cifra.

Si può fare ancora meglio?

La realizzazione del programma ha finora seguito fedelmente l’elencazione del testo degli enigmes informatiques.
In effetti c’è da attendersi che la verifica che il numero di, ad esempio, 3 cifre sia divisibile per 3, lasci filtrare più permutazioni rispetto alla verifica che il numero di 8 cifre sia divisibile per 8.

Quindi conviene rovesciare l’ordine dei filtri, sempre però lasciando in cima i due filtri più efficienti (quinta cifra e parità delle cifre pari).
La nuova forma dell’algoritmo (Algo_C):

conta = Hash.new(0)
t0 = Time.now
[1,2,3,4,5,6,7,8,9].permutation.each do |p|
	conta[1] += 1
	next if p[4] != 5
	conta[2] += 1
	next if p[0]*p[2]*p[4]*p[6]*p[8] % 2 == 0
	conta[3] += 1
	next if p[0..7].join.to_i % 8 != 0
	conta[4] += 1
	next if p[0..6].join.to_i % 7 != 0
	conta[5] += 1
	next if p[0..5].join.to_i % 6 != 0
	conta[6] += 1
	next if p[0..3].join.to_i % 4 != 0
	conta[7] += 1
	next if p[0..2].join.to_i % 3 != 0
	print p, "\n"
end
t1 = Time.now
print "efficienza del filtraggio: ", conta, "\n"
print "tempo impiegato: ",t1-t0," sec"

Quanto aumenta velocità?

[3, 8, 1, 6, 5, 4, 7, 2, 9]
efficienza del filtraggio: {1=>362880, 2=>40320, 3=>576, 4=>144, 5=>17, 6=>8, 7=>2}
tempo impiegato: 0.191415 sec

Qualcosa si guadagna, ma non molto. La ragione risiede nel fatto che il grosso del lavoro è svolto dai primi due filtri. Il terzo filtro lascia in campo 240 permutazioni nel primo caso, 144 nel secondo. Sono numeri troppo piccoli per avere un effetto visibile.

La figura che segue riporta l’efficienza delle tre serie di filtri presentati.

Il problema proposto dagli enigmes informatiques è, tutto sommato, semplice e di immediata realizzazione, con un linguaggio di programmazione della potenza ed espressività di Ruby.
Il breve viaggio verso la sua soluzione spero, però, che abbia messo nella giusta luce le due linee guida fondamentali nella realizzazione degli algoritmi: ricerca della correttezza e dell’efficienza. In particolare, per quest’ultimo aspetto, il posizionamento dei vari pezzi del puzzle della soluzione può avere effetti notevoli sul risultato finale. Non basta accontentarsi semplicemente di trovare la soluzione, se la strada per arrivarci è lunga!