Worst Abuse of the C Preprocessor: and Most Likely To Amaze: 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