Matrix67: My Blog » 2006

Sep 29

IOCCC近几年的获奖作品

Matrix67 | icon2

Program Impossible | icon4

2006-09-29 1:05 | icon3

7 Comments »

    想起在网上找找这个是因为lakeblur给我发过这样一个C代码：

#include <stdio.h> main(t,_,a) char *a; { return!0<t?t<3?main(-79,-13,a+main(-87,1-_,main(-86,0,a+1)+a)): 1,t<_?main(t+1,_,a):3,main(-94,-27+t,a)&&t==2?_<13? main(2,_+1,"%s %d %d\n"):9:16:t<0?t<-72?main(_,t, "@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l+,/n{n+,/+#n+,/#\ ;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \ q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# \ ){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \ iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \ ;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')#\ }'+}##(!!/")   :t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)     :0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a, "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a+1); }

    程序编译运行后不可思议地打印出一长段超过源代码长度的文字，而这些字串竟然根本没有在源代码中出现过。我知道C代码可以写得很怪，而且看这个程序估计还用了不少递归；但从没有想过还有如此荒唐的源代码，看上去基本上就是乱码。刚才我搜索到，这段代码是IOCCC的一个获奖作品。

    IOCCC即International Obfuscated C Code Contest，比谁的C代码写得最乱最读不懂。
    这个比赛已经举办了17年了，下面是近几年的一些获奖作品。
    你可以在http://www.au.ioccc.org/years.html看到更多，但很多需要在Linux环境下编译运行。比较有趣的又能够在windows环境下运行都已经在下面了。
    我们假设你编译后的文件名都是abc.exe。

编译后在dos下输入
abc "ash nazg durhbatuluhk, ash nazg gimbatul, ash nazg thrakatuluhk, agh burzhumh-ishi krimpatul." >abc.pgm
然后用图片编辑器查看abc.pgm

                                  #include\                                   <stdio.h>                      #include                <stdlib.h>                      #include                <string.h>                     #define w "Hk~HdA=Jk|Jk~LSyL[{M[wMcxNksNss:"                    #define r"Ht@H|@=HdJHtJHdYHtY:HtFHtF=JDBIl"\                   "DJTEJDFIlMIlM:HdMHdM=I|KIlMJTOJDOIlWITY:8Y"                  #define S"IT@I\\@=HdHHtGH|KILJJDIJDH:H|KID"\                 "K=HdQHtPH|TIDRJDRJDQ:JC?JK?=JDRJLRI|UItU:8T"                #define _(i,j)L[i=2*T[j,O[i=O[j-R[j,T[i=2*\               R[j-5*T[j+4*O[j-L[j,R[i=3*T[j-R[j-3*O[j+L[j,              #define t"IS?I\\@=HdGHtGIDJILIJDIItHJTFJDF:8J"     #define y                  yy(4),yy(5),                yy(6),yy(7)   #define yy(              i)R[i]=T[i],T[i ]            =O[i],O[i]=L [i] #define Y _(0          ], 4] )_ (1 ], 5] )_ (2      ], 6] )_ (3 ], 7] )_=1 #define v(i)(      (( R[ i ] * _ + T [ i ]) * _ + O [ i ]) * _ + L [ i ]) *2 double b = 32  ,l ,k ,o ,B ,_ ; int Q , s , V , R [8 ], T[ 8] ,O [8 ], L[ 8] ; #define q( Q,R ) R= *X ++ % 64 *8 ,R |= *X /8 &7 ,Q=*X++%8,Q=Q*64+*X++%64-256, # define  p      "G\\QG\\P=GLPGTPGdMGdNGtOGlOG"   "dSGdRGDPGLPG\\LG\\LHtGHtH:" #  define W         "Hs?H{?=HdGH|FI\\II\\GJlHJ"    "lFL\\DLTCMlAM\\@Ns}Nk|:8G" # define   U           "EDGEDH=EtCElDH{~H|AJk}"       "Jk?LSzL[|M[wMcxNksNst:" #  define u                  "Hs?H|@=HdFHtEI"             "\\HI\\FJLHJTD:8H" char  *   x                   ,*X , ( * i )[               640],z[3]="4_", *Z = "4,8O4.8O4G" r U "4M"u S"4R"u t"4S8CHdDH|E=HtAIDAIt@IlAJTCJDCIlKI\\K:8K"U "4TDdWDdW=D\\UD\\VF\\FFdHGtCGtEIDBIDDIlBIdDJT@JLC:8D"t"4UGDNG\\L=GDJGLKHL\ FHLGHtEHtE:"p"4ZFDTFLT=G|EGlHITBH|DIlDIdE:HtMH|M=JDBJLDKLAKDALDFKtFKdMK\ \\LJTOJ\\NJTMJTM:8M4aGtFGlG=G|HG|H:G\\IG\\J=G|IG|I:GdKGlL=G|JG|J:4b"W S"4d"W t t"4g"r w"4iGlIGlK=G|JG|J:4kHl@Ht@=HdDHtCHdPH|P:HdDHdD=It\ BIlDJTEJDFIdNI\\N:8N"w"4lID@IL@=HlIH|FHlPH|NHt^H|^:H|MH|N=J\\D\ J\\GK\\OKTOKDXJtXItZI|YIlWI|V:8^4mHLGH\\G=HLVH\\V:4n" u t t "4p"W"IT@I\\@=HdHHtGIDKILIJLGJLG:JK?JK?=JDGJLGI|MJDL:8M4\ rHt@H|@=HtDH|BJdLJTH:ITEI\\E=ILPILNNtCNlB:8N4t"W t"4u" p"4zI[?Il@=HlHH|HIDLILIJDII|HKDAJ|A:JtCJtC=JdLJtJL\ THLdFNk|Nc|\ :8K"; main ( int C,char**        A) {for(x=A[1],i=calloc(strlen(x)+2,163840); C-1;C<3?Q=_=       0,(z[1]=*x++)?((*x++==104?z[1]^=32:--x), X = strstr(Z,z))      &&(X+=C++):(printf("P2 %d 320 4 ",V=b/2+32), V*=2,s=Q=0,C     =4):C<4?Q-->0?i[(int)((l+=o)+b)][(int)(k+=B) ]=1:_?_-=.5/    256,o=(v(2)-(l=v(0)))/(Q=16),B=(v(3)-(k=v(1) ))/Q:*X>60?y   ,q(L[4],L[5])q(L[6],L[7])*X-61||(++X,y,y,y), Y:*X>57?++X,  y,Y:*X >54?++X,b+=*X++%64*4:--C:printf("%d " ,i[Q][s]+i[Q ][s+1]+i[Q+1][s]+i[Q+1][s+1])&&(Q+=2)<V||(Q= 0,s+=2)<640 ||(C=1));}

编译后在dos下输入abs > ioccc_ray.ppm，生成一个图片（等得可能有点久）

X=1024; Y=768; A=3; J=0;K=-10;L=-7;M=1296;N=36;O=255;P=9;_=1<<15;E;S;C;D;F(b){E="1""111886:6:??AAF" "FHHMMOO55557799@@>>>BBBGGIIKK"[b]-64;C="C@=::C@@==@=:C@=:C@=:C5""31/513/5131/" "31/531/53"[b ]-64;S=b<22?9:0;D=2;}I(x,Y,X){Y?(X^=Y,X*X>x?(X^=Y):0,  I (x,Y/2,X )):(E=X);      }H(x){I(x,    _,0);}p;q(        c,x,y,z,k,l,m,a,          b){F(c );x-=E*M     ;y-=S*M           ;z-=C*M         ;b=x*       x/M+         y*y/M+z *z/M-D*D    *M;a=-x              *k/M     -y*l/M-z        *m/M;    p=((b=a*a/M- b)>=0?(I    (b*M,_      ,0),b    =E,      a+(a>b      ?-b:b)):     -1.0);}Z;W;o (c,x,y,     z,k,l,    m,a){Z=!    c?      -1:Z;c     <44?(q(c,x         ,y,z,k, l,m,0,0     ),(p>      0&&c!=     a&&        (p<W         ||Z<0)          )?(W= p,Z=c):     0,o(c+         1,    x,y,z,        k,l,          m,a)):0     ;}Q;T; U;u;v;w    ;n(e,f,g,            h,i,j,d,a,    b,V){o(0      ,e,f,g,h,i,j,a);d>0 &&Z>=0? (e+=h*W/M,f+=i*W/M,g+=j*W/M,F(Z),u=e-E*M,v=f-S*M,w=g-C*M,b=(-2*u-2*v+w) /3,H(u*u+v*v+w*w),b/=D,b*=b,b*=200,b/=(M*M),V=Z,E!=0?(u=-u*M/E,v=-v*M/E,w=-w*M/ E):0,E=(h*u+i*v+j*w)/M,h-=u*E/(M/2),i-=v*E/(M/2),j-=w*E/(M/2),n(e,f,g,h,i,j,d-1 ,Z,0,0),Q/=2,T/=2,       U/=2,V=V<22?7:  (V<30?1:(V<38?2:(V<44?4:(V==44?6:3)))) ,Q+=V&1?b:0,T                +=V&2?b        :0,U+=V    &4?b:0)     :(d==P?(g+=2 ,j=g>0?g/8:g/     20):0,j    >0?(U=     j    *j/M,Q      =255-    250*U/M,T=255 -150*U/M,U=255    -100    *U/M):(U    =j*j     /M,U<M           /5?(Q=255-210*U /M,T=255-435*U           /M,U=255    -720*      U/M):(U       -=M/5,Q=213-110*U /M,T=168-113*U    /       M,U=111               -85*U/M)      ),d!=P?(Q/=2,T/=2 ,U/=2):0);Q=Q<    0?0:      Q>O?     O:          Q;T=T<0?    0:T>O?O:T;U=U<0?0: U>O?O:U;}R;G;B    ;t(x,y     ,a,    b){n(M*J+M    *40*(A*x   +a)/X/A-M*20,M*K,M *L-M*30*(A*y+b)/Y/A+M*15,0,M,0,P,  -1,0,0);R+=Q    ;G+=T;B   +=U;++a<A?t(x,y,a, b):(++b<A?t(x,y,0,b):0);}r(x,y){R=G=B=0;t(x,y,0,0);x<X?(printf("%c%c%c",R/A/A,G /A/A,B/A/A),r(x+1,y)):0;}s(y){r(0,--y?s(y),y:y);}main(){printf("P6\n%i %i\n255" "\n",X,Y);s(Y);}

编译后输入abc 0 0 1可以画出x^2的函数图像，输入abc -1 0 0 1可以画出x^3-1的图像。你也可以试试其它的。

#include <stdio.h> #include <stdlib.h> #include <math.h> #define _   ;double #define void   x,x #define case(break,default) break[O]:default[O]: #define switch(bool)   ;for(;x<bool; #define do(if,else)  inIine(else)>int##if? #define true   (--void++) #define false   (++void--) char*O=" <60>!?\\\n"_ doubIe[010]_ int0,int1 _ Iong=0 _ inIine(int eIse){int O1O=!O _ l=!O;for(;O1O<010;++O1O)l+=(O1O[doubIe]*pow(eIse,O1O));return l;}int main(int booI,char*eIse[]){int I=1,x=-*O;if(eIse){for(;I<010+1;I++)I[doubIe-1] =booI>I?atof(I[eIse]):!O switch(*O)x++)abs(inIine(x))>Iong&&(Iong=abs(inIine(x )));int1=Iong;main(-*O>>1,0);}else{if(booI<*O>>1){int0=int1;int1=int0-2*Iong/0 [O]switch(5[O]))putchar(x-*O?(int0>=inIine(x)&&do(1,x)do(0,true)do(0,false) case(2,1)do(1,true)do(0,false)6[O]case(-3,6)do(0,false)6[O]-3[O]:do(1,false) case(5,4)x?booI?0:6[O]:7[O])+*O:8[O]),x++;main(++booI,0);}}}

高精度开方。这个有点意思，已经发到OIBH上了。
输入abc 01524157875019052100试试。
你输入的数字需要有偶数位，否则自行添加前导0补足。

#include <stdio.h> int l;int main(int o,char **O, int I){char c,*D=O[1];if(o>0){ for(l=0;D[l              ];D[l ++]-=10){D   [l++]-=120;D[l]-= 110;while   (!main(0,O,l))D[l] +=   20;   putchar((D[l]+1032) /20   )   ;}putchar(10);}else{ c=o+     (D[I]+82)%10-(I>l/2)* (D[I-l+I]+72)/10-9;D[I]+=I<0?0 :!(o=main(c/10,O,I-1))*((c+999 )%10-(D[I]+92)%10);}return o;}

画一个月亮

#include <stdio.h> #include <math.h> double l;main(_,o,O){return putchar((_--+22&&_+44&&main(_,-43,_),_&&o)?(main(-43,++o,O),((l=(o+21)/sqrt(3-O*22-O*O),l*l<4&&(fabs(((time(0)-607728)%2551443)/405859.-4.7+acos(l/2))<1.57))[" #"])):10);}

类似于hangman的猜单词游戏

#ifndef int #ifdef while char s[234],d[56],*p=s,m='m'; #define int typedef (*define)();\ define O [6]={getc,putchar,(y)memmove,(y)printf,(y)n,(y)l}; #include __FILE__ signed short n(short bz){ short pb=0,Md=1,ih=2,sfp=3,sjs=4,fo,u=5,scp=6,t,gq=7,oh,r=8,pcf=9,rs=10; char o=1,i=1,l,pc=i,b=r+o/2,_f=6,m=7,s=8,g,q,od=o*rs+4^s,js=_f/*3-m*'c',bs='g'; return 1; } #y FILE c[a]+s,p[c],r[m]+u[i+4*o|f]-r[wob][wad]+s*f-!w|o,L+x     |  cut ;}int main(i,love_unix){*/;}int main(i,love_unix){/*;}int main(i,love_unix){*\;}|  here */ while(FILE)for(;9-(i=0[O](f));); for(;32-(i=0[O](f));0&& 3[O]("-->%s<--", "gxdgbtgxsxpcctvpixktedhiedcte")); for(;'\n'-(i=O[0](f));)(i>='a'&&i<'z')?* #include __FILE__                                   "Demonic Smiley" );}  /* <g> */ #else #define while(int) short c=0;int*f=fopen(__##int##__,"r");for(i=0;i<25;i _)i[d]='A'+(13+i)%26;main: #define y define #define _ ++ #include <stdio.h> #include <string.h> #include <time.h> #include __FILE__ #endif #elif defined(signed) (p _)=(i-'a')[d]:!(i-'z')?*(p _)=32:(i>='A'&&i<='Z')&&((3&8|2)[O](d+1,d,24L),*(p _)=0[d]=i);/* #y FILE t,ra|js+t*gj,at[qdd]-=K,is _,qv _,veb _,ti _,ao[mqht] _*/ if(c _<6) goto main; 5[O]( #else #define signed short l(){char q='_';p=s+4*(time(NULL)%24)*2,m=(char)p+1;\ *(p+8)=0; for(d[3]=10,d[33]=3[d]-10;d[3]<18;3[d] _) d[3][p]=q;3[d][p]=0;\ hell:  printf("\t[%s]\n",p+10);if(!m) goto stoned;\ froze: d[8]=(scanf("%c",&(2[d+__STDC__])),2[d+!NULL])&223;if(!(3[d+5]-'\n')) goto froze;\ for(m=1[d]=0;d[1]<8;2[d-1] _) (p[d[1]]-d[8]||(p[3[d-2]+10]=4[d+4]))+(p[d[1]+10]-q||m _);\ goto hell;stoned:;} FILE *X(FILE s){ char i,iev,jmqhu,xqht,mqh,ujek,sxydw,kdj,yjb,utou,qhre,eamy,jxxe,bt;} #endif

Sep 26

什么是离散化？

Matrix67 | icon2

Program Impossible | icon4

2006-09-26 21:09 | icon3

17 Comments »

    如果说今年这时候OIBH问得最多的问题是二分图，那么去年这时候问得最多的算是离散化了。对于“什么是离散化”，搜索帖子你会发现有各种说法，比如“排序后处理”、“对坐标的近似处理”等等。哪个是对的呢？哪个都对。关键在于，这需要一些例子和不少的讲解才能完全解释清楚。
    离散化是程序设计中一个非常常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中“只考虑我需要用的值”。下面我将用三个例子说明，如何运用离散化改进一个低效的，甚至根本不可能实现的算法。

    《算法艺术与信息学竞赛》中的计算几何部分，黄亮举了一个经典的例子，我认为很适合用来介绍离散化思想。这个问题是UVA10173(http://acm.uva.es/p/v101/10173.html)，题目意思很简单，给定平面上n个点的坐标，求能够覆盖所有这些点的最小矩形面积。这个问题难就难在，这个矩形可以倾斜放置（边不必平行于坐标轴）。

    这里的倾斜放置很不好处理，因为我们不知道这个矩形最终会倾斜多少度。假设我们知道这个矩形的倾角是α，那么答案就很简单了：矩形面积最小时四条边一定都挨着某个点。也就是说，四条边的斜率已经都知道了的话，只需要让这些边从外面不断逼近这个点集直到碰到了某个点。你不必知道这个具体应该怎么实现，只需要理解这可以通过某种方法计算出来，毕竟我们的重点在下面的过程。
    我们的算法很显然了：枚举矩形的倾角，对于每一个倾角，我们都能计算出最小的矩形面积，最后取一个最小值。
    这个算法是否是正确的呢？我们不能说它是否正确，因为它根本不可能实现。矩形的倾角是一个实数，它有无数种可能，你永远不可能枚举每一种情况。我们说，矩形的倾角是一个“连续的”变量，它是我们无法枚举这个倾角的根本原因。我们需要一种方法，把这个“连续的”变量变成一个一个的值，变成一个“离散的”变量。这个过程也就是所谓的离散化。
    我们可以证明，最小面积的矩形不但要求四条边上都有一个点，而且还要求至少一条边上有两个或两个以上的点。试想，如果每条边上都只有一个点，则我们总可以把这个矩形旋转一点使得这个矩形变“松”，从而有余地得到更小的矩形。于是我们发现，矩形的某条边的斜率必然与某两点的连线相同。如果我们计算出了所有过两点的直线的倾角，那么α的取值只有可能是这些倾角或它减去90度后的角（直线按“\”方向倾斜时）这么C(n,2)种。我们说，这个“倾角”已经被我们 “离散化”了。虽然这个算法仍然有优化的余地，但此时我们已经达到了本文开头所说的目的。

    对于某些坐标虽然已经是整数（已经是离散的了）但范围极大的问题，我们也可以用离散化的思想缩小这个规模。最近搞模拟赛Vijos似乎火了一把，我就拿两道Vijos的题开刀。
    VOJ1056(http://www.vijos.cn/Problem_Show.asp?id=1056) 永远是离散化的经典问题。大意是给定平面上的n个矩形（坐标为整数，矩形与矩形之间可能有重叠的部分），求其覆盖的总面积。平常的想法就是开一个与二维坐标规模相当的二维Boolean数组模拟矩形的“覆盖”（把矩形所在的位置填上True）。可惜这个想法在这里有些问题，因为这个题目中坐标范围相当大（坐标范围为-10^8到10^8之间的整数）。但我们发现，矩形的数量n<=100远远小于坐标范围。每个矩形会在横纵坐标上各“使用”两个值， 100个矩形的坐标也不过用了-10^8到10^8之间的200个值。也就是说，实际有用的值其实只有这么几个。这些值将作为新的坐标值重新划分整个平面，省去中间的若干坐标值没有影响。我们可以将坐标范围“离散化”到1到200之间的数，于是一个200*200的二维数组就足够了。实现方法正如本文开头所说的“排序后处理”。对横坐标（或纵坐标）进行一次排序并映射为1到2n的整数，同时记录新坐标的每两个相邻坐标之间在离散化前实际的距离是多少。这道题同样有优化的余地。
    最后简单讲一下计算几何以外的一个运用实例（实质仍然是坐标的离散）。才考的VOJ1238(http://www.vijos.cn/Problem_Show.asp?id=1238)中，标程开了一个与时间范围一样大的数组来储存时间段的位置。这种方法在空间上来看十分危险。一旦时间取值范围再大一点，盲目的空间开销将导致Memory Limit Exceeded。我们完全可以采用离散化避免这种情况。我们对所有给出的时间坐标进行一次排序，然后同样用时间段的开始点和结束点来计算每个时刻的游戏数，只是一次性加的经验值数将乘以排序后这两个相邻时间点的实际差。这样，一个1..n的数组就足够了。

    离散化的应用相当广泛，以后你会看到还有很多其它的用途。

2007.04.05补充：
VOJ1056那个例子看来还是有人不明白。
我发一张示意图，注意左边的10*7的数组是如何等价地转化为右边两个4*4的数组的

Matrix67原创
转载请注明出处

Sep 19

这几天里有意思的东东

Matrix67 | icon2

This is My Life | icon4

2006-09-19 23:29 | icon3

3 Comments »

    很多人闹着问我最近有什么好玩的东西。20多天里还是有很多有意思的东西

    Prison Break第二季Premiere的时候刚好把第一季看完。显然没有24精彩，同时疑问为什么PB在中国就这么火。
    新剧Justice非常好看，节奏异常快。House的第三季同样精彩，第二集相当有意思。
    前几天看了《东京审判》，难看死了，什么亮点都没有。今天看了《夜宴》，还是难看死了，节奏比2001太空漫游还慢。或许我不喜欢这类电影吧。总觉得国产电影是垃圾，除了《疯狂的石头》和《英雄》（别打我）。
    《侦探们的镇魂歌》有点意思，是剧场版中首次尝试把一些（简单的）谜团留给观众；比如，有些人看完了都还不知道那个侦探是KID变的。

    才发现的一些好玩的网站
    http://1tie.cn/一个免费的在线文本储存系统，相当有意思，使用它甚至不需要申请用户，直接在后面跟一个字串就行了。它的主页上有详细说明。我搞了一个：http://1tie.cn/matrix67/
    http://www-ui.is.s.u-tokyo.ac.jp/~takeo/teddy/teddy/teddy.html可以帮助你建一个三维模型草图。它的操作方式和真正意义上的草图没什么区别。比如，画一条线可以把你的模型切开，然后在切口上画一个半圆可以让你的模型在切面上长个包。JAVA的，首页上有个链接里有详细的帮助说明。

    本来还想写点和一中MM有关的东西，想了一下还是算了；对一中产生恐惧感了，天知道一中MM又会从哪里得知我的Space地址。