A=B, ovvero un unico comando per un gioco intero

Non sono un programmatore. Mi sono avvicinato numerose volte alla programmazione, senza andare mai troppo a fondo nell’argomento, e ho realizzato dei programmi, degli script per browser e delle automazioni, alcune più utili alcune semplicemente più divertenti. Dentro la facoltà di Matematica, in fondo, era normale avvicinarsi ad alcuni linguaggi di programmazione, e il mio interesse per la logica e per gli enigmi hanno fatto il resto per avvicinarmi a quei videogiochi che richiedono al giocatore di risolvere dei puzzle attraverso la scrittura di codice.

Seppure Zachtronics sia indubbiamente la casa di sviluppo di riferimento per i giochi open-ended di questo calibro, non sono gli unici a realizzare videogiochi di valore in questo campo. Raccontarvi di giochi del genere è però molto meno efficace di procedere per esempi concreti, un po’ come ho fatto quando vi ho parlato della bellezza dei Sudoku Variants o quando ho consigliato a molti il meraviglioso Tametsi.

Avete mai sentito parlare degli Esolang? Sono definiti così:

An esoteric programming language (ess-oh-terr-ick), or esolang, is a computer programming language designed to experiment with weird ideas, to be hard to program in, or as a joke, rather than for practical use.

da https://esolangs.org/wiki/Esoteric_programming_language

Sostanzialmente sono dei linguaggi di programmazione spesso scomodi da utilizzare ma interessanti per qualche motivo specifico. Ne esistono di estremamente minimali, di difficilissimi da leggere, di tematici o di particolari per determinati motivi (utilizzano design unici, permettono di fare delle operazioni per cui altri linguaggi necessitano di molte righe di codice, etc etc). Il linguaggio Shakespeare ad esempio chiede al programmatore di scrivere le istruzioni come se fossero lo script di un’opera teatrale (giuro, cliccate qui sotto e stupitevi di un codice corrispondente a un Hello, World!).

Altri linguaggi, come Unreadable, sono stati pensati apposta per essere praticamente impossibili da leggere dagli umani. Ora, non tutti gli Esolang sono in grado di compiere qualunque operazione che normalmente compieremmo con altri linguaggi. Non tutti gli Esolang, cioè, sono “Turing-completi”, nel senso di poter compiere tutte le operazioni che una macchina di Turing può compiere. Senza scendere troppo nel dettaglio, questa proprietà è estremamente rilevante, dato che – di fatto – la completezza secondo Turing è una proprietà condivisa anche dalle più potenti macchine e dai più avanzati linguaggi classici. Ed è condivisa dai due linguaggi che ho citato qui sopra. In altri termini ogni cosa che possiamo fare oggi con i linguaggi di programmazione più comune può essere fatta, con molta più difficoltà, in Shakespeare e in Unreadable.

Cosa c’entra tutto questo con A=B, e soprattutto cos’è A=B? È un puzzle game sulla programmazione basato tutto su un solo comando: A=B. Cosa fa il comando? Semplice: sostituisce A con B, ogni volta che può.

A=B è presentato come A One-Instruction Esolang, perché l’intero gioco è sostanzialmente scritto attraverso quella sola istruzione, oltre a qualche piccolo comando extra non necessario ma utile per rendere l’apprendimento e la sfida sempre interessanti.

Per esempio quello che vedete qui di seguito è un tipico livello di A=B: l’input è una serie di stringhe composte da “a”, “b” o “c”. Questo è l’alfabeto del livello. Il gioco vuole che il programma restituisca in output “true” se l’input contiene esattamente tre lettere, altrimenti deve restituire in output “falso”. La barra a destra dei comandi funziona così: il programma legge in ordine: se può eseguire il comando lo esegue e riparte da capo, altrimenti scorre al comando successivo. Il comando (return) manda in output quello che c’è scritto a destra del comando.

In questo caso uso i primi due comandi per dirgli che b=a e che c=a, in modo da trasformare tutte le lettere della stringa di input in a. A questo punto gli dico che se trova una stringa composta da quattro a significa che l’input contiene almeno quattro lettere, e quindi gli faccio inviare in output “false”. Se ha superato quella riga significa che non ha trovato “aaaa”. Se a quel punto trova “aaa” significa che l’input contiene tre lettere (e non di più perché si sarebbe fermato prima), quindi posso mandare in output “true”. Se invece anche questa riga viene superata significa che la stringa in input contiene soltanto una o due lettere e quindi la riga finale dice di inviare in output “false”.

Giusto per maggiore comprensione, mostro cosa succede nel caso di due stringhe di esempio: ogni volta che il programma ha eseguito una riga è ripartito dalla riga 1. Questa è la stringa baacabb:

Questa invece è la stringa abc:

Un solo livello, decine di tentativi

Cos’ha però di speciale A=B? Tante cose. La prima di queste è che è un linguaggio Turing-completo, quindi attraverso questo solo comando è in grado di compiere operazioni aritmetiche e sviluppare algoritmi capaci di fare praticamente qualunque cosa fanno altri linguaggi ben più articolari di esso. La seconda di queste è che dietro l’apparente semplicità di un comando banale (sostituire qualcosa con qualcos’altro) nasconde una profondità enorme che dona sensazioni tipiche dei giochi di Zachtronics.

Ho passato ore sui livelli di A=B, prima per risolverli e poi per migliorarli. Le soluzioni non sono mai uniche, ma migliorarsi e cercare di capire cosa stiamo sbagliando è una base essenziale e fondante dell’esperienza ludica di A=B. E, incidentalmente, è un buon modo di imparare qualcosa in più sulla programmazione, almeno nei termini della comprensione.

Per questo voglio mostrarvi un esempio molto indicativo, legato a uno dei livelli facili (ancora nel secondo blocco di livelli), per farvi capire quanto rapidamente le meccaniche si complicano. Mi sto riferendo al livello 2-5, intitolato Odd.

Il livello richiede di scrivere un programma che mandi in output “true” se il numero di occorrenze di ogni lettera è un numero dispari, oppure zero. Altrimenti deve mandare in output “false”.

Al contrario di quanto possa sembrare inizialmente, questa richiesta è ardua a causa della parte “oppure zero”. Riuscire a determinare se la quantità di volte in cui una lettera appare è pari o dispari è molto semplice anche senza contare (questo linguaggio non è in grado di contare in modo ovvio, e non ha una memoria né una pila – restando nel linguaggio dell’informatica teorica). Al di là di quel primo tentativo, che serviva soltanto per iniziare a ragionare sul problema, è sufficiente mettere in ordine le lettere (tutte le a, seguite da tutte le b, seguite da tutte le c), poi eliminare le coppie “aa”, “bb” e “cc” e vedere cosa resta. Se ogni lettera ha un numero dispari di occorrenze, la stringa “abc” è l’unico output che darà “true”. Il problema è che è ammesso anche che non ci sia nessuna occorrenza di una lettera per mandare in output “true”.

Così ho iniziato a ragionare su come potessi separare il caso in cui una lettera non era presente fin dall’inizio (il che andava bene) e il caso in cui la lettera scompariva perché eliminavo le coppie (il che non andava bene, perché ovviamente significava che c’era un numero pari di occorrenze di quella lettera). Allora ho deciso di utilizzare delle lettere arbitrarie:

Sostanzialmente così con le prime tre righe ordinavo la stringa, poi sostituivo le coppie “aa”, “bb” e “cc” con altre lettere e parte del gioco era effettivamente risolta: se rimane una “a” significa che dopo aver trasformato tutte le coppie “aa” in “dd” è effettivamente rimasta una “a” spaiata. Cioè, in altri termini, il numero di “a” è dispari. Ovviamente l’output era ancora tutto da sistemare.

D’altra parte, mi sono reso conto, non serviva che “aa” diventasse “dd”. Il punto era indicare l’esistenza di coppie. Quindi era sufficiente utilizzare una sola “d” e stringere la stringa il più possibile in modo da ridurmi a pochi casi possibili di cui potevo indicare l’output:

La soluzione non era ancora corretta, perché mi mancavano dei casi. Ad esempio, la stringa aaabbbc veniva portata a daebc e poi a causa della riga 18. e=(return)false mi dava in output “false” anche se avrebbe dovuto darmi “true”. Questo perché non avevo inserito correttamente i casi dimenticando che le coppie venivano trasformate in “d”, “e” o “f” da sinistra, e quindi esistevano i casi “da”, “eb” e “fc” da tenere in considerazione. Così arrivai alla soluzione:

Cerco, di nuovo in tabella, di farvi seguire il passaggio logico di queste operazioni mostrandovi l’output nel caso, ad esempio, della stringa bbaabca, che contiene 3a, 3b e 1c, e che quindi deve mandare in output “true”:

Insomma, tutti felici adesso? No, perché una volta risolto il puzzle A=B mi dà accesso a un’informazione: la cosiddetta “challenge”, che recita “At most 10 lines”.

Ammetto che lì per lì non me l’aspettavo. Immaginavo che non fosse una soluzione efficientissima, ma non credevo si potesse scendere addirittura da 22 a 10 righe di codice. Avrei potuto andare avanti, ovviamente, ma sapevo già che non l’avrei fatto. Dovevo capire.

Di una cosa ero certo: la parte meno efficace della mia soluzione risiedeva nella necessità di dover “differenziare” tutti i casi tra loro, e il programma era tutto tranne che un programma scalabile in relazione all’alfabeto. Cosa vuol dire? Che se l’alfabeto fosse stato di 26 lettere anziché di 3 la quantità di righe di codice sarebbe aumentata in modo esagerato. Così ho deciso di tornare all’idea iniziale, quella di evitare lettere extra.

In fondo cosa stavo cercando di fare? Volevo trovare un modo di differenziare le coppie “aa” dalle singole “a”. Inizialmente avevo cercato di eliminare le coppie “aa”, ma mi sono reso conto che forse non era necessario. Per farlo mi sono concentrato su una sola lettera e ho ragionato sulle possibili occorrenze con l’istruzione aa= e il risultato è stato questo:

Il problema, come avevo capito inizialmente, risiede nel caso in cui non ci sono “a” fin dall’inizio. Cosa succede allora se al posto di eliminare la coppia “aa” io lavoro sulla tripla “aaa”? Dalla tabella qui su noto che “aaa” deve diventare semplicemente “a” affinché il sistema funzioni. Qual è il vantaggio? Che se l’istruzione diventa “aaa=a” elimino comunque le coppie “aa” ma non agisco sull’unico caso che mi crea problemi (cioè la singola coppia “aa”). Il risultato è questo:

In altri termini, “aaaa” veniva effettivamente trasformato in “aa” ma non perché cancellavo una coppia “aa”, bensì perché sostituivo la tripla “aaa” con una sola “a”. La differenza, seppure a prima vista lieve, cambiava del tutto la situazione e mi ha portato alla soluzione:

Dieci righe esatte, che mi hanno permesso di completare la challenge. Le prime tre righe servono a ordinare la stringa, le successive tre trasformano le triplette in singole lettere, e poi se restano coppie significa che il numero di occorrenze della lettera era pari. In caso contrario (compresi i casi in cui non ci sono occorrenze di una lettera) il programma manda in output “true”. Ecco cosa succede con la stringa bbaabca mostrata sopra:

Questo invece succede con una stringa che contiene un numero pari di “b”, come abbbaba:

A cosa è servito, oltre semplicemente a darmi la soddisfazione di “esserci riuscito”? Mi sarei potuto limitare alla soluzione da 22 righe e andare avanti in A=B, ma non avrei imparato. Non avrei fatto riflessioni ulteriori, non avrei approfondito. Non gli avrei dedicato il tempo che meritava. E non avrei capito come utilizzare quella tecnica in altri livelli più avanzati.

Perché il secondo capitolo è ancora pieno tutorial, e senza farmene rendere conto mi ha fatto fare le domande giuste, mi ha fatto cercare le risposte giuste, e mi ha insegnato qualcosa. Mi ha insegnato un linguaggio, e lo ha fatto by design. O meglio, mi ha insegnato come usare quel linguaggio. Sapete, non vi ho detto come si scrive “Hello, World!” nell’Esolang di A=B.

Bello, no?