I numeri degli inni

Sommario

Un altro classico problema numerico tratto da un best seller di enigmi e puzzle per C64. Viene proposta e sviluppata una soluzione in BASIC V2 alternativa a quella fornita dal testo, in questo caso incentrata su un notevole miglioramento prestazionale conseguito tramite l’uso accorto di una struttura dati elementare ma massimamente idonea alla rappresentazione dei sottoinsiemi: un semplice array booleano.
E’ disponibile anche una versione PDF di quest’articolo ed i sorgenti per CBM Prg studio in formato ZIP.

«Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk.»
(Leopold Kronecker, 1823-1891)

1 Introduzione.

Col presente articolo vogliamo rivisitare un semplice problema numerico che molti di noi «retroprogrammatori» si sono all’epoca divertiti a risolvere programmando il proprio PET. Il linguaggio è intenzionalmente informale, divulgativo e didascalico, scevro da particolari pretese di rigore, al fine di raggiungere il più vasto uditorio informatico possibile.
L’articolo è organizzato in tre parti principali. Nella prima parte si illustra semplicemente il problema nella sua forma originale, mentre nella seconda parte si presenta la soluzione proposta dagli autori del testo. Nella terza e ultima parte si discute una soluzione alternativa, che comporta un netto miglioramento prestazionale e fa uso di una delle strutture dati elementari maggiormente efficienti per la rappresentazione di sottoinsiemi, universalmente utilizzata nella combinatorica computazionale.

2 Hymn Numbers.

Il problema originale, a pagina 3 del testo [1], è di fatto il primo quesito proposto nel libro. Eccone di seguito il testo completo:

The other Sunday, the hymn numbers on the board appeared as shown. It caught my eye because I saw that all the digits were different. I then noticed that the second hymn number was twice the first, and the third was equal to the first two added together.
192
384
576
This made me wonder if there were any other sets of numbers, all different, that could be formed into 3 three digits numbers with this curious property.

Il testo è brevissimo e sufficientemente chiaro. Viene dato per scontato che si opera in base dieci e si richiede di individuare delle particolari terne di numeri naturali (interi positivi): per fissare le idee, siano essi a,b,c . Sappiamo che b=2 ⋅ a e c=a+b=3 ⋅ a . Il testo precisa inoltre esplicitamente che tutti i numeri devono essere di tre cifre: questo implica, in particolare, che c<1 03 e di conseguenza a<c/3 . Dal momento che non sono ammesse cifre ripetute, si deve in realtà considerare come limite superiore il valore naturale a tre cifre più prossimo a 999 composto con cifre tutte distinte, vale a dire 987, da cui a ≤ 329 . Con analogo ragionamento si stabilisce il limite inferiore, per cui in definitiva 102 ≤ a ≤ 329 .
Scrivendo tali numeri tutti di seguito, inoltre, tutte le nove cifre devono essere diverse tra loro, ossia ciascuna cifra dell’intervallo naturale [0,9] deve comparire zero o esattamente una volta.

3 La soluzione originale.

La soluzione proposta a pag. 50 di [1] genera tutte le terne di numeri di tre cifre che godono delle proprietà desiderate.

1 rem soluzione originale dal puzzle book
2 rem problema 1: hymn numbers
3 s = ti: print "soluzione originale dal puzzle book"
10 for h = 1 to 3
20 for t = 0 to 9
30 if (h = t) then 260
40 for u = 0 to 9
50 if (u = t) or (u = h) then 250
60 n = 100*h + 10*t +u
65 if (n > 329) then print "run time: "; (ti-s)/60;"s": end
70 a = n*2
80 b = n*3
90 a$ = mid$(str$(a),2)
100 b$ = mid$(str$(b),2)
110 n$ = mid$(str$(n),2)
120 c$ = a$ + b$
130 for m = 1 to 5
140 for l = (m + 1) to 6
150 if (mid$(c$,m,1) = mid$(c$,l,1)) then goto 250
160 next l
170 next m
190 for m = 1 to 3
200 for l = 1 to 6
210 if (mid$(n$,m,1) = mid$(c$,l,1)) then goto 250
220 next l
230 next m
240 print n$; ", "; a$; ", "; b$
250 next u
260 next t
270 d(h+1) = 0: next h

Come è immediato rilevare dalla lettura del codice, il programma si può dividere concettualmente in due blocchi fondamentali: la generazione dei valori di base, e il calcolo dei valori derivati con la relativa validazione.
Il loop esterno genera esaustivamente tutti i valori a tre cifre nell’intervallo [100, 329] tramite un semplice generatore di tipo odometrico che consta in realtà di tre loop annidati.
Per ogni valore di base, per costruzione già privo di cifre ripetute (ciò è garantito dai controlli effettuati rispettivamente alle linee 30 e 50), vengono poi calcolati il doppio e il triplo, ed infine si procede a verificare l’unicità di ciascuna cifra, secondo il paradigma combinatorio denominato generate and test. A questo provvedono le linee dalla 70 alla 230 incluse nel listato proposto.
Dal punto di vista combinatorio, i numeri di base da generare sono ovviamente caratterizzati per l’ordine delle cifre. L’ampiezza della presentazione (tre cifre) è strettamente minore del numero di simboli disponibili (dieci), e non sono ammesse ripetizioni come 11, 22, 33, 202, 244, etc. Pertanto, per definizione, si tratta di generare restrizioni di disposizioni semplici di dieci simboli su tre posizioni.

In linea di principio, il programma eseguirà non meno di 329-100+1=230 passi nel loop principale, saltando però l’elaborazione per quei rami improduttivi dell’albero computazionale che non corrispondono a disposizioni semplici (questa fondamentale tecnica di generazione combinatoria è detta pruning o anche early filtering). L’ampiezza dello spazio combinatorio in questione è ovviamente data da
2 ⋅ D (9,2) +3 ⋅ 8=168
laddove il primo addendo tiene conto delle disposizioni semplici tra 102 e 298 costruite anteponendo rispettivamente 1 e 2 e utilizzando poi i rimanenti 9 simboli su due cifre, mentre il secondo addendo enumera le disposizioni semplici costruite col medesimo criterio, ma maggiori di 301 e inferiori a 329: infatti, dopo avere anteposto il 3 si hanno tre sole possibilità {0,1,2} per la scelta della seconda cifra, a causa del vincolo, e per ciascuna scelta della seconda cifra rimangono altre otto possibilità per la cifra meno significativa.
La struttura fondamentale del programma risulta quindi molto razionale e in linea con i principi asseverati della generazione combinatoria, per quanto attiene la prima parte del problema. Tuttavia, gli autori hanno scelto una soluzione implementativa per la convalida e il controllo di unicità delle cifre che ha un costo computazionale eccessivamente elevato. Osservando i loop annidati alle linee 130 ÷ 170 e 190 ÷ 230 risulta evidente la farraginosità ed inefficienza del metodo impiegato per il confronto diretto tra le cifre. Ciò si traduce, su C64, in un tempo di esecuzione dell’ordine di 45”. Come vedremo a breve, è possibile (e informaticamente doveroso) fare di meglio con l’uso di una opportuna struttura dati.

Runtime della soluzione originale del testo.

4 Soluzione alternativa.

Si propone nel seguito una soluzione completa in BASIC V2 al quesito del testo, in grado di migliorare notevolmente la prestazione a runtime, pur mantenendo sostanzialmente inalterata la struttura di base del generatore combinatorio impiegato e rispettando l’impostazione fortemente didattica dell’intera soluzione.
Ragionando dal punto di vista meramente combinatorio e ponendo a margine le condizioni b=2 ⋅ a,c=3 ⋅ a (che di fatto riducono notevolmente lo spazio combinatorio da esplorare, ma non cambiano la natura intrinseca del problema), il quesito si riduce essenzialmente alla generazione di disposizioni semplici di dieci elementi su nove posizioni. Poiché le ripetizioni sono proibite, si tratta quindi di selezionare un opportuno sottoinsieme proprio dall’insieme di partenza { 0,1,2,3,4,5,6,7,8,9 } : la struttura dati per eccellenza più adatta a rappresentare un sottoinsieme è l’array booleano, nel quale ad ogni posizione è associato biunivocamente un singolo elemento dell’insieme, secondo un ordine prefissato in modo arbitrario. Il valore booleano di ogni cella del vettore indica lapalissianamente se l’elemento appartiene o meno al sottoinsieme considerato. Un po’ più formalmente, dato l’insieme finito A di cardinalità |A|>0 , e un suo sottoinsieme proprio B ⊂ A , con i opportuno indice, il vettore binario V di dimensione |A| risulta così definito:
per ogni ai ∈ A,V( i ) ={ 1 se ai ∈ B, 0 se ai ∉ B
Si consideri ad esempio, per l’insieme delle dieci cifre decimali da noi utilizzato, il sottoinsieme {1,3,5} : la sua rappresentazione con un vettore binario, considerando l’ordine naturale, è ⟨ 0,1,0,1,0,1,0,0,0,0 ⟩ . Nel nostro caso infatti non occorre alcun particolare sforzo immaginativo per scegliere un ordine da applicare all’insieme di partenza: ci accontenteremo del naturale ordine ascendente delle prime dieci cifre decimali per la implicita corrispondenza posizionale con le celle del vettore binario.
Si richiama l’attenzione sulla universalità di questo metodo, che lo rende adatto alla rappresentazione di qualsivoglia insieme simbolico arbitrario finito, grazie ad fondamentale lemma enumerativo che sancisce la possibilità di stabilire sempre una biezione arbitraria di qualsiasi insieme finito su un qualsiasi intervallo intero, e a fortiori naturale. Questo spiega la sua universale pervasività nella letteratura teorica e applicativa per un vastissimo numero di utilizzi in ambito discretistico e combinatorico.
In generale la più naturale implementazione di questi array booleani è l’uso di bit array, un tipo di dato che molti linguaggi e piattaforme gestiscono efficientemente in modo nativo. Alcune CPU e molti microcontroller coevi al 6502/6510 gestiscono in hardware aree di memoria bit-addressable; in genere lavorando in Assembly si può ottenere la massima efficienza su quasi ogni CPU convenzionale usando istruzioni booleane atomiche per azzerare, impostare, invertire e verificare lo stato di un singolo bit in un registro. Alternativamente, usando linguaggi HLL, si possono utilizzare array di (piccoli) interi, raggiungendo un compromesso ingegneristico tra prestazioni e footprint di memoria generalmente accettabile, a maggior ragione in sede didattica ed illustrativa.
Con l’uso di tale struttura dati risulta in ogni caso immediato controllare se un dato elemento appartiene o meno al sottoinsieme considerato, e quindi nel caso specifico se una cifra è già stata eventualmente utilizzata: è sufficiente un accesso alla memoria, alla posizione i-esima dell’array, dove i è la cifra attualmente in fase di controllo.

100 print "{clear} **************************************"
101 print " *** 1: hymn numbers ***"
102 print " **************************************"
120 s = ti : print " soluzione alternativa: array booleano" : ?
140 for h = 1 to 3
150 d%(h+1) = 1
160 for t = 0 to 9
170 if d%(t+1) = 1 then goto 350
180 d%(t+1) = 1 190 for u = 0 to 9
200 if d%(u+1) = 1 then goto 330
210 d%(u+1) = 1
220 n = 100*h + 10*t +u
230 if (n > 329) then print "run time: "; (ti-s)/60;"s": end
240 a$ = mid$(str$(n+n),2): b$ = mid$(str$(3*n),2): c$ = a$ + b$
250 for j = 1 to 6: i = 1 + val(mid$(c$,j,1))
260 if d%(i) = 1 then goto 300
270 d%(i) = 1
280 next j
290 print mid$(str$(n),2); ", "; a$; ", "; b$
300 if j > 1 then for k = 1 to j-1: d%(1 + val(mid$(c$,k,1))) = 0: next k
320 d%(u+1) = 0
330 next u
340 d%(t+1) = 0
350 next t
360 d%(h+1) = 0: next h

Come risulta evidente dallo screenshot, il guadagno prestazionale ottenuto col semplice impiego di una struttura dati più adatta, che consente l’accesso diretto all’informazione necessaria alla convalida di ogni singola cifra, è quantificabile nell’ordine del 40%: in pratica si consegue quasi un raddoppio prestazionale, pur lasciando inalterata la natura del loop principale a triplice annidamento.
Vale forse la pena di sottolineare a margine lo stupore e il dispiacere dell’autore nel constatare che, nonostante l’assoluta intuitività e banalità della soluzione proposta, la sua enorme pervasività nei testi di ogni livello interenti l’algoritmica e la combinatorica (anche laddove non venga presentata esplicitamente, la si dà praticamente per acquisita) e il fatto incidentale che nel 1985 sia stata in assoluto la prima soluzione a balenare per la mente dell’allora adolescente studentello liceale che oggi scrive il presente articolo, ancora oggi ci si imbatte fin troppo spesso in disperate richieste di aiuto da parte di programmatori d’ogni età e livello di esperienza impantanati in soluzioni farraginose e dispersive quando messi alle prese per le più varie esigenze con la generazione di oggetti combinatori isomorfi a sottoinsiemi.

Soluzione alternativa, nettamente più efficiente.

Riferimenti bibliografici:
[1] Gordon Lee and Nevin B. Scrimshaw, The Commodore Puzzle Book – BASIC Brainteasers (Boston, USA: Birkhauser, 1983).

Have your say