Decadimento audioattivo di Conway

Lotus - domenica 25 agosto

John Conway (ok, sono fissato con lui) era davvero una persona strana: amava i giochi, amava la matematica e a quanto pare anche la chimica.
Durante la sua lunga carriera si è imbattuto in un gioco assai particolare, chiamato Decadimento audioattivo.
Il funzionamento di questo gioco ( anche se non capisco cosa ci sia di divertente ) è semplice: data una stringa di lunghezza N si deve sostituire ogni ripetizione di x lettere di valore y con xy.
Per esempio, data la stringa:

3333

Si ottiene:

43

Bene, la faccenda è davvero semplice. La cosa figa cool ipermagica super è che il signor Conway e un certo Richard Parker (probabilmente il padre di Spiderman) hanno scoperto che dopo un numero finito di iterazioni, tale stringa si decompone in valori rappresentanti elementi di atomi comuni e transuranici. Adesso passiamo ad un po’ di chimica: cos’è un atomo transuranico? Niente di più semplice. Un atomo transuranico è semplicemente un atomo che abbia un numero atomico, indicato con Z, maggiore di quello dell’Uranio, ovvero 92. Noti elementi transuranici che compaiono nella vita di tutti i giorni sono il Seaborgio, il Mendelevio ( mia nonna è solita a farmi le polpette al Mendelevio ), il Curio e il mitico Hassio.

Questa loro scoperta viene chiamata Teorema cosmologico di Conway, successivamente il signor Mike Guy scopri che quel famoso N dopo del quale tutto decade era 24, purtroppo si perse la dimostrazione matematica, dunque ancora più tardi Doron Zeilberge e il suo Computer Shalosh B. Ekhad ( che soggetto Zeilberge, ha voluto che il suo Computer comparisse come co-autore della dimostrazione ) dimostrò che l’enunciato era corretto attraverso un software che girava sotto Maple, gli ci vollero un paio di settimane di esecuzione del programma, per chi fosse interessato l’articolo originale si trova qui.

Dunque, noi lavoriamo nell’ambito dell’informatica e l’informatica lavora grazie ad algoritmi, dunque scriviamo un fantastico algoritmo per il calcolo del decadimento audioattivo data una stringa! Vediamo la mia implementazione in C, commentiamola e eseguiamo una dimostrazione performante ( alla faccia di Zeilberge ).

Per prima cosa dichiariamo una funzione decode che attraverso una chiamata ricorsiva ( bleah ) analizzi passo per passo il risultato di ogni passaggio fino a che non si arriva a 24.

void decode( char string[MAX_CHARACTERS], int step );

Si hanno due argomenti, il primo è l’insieme di caratteri che andiamo ad analizzare, il secondo è una variabile che ci permette di contare le iterazioni svolte. Adesso vediamo l’algoritmo che ci porterà a filtrare la stringa trovando le ripetizioni, esse verranno sostituite con la notazione xy e poi verranno conseguentemente analizzate fino a che gli step non saranno uguali ad un valore che specifichiamo ( nel nostro caso 24 per dimostrare la validità del teorema cosmologico di Conway ).


Iterando fino alla fine della stringa se il primo carattere si succede in una sequenza, una volta terminata si crea una nuova stringa in notazione xy e si procede con l’esame della lettera successiva alla serie. In questo modo dando in input il numero 1132 si ottiene:


Con sole 10 iterazioni, si ha una sequenza di 2877 caratteri. Questo è tutto, il sorgente completo dell’applicazione lo trovate su Github.

Theme made by Koala