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 ).
void decode( char *sequence, int step ) {
char first = sequence[0];
char repeat = '1';
char *result = calloc(sizeof(sequence) * (step * MULTIPLIER), sizeof(char));
char *temp = calloc(2, sizeof(char));
int i, length = strlen(sequence);
for( i = 1; i <= length; i++ ) {
if( first == sequence[i] && i != length ) {
repeat++;
} else {
sprintf( temp, "%c%c", repeat, first );
strcat( result, temp );
first = sequence[i];
repeat = '1';
}
}
if( step < MAX_STEPS ) {
printf("> %s\n", result);
decode( result, step + 1 );
}
}
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:
[!] Sequence: 1132 [!] Length: 4 > 211312 > 1221131112 > 112221133112 > 213221232112 > 12111322111213122112 > 11123113223112111311222112 > 311213211322132112311321322112 > 1321121113122113221113122112132113121113222112 > 111312211231131122211322311311222112111312211311123113322112 > 3113112221121321132132211322132113213221123113112221133112132123222112 > 132113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112 > 1113122113121113222112311311222113111231133221132231131122211311123113322112111312211312111322111213122112311311123112 1123222112 > 3113112221131112311332211213211321322113311213212322211322132113213221133112132123222112311311222113111231132231121113 112221121321133112132112211213322112 > 1321132132211331121321232221121113122113121113222123211211131211121332211322111312211312111322212321121113121112133221 121321132132211331121321132213211231132132211211131221232112111312212221121123222112 > 1113122113121113222123211211131211121332211231131122211311123113321112131221123113111231121123222113223113112221131112 311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213 1221123113112211322112211213322112 > 3113112221131112311332111213122112311311123112112322211213211321322113311213212312311211131122211213211331121321122112 133221132213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311 22211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112 > 1321132132211331121321231231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112 311321322112111312212321121113122122211211232221132211131221131211132221232112111312111213111213211231132132211211131221 232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213 21232221121113122113121122132112311321322112111312211312113221133211322112211213322112 > 1113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211231131122211311123113 321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221132231131122 211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221 121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221 232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322 2112 > 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112 211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113 212231121113112221121321132122211322212221121123222113221321132132211331121321231231121113112221121321133112132112312321 123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332 111213122112311311123112111331121113122112132113121113222112311311222113111231133221132231131122211311123113322112111312 211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331 22211332111213112221133211322112211213322112 > 1321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211 131122211213211321222113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211 131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332 113221122112133221132211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112 132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213 211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321322113311213 212322211322132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312 111322212311222122132113213221123113112221133112132123222112111312211312111322212311322123123112111321322123122113222122 21121123222112 > 1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311 222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332 111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221 131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112211322 212312211322212221121123222113223113112221131112311332111213122112311311123112111331121113122112132113121113222112311311 221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112 212211131221121321131211132221123113112221131112211322212312211322212221121123222112111312211312111322212321121113121112 131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113 222123211211131211121332211322111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211 131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211 121332211231131122211311123113321112132113221112131112132112311312111322111213112221133211322112211213322112 > 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113 311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221 123113112221131112211322212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112 311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221 121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321 322113312221133211121311222113321132211221121332211322132113213221133112132123123112111311222112132113311213211231232112 311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221 121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321 322113312221133211121311222113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321 131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332 211231131122211311123113321112131221123113111231121123222113223113112221131112311332111213122112311311123112112322211211 131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321 322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321 1321322113311213212312311211131221132231121113311211131221121321131112311322311211132132212312211322212221121123222112 > 1321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211 131122211213211321322112312321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221 121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112 111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122 211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221 133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113 213221123113112221133112132123222112111312211312111322212311322123123112111321322123122113222122211211232221132211131221 131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112 132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213 212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112 311311222113311213212322211211131221131211132221231132212312311211132132212312211322212221121123222112132113213221133112 132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132 211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112 132123123112111311222112132113311213211221121332211322132113213221133112132123123112111311222112132113311213211221121332 211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113 212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123 222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112 31131122211322132112312321123113112221121113122113311213211322132112311312111322111213112221133211322112211213322112 > 1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311 222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132 211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321 132132211231131122211331121321232221121113122113121113222123113221231231121113213221231221132221222112112322211231131122 211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311 222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122 211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113 311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213213211221113122113121113 222112132113213221232112111312111213322112311311222113111231133211121321132211121311121321123113121113221112131122211332 113221122112133221132231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312 211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312 211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211 131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332 111213213211221113122113121113222112132113213221232112111312111213322112311311222113111231133211121321132211121311121321 123113121113221112131122211332113221122112133221121113122113121113222123211211131211121311121321123113213221121113122123 211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113 222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321 122112133221121113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211322111312 211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231 121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211 322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321133112132113212221221113 122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221 123113112221131112311332111213122112311311123112111331121113122112132113213221132211131221121311121312211213211321322112 311311222123211211131221132211131221121321131112311322311211132132212312211322212221121123222112
Con sole 10 iterazioni, si ha una sequenza di 2877 caratteri. Questo è tutto, il sorgente completo dell’applicazione lo trovate su Github.
