Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2014-01-05

[][] The 22nd IOCCC: Most tweetable 1-liner のエントリ

http://www.ioccc.org/2013/endoh3/endoh3.c

char a;float b,c;main(d){for(;d>2e3*c?c=1,scanf(" %c%f",&a,&c),d=55-a%32*9/5,b=d>9,d=d%13-a/32*12:1;a=2)++d<24?b*=89/84.:putchar(a=b*d);}

ツイート可能 (137B) なワンライナー

解説

ABC 記譜法 (のサブセット) のサウンドシンセサイザーです。ABC 記譜法とは、外国で使われる MML みたいなものです。

$ gcc -o endoh3 endoh3.c
$ echo "CDEFGABc" | ./endoh3 > /dev/dsp

とやるとドレミファソラシドが流れます。/dev/dsp が使えない人は padsp とか sox とか使って下さい。面倒な人のための動画。(音量注意)

D

137 バイトのコードの中に ABC 記譜法のパースと波形の生成が詰まってます。以下、実装について、概要だけご紹介。ドキュメントの Spoiler で結構詳細に説明しています。


パース

まず scanf で 1 音符分の音階と長さを持ってきます。

scanf(" %c%f", &a, &c)

これで得られた音階の ASCII コードに以下の謎の変換をかまします。*1

(a % 32 + 5) * 9 / 5 % 13 + a / 32 * 12 - 22

これによって音符を半音ずつ並べた数字 (MIDI ノート番号みたいなの) が得られます。


周波数への変換

この数字を周波数に直すには、pow(2, n/12) みたいな変換をします。が、pow は使えない *2 ので、pow(2, 1/12) を n 回掛け算します。この定数は 89/84. で近似できます。*3


波形の生成

あとは以下で波形を出力。

for(c = 0; c < len; c++) putchar(a = n * D);

n * D は単調増加ですが、char 型の変数に代入することで mod 256 の値になります *4 。これによってめでたく倍音豊かなのこぎり波が出力されます。


で、後はゴルフ。とりあえず 140B を切るまでは頑張りましたが、プロゴルファーならどのくらい削れるもんなんでしょうねえ。

狙いと戦略

これはわりと自信のある方でした。ワンライナーIOCCC の定番枠なので。

2 オクターブに収まり、(なるべく) 黒鍵を使わず、著作権フリーであるサンプル曲を探すのが大変でした。Happy Birthday to You はアメリカではまだ著作権存続中 (?) で去年も裁判起きたらしい、とか、長い休止符は例の曲著作権に抵触する可能性がある、とか。



[][] The 22nd IOCCC: Most solid のエントリ

http://www.ioccc.org/2013/endoh4/endoh4.c

int
**F,**
V,M, N,i;
#ifndef/**/S
#define S 70,23
#endif/* 000-2E5*/
#define/* 2E5-2E5,2E5
*/_POSIX_C_SOURCE 199309
#include/* 2E5XXX*/<time.h>
/* 2E5-2E5X*/#include<stdio.h>
#include<stdlib.h>/* -2E5-2E5XX*/
struct timespec R={0,1E6};int j,k,m,
#define U/* -2E5X*/rand()*2./RAND_MAX-1
#define/* 2E5*/O(p,q,i)(P[p*3+i]-P[q*3+i])
/* IOCCC2013 IOCCC2013*/#define B(p,q,\
r)(O(q,p,0)*O(r,p,1)-O(q,p,1)*O(r,p,     0))
#define A(t,n)( t*)malloc( sizeof     (t)*n)
#define E(p,q,r,s)B(p,q,r)*O(s     ,p,2)+B(\
p,r,s)*O(q,p,2)+B(p,s,q)*O(     /*XX*/r,p,2)
#define D(e,f)(c-a)?s=a,     a=e,e=s,s=f,f=\
d,d=s:0;u=a+.5;m=u+1;     T[01]=91;T[2]=060;
#define C (Q[u]-X)     *a+(Q[u+1]-Y)*b+(Q[u\
+2]-Z)*c,g=e*c-     f*b,h=f*a-d*c,f=c,c=d*b\
-e*a,d=a,a=g     ,e=b,b=h,P[k]=W/2-q/s/p*3*\
W,P[k+1]=     H/2+r/s/p*H/2,T[3]=0x48,*T=033
n,u,v,     w,t,W,H;double*P,*Q,I,J,K,L,x,y,z
,X,     Y,Z,a,b,c,d,e,f,g,h,p,q,r,s ;void o(
     double x){for(p=q=i=0,s=r=1;i<99;s=(s+x
  /s)/2)i%2?q+=r,r=-r:(p+=r),r*=3.14*x/++i;}
     int G(int p,int q,int s,int g,int f){i\
nt*     v=A(int,N),*a,*b,h=-1,r=h;for(F[f]=V
[f]=v;     ++h<f;)if(V[h][p]==q){if(s+1&&E(p
,q,V[h][q     ],s)<1E-4){for(a=F[g],b=F[h];N
>++r;v[r]=q+     1?a[q]-r?q:b[p]-r?p:-1:p)p=
a[r],q=b[r];for     (r=0;r<f;r++)F[r]==a||F[
r]==b?F[r]=v:0;};;     return f;}for(h=0;h<N
;v[h++]=-1)r=h-p&&h-q     &&(r<0||E(p,q,r,h)
<0)?h:r;v[v[v[p]=q]=r]=p     ;return G(r,q,p
,f,G(p,r,q,f,G(p,q,s,g,f+1)     ));}char *T;
int main(void) {H=(W=S)*2;T=A(     char,(H*W
+4));for(srand(t=(int)time(0));i=     scanf(
"%lf,",P=(Q=(double*)realloc(Q,(N+1)     *s\
izeof(double)))+N),i>=0;)i?c+=*P**P,1<N
++%3?o(c),b=b<s?s:b,c=0:0:scanf("%*s");for
(P=A(double,N*2);j<N;)Q[j++]/=b;o(U);I=
p/1E3;J=q/1E3;K=U;L=U;N/=3;F=A(int*,     4*N
);V=F+2*N;for(;u==v;){for(j=u=m=n     =0;j<3
*N;j++)P[j]=Q[j]+(U)/1E5;for(;     m<N;m++)u
=P[u*3]>P[m*3]?m:u;for(v=!u     ;n<N;n++)v=B
(u,v,n)>0?n:v;}for(puts(     "\x1b[2J"),M=G(
u,v,-1,-1,0);;K+=I+0,     L+=J){for(i=4;i<W*
H/2+3;T[++i]=j=0)T     [i]=i%W-3?32:10;for(;
j<M;j++){for(n=     k=0;F[j][m=n]<0;)n++;for
(;u=F[j][m]*     3,o(K=K<-1?K+2:K>1?K-2:K),c
=z=9*p,b=     9*q,o(L=L<-1?L+2:L>1?L-2:L),a=
x=b*q,     y=b*=p,d=x-X,e=y-Y,f=z-Z,o(d*d+e*
e+f     *f),p=C,q=C,r=C,k+=2,m=F[j][m],m-n;)
     ;for(p=n=0;n<k;n+=2)p+=P[n]*(P[(n+3)%k]
  -P[(n+k-1)%k]);for(q=time(0)<t+3;(q||p>=0)
     &&n;){a=P[n%k];b=P[n%k+1];c=P[n-=2];d=P
        [n+1];e=d-b;i=e*e>(c-a)*D(b,c)0>D(c,
           b)for(;c-a&&u<c+.5;0<=w&&w<W-1&&0
              <=m&&m<H?v=m/2*W+w+4,T[v]="',"
                 ";;;,;'"[T[v]%8^m%2]:0)m=v=
                    (d-b)*(u-a)/(c-a)+b+0.5,
                       w=i?m=u++,v:u++,u=u<c
                          &&q?c+0.5:u;}}puts
                             (T);nanosleep(&
                                R,0);X=x;Y=y
                                   ;Z=z;}}/*
                                      IOCCC*
                                         \*/

使い方

動画でどうぞ。

D

解説

端末上で動く凸多面体ビューアです。

1. 3 次元の頂点データを読み込む

2. 凸包を計算する

3. 端末上にレンダリングする

という単純なものです。

凸包計算は 3 次元 gift-wrapping アルゴリズムでやってます。ほぼ同一平面上の面を 1 つの面にマージすることで、四角形以上の面をきちんとサポートしてます (三角形 2 つとかで描かない) 。これのおかげでサッカーボールがサッカーボールらしくレンダリングされます。点が重複しているとか、同一平面上に点があるとか、コーナーケースにもまあまあ堅牢に動作するはずです。*5

3D レンダリングとかは普通です。ちょっとした工夫として、ドットを書くのに

T[v]="',;;;,;'"[T[v]%8^m%2]

という、謎の代入文を使ってます。あと、カメラを球面螺旋の軌道に沿って動かしています。

さらに以下のような小ネタ。

  • 意外にも math.h を使わない (cos と sqrt を自力計算しているだけだけど)
  • コード形状は正四面体の展開図 (入力に使うと正四面体が出てくる)
  • 画面サイズはマクロで調整可能
  • いろんな多面体のデータをつけてみた

狙いと戦略

最近の IOCCC は難しげなアルゴリズムが通りやすい→ロバストな凸包計算って難しいよね、という着想から作ったのですが、あまり変態的な方向に発想が広がらず、小さくまとまってしまいました。これが評価されたっぽいのは正直予想外でした。形状以外、いたって普通の C コードなので。まあ 3D のインパクトなのかなあ。

*1:この式は試行錯誤+総当たりで見つけました。

*2ワンライナーでは #include <math.h> ができない。

*3:この近似値は Stern-Brocot tree を使って見つけました。

*4:厳密にはこれは未定義挙動ですが、まあ大概の環境でこうなるんじゃないですかと……。詳しくはドキュメントを参照。

*5:専門用語で random perturbation という手法でコーナーケースをつぶしています。具体的には点を乱数でずらしているだけ。

2014-01-04

[][] The 22nd IOCCC の結果が公開されました

C 言語のプログラムの汚さで競い合うプログラミングコンテストThe 22nd International Obfuscated C Code Contest の今年の結果が公開されました。

http://www.ioccc.org/years.html#2013

相変わらずの変態ぞろいですのでぜひご覧ください。既報の通り、ぼくは以下の 4 つの賞を貰いました。

それぞれ順次紹介していきたいと思います。


[][] The 22nd IOCCC: Most lazy SKIer のエントリ

ref: http://ioccc.org/2013/endoh1.c

#ifndef SKI
#define A(x)B(x##0)B(x##1)B(x##2)B(x##3)B(x##4)B(x##5)
#define B(x)C(x##0)C(x##1)C(x##2)C(x##3)C(x##4)C(x##5)
#define C(x)D(x##0)D(x##1)D(x##2)D(x##3)D(x##4)D(x##5)
#define D(x)Z(x##0)Z(x##1)Z(x##2)Z(x##3)Z(x##4)Z(x##5)
#define p(x)(*(*(*(*(*(*x)())())())())())()

#include <stdio.h>
#include <stdlib.h>

#define S (Y(s+6))
#define K (Y(s+4))
#define I (Y(s+2))




#define Z(x)\
f x;f Y(v);g\
   j;f \
   x##z(                              f\
    y){y        =y?!    x?x=          y:Y(     m(*(    w)&\
    x,((         g)y)  (0))    ):x;return y;    /*ab  c*/}
    /**/          typedef             void       *v ;int
    n=0;           typedef            v*         w;typed\
ef v(*g)();v     s[]=  {0,0,                    s+6,  s+2,
s+4,s,s+3,s+    5,s+    1};w                   m( v    l ,v




r){w    e=ma\
lloc    (siz\
eof(   v)*3
);*e  =r;e                                           [1
]=l;return      (e[2    ]=s,   e);}    /*de          fghi     jk*/    typ\
edef v(p(        p(p(  p(p(    p(p(    p(p(   p(p(f)))) )))    ))))  );A(
x)w   u(){        return n      --?m  (j(0           ),u(       )):s+3;}
w z(   w e)       {w a,b ,       c,d;for             (d         =e=m(e,0
);n=    (w)d[    2]-s  ,n?*       (n>1?                        n<4?  b:a:
c)?n    <2?c[   1]=m    (*a,      *c),                        *c=m    (*b,
                                 *c):
                                n>5?


  #undef Z
#define Z(x\
) &x    ##z,
a[1]=                                                               m(
 *a,!*d?        d[1]    =c=m   (0,0    ),n=   getchar(),n=          n<0?
    256:n,c      [2]=  s+6,    *d=u    ():*   d),*a=d[1]:    n<5?n<3?n=z(*
       a)-s,      putchar(      (255  <n)?         exit             (n-4
*64)    ,0:n      ),fflush       (stdout)        ,c[1               ]=
*b:((n-3?b:c     )[1]  =*a)       :(2[*        a=z(*a)+1,a
  ]=s+5),d      =e:0    :e;d      =d[1        ])c=b,b=a,a=
                                 d;a=
                                *(w*

                                      )e                               [1
                                     ];                                 ;;
     /*lm    no*/   return a;}f(     *h   [])(    )={A   (x)0};f Y(v    x)
      {g y  =(g)    h[n++] ;y(!     y?    exit(   puts   ("out of c"     ""
       "losure"          )),x       :x     );return(f         )y/*       pq
       r*/;}int        main         ()       {z(((g         )(S          S(
      j=(g  )S(S     (K S)K))(K(    S        I I))        (S(K(S I))(    S(
     K K)    (S(K   (S(S(K(Y(s+1     ))      )(S(        S S(K I)) (K   (Y
                                     (s     +5))                        ))
                                      ))   )K))                        )(





#endif

#if (!defined(__INCLUDE_LEVEL__) || !__INCLUDE_LEVEL__) && !defined(SKI)

K(I(I(I(S I I(S(K(S(S(K S)(S(S S S(K(S(K S)))(S(S S S(K(S(K S)))(S(K(S(S(K S)(S(S(K S)K)(K(S(S(K S)(S(K(S(S(S I(K K))(K K))))(S(K K)(S(S(K S)(S(K(S(S I(K K))))(S(K K)(S(S(K K))(K(S(S(S(S(K S)K)))I(S(S(K S)K)I)))))))(S(K K)(S(S(K K))(K(S(K(S(S(K S)K)I))(S(S(K S)K)(S I I(S(S(K S)K)I)))))))))))(S(K K)(S(K K)(S(S(K K))(K(S(K(S(S(K S)K)I))(S(S I I)I(S(S(K S)K)I)))))))))))))(S(K K)(S(K K)(S(K(S(S I(K(S(S I(K(K I)))(K S))))))K)))))(K(K(K K)))))(K(K(K(K I))))))))(S(K(S(K K)))(S(S(K S)(S(K K)(S(K S)(S(S(K K))I))))(K(S(K(S(S(K S)(S(K(S I))K))))(S(K K)K))))))(S(S I(K(S I I(S I I(S(S(K S)K)I)))))(K(K K)))S K K K I I I K K K I I I K K K I I I K K K I I K K K K K S K I I I K I K I I I K I K)I I I K I K I I I K I I I K I I S K I I I I I K I I I I I K I K I I I K I I I K I I S K I I)I K I K I I I K I K I I I K I K I I I K I I I K I I S K K K I I I K K K I I I K K K I I I K K K I I K K K K K S S K I I I K S)K I I K S K K K S K I I K S K I I I K S S K K K K K S K I I I I S K K K K K S K S K K K K K(K K))

#define SKI
#endif

#ifdef SKI
(Y(s)))))(0));return 0;}
#else
#define SKI
#endif

使い方

単体でもコンパイル・実行できるんですが、

$ gcc -o endoh1 endoh1.c
$ ./endoh1
@@@@@
@
@@@@@
    @
@@@@@

@   @
@  @
@@@
@  @
@   @

@@@@@  @@@   @@@   @@@   @@@
  @   @   @ @   @ @   @ @   @
  @   @   @ @     @     @
  @   @   @ @   @ @   @ @   @
@@@@@  @@@   @@@   @@@   @@@

これは本題ではありません。


このプログラムは、C コンパイラに Lazy K のコードを食わせていじめためのライブラリです。これがあれば、C コンパイラしかない状況で Lazy K を楽しむことができます。*1

Lazy K ってのは SKI コンビネータ遅延評価で云々という言語なんですが*2、要するに関数 3 つだけ (S と K と I) の難解言語です。見た目はこんな感じ。

K(S(S I(K(S(K(S I I(S(S(K S)K)I))) ... ))))

これの最初と最後に #include <endoh1.c> をくっつける。

#include <endoh1.c>

K(S(S I(K(S(K(S I I(S(S(K S)K)I))) ... ))))

#include <endoh1.c>

これだけで valid な C プログラムになります。この通り。

$ gcc -o hello -xc hello.lazy
$ ./hello
Hello, IOCCC!

変な行入れたら Lazy K じゃなくなるじゃないか!という Lazy K ファンの方もご安心を。Lazy K において # は行コメントですので、そのまま実行できます。

$ lazy hello.lazy
Hello, IOCCC!

つまり、Lazy K と C の polyglot (と言えなくもない) です。

解説

#define S (s)
#define K (k)
#define I (i)

マクロ定義することで

S (K I)

(s) ((k) (i))

となり、冗長な括弧をとると

s(k(i))

あれっこれ普通の C じゃん、というのが肝です。ここから苦労した点はいっぱいあって

結果、C コンパイラいじめの塊になりました。詳細はドキュメントを見てください。

なお、処理系部分は項書き換えっぽいアプローチで実装してます (コードの形状が示す通り) 。おかげでかなり小さくなっていると思う。

狙いと戦略

これは一番頑張った作品で、ネタにもコンパイラいじめ度にも自信ありました。が、掲載順位から察するに、それほど評価されなかった印象です。地味だからですかね。去年の金賞も地味なんだけどなあ。残念。


[][] The 22nd IOCCC: Most recyclable のエントリ

              /*@@@sssss8]][[[[a#@@sss0['w}8|v}a<{av}a@{av}j>~{v}j8|c[sa?|{8[|#~}
          [j#@ra>~}sa!{>}|#r0l}sao8}[a'f8|r'8[j?x[?@<[j?@[j?@[s?>|;[[[j!>b'8'a@<cb@>?
        c$kg_@<b#0pf<#keab{_b0|c0#d#0#|'o{i<!8dr,f_{#rg{baiderh{er0}|'{0{ic.df?'o|j{lim
       0'{i?#c0b|c#kg!}r!8lp1g!|i_ar<[#0g|h_}ieg>|_ah|sr<|i[[[}s#f@}[{@u~~~r@[|#|{ssss{a
      }|0~{?}|<{?}|qj?}s@[_}j0]][[[[a_@@@sssss<[[?>=sln5+a[so#,g-0aw;#*a>*abwa.*+da9=n?<6
      -'7%71>e_?>a[j;e=;scdet?>shd??a;5&6:=[ch@aw[sf;[#<[[j>k7__?>>d>==n'6+7*abcdnh3a_jhw
     b6;73;b#<ww<7bcw7d+;&i=cn?c>=#d5;8w3;nawn#<;;77__ra?8hi1abcww#>==<[;k7[wn7[=,>ab[a@s[
     ='b,.[8.?>>fdjn(_2$a8c8[[j_8.=B6+b8]]]]]]]]]j1;7_sj<[[af;7sjd][j_<7!=a>d7_j8d.ab[hybm
     ?>=;ei7aws1d!ebn                                                       _,?>0aka[#;5+7
     !?ac;7_wa7{;a3_                                                        bjcna>a<;bs8;7
     j-=cabh?97_sj['                                                  -5*j[!;5+a7[1wb[!wBb7w?0wb
     _?an+&e_|j'4a<7                                                  0v;7d.kd8wa?.=:a-wwm=:;[e5
     *-=fwn7rab[c.j#                                                    eaw#c>>>bml;mtdekssae
     zqtd[39<u_char*                                                      p=$,w[13997],*h=w,
     *q,*r_****_;#in                                                        clude_*ioccc*2
     013*_<stdio.h>_                                                         *--2013-ioc
     cc-2013-ioccc-2        013--                                             *_#define
                           @n(d);c                                              ((d)>
                            >8);c                                                 (
            d
          );*B=             32;B[   y=1]=22 .627400;       B[2]=16;_*-i       occc-2013 -ioccc
        -2013-io           ccc-201  *_int@a,b,d,e,s,t    ,g,z,y;double@f,    B[3],i,j,k,l;void
       @m(int@z){f         or(j=k=  l=y=1;y<99;y+=2+0)  l*=z*z*    .038553  ,k*=-y*(y+1),j+=l_
     k;i*=j;}int@c(        int@d){  return@    putchar (d)_255;    }intmain (){for(    ;*p;p++
    )*p<33?0:(*h++=*p      -32);q=  h;for(p     =w;p<w +823;p++)for(d=*p-56 ,e=-1+     0;++e<(
  d<00?5:d<6?d>4?160:30    :d>35?2  7<<(d-3    6):d_9* 6);q++)*q=d<0?*p>>e& 1:d<6||    q[d>35?
-108:d%9*-12-12];for(q=h   ;g++<61  56;q++)*  q?*q=*p-  4?e=*p+             +,e-32?e:0:r&&*r?g
%108<2?2:*r++:(r=r?p++:w,  2):0;n(  g=8*8187)n(g+8)n(1  6)n(19014)n(18758)   ;for(;s<10;s++)c(
     s<3?s:0)n(g+3)n       (67)for  (;t<65;)c(t++>0)      n(g-24)n(11)c(8      )n(612)n(656)n(
     257)n(4352)n(g+       0-20)n(  5*42);; for(;y          ++<207;)c(      y<3        1?y<19?
     y>6:30-y:y<47?y    <32||y>36?  16:0:y<                                 48?2:y%1  6*16+13-
     y_16)n(64*960)n   (g+5)n(4)n(  1)n(g+2                                 )n(8)n(257)n(0)n(
     2*8064)for(;b<4    04096;b++   ){e=32<                                   a?63-a:a;for(f
     =d=t=s=0;e>t;)e
     -=++t;e=t%2?e:t                                                        -e;;;for(d=a>3
     1?e=7-e,14-t-e:                                                        t-e;s<64;t=f-=
     i*B[!d+!e])z=b_                                                        64%82*8+s_8-4,
     y=b_5248*8+s%8+7                                                      ,i=z<0||z>647||
     y%11>9?1:q[h[z_6+y_11*108]*60+y%11*6+z%6]*2-1,m(s_8*2*d+d),m(s++%8*2*e+e);s=2+t*t;;fo
     r(d=2;s>3;s_=4)d*=2;;s=8<<(a?12:9);s-=d*2<<!!a*4;s|=t>0?t:t-1+d;c(s_256)?c(0):0;c(s)?
     c(0):0;if(a++>62){n(g-8+b_64%8)a=0;}}n(g+1)return@0+0;}*/ /*IOCCC*/#include<stdio.h>
      char*p,w[13997],*h=w,*q,*r;int d,e,g;int main(){for(;e<3583;e++>15&&e<3582&&d>32?*h
       ++=d-95?d:47:0)d=getchar();q=h;for(p=w;p<w+823;p++)for(d=*p-88,e=-1;++e<(d<0?5:d<
        6?d>4?160:30:d>35?27<<(d-36):d/9*6);q++)*q=d<0?*p>>e&1:d<6||q[d>35?-108:d%9*-12
          -12];for(q=h+108;g++<5995;)putchar(g%109<1?10:*q++?*p-36?e=*p++,e-64?e:32:r
              /*IOCCC2013*/&&*r?g%109%108<2?34:*r++:(r=r?p++:w,34):32);return 0;}

使い方

まず普通にコンパイルし、以下のように実行します。

$ gcc -o endoh2 endoh2.c
$ ./endoh2 < endoh2.c > jpeg.c

すると本番のプログラムが出てきます。

char*p="@@@sssss8]][[[[a#@@sss0['w}8|v}a<{av}a@{av}j>~{v}j8|c[sa?|{8[|#~}[j#@ra>~}sa!{>}|#r0l}sao8}[a'f8|r'"
"8[j?x[?@<[j?@[j?@[s?>|;[[[j!>b'8'a@<cb@>?c$kg/@<b#0pf<#keab{/b0|c0#d#0#|'o{i<!8dr,f/{#rg{baiderh{er0}|'{0{"
"ic.df?'o|j{lim0'{i?#c0b|c#kg!}r!8lp1g!|i/ar<[#0g|h/}ieg>|/ah|sr<|i[[[}s#f@}[{@u~~~r@[|#|{ssss{a}|0~{?}|<{?"
"}|qj?}s@[/}j0]][[[[a/@@@sssss<[[?>=sln5+a[so#,g-0aw;#*a>*abwa.*+da9=n?<6-'7%71>e/?>a[j;e=;scdet?>shd??a;5&"
"6:=[ch@aw[sf;[#<[                                                                       [j>k7//?>>d>==n'6+"
"7*abcdnh3a/jhw                                                                             b6;73;b#<ww<7bc"
"w7d+;&i=cn?c                                                                                >=#d5;8w3;nawn"
"#<;;77//ra?                                                                                   8hi1abcww#>="
"=<[;k7[wn7                                                                                     [=,>ab[a@s["
"='b,.[8.?>                                                                                     >fdjn(/2$a8"
"c8[[j/8.=                                                                                       B6+b8]]]]]"
"]]]]j1;7/              sj<[[af;7sjd][j/<7!=a>d7/j8d.ab[hybm?>=;ei7aws1d!ebn/,?>0ak              a[#;5+7!?a"
"c;7/wa7{;             a3/bjcna>a<;bs8;7j-=cabh?97/sj['-5*j[!;5+a7[1wb[!wBb7w?0wb/?a             n+&e/|j'4a"
"<70v;7d.k             d8wa?.=:a-wwm=:;[e5*-=fwn7rab[c.j#eaw#c>>>bml;mtdekssaezqtd[3             9<u/char*p"
"=$,w[1399             7],*h=w,*q,*r/****/;#include/*ioccc*2013*/<stdio.h>/*-                           -20"
"13-ioccc-             2013-ioccc-2013--*/#define@n(d);c((d)>>8);c(d);*B=32;B                           [y="
"1]=22.627             400;B[2]=16;/*-ioccc-2013-ioccc-2013-ioccc-201*/int@a,b,                       d,e,s"
",t,g,z,y;             double@f,B[3],i,j,k,l;void@m(int@z){for(j=k=l=y=1;y<99;y+=                   2+0)l*="
"z*z*.0385             53,k*=-y*(y+1),j+=l/k;i*=j;}int@c(int@d){return@putchar(d)/2               55;}int@m"
"ain(){;;f             or(;*p;p++)*p<33?0:(*h++=*p-32);q=h;for(p=w;p<w+823;p++)for(d=           *p-56,e=-1;"
"++e<(d<0?             5:d<6?d>4     ?160:30:d>35?27<<(d-36):d/9*6);q++)*q=d<0?*p>>e&1         :d<6||q[d>35"
"?-108:d%9*-12-12];for(q=h;g++<       6156;q++)*q?*q=*p-4?e=*p++,e-32?e:0:r&&*r?g%108<2?     2:*r++:(r=r?p+"
"+:w,2):0;n(g=8*8187)n(g+8)n(16)     n(19014)n(18758);for(;s<10;s++)c(s<3?s:0)n(g+3)n(67)f or(;t<65;)c(t++>"
"0)n(g-24)n(11)c (8)n(612)n(656)n(257)n(4352)n(g+0-20)n(5*42);;for(;y++<207;)c(y<31?y<19?y>6:30-y:y<47?y<32"
"||y>36?16:0:y     <48?2:y%16*16     +13-y       /       16)n(64*9            60)n(g+5)        n      (4)n("
"1)n(g+2)n(8        )n(257)n(0)       n(2*                 8064)                for(;                 b<404"
"096;b++){e           =32<a?63-       a:a;                  for       (f=d       =t=                  s=0;e"
">t;e-=++              t);e=t%2       ?e:t       -e;;       ;f        or(d        =a       >31?       e=7-e"
",14-t-e                 :t-e;s       <64;       t=f-=      i*                    B[      !d+!e       ])z=b"
"/64%8                     2*8+       s/8-       4,y=b      /5                    24      8*8+s       %8+7,"
"i=z                        <0|       |z>6       47||       y%1       1>9?1:q[h[z/6+                  y/11*"
"108                         ]*       60+y                  %11                  *6+z                 %6]*2"
"-1,m(s/8*             2*d+d),m       (s++                 %8*2*e               +e);s=2               +t*t;"
";for(d=2;             s>3;s/=4       )d*=       2       ;;s=8<<(a?           12:9);   s-=d*2<<       !!a*4"
";s|=t>0?t             :t-1+          d;c(       s/256)?c(0):0;c(s)?c(0):0;if(a++>62       ){n        (g-8+"
"b/64%8)a=             0;}}           n(g+       1)return@0+0;}",w[13997],*h=w,*q,*r                 /****/;
#include/*             ioccc         *2013       */<stdio.h>/*--2013-ioccc-2013-ioccc-              2013--*/
#define n(             d);c((d)>>8);c(d);*B=32;B[y=1]=22.627400;B[2]=16;/*-ioccc-2013-ioccc-2013-ioccc-201*/
int a,b,d,             e,s,t,g,z,y;double f,B[3],i,j,k,l;void m(int z){for(j=k=l=y=1              ;y<99;y+=2
+0)l*=z*z*             .038553,k*=-y*(y+1),j+=l/k;i*=j;}int c(int d){return putchar(             d)/255;}int
 main(){;;             for(;*p;p++)*p<33?0:(*h++=*p-32);q=h;for(p=w;p<w+823;p++)for(             d=*p-56,e=-
1;++e<(d<0             ?5:d<6?d>4?160:30:d>35?27<<(d-36):d/9*6);q++)*q=d<0?*p>>e&1:d             <6||q[d>35?
-108:d%9*-             12-12];for(q=h;g++<6156;q++)*q?*q=*p-4?e=*p++,e-32?e:0:r&&*r?             g%108<2?2:*
r++:(r=r?p              ++:w,2):0;n(g=8*8187)n(g+8)n(16)n(19014)n(18758);for(;s<10;              s++)c(s<3?s
:0)n(g+3)n                                                                                       (67)for(;t<
65;)c(t++>0                                                                                     )n(g-24)n(11
)c(8)n(612)                                                                                     n(656)n(257)
n(4352)n(g+0                                                                                   -20)n(5*42);;
for(;y++<207;                                                                                 )c(y<31?y<19?y
>6:30-y:y<47?y<                                                                             32||y>36?16:0:y<
48?2:y%16*16+13-y/                                                                       16)n(64*960)n(g+5)n
(4)n(1)n(g+2)n(8)n(257)n(0)n(2*8064)for(;b<404096;b++){e=32<a?63-a:a;for(f=d=t=s=0;e>t;e-=++t);e=t%2?e:t-e;;
;for(d=a>31?e=7-e,14-t-e:t-e;s<64;t=f-=i*B[!d+!e])z=b/64%82*8+s/8-4,y=b/5248*8+s%8+7,i=z<0||z>647||y%11>9?1:
q[h[z/6+y/11*108]*60+y%11*6+z%6]*2-1,m(s/8*2*d+d),m(s++%8*2*e+e);s=2+t*t;;for(d=2;s>3;s/=4)d*=2;;s=8<<(a?12:
9);s-=d*2<<!!a*4;s|=t>0?t:t-1+d;c(s/256)?c(0):0;c(s)?c(0):0;if(a++>62){n(g-8+b/64%8)a=0;}}n(g+1)return 0+0;}

これをまた実行すると

$ gcc -o jpeg jpeg.c
$ ./jpeg > jpeg.jpg

以下のような jpg 画像が出てきます。

それだけ。

解説

qng 画像qif 画像と同じネタです。すみません。

一応、現時点で世界最小の jpeg エンコーダじゃないかと思います。jpeg ってヘッダに色々書かないと行けないし、ジグザグスキャンとか離散コサイン変換とかハフマンエンコーディングとかやることが多くて大変なんです。

それでもサイズ制限を完全にオーバーしたので、チート気味に回避してます。というのは、今回初めてサイズチェッカが審査員から提供されたのですが、それが微妙にバグってた (ルール上はコメント含めて 2KB なのに、チェッカはコメント含めず 2KB になってた) ので、本番プログラムをコメントに埋めて、最初のプログラムはコメントをデコードする感じ。(ちなみに、IOCCC ではチートが推奨されてます)

あと、jpeg のハフマンエンコーディングチートしていて*3、生成される jpeg ファイルは同等な PBM ファイルの 16.4 倍もでかい。(審査員調べ)

一応、正統派の圧縮もがんばっていて、たとえばフォントと形状データには LZ77 風の圧縮をかけてます。

狙いと戦略

1 つくらい Quine ネタをやるかー、と思って作りました。しかし特にひねりがなく、ネタのわりに超巨大。

記念受験のつもりで送ったら意外にも通りましたが、正直あんまし満足な出来じゃないです。次回はもうちょっと頑張りたい。

*1:普通に C で Lazy K インタプリタを書けばいいって?あーあー聞こえない

*2:詳しくは公式サイトを見てください。

*3:ビット処理したくなかったので、コードがバイトにアラインするように巧妙に作ったハフマンテーブルを定義してる。圧縮効果は全くない。

2013-11-24

[][] IOCCC2012 endoh1.c のデモ動画

昨年の IOCCC に入賞した流体シミュレータの動画を作って公開しときました。

D

今年の IOCCC のやつもソースコードが公開されたら動画にしたい。

2013-11-17

[][] The 22nd IOCCC に入賞したよ

今年も IOCCC に入賞しました。史上初の 4 冠 *1 です。嬉しい。

昨年は 2 作品投稿して 2 冠だったので、今年は 4 作品で 4 冠 *2 を目指したところ、なんと狙い通りになりました。一応もう 1 つ akari.c 的なネタがあったんですが、著作権を気にして自重しました。こういうのはフェアユースなのかなあ。

今年は他に 3 冠の人と 2 冠の人が 1 人ずついて、入賞作品は 15 件だけど作者は全部で 9 人という、独占禁止法にひっかかりそうな結果でした。国別では、US 6 人で 8 件、JP 1 人 で 4 件、FR 1 人で 2 件、CN 1 人で 1 件、と US 大勝利。

なお、実質的な優勝である Best of show も US の 3 冠の人が取りました。悔しい。来年は数撃つより、Best of show 狙いたいなあ。(無理)

作品は今年中には公開予定とのこと *3 で、公開後にまた自分の作品の解説とか書きます。

*1IOCCC の審査は、「作者情報を見ずに作品だけを見て 15 個程度の入賞作品を決める」というプロセスなので、同じ大会で同じ作者の作品が複数受賞しうる。逆方向の single blind review というのかな?

*2:3 冠は 1998 年と 2006 年に前例がある。

*3:審査員からのコメントを受けて各作者が改良をする期間がある。camera ready みたいな。

2012-10-18

[][] The 21st IOCCC の結果が公開されました

C 言語のプログラムの汚さで競い合う有名なプログラミングコンテスト IOCCC の今年の結果が公開されました。

ref: http://www.ioccc.org/years.html#2012

目を見張る変態ぞろいですので、ぜひご覧ください。個人的には、deckmynhamanohoukangtromp あたりがお気に入りです。nyaruko は内容より spoiler がすごい。あれエディタでアタリなしで描いてんのかよ、という。

ぼくのプログラムが 2 つ入賞していますのでご紹介。以下、ネタバレ+自慢エントリなので嫌な人は見ないで!

[][] The 21st IOCCC: PiE in the sky award のエントリ

ref: http://www.ioccc.org/2012/endoh2/endoh2.c

ref: http://www.ioccc.org/2012/endoh2/hint.html

#include<stdio.h> /******** SpigotQuine -- usage: ./spigot [pi or e] ********/
char*s="G1%%xJ{;Q7wunmuGuu%%uu#include<stdio.h>/*Spigot_Quine*/#include<stdli"
"b.h>/*_IOCCC2012_*/int*e,"    "i,j,k,n"     ";char*q"    ",*a,*d,*z,*p=%s%c;"
"int" "%cmain(){a=calloc("                                 "1,1e4+n*2);;for(*"
"a=\0@3,z=d=a+n+1,j=n*8-7;"    "k=0,j-1"     ";j-=2){"    "for(a[1]+=2;--z-a;"
"*z=k%%10,k/=10)k+=j/2**z;;for(;k=k%%j*"     "10+*++z,z<d;)*z=k/" "j;;\0@2,z="
"d=a+n*2,*z=1,j=0;++j<n;){for(;k=k%%"           "j*10+*z,a-z;*z"   "--=k/j)a+"
"+;for(k=0;z-d;*a--=k%%10,k/=10)k+"               "=*++z+*a\0"     "@;}d+=spr"
"intf(q=d-20,p,p,34,32,n+1)+2;;;;"                 "for(n=n*2"     "0-400;k<n"
";++k%%n?j=!puts("                                                 "d):(d[j]="
"47,d++,d[j-2"                                                     "]=42),k%%"
"20<1?puts(d"                                                      "-1),a++:0"
"){for(i=-1"                                                       ";i++<32;!"
"*z?q[662]"          "=0,z=q+207:"                 "*z+z[1]<6"     "5?z+=11:*"
"z==34?p=0"         ":0)d[i]=((k/2"               "0-1?275*q["     "*a+10]-8*"
"q[*a+0]-8"         ":128)>>(i/11+k/"           "4%%5*3))&1?k"     "/3*!j&&p?"
"j=34:(j="           "i+1,*z++):32;k/3*"     "j--&&p?d[z--,j]=3"   "4:0;}}int"
"*y,n=%d;/*..~",*f="nnLa5~z23~|22t$q(s82r&q(s82q'q(s8;q(s8;q(s8:" "r(s8:r(s8:"
"q)s89r)sLr#t+" "sLx,uJw-yGu/wnnnU",*g="nnLa<z::t$u88t(u67t*u57s,t56t,t56~v56"
"tF6tF6tF8t1p"   "Nu/qOv+rS}Xxnng";int main(int m,char**v){char a[2012],b[2012
],*p=a,*r=m>1     &&*v[1]=='e'?g:f,*q=b,*t=r;;sprintf(a,"%s%s%s",s,r==g?s+281:
s+168,s+386);     sprintf(b,a+22,a,34,32,24);for(sprintf(a,"%.33s/*%.28s*/%.3"
"3s/*%.28s*/%"   ".33s\"%s*/",b,b+66,b+33,b+76,b+66,b+99);*r;r++){;for(m=0;m++
<(*r-34)%77;*q++=*r>111?32:*p++)(q-b)%66<1?*q++=10:0;*r-110&&*r-126&&r-t<(t-g?
62:45)?*q++=34,((q-b)%66<1?*q++=10,*q++=34:0):0;}*q=0;puts(b+1);}/*IOCCC2012*/

解説

蛇口です。なんで蛇口かは後で説明するとして、とりあえずコンパイル・実行すると……

$ gcc -o endoh2 endoh2.c
$ ./endoh2

#include<stdio.h>/*Spigot_Quine*//*int*e,i,j,k,n;char*q,*a,*d,**/
#include<stdlib.h>/*_IOCCC2012_*//*k,n;char*q,*a,*d,*z,*p=G1%%x*/
int*e,i,j,k,n;char*q,*a,*d,*z,*p="G1%%xJ{;Q7wunmuGuu%%uu#include"
"<stdio.h>/*Spigot_Quine*/#include<stdlib.h>/*_IOCCC2012_*/int*e"
",i,j,k,n;char*q,*a,"                          "*d,*z,*p=%s%c;in"
"t%cmain(){a=callo"                            "c(1,1e4+n*2);;fo"
"r(*a=3,z=d=a+n+1"     ",j"  "=n*8-7"    ";k=0,j-1;j-=2){for(a[1"
"]+=2;--z-a;*z=k%"   "%10,"  "k/=10)"    "k+=j/2**z;;for(;k=k%%j"
"*10+*++z,z<d;)*z"  "=k/j;"  ";;}d+="    "sprintf(q=d-20,p,p,34,"
"32,n+1)+2;;;;for(n=n*20-4"  "00;k<n"    ";++k%%n?j=!puts(d):(d["
"j]=47,d++,d[j-2]=42),k%%2"  "0<1?pu"    "ts(d-1),a++:0){for(i=-"
"1;i++<32;!*z?q[662]=0,z="   "q+207:"    "*z+z[1]<65?z+=11:*z==3"
"4?p=0:0)d[i]=((k/20-1?27"   "5*q[*a"    "+10]-8*q[*a+0]-8:128)>"
">(i/11+k/4%%5*3))&1?k/3*"  "!j&&p?j"    "=34:(j=i+1,*z++):32;k/"
"3*j--&&p?d[z--,j]=34:0;"   "}}int*y"    ",n=%d;/*..~";int main()
{a=calloc(1,1e4+n*2   )     ;;for(*a=    3,z=d=a+n+1,j=n*8-7;k=0,
j-1;j-=2){for(a[1]         +=2;--z-a;      *z=k%10,k/=10)k+=j/2**
z;;for(;k=k%j*10+*        ++z,z<d;)*z          =k/j;;;}d+=sprintf
(q=d-20,p,p,34,32,n      +1)+2;;;;for(        n=n*20-400;k<n;++k%
n?j=!puts(d):(d[j]=47,d++,d[j-2]=42),k%20<1?puts(d-1),a++:0){for(
i=-1;i++<32;!*z?q[662]=0,z=q+207:*z+z[1]<65?z+=11:*z==34?p=0:0)d[
i]=((k/20-1?275*q[*a+10]-8*q[*a+0]-8:128)>>(i/11+k/4%5*3))&1?k/3*
!j&&p?j=34:(j=i+1,*z++):32;k/3*j--&&p?d[z--,j]=34:0;}}int*y,n=24;

πが出てきます。これはまた C のプログラムになっていて、実行すると……

$ ./endoh2 > pi.c
$ gcc -o pi pi.c
$ ./pi

#include<stdio.h>/*Spigot_Quine*/
#include<stdlib.h>/*_IOCCC2012_*/
int*e,i,j,k,n;char*q,*a,*d,*z,*p=
"G1%%xJ{;Q7wunmuGuu%%uu#include<"
                      "stdio.h>/"
                      "*Spigot_Q"
                      "uine*/#in"
                      "clude<std"
"lib.h>/*_IOCCC2012_*/int*e,i,j,"
"k,n;char*q,*a,*d,*z,*p=%s%c;int"
"%cmain(){a=calloc(1,1e4+n*2);;f"
"or(*a=3,z=d=a+n+1,j=n*8-7;k=0,j"
                      "-1;j-=2){"
                      "for(a[1]+"
                      "=2;--z-a;"
                      "*z=k%%10,"
"k/=10)k+=j/2**z;;for(;k=k%%j*10"
"+*++z,z<d;)*z=k/j;;;}d+=sprintf"
"(q=d-20,p,p,34,32,n+1)+2;;;;for"
"(n=n*20-400;k<n;++k%%n?j=!puts("

                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
           "d):(d[j]="           
           "47,d++,d["           
           "j-2]=42),"           
           "k%%20<1?p"           
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 

           "uts(d-1),"           
           "a++:0){fo"           
           "r(i=-1;i+"           
           "+<32;!*z?"           
"q[662]=0,z=q+207:*z+"           
"z[1]<65?z+=11:*z==34"           
"?p=0:0)d[i]=((k/20-1"           
"?275*q[*a+10]-8*q[*a"           
           "+0]-8:128"           
           ")>>(i/11+"           
           "k/4%%5*3)"           
           ")&1?k/3*!"           
           "j&&p?j=34"           
           ":(j=i+1,*"           
           "z++):32;k"           
           "/3*j--&&p"           
"?d[z--,j]=34:0;}}int*y,n=%d;/*."
".~";int main(){a=calloc(1,1e4+n*
2);;for(*a=3,z=d=a+n+1,j=n*8-7;k=
0,j-1;j-=2){for(a[1]+=2;--z-a;*z=

k%10,k/=10)           k+=j/2**z;;
for(;k=k%j*           10+*++z,z<d
;)*z=k/j;;;           }d+=sprintf
(q=d-20,p,p           ,34,32,n+1)
+2;;;;for(n           =n*20-400;k
<n;++k%n?j=           !puts(d):(d
[j]=47,d++,           d[j-2]=42),
k%20<1?puts           (d-1),a++:0
){for(i=-1;i++<32;!*z?q[662]=0,z=
q+207:*z+z[1]<65?z+=11:*z==34?p=0
:0)d[i]=((k/20-1?275*q[*a+10]-8*q
[*a+0]-8:128)>>(i/11+k/4%5*3))&1?
                      k/3*!j&&p?j
                      =34:(j=i+1,
                      *z++):32;k/
                      3*j--&&p?d[
                      z--,j]=34:0
                      ;}}int*y,n=
                      25;/*..~int
                      *e,i,j,k,*/

縦書きで 3.14 になります。やはりこれも C プログラムで、実行すると……

$ ./pi > 314.c
$ ./314

#include<stdio.h>/*Spigot_Quine*/
#include<stdlib.h>/*_IOCCC2012_*/
int*e,i,j,k,n;char*q,*a,*d,*z,*p=
"G1%%xJ{;Q7wunmuGuu%%uu#include<"
                      "stdio.h>/"
                      "*Spigot_Q"
                      "uine*/#in"
                      "clude<std"
"lib.h>/*_IOCCC2012_*/int*e,i,j,"
"k,n;char*q,*a,*d,*z,*p=%s%c;int"
"%cmain(){a=calloc(1,1e4+n*2);;f"
"or(*a=3,z=d=a+n+1,j=n*8-7;k=0,j"
                      "-1;j-=2){"
                      "for(a[1]+"
                      "=2;--z-a;"
                      "*z=k%%10,"
"k/=10)k+=j/2**z;;for(;k=k%%j*10"
"+*++z,z<d;)*z=k/j;;;}d+=sprintf"
"(q=d-20,p,p,34,32,n+1)+2;;;;for"
"(n=n*20-400;k<n;++k%%n?j=!puts("

                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
           "d):(d[j]="           
           "47,d++,d["           
           "j-2]=42),"           
           "k%%20<1?p"           
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 

           "uts(d-1),"           
           "a++:0){fo"           
           "r(i=-1;i+"           
           "+<32;!*z?"           
"q[662]=0,z=q+207:*z+"           
"z[1]<65?z+=11:*z==34"           
"?p=0:0)d[i]=((k/20-1"           
"?275*q[*a+10]-8*q[*a"           
           "+0]-8:128"           
           ")>>(i/11+"           
           "k/4%%5*3)"           
           ")&1?k/3*!"           
           "j&&p?j=34"           
           ":(j=i+1,*"           
           "z++):32;k"           
           "/3*j--&&p"           
"?d[z--,j]=34:0;}}int*y,n=%d;/*."
".~";int main(){a=calloc(1,1e4+n*
2);;for(*a=3,z=d=a+n+1,j=n*8-7;k=
0,j-1;j-=2){for(a[1]+=2;--z-a;*z=

k%10,k/=10)           k+=j/2**z;;
for(;k=k%j*           10+*++z,z<d
;)*z=k/j;;;           }d+=sprintf
(q=d-20,p,p           ,34,32,n+1)
+2;;;;for(n           =n*20-400;k
<n;++k%n?j=           !puts(d):(d
[j]=47,d++,           d[j-2]=42),
k%20<1?puts           (d-1),a++:0
){for(i=-1;i++<32;!*z?q[662]=0,z=
q+207:*z+z[1]<65?z+=11:*z==34?p=0
:0)d[i]=((k/20-1?275*q[*a+10]-8*q
[*a+0]-8:128)>>(i/11+k/4%5*3))&1?
                      k/3*!j&&p?j
                      =34:(j=i+1,
                      *z++):32;k/
                      3*j--&&p?d[
                      z--,j]=34:0
                      ;}}int*y,n=
                      25;/*..~int
                      *e,i,j,k,n;

           char*q,*a,*
           d,*z,*p=%s%
           c;int%cmain
           (){a=calloc
(1,1e4+n*2);;for(*a=3,
z=d=a+n+1,j=n*8-7;k=0,
j-1;j-=2){for(a[1]+=2;
--z-a;*z=k%%10,k/=10)k
           +=j/2**z;;f
           or(;k=k%%j*
           10+*++z,z<d
           ;)*z=k/j;;;
           }d+=sprintf
           (q=d-20,p,p
           ,34,32,n+1)
           +2;;;;for(n
=n*20-400;k<n;++k%%n?j=!puts(d):(
d[j]=47,d++,d[j-2]=42),k%%20<1?pu
ts(d-1),a++:0){for(i=-1;i++<32;!*
z?q[662]=0,z=q+207:*z+z[1]<65?z*/

3.141 になります。以下同様に、1 桁ずつ増えていきます。

ちなみに最初のプログラムに引数 e を渡すと……

$ ./endoh e

#include<stdio.h>/*Spigot_Quine*//*int*e,i,j,k,n;char*q,*a,*d,**/
#include<stdlib.h>/*_IOCCC2012_*//*k,n;char*q,*a,*d,*z,*p=G1%%x*/
int*e,i,j,k,n;char*q,*a,*d,*z,*p="G1%%xJ{;Q7wunmuGuu%%uu#include"
"<stdio.h>/*Spigot_Quine*/#include<stdlib.h>/*_IOCCC2012_*/int*e"
",i,j,k,n;char*q,*a,*d,*z,*"           "p=%s%c;int%cmain(){a=cal"
"loc(1,1e4+n*2);;for(*a=2"     ",z"      "=d=a+n*2,*z=1,j=0;++j<"
"n;){for(;k=k%%j*10+*z,"     "a-z;*z"      "--=k/j)a++;for(k=0;z"
"-d;*a--=k%%10,k/=10)k"     "+=*++z+*"      "a;}d+=sprintf(q=d-2"
"0,p,p,34,32,n+1)+2;;;"    ";for(n=n*2"     "0-400;k<n;++k%%n?j="
"!puts(d):(d[j]=47,d+"     "+,d[j-2]=4"     "2),k%%20<1?puts(d-1"
"),a++:0){for(i=-1;i+"                      "+<32;!*z?q[662]=0,z"
"=q+207:*z+z[1]<65?z+"     "=11:*z==34?p=0:0)d[i]=((k/20-1?275*q"
"[*a+10]-8*q[*a+0]-8:"     "128)>>(i/11+k/4%%5*3))&1?k/3*!j&&p?j"
"=34:(j=i+1,*z++):32;"     "k/3*j--&&p?d[z--,j]=34:0;}}int*y,n=%"
"d;/*..~";int main(){a=     calloc(1,1e4+n* 2);;for(*a=2,z=d=a+n*
2,*z=1,j=0;++j<n;){for(      ;k=k%j*10+*z,  a-z;*z--=k/j)a++;for(
k=0;z-d;*a--=k%10,k/=10)       k+=*++z+*   a;}d+=sprintf(q=d-20,p
,p,34,32,n+1)+2;;;;for(n=n*              20-400;k<n;++k%n?j=!puts
(d):(d[j]=47,d++,d[j-2]=42),k%         20<1?puts(d-1),a++:0){for(
i=-1;i++<32;!*z?q[662]=0,z=q+207:*z+z[1]<65?z+=11:*z==34?p=0:0)d[
i]=((k/20-1?275*q[*a+10]-8*q[*a+0]-8:128)>>(i/11+k/4%5*3))&1?k/3*
!j&&p?j=34:(j=i+1,*z++):32;k/3*j--&&p?d[z--,j]=34:0;}}int*y,n=24;

これの実行結果は、もうお分かりですよね。ネイピア数が出てきます。

蛇口マークなのは、こういう数学定数を次々に列挙していく spigot (=蛇口) algorithm にちなんだものでした。*1


狙いと戦略

ぼくが超絶技巧プログラミング、特に Quine を始めたきっかけの 1 つは、IOCCC 2000 の有名 winner であるあくそくざんに出会ったことなのです。なので IOCCC にはぜひ Quine ネタで入賞したかった。

しかし IOCCC の FAQ には、「審査員が飽きてるので勝ち目がないネタ (MUCH HARDER to win)」として self reproducing program が挙がってました。

そこで、開きなおって嫌がらせ的に、審査員が飽きてるネタを融合させることにしました。融合させるネタには、相性のよさそうなπと e の計算を選びました。

実装自体はわりと普通の Quine + π/e 計算です。2 種類の形状で動くようにするのと、マジック文字列 "G1%xJ{;Q7wunmuGuu%uu" *2を作るのがちょっと大変だった。あとは、guideline によると portable なコードが好まれるらしいので、gcc と clang で警告オプション (-Wall -W -Wextra -pedantic) をのせても何も言われないようにしました。

remark (コードにつける紹介文) にも結構気を使いました。怪しい書き出しとか、知的好奇心をくすぐりそうなキーワードを入れて、審査員の気を引けるように。実際、入賞決定後に審査員から「Bezout's identity の解説をつけてくれ」と言われました。

使い古されたネタにも関わらず入賞できたのは、この辺のこずるい目論見がうまくいった結果かと自画自賛してます。しかし PiE in the sky award とはうまいこと言う。審査員が賞名に面白いダジャレを思いつくかどうかが最大の鍵かもしれない。


[][] The 21st IOCCC: Most complex ASCII fluid のエントリ

ref: http://www.ioccc.org/2012/endoh1/endoh1.c

ref: http://www.ioccc.org/2012/endoh1/hint.html

#  include<stdio.h>//  .IOCCC                                         Fluid-  #
#  include <unistd.h>  //2012                                         _Sim!_  #
#  include<complex.h>  //||||                     ,____.              IOCCC-  #
#  define              h for(                     x=011;              2012/*  #
#  */-1>x              ++;)b[                     x]//-'              winner  #
#  define              f(p,e)                                         for(/*  #
#  */p=a;              e,p<r;                                        p+=5)//  #
#  define              z(e,i)                                        f(p,p/*  #
## */[i]=e)f(q,w=cabs  (d=*p-  *q)/2-     1)if(0  <(x=1-      w))p[i]+=w*/// ##
   double complex a [  97687]  ,*p,*q     ,*r=a,  w=0,d;    int x,y;char b/* ##
## */[6856]="\x1b[2J"  "\x1b"  "[1;1H     ", *o=  b, *t;   int main   (){/** ##
## */for(              ;0<(x=  getc (     stdin)  );)w=x  >10?32<     x?4[/* ##
## */*r++              =w,r]=  w+1,*r     =r[5]=  x==35,  r+=9:0      ,w-I/* ##
## */:(x=              w+2);;  for(;;     puts(o  ),o=b+  4){z(p      [1]*/* ##
## */9,2)              w;z(G,  3)(d*(     3-p[2]  -q[2])  *P+p[4      ]*V-/* ##
## */q[4]              *V)/p[  2];h=0     ;f(p,(  t=b+10  +(x=*p      *I)+/* ##
## */80*(              y=*p/2  ),*p+=p    [4]+=p  [3]/10  *!p[1])     )x=0/* ##
## */ <=x              &&x<79   &&0<=y&&y<23?1[1  [*t|=8   ,t]|=4,t+=80]=1/* ##
## */, *t              |=2:0;    h=" '`-.|//,\\"  "|\\_"    "\\/\x23\n"[x/** ##
## */%80-              9?x[b]      :16];;usleep(  12321)      ;}return 0;}/* ##
####                                                                       ####
###############################################################################
**###########################################################################*/

解説

流体力学シミュレータです。以下のように実行してみてください。

$ gcc -o endoh1 endoh1.c -DG=1 -DP=4 -DV=8 -D_BSD_SOURCE -lm
$ ./endoh1 < endoh1.c

忙しい人のためのデモ動画。

D

教科書的な粒子法 (SPH 法)です。粒子はそれぞれ位置と密度と速度を持っていて、ナビエ・ストークス方程式に従い、外力、圧力、粘性抵抗によって動きます。("-DG=1 -DP=4 -DV=8" は、それぞれの力の係数。変えれば流体の挙動が変わる)

標準入力は初期盤面として使います。'#' は壁粒子 (動かない粒子) 、それ以外の文字は動く粒子として扱います。

他にもいくつか盤面を用意してあります。

$ ./endoh1 < logo.txt
$ ./endoh1 < column.txt
$ ./endoh1 < pour-out.txt
$ ./endoh1 < tanada.txt

審査員や銀賞の @hamano さんが作ってくれた盤面も公開されてます。

さらに、粒子の密度を端末の 256 色で表示する endoh1_color.c も (入賞後に審査員に言われて) 作り足しました。


狙いと戦略

1 つめが趣味のエントリだったので、こっちは積極的に入賞を狙って行きました。

去年の winner をみて、shinh さんのピクロスソルバとかライフゲームの Garden of Eden 計算とか、普通に実装しようとしても難しいネタの受けがいいみたいなので、流体シミュレーションを選びました。というのは、妻であるところの @hirekoke さんが当時趣味で SPH 法を調べていて、教えてもらえたので。

実装自体は、1 つめの作品以上に普通です。強いて変わったところを挙げるなら、ベクトルを C99 feature の double complex 型で表現してるところ (ソースコード自身を初期盤面にするのは IOCCC では必然ですが、そのために C99 feature である一行コメント (//) が必要だったので、いっそ完全に C99 依存とした) ですが、複素数でベクトルを表すとかすごく普通だよね。

こっちも remark には力を入れました。1 つめの remark とフォーマットを変えてみたとか。その方が説明しやすかったというのもあるけれど、remark のフォーマットで明らかに同一人物のエントリだとわかると「どっちか落とそう」って心理が働きそうだなーとか。あとはロゴを入れたりとか、審査員にお茶を淹れてみたりとか。

流体シミュレーションというネタ選定にはわりと自信あったのですが、でも優勝できるネタではないですよね。ひねりがない。脇役にはなれても主役にはなれない感じ。その点、銅賞は賄賂だし、銀賞は出力が見栄えするし、金賞は形而上な感じだし。これぞ主役のオーラですよね。

*1:ちなみに、ちなんでいるだけで spigot algorithm は使っていません。釣りです。

*2:ネタばれすると数字のビットマップフォントデータ。これの求解プログラムもあわせて公開されてます。たぶん IOCCC 初の .rb ファイル!