#ifndef pdbq #ifndef n #define n 05 #endif pqbd #define dpqb __FILE__ #define ppbd "Move disk %d from peg %d to peg %d\n" #define pdbq #if n&01 #define dqbp #endif bpdq #if n&02 #define dbpq #endif pbdq #if n&04 #define pbqd #endif qbpb #if n>>3 #define bqdp #endif pbbq main(){ pdbq printf( pdbq #include dpqb #define qbdp #include dpqb );} qbdp #else dpdp #ifdef dqbp #define bdpq #endif bpdd #ifdef dbpq #define bdpq #endif pqpb #ifdef pbqd #define bdpq #endif pdpp #ifdef bqdp #define bdpq #endif pdpp #ifdef bdpq #undef bdpq #ifndef dqbp #define dqbp #ifndef dbpq #define dbpq #ifndef pbqd #define pbqd #ifndef bqdp #define bqdp #else dbqb #undef bqdp #endif qdqb #else pdbq #undef pbqd #endif qdbp #else pqbb #undef dbpq #endif pqbd #else bbpp #undef dqbp #endif ppqb #include dpqb #ifndef dqbp #ifndef dbpq #ifndef pbqd #ifndef bqdp #define bdpq #endif pbpp #endif qpdp #endif ddpb #endif qppb #ifdef bdpq #undef bdpq #ifndef qbdp pdbq ppbd #else qbbd #ifdef pqdb ,1,2,3 pqdb #undef pqdb #define qdbp #else bdbb #ifdef qdbp ,1,3,1 qdbp #undef qdbp #else bdbd ,1,1,2 pdbq #define pqdb #endif qppq #endif pqpb #endif bpdd #else pqpq #ifndef qbdp pdbq ppbd #else qqqb ,1 pdbq #ifdef dqbp +1 dqbp #endif qqdb #ifdef dbpq +2 dbpq #endif ppqb #ifdef pbqd +4 pbqd #endif pqpp #ifdef bqdp +8 bqdp #endif bbpb #ifdef pqdb #ifdef dqbp ,1,3 dqbp #else pddp ,3,1 pdbq #endif qpqq #else dbqb #ifdef qdbp #ifdef dqbp ,2,1 dqbp #else pqdb ,1,2 pdbq #endif dbdp #else pdpp #ifdef dqbp ,3,2 dqbp #else pdbb ,2,3 pdbq #endif pqpp #endif qbdp #endif pqpp #endif pdbp #endif pqdp #include dpqb #ifdef dqbp #undef dqbp #ifdef dbpq #undef dbpq #ifdef pbqd #undef pbqd #ifdef bqdp #undef bqdp #else qddb #define bqdp #endif ppqp #else bddq #define pbqd #endif ddbq #else bbdb #define dbpq #endif qqbd #else ddbq #define dqbp #endif qbdb #endif qbdb #endif qbpp ********************************************************************* Worst Abuse of the C Preprocessor: Mark Schnitzius and Most Likely To Amaze: David Van Brackle Mark Schnitzius & David Van Brackle ISX Corporation 1165 Northchase Parkway Suite 120 Marietta, GA 30067 USA Judges' comments: To use: make vanschnitz Try: vanschnitz For a good time, try: rm -f vanschnitz make vanschnitz LEVEL=8 Warning: Values of LEVEL>8 have been known to cause compilers (and in one case a system) to crash during compilation. For a bad/slow time try LEVEL=15. Selected notes from the authors: A classic problem in computer science is known as the Towers of Hanoi. It involves a set of different-sized disks mounted on one of three pegs. The object is to move the pile of disks to one of the other pegs. You may only move one disk at a time, and there is an additional constraint that a disk may never be placed on top of a smaller disk. Our program solves the Towers of Hanoi problem. Well, that's not exactly true; actually, it's the compiler that solves the problem. The resulting program just prints out the correct solution. How do you trick a compiler into actually solving the problem? First, you must tell it how many disks you wish to solve it for. This is done by defining the symbol 'n' on the compile line. For instance, to cause the compiler to solve the Towers of Hanoi problem with four disks, you would compile the program like this: gcc hanoi.c -o hanoi -Dn=4 A default value of 5 will be used for n if you do not define it on the command line. The value of n cannot be greater than fifteen (the compiler we used to test has a limit on the #include depth). The compiler then solves the problem using binary arithmetic based on whether particular symbols are defined or not. To loop, the program #include's itself. This is, of course, expensive; one compile we did with n=14 took about fifty minutes to compile on our system (compiling with n=15 caused our system to crash). The resulting program that the compiler generates simply prints out the answer. Did I say "simply"? Actually, the whole resulting program consists of a single printf statement, consisting of a massive string constant of length 35*(2^n-1), followed by 3*(2^n-1) integers which get formatted into the string. For our n=14 run, this adds up to a string constant of length 573405, followed by 49149 integers delimeted by commas. (Generating the string constant depends on the ANSI C feature in which adjacent character strings are catenated; a version that does not use this feature has been included for people who can only run K&R). A good way to see the resulting program (on a Unix system) is to do the command gcc hanoi.c -E -Dn=5 | grep -v \# | grep -v ^\$ For an odd number of disks, the program will provide a solution wherein the disks end up on peg 2; for an even number of disks, they will end on peg 3. This should provide some hint as to what sort of algorithm is used. We have included a "spoiler" version of the program, with meaningful symbol names and comments, but we encourage you to try to decipher the program without it... begin 444 spoiler.c M(VEF;F1E9B`@24Y)5$E!3$E:140*"B\J"B`J("!)9B!N(&ES;B=T(&1E9FEN M960L(&UA:V4@:70@-0H@*B\*(VEF;F1E9B`@;@HC9&5F:6YE("!N(#`U"B-E M;F1I9@H*+RH*("H@4V]M92!UPIP2!N('=E)W)E(&UO=FEN9R!D:7-K(&XK,2X@5&AA="!M96%N6-L92`Q M(#T^(#(@/3X@,R`]/B`Q+B!#;VUB:6YE('1H:7,@=VET:"!T:&4@:VYO=VQE M9&=E"B`J("!O9B!W:&5R92!D:7-K(#$@:7,L(&%N9"!W92!C86X@9&5T97)M M:6YE(&AO=R!T;R!M;W9E(&%N>2!D:7-K+@H@*B\*(VEF;F1E9B`@3D]77T1/ M7U1(15].54U"15)3"D9/4DU!5%]35%))3D<*(V5L