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 ).

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.

Theme made by Koala