Most GIFted expressions

もっとも天才的な式

Line wrap

Highlight

#define o(a,b,c,d) a##f b##f c##f d; a##g b##g c##g d;q--
#define Z(z)if(*j==z)
#define c(z,p) Z(z){y;v p##=r;o(b,[q-1]=b,[q] p b,[q]);}
#define y q+=t;t=0
#define r w[q]
#define v w[q-1]
#define w(a,m,f) Z(a){y;r=m(r);q++;o(b,[q-1] = -b,[q-1]*f(r)+0*b,[0]);}
#define A(p,w,o) for(p=0;p<w;p++)_(o)
#define P(a) for(a=Z;a<Z;a++)
#define _ putchar
typedef double o;
typedef char z;
o A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y, E_, w[20], bf[20], bg[20],x=-1.3/8,p,d,l=0,h=4e-3,f,m;
z e[17] = "FKE<<gMAQUDIYO9\"=", *k, *j; o g(o p, o d){int q =-1,t=0;j=k;while( *j ){c(45,-);Z(100){y;q++;r=v;q[bf]=bf[q-1];q[bg]=bg[q-1];}Z(42)
     {y;v*=r;o(b,[q-1]=r*b,[q-1] + v*b,[q]);}Z(44){t=0;q++;}Z(116){f=v;v=r;r=f;f=bf[q];q[bf]=bf[q-1];bf[q-1]=f;f=q[bg];bg[q]=(q-1)[bg];bg[q-1]=f;



      }c(43,+);Z(47){y;v/=r;              o(b,[q-1]=b,[q-1]/r-v/                (r*r)*b,[q]);}Z(121){y;q++                        ;r=d; bf[ q]=0;bg[q]=1;}
      Z(94){y;f=v;v=pow(v,r)              ;o(b,[q-1]=r*b,[q-1]*                 pow(f,r-1)+0*b,[q]);}w(115                        ,sin,cos);w(99,cos,sin);
      Z(120){y;q++;r=p;bf[q]              =1;bg[q]=0;}if(*j>=48                 &&*j<58){q++;t=1;r=*j-48 ;                        bf[q] = 0;(q--)[bg] = 0;
                             }j++;}H=bf[0]                                                                ;K= bg[ 0]; return w[0];}
                             void s(){int                                                                 e=0;X=Q*8;f=g (Y*8, L*8 )
                             ;e=(f-X<0)?1:                                                                -1;l=0;while((l+=h)<8)  {
      V=Y*8+l*R;W=L* 8+l*D;X=             Q*8+l*U;f=g(V,W);if((f                                          -X)*e>0){if(V>-1&&V<1&&W>                   
      -1&&W<1){p=V;d=W;return            ;}else e/=-1;}}p=d=-10                                           ;}int main(int argc, z **
      argv){int c, f;z b[2],Z            ;S=0,C=1;k=argv[1];Z =                                           atoi(argv[2])>>1;b[1]=Z*2


      &255;b[0]=Z>> 9;J= 3.1415/Z;A(f,6,f[e]^f+1);while(--f>1)_(
      (f%2)[b]);_(246);A(c,384,c/3%2?c/6<<2:0);_(_(0));_(_((_(33)
      <<3)-9)/23);for(f+=5;f < c/22 ; f++) _(e[f] ^ f - 3);for(;f
                                           > c/29;f--)_(f>15?2*f-
                                           31:c);_(0);for(f=0;f<=
                                           Z*2 ; f++){N = S;E_=1-
                        J*J/2;T=J*(1-J*J/6);
                        S=S*E_+C*T;C=C*E_-N*
                        T;A=-(C*C-S*S);P=-A*
     C;E=A*S;G=S*C*2;I=-
     G*S;F=G*C;_((_(e[10
     ]/2-1)<<3)-18);for(
     c=-1;c<5;c++)_((c+1)%2?0:-2*c*c+3*c+9);_(44);A(c,9,c&4?(1-c%2
     )[b]:0);_(7);for(B=-Z ; B<Z ; B++){_(Z+2);for(O=-Z;O<Z;O++){Y
     = (E - P*B/Z - G*O/Z)*x;L = (I - F*B/Z - A*O/Z)*x;Q = (-C +S*

     B/Z)*x;R = - Y + E; D =-L+I; U =-Q-C;s();3[w] = sqrt(R*R + D*D + U*U);m=p==-10?1:(4[w]=sqrt(H*H+K*K+1)*w[3],H/=-4[w],K/=-4[w],
     fabs(H*R + K*D + U/4[w])*exp(-l*l/2) );_((z)(m * 63)*2 + ((z)((p+1)*6) % 2 + (z)((d+1)*6) % 2 == 1 ? 1 : 0));O?l:(_(128),_(B!=
     Z-1 ? Z : Z+1));}_(128);}_(_(129)-129);}_(0x3b);}

引用元：https://www.ioccc.org/2012/blakely/blakely.c

審査員・作者による説明：https://www.ioccc.org/2012/blakely/hint.html

動作

逆ポーランド記法で書いた式をコマンドライン引数に与えると、その式を3次元の曲面としてレンダリングした図をアニメGIFとして出力する。

$ gcc -o blakely blakely.c -lm

$ ./blakely "xx*yy*+" 64 > paraboloid.gif

第2引数は画像のサイズ。次のコマンドは20分くらいかかった。

$ ./blakely xy* 250 > saddle.gif

次のコマンドは1時間以上。

$ ./blakely xx*yy*1++d5*ct/ 250 > ripple.gif

解説

IOCCCでは比較的おなじみのネタ（逆ポーランド記法、アニメGIF生成、レイトレーシング）を1つにまとめたというネタ。

式の指定で使えるのは、四則演算、指数関数、sin/cos、定数、dup、swap、x座標、y座標。 3つの座標がすべて-1から1に入っている範囲だけが描画される。

コード形状は、非常に荒く横長なドットで、”x” “y” “z”を表現している。賞名の”GIFted”は、gifted（天賦の才のある）とGIFをかけている。

いくつか作者からの読者への挑戦的な質問がある。

逆ポーランド記法のところを除いて、sin()とcos()を使っていない。どうやって視点を回転しているか？

次は、フレームごとに実行されるコードをまともな見た目にしたもの。

      N = S;
      E_ = 1 - J * J / 2;
      T = J * (1 - J * J / 6);
      S = S * E_ + C * T;
      C = C * E_ - N * T;
      A = -(C * C - S * S);
      P = -A * C;
      E = A * S;
      G = S * C * 2;
      I = -G * S;
      F = G * C;

Jは (3.1415 / フレーム数 * 2) という値。ポイントは最初の5行程度。

E_ = 1 - J * J / 2はcos(J)の近似式。同様にTはsin(J)の近似式。どちらもテイラー展開で、Jが0に近いとき、高精度の近似となる。
S = S * E_ + C * Tはsin()の加法定理で、角度をJだけ増やすことになる。同様にCの定義はcos()の加法定理。

このようにして、フレームごとに角度をJずつ変えている。

アニメーションは何回繰り返すか？

フレーム数のことなら、サイズに指定した回数だけ生成するもよう。

解像度の上限が250x250なのはどこから来ているか？

これは無圧縮GIFの出力方法に依存した微妙な話だと思う。ちゃんとは確認していないのでざっくり説明する。 256色のGIFは初期状態で258要素のテーブル（256個の色コードと、2つの制御コード）を持っていて、1ピクセル出力するごとにこのテーブルは長くなる。このテーブル長が511未満ならば1ピクセル出力するのに8ビット、つまりちょうど1バイトで表現できるのだが、このしきい値を超えると桁上りして9ビット必要になり、ビットストリームを扱う必要が起きてしまう。そこで、しきい値を超える前に「クリアコード」という制御コードを出力することで、伸びたテーブルを縮める。これが無圧縮GIFを出力する基本技法。おそらくクリアコードを1行表示し終えたら出力するようにしているので、横幅がこれを超えるとビットのずれが生じてしまうのだろう。詳細はGIFのファイルフォーマットや、その圧縮アルゴリズムのLZWを調べてほしい。

b[0]のポイントはなにか？

これはよくわからない。 b[0]とb[1]にはそれぞれ画像サイズ（16ビット）の上位バイトと下位バイトが入っているが、前述の通り250以下なので、b[0]はつねに0となる。そして、char型の変数Zに対してb[0] = Z >> 9で初期化しているように見えるので、未定義動作になっているような気もする。

ソースの中に隠された”NETSCAPE”と”GIF”の語はどこにあるか？

上記の、cos()とsin()を近似計算しているコード。代入されている変数名が順にNETSCAPEGIFになっている。