I problemi apparsi sul numero 142 di Dev - per chi non se li
ricordasse, erano la ricerca di numeri "riciclati" e numeri "autodefiniti"
- hanno avuto solamente qualche sparuto solutore che si è cimentato nella
soluzione e nel compito forse ancora più arduo di far passare i programmi
attraverso l'antivirus di Infomedia. Per quest'ultimo punto, consiglierei
a chi non ricevesse risposta entro un paio di giorni di provare a scrivere
una mail senza allegati, oppure inviarmi il tutto all'indirizzo
algomatica@gmail.com, o ancora usare l'accortezza di codificare con un
programma come uuencode gli eseguibili.
Tornando ai problemi, ho
ricevuto risposte da Filippo Bonanni, che ha scelto come linguaggio per
scrivere i programmi VB.NET; Sebastien Costa, che ha preferito C# e C, e
Simone Piccardi, che si è cimentato con i numeri riciclati con un
programma .net; le sue spiegazioni, insieme con le parti principali del
suo programma, si possono trovare nel Listato 1.
Per i numeri
riciclati, Filippo ha pensato che il sistema più semplice per verificare
che un numero fosse multiplo di quello ottenuto spostando la prima cifra
in fondo fosse calcolare il modulo: se è zero, a questo punto è possibile
fare la divisione e verificare quante volte il numero iniziale è multiplo
di quello finale. In questo modo si può lavorare tranquillamente con
l'aritmetica intera; naturalmente questa ha scelta ha reso necessario per
Filippo dovere aggiungere una funzione ausiliaria per trovare i numeri
riciclati in una base diversa da 10, ma il costo di questa conversione non
è così importante nell'economia di scala. Per quanto riguarda i valori
riciclati, l'approccio è stato molto più brutale: Filippo ha preparato un
array contenente i numeri di occorrenze per ogni cifra, e ha fatto
verificare al programma se i numeri che via via generava fossero
effettivamente autodefiniti. Il problema di questo approccio è chiaro non
appena si prova a lanciare il programma: al crescere del numero di cifre,
l'esecuzione rallenta notevolmente.
L'approccio di Sebastien ai
problemi è stato invece di tipo iterativo: in un lungo e interessante
documento che purtroppo non posso pubblicare per ragioni di spazio ha
mostrato come l'aggiunta di raffinamenti ha portato alla velocizzazione
del proprio algoritmo per i numeri riciclati di un fattore 15. Per quanto
riguarda i numeri riciclati, anche Sebastien ha usato un vettore v in cui
salvare il numero di occorrenze delle varie cifre. Però la ricerca non era
esaustiva, e veniva fermata in uno dei casi seguenti: (a) veniva trovato
un valore autodefinito (chiaro...); (b) la somma delle cifre supera il
valore B della base in cui si sta lavorando (un numero autodefinito può
infatti contenere al massimo B cifre); oppure (c) il conteggio di una
cifra già definita supera il valore imposto (se v[0]=1, è inutile provare
un numero con due o più zeri). Nella Tabella 1
trovate l'elenco di numeri autodefiniti da sinistra a destra nelle
basi da 2 a 10 e in base 16; non esistono numeri autodefiniti da destra a
sinistra.
Detto questo, sono rimasto un po' deluso dal fatto
che nessuno, almeno inizialmente, avesse trovato soluzioni al problema di
trovare un numero riciclato, scritto in base 10, di ordine 2. Ho perso un
po' di tempo prima di capire il motivo, che è davvero banale. Ciascuno dei
solutori aveva utilizzato il tipo Int64 per memorizzare i numeri, in modo
da potere fare tutte le operazioni necessarie in aritmetica intera.
Peccato che nel caso qui sopra le soluzioni fossero numeri di diciotto cifre! Mettendosi a fare qualche conto a
tavolino è abbastanza facile trovare che il limite superiore del numero di
cifre che compone un numero riciclato di ordine N in base B è dato da
B*N-2; se siamo molto sfortunati, infatti, potrebbe darsi che ogni cifra
appaia N volte nel numero, ciascuna volta lasciando un resto diverso
quando si fa la divisione del numero maggiore per quello minore. Le uniche
eccezioni sono il caso di zero con resto zero e B-1 con resto B-1; nel
primo caso la divisione terminerebbe prematuramente, nel secondo avremo un
loop infinito. Bene, in questo caso otteniamo proprio il massimo numero di
cifre. Per quello che posso dire del doctor Brom, deve averlo fatto
apposta, a scegliere un problema di questo tipo! Dopo uno scambio di email
con Sebastien, lui mi ha presentato un nuovo algoritmo per trovare i
numeri riciclati, che, come lui stesso dice, "ricalca quello che avrei
fatto manualmente". In pratica, data la base numerica determina tutti i
valori a due cifre e per ognuno di questi procede ricorsivamente ad
aggiungere una cifra prima dell'ultima. In questo modo il tempo di
esecuzione si riduce drasticamente; inoltre, con l'accortezza di
utilizzare anche in questo caso un array per contenere le varie cifre del
numero, finalmente sono state trovate anche le risposte alla domanda
iniziale. Nella Tabella 2 si possono trovare i
numeri riciclati per alcuni valori della base e
dell'ordine.
Un'ultima nota: il primo problema apparso sul
numero 143 di Dev, dove il contadino doveva fare attraversare il fiume a
un leopardo, una capra, un topo e un sacco di mais, non era risolvibile
con la condizione data di potere portare solamente un animale oppure
oggetto con sé. Sono sicuro ve ne siete accorti tutti: ma avete provato a
verificare se il problema è risolubile se il contadino può portare sulla
barca due tra animali e oggetti?