Numeri strobogrammatici, cosa sono e come trovarli

Come elencare i numeri strobogrammatici con N cifre? Me lo chiede la newsletter Daily Coding Problem, con il suo Problem #402.
Intanto ho dovuto cercare il significato del termine: un numero strobogrammatico è un numero che rimane uguale quando ruotato di 180°. Ad esempio 689 è strobogrammatico.
Il problema è considerato Easy, e in effetti lo è, una volta definito con un minimo di attenzione. È comunque un utile esercizio di programmazione per chi, come me, non codifica (nel mio caso in Python) quotidianamente per lavoro.

Il problema

La domanda posta dalla newsletter è:

A strobogrammatic number is a positive number that appears the same after being rotated 180 degrees.
For example, 16891 is strobogrammatic.
Create a program that finds all strobogrammatic numbers with N digits.

Il quesito è stato proposto a un colloquio di assunzione in Twitter, mi informa la newsletter. Un po’ deludente, pensavo che Musk chiedesse cose più elevate.

Definire il problema

I numeri cercati non potranno contenere tutte le 10 cifre, ma solo quelle che, ruotate di 180*, rimangono uguali a sé stesse (0,1,8) oppure si trasformano in un’altra cifra strobogrammatica (6,9).
I numeri strobogrammatici non contengono quindi le cifre: 2, 3, 4, 5, 7.
Un’ulteriore condizione è che a ogni cifra dei numeri cercati dovrà corrispondere il suo gemello nella posizione simmetrica rispetto agli estremi del numero. Un esempio chiarisce:

. . 6 . . . . 9 . . va bene, perché al 6 nella terza posizione dall’inizio corrisponde un 9 nella terza posizione dalla fine;
. . . 8 . . . . 8 . . non va bene, perché il primo 8 è in quarta posizione dall’inizio, mentre l’altro 8 è nella terza posizione dalla fine.

Altro importante aspetto: i numeri strobogrammatici possono avere un numero pari o un numero dispari di cifre. In questo secondo caso, al centro del numero si troverà una cifra che corrisponde a sé stessa e che quindi può essere solo 0, 1 oppure 8.

L’algoritmo per elencare i numeri strobogrammatici

Per generare tutti i numeri strobogrammatici con N cifre, si può procedere con un algoritmo ricorsivo, estendendo uno strobogrammatico con un numero minore di cifre.
Ad ogni passaggio l’estensione aggiunge due cifre, quindi, ad esempio, per ricavare gli strobogrammatici con 8 cifre, si avrà una ricorsione del tipo:
8 <– 6 <– 4 <– 2 <– 0
Mentre per 7 cifre si avrebbe:
7 <– 5 <– 3 <– 1

L’algoritmo può quindi partire dalla lista degli strobogramamtici con 0 cifre (lista con una stringa vuota, [“”]) o con 1 cifra ([“0”, “1”, “8”]) e ricavare progressivamente la lista estendendo in tutti i modi possibili con 2, 4, … oppure con 3, 5, … cifre.
A ogni passaggio occorrerà estendere i numeri della lista ponendo, uno all’inizio e uno alla fine, gli elementi delle coppie “1” – “1”, “8” – “8”, “6” – “9”, “9” – “6”.
La coppia “0” – “0” sarà da inserire solo se non si è nell’ultimo passaggio, per evitare di inserire uno 0 come cifra iniziale.

A questo punto il codice è abbastanza semplice.

Il codice per generare i numeri strobogrammatici

def strobo(n,nmax):
	if n == 0:
		return [""]
	if n == 1:
		return ["0","1","8"]
	interno = strobo(n-2,nmax)
	lista = []
	for elem in interno:
		if n!= nmax:
			lista.append("0" + elem + "0")
		lista.append("1" + elem + "1")
		lista.append("8" + elem + "8")
		lista.append("6" + elem + "9")
		lista.append("9" + elem + "6")
	return lista
#
n = 4
lista = strobo(n,n)
print (lista)
print (len(lista), "elementi")

La funzione ricorsiva è strobo(n,nmax), che restituisce la lista degli strobogramatici con nmax cifre, includendo gli elementi con uno “0” all’inizio e al fondo solo quando n < nmax.
Quindi, ad esempio, se si cercano i casi con 8 cifre, la prima chiamata avverrà con strobo(8,8), che a sua volta chiamerà strobo(6,8), a seguire strobo(4,8), strobo(2,8) e infine strobo(0,8) che restituirà una lista vuota. Risalendo il flusso, la lista si arricchirà degli elementi con 2, poi 4, 6 e infine 8 cifre.

Notare che, nel caso di numero con 0 cifre, la funzione strobo() restituisce una lista con una stringa vuota, che sarà poi estesa con le coppie di cifre opportune dal livello che ha chiamato la funzione.

Ecco i numeri strobogrammatici!

Proviamo il codice con n = 3.
L’output sarà:

['101', '808', '609', '906', '111', '818', '619', '916', '181', '888', '689', '986']
12 elementi

La lunghezza della lista aumenta abbastanza rapidamente con n. Nel caso n = 10, ad esempio, si avranno 2500 elementi.
In realtà è abbastanza semplice ricavare una regola generale per calcolare il numero di elementi strobogrammatici di un dato numero di cifre n, una volta nota la numerosità per il caso n-2.
Infatti, nel passare da n-2 a n, si dovrà aggiungere ciascuna delle 4 coppie “1” – “1”, “8” – “8”, “6” – “9”, “9” – “6” a:

ciascuno degli elementi con lunghezza n-2 (L_n-2), questi elementi cominciano per “1”, “8”, “6” oppure “9”;
e a ciascuno degli elementi con lunghezza n-2 con uno 0 all’inizio e uno alla fine (L_n-2 / 4).

Quindi:
L_n = 4 ( L_n-2 + L_n-2 / 4) = 5 L_n-2.

Ad ogni passaggio, quindi, la lunghezza della lista si moltiplica per 5.
Questo ragionamento vale in generale, tranne che nel passaggio dalla lista di lunghezza 1 a quella di lunghezza 3 e nel passaggio da lista di lunghezza 0 a lista di lunghezza 2.
Nel primo caso, infatti, la lista L₁ = [“0”, “1”, “8”] contiene già l’elemento che comincia con 0.
Nel secondo caso, invece, la lista L₂ comprende 4 elementi: [“11”, “88”, “69”, “96”].

Quindi si avrà:

partendo da n = 0, le lunghezze saranno di:
0 –> 4 –> 20 –> 100 –> 500 –> 2500 –> …
partendo da n = 1:
3 –> 12 –> 60 –> 300 –> 1500 –> …

Alla fine della gita tra i numeri

Problema indubbiamente easy, come dice Daily Coding Problem.
Ma, come al solito, mettere giù un algoritmo, ancorché semplice, e sistemare il codice fino a che dia i risultati corretti è una buona ginnastica mentale. Meglio di un Sudoku o di uno schema di parole incrociate.
Il tutto con poca spesa, avendo a disposizione un ambiente gratuito di esecuzione del codice Python, come è Google Colab.

Foto di Susan Holt Simpson su Unsplash.