Hatena::ブログ(Diary)

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

2012-10-18

[][] 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 ファイル!

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証