#define Nd Np define #define Ni(N) Np include <std##N##.h> #define Np ??= Ni(def) Ni(io) Ni(lib) Nd Ba BC(B, I) Nd Be BC(Br, I) Nd Ca(C, Ca) CB(B, In C, Ca) Nd Cl(Cl) Cl Cl Nd Cs const Nd FrB N = Zr; Fr((O, B = BrB(BrF, I))) Nd Fe(F) FO (In = Zr; F; In++) Nd FF FB(B); FB(BF); Nd FI Fe(IO) Nd FO for Nd Fr(F) FO (I = Zr; F; I++) Nd II I I, In Nd In(I, Ir) main(I, Ir) Nd IO In[O[C + I]] Nd Ir(I) if (I) Nd Nb N > N && N > -O Nd Rb(Rb, B) BBr(Br, Rb, B) Nd Re return Nd Sc struct Nd Si(Te) sizeof (Te) Nd Te typedef Nd Zn N < Zr Te char C; Te int I; Te size_t Si; Te void V; Cs C *Na = "H " "He " "Li Be " "B C N O F Ne " "Na Mg " "Al Si P S Cl Ar " "K Ca Sc Ti V Cr Mn Fe Co Ni Cu Zn Ga Ge As Se Br Kr " "Rb Sr Y Zr Nb Mo Tc Ru Rh Pd Ag Cd In Sn Sb Te I Xe " "Cs Ba* Lu Hf Ta W Re Os Ir Pt Au Hg Tl Pb Bi Po At Rn " "Fr Ra**" " *La Ce Pr Nd Pm Sm Eu Gd Tb Dy Ho Er Tm Yb " " **Ac Th Pa U Np Pu "; Cs C *Xe = "111%%d:\0\n"; Cs C H[] = "22"; Cs C U[] = "3"; Cs I Zr = 0; Cs I O = 1; Cs I W = 2; V (*At)(V) = abort; V (*F)(V *) = free; V *(*Mo)(Si) = malloc; I (*Pr)(Cs C *, ...) = printf; I (*P)(I) = putchar; Nd Tm(B,C) \ Sc B { \ C *B; \ I N; \ } ; \ Te Sc B *B; \ \ B N##B (I) ; \ V F##B (B) ; \ C B##C (B, I) ; \ V C##B (B, I, C) ; \ \ B N##B (I N) { \ B B; \ \ Re (W, B = Mo(Si(Sc B))) ? \ (O, B->B = Mo(((W, B->N = N) ? N : O) * Si(C))) ? \ B Cl(: (At(), B)); \ } \ V F##B (B B) { \ F(B->B); \ F(B); \ } \ C B##C (B B, I N) { \ Re B->Nb ? B->B[N] : (C) Zr; \ } \ V C##B (B B, I N, C C) { \ N; \ B->Nb ? B->B[N] = C : C ? At(), C : C; \ } Tm(B,C) V Pb (B) ; I Bi (B) ; C Co (B, B, I) ; B Sb (B, I) ; V Pb (B B) { I I; Fr(Ba) P(Ba); } I Bi (B B) { I I; Fr(Ba) ; Re I; } C Co (B Br, B B, I N) { I I; Fr(I < N) Ir(Be - Ba) Re Be - Ba; Re Zr; } B Sb (B Br, I N) { B B; I I; B = NB(Zn ? Bi(Br) + N : N); FO(I = Zn ? -N : Zr; Zn ? Be : I < N; I++) CB(B, Zn ? I + N : I, Be); Re B; } Tm(Br,B) V PBr (Br, I) ; V PBr (Br B, I N) { I I; Pr(W * W + Xe, N); Fr(BrB(B, I)) { P(O[Na]); Pb(BrB(B, I)); } P(Xe[W << W]); } B Dy (B, I) ; I S (C, B) ; Br Sr (Br) ; B Dy (B Br, I N) { B B; C C, Cr; II; B = NB(W * Bi(Br)); FO(In = I = Zr; (O, C = Be); I++) { FO(Cr = O; (W, C == BC(Br, I + Cr)); Cr++) ; I += Cr - O; Ca(++, Cr + Si(H)**H - Si(U)**U); Ca(++, C); } Ir(N) FB(Br); Ca(-N, W[H]); Re B; } I S (C C, B Br) { B B, BF; II; Ir(C == BC(Br, Zr)) Re Zr; Fr(Be) { B = Cl(BF = Sb(Br, I); ) Fe(BC(B, Zr)) { B = Dy(B, W); Ir(C == BC(B, Zr)) { FF Re Zr; } Ir(In % W) BF = Dy(BF, W); Ir(Zr == Co(B, BF, Bi(BF))) { FF Re O; } } FF } B = Dy(Br, Zr); I = S(C, B); FB(B); Re I; } Br Sr (Br BrF) { Br Br; B B, BF; II, N; FrB N += Bi(B); Br = NBr(N); FrB { Rb(N++, B); Fe(BC(B, In + O)) S(BC(B, In), BF = Sb(B, -In - O)) ? Ca(+O, O[U]), Rb(N++, B = BF), In = Zr : (FB(BF), W); } FBr(BrF); Rb(N, (V *) Zr); Re Br; } I In (I, C **) ; I In (I N, C ** C) { Br Br; B B; II; Br = NBr(--N); Fr(I < N) { FI ; Rb(I, B = NB(In)); FI Ca(-Zr, IO); } Fr(BrB(Br, Zr)) { Br = Sr(Br); PBr(Br, I); Fe((W, B = BrB(Br, In))) { Rb(In, Dy(B, Zr)); FB(B); } } { } { } { } { } { } { } { } { } { } { } { } { } { { } } { } { } { } { } { } { } { } { } { { } } { { } } { } { } { } { } { } { } { { } } { } { } { { } } C; { } { { } } { } { } { } { } { } { } { } { } { { } } { } { } { } { } { } { } { } { } { } { } { } Re Zr; }

引用元：https://www.ioccc.org/2004/jdalbec.c

審査員・作者による説明：https://github.com/ioccc-src/winner/blob/main/2004/jdalbec.hint

動作

Look-and-say sequenceを生成する。

$ gcc -trigraphs -E jdalbec.c > jdalbec2.c

$ sed -e 's/ (/(/g' < jdalbec2.c > jdalbec3.c

$ ruby -i -p -e 'if /# define Tm/.../^Tm/; if /^Tm/; $_ = "\n" + $_; else; $_.sub!(/$/, "\\"); end; end' jdalbec3.c

$ gcc -o jdalbec jdalbec3.c

$ ./jdalbec 1
0: 1
1: 11
2: 21
3: 1211
4: 111221
5: 312211
6: 13112221
7: 11132 13211
8: 311312 11131221
9: 1321131112 3113112211
10: 11131221133112 132113212221
11: 311311222 12 32112 111312211312113211
12: 1321132 132 1112 13122112 311311222113111221131221
13: 111312211312 111312 3112 111311222112 1321132 132211331222113112211
14: 3113112221131112 31131112 132112 31132 1322112 111312211312 1113222 12 311322113212221
...

最初の数字はコマンドライン引数で指定する。 次の数字は、前の数字の桁を読み上げる形で決める。

• 最初の”1”は「1つの1がある」と読み、この数字をひろってくっつけた数字”11”が次の数字。
• “11”は「2つの1がある」と読み、この数字をひろってくっつけた数字”21”が次の数字。
• “21”は「1つの2、1つの1がある」と読み、数字だけくっつけて”1211”が次の数字。
• “1211”は「1つの1、1つの2、2つの1がある」なので、”111221”が次の数字。

これを繰り返していく。

ポイントは、勝手に空白が入っているところ。 これは、空白の前と後がこの先独立に発展していくことを示している。 詳しくは解説で。

解説

Look-and-say sequenceは、ライフゲームの考案者として知られるコンウェイが導入・解析したもの。 一見するとよくある数遊びに見えるけれど、意外と面白い性質があるらしい。

数学系の情報サイトであるWolfram MathWorldにも載っている、Cosmological Theorem（宇宙論的定理？）という次のような定理。

「次のような整数Nが存在する：Look-and-say sequenceのすべての文字列は、最大でN日のうちに、普通の元素と超ウラン元素の化合物に減衰する」

この定理の詳しい説明がjdalbec.hintにもWolframにもないので苦労したが、CMUのサイトにあった資料の導入を見たら理解できたので詳しく説明する。

---

Look-and-say sequenceを繰り返していくと、「切り離して扱っても問題ない箇所」が出てくる。たとえば”2111”は”2”と”111”に分割できる。

   2 111
-> 12 31
-> 1112 1311
-> 3112 111321
-> 132112 31131211
-> 1113122112 132113111221
-> 311311222112 1113122113312211
-> 13211321322112 311311222123112221

切れ目の左側の数字は常に2、右側の数字は1と3の繰り返しになっていることがわかる。 少し観察すると、この性質はこの先ずっと続くことがわかる。 よって、ここは切り離して扱っても問題ない。

これは、どこを切っても良いわけではない。 例えば”111”を”1 11”に分割すると、”111”→”31”だが”1 11”→”11 21”なので、別の文字列になってしまう。

Cosmological Theoremの主張は、どんな文字列もlook-and-sayの操作を繰り返していくうちに、ある92+2種類の部分文字列を連結した文字列になる、ということ。

92というとウランの原子番号なので、コンウェイは92種類の部分文字列を「普通の元素」と呼び、元素記号を割り当てた。 これがCosmological Theoremの表に書かれているもので、すべて1、2、3の数字だけからなる。

残りの2種類は、1、2、3以外の数字を持つもの。 次の2種類だけとのこと。

• Pu = 31221132221222112112322211n
• Np = 1311222113321132211221121332211n

nの部分は1～3以外の数字、または数字以外の文字が入る（同位体と言われている）。なお、look-and-sayの操作をするとPuとNpは交互に入れ替わる。 この2つ（プルトニウムとネプツニウム）が、超ウラン元素。

ということで、定理が言っていた「普通の元素と超ウラン元素の化合物」は、独立して変化していく92+2種類の部分文字列を結合した文字列という意味だった。

---

元のプログラムは、プリプロセスを2回行う必要があるコードになっている。 残念ながら現代のCコンパイラでは期待通りにプリプロセスされないので、1点のコード修正と1点のビルドプロセス修正を行った。

• #include <std##N##.h> は期待通りに動作しないので、書きくだした。
• 生成されたコードの中で、# define Tm(B,C)の定義本体を\で行継続していく必要があった。rubyコマンドでこの変換を行っている。

コード中の識別子は元素記号や化合物。 コードには周期表が含まれていたり、最後の方に”OBFUSCATED”のアスキーアートがややわかりにくい形で仕込まれてたりする。

 {   }  {    }  {   } { } { }  {  }  {  }   { } {     } {   } {    }
{     } { { } } { }   { } { } { }   { }    {   }  { }   { }   { { } }
{ { } } {    }  {   } { } { }  { }  { }   { { } } { }   {   } { {  } }  C;
{     } { { } } { }   { } { }   { } { }   {     } { }   { }   { { } }
 {   }  {    }  { }    {   }  {  }   {  } { } { } { }   {   } {    }

このアスキーアートは、わかりやすく@で埋めると次のようになる。

 {@@@}  {@@@@}  {@@@} {@} {@}  {@@}  {@@}   {@} {@@@@@} {@@@} {@@@@}
{@@@@@} {@{ }@} {@}   {@} {@} {@}   {@}    {@@@}  {@}   {@}   {@{ }@}
{@{ }@} {@@@@}  {@@@} {@} {@}  {@}  {@}   {@{ }@} {@}   {@@@} {@{  }@}  C;
{@@@@@} {@{ }@} {@}   {@} {@}   {@} {@}   {@@@@@} {@}   {@}   {@{ }@}
 {@@@}  {@@@@}  {@}    {@@@}  {@@}   {@@} {@} {@} {@}   {@@@} {@@@@}

パッチ

--- jdalbec.c +++ jdalbec.c @@ -1,10 +1,10 @@ #define Nd Np define -#define Ni(N) Np include <std##N##.h> +#define Ni(N) Np include N #define Np ??= -Ni(def) -Ni(io) -Ni(lib) +Ni(<stddef.h>) +Ni(<stdio.h>) +Ni(<stdlib.h>) Nd Ba BC(B, I) Nd Be BC(Br, I)

パッチをダウンロード