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 とはうまいこと言う。審査員が賞名に面白いダジャレを思いつくかどうかが最大の鍵かもしれない。

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

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

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

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

教科書的な粒子法 (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 のフォーマットで明らかに同一人物のエントリだとわかると「どっちか落とそう」って心理が働きそうだなーとか。あとはロゴを入れたりとか、審査員にお茶を淹れてみたりとか。

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