Average rating: 4/4
Number of ratings: 6
Rate this project:
Average rating: 4/4
Number of ratings: 6
Rate this project:
by Christopher, 2009-07-03 18:21:30
Tags: programming puzzle mathematics
The International Obfuscated C Code Contest is a contest to write the most obscure, confusing program possible in the C programming language. I entered the 19th IOCCC in 2006, and was selected as one of 11 winners. I was awarded "Best Abuse of Computation". Here is the source code for my entry (slightly modified for usability):
#include <ncurses.h>
#include <inttypes.h>
#include <time.h>
#include <stdlib.h>
#define GG(T,C) attrset(A_BOLD*!(T)|COLOR_PAIR(C%2+1));
#define AGG A&2?KEY_UP:KEY_DOWN:A&1?KEY_RIGHT:KEY_LEFT
#define AC(G) init_pair(G/2,G,nodelay(stdscr,G/3));
#define TCT(A,G,C) mvaddch(A+CTT*6+4,CGA*12+G,C)
#define ATG srand(time(0)); initscr(); cbreak(); \
noecho(); start_color(); keypad(stdscr,1);
#define CAT mvprintw(2,40,"%d",TC)
#define T(T) #T#T#T#T#T#T T
#define GAT int main()
#define AAA refresh()
#define G(G) while(G)
#define A(A) A { A }
#define TAG endwin()
#define TCA clock()
#define GCA clear()
#define CCC rand()
#define CC getch()
#define GA return
typedef uint32_t G;
typedef uint16_t CT;
G AA[1<<16]; G GT[1<<16],CAA,CA,CTG,TA,CG,CTT,CGA,TC,T,GTC;
char *ACG="HXXTP02^OCBHL\\XP``T^NDP800SQSW\\X@@@0c13RZLLH<"
"WWWWWWWW\0\0.jW\0\0\0\0\0\0\0Wq.\0'9W\0\0\0\0\0\0\0WP'\0"
"\0jb\0\0WW\0\0007F\0\0WWWWWWWWBjPWWbo^^WW^^9WWP^__WW__6,"
"D:^HRioV;:VztZ"
,*GCC,
*AGT,GTT []=T(;
G AG; G TG; G AC; G C;
G A=0; G AAG; G TT; G
GG; G AT (CT A){ GA A
%4* 2>> A%4; } CT GC
(){ AC=!(AAG&(CA/=2)); CTG=15*CA*CA/4; G A
=TG; GA AC||(A&&AT(A/CA/CA)); } CT GTCA(G C,G
A,G CG ){ GG(C>=A,
C)G(!A )GA ( C&&
CC)*CG *TAG; CG
+=(C<A)<<(G)20; G(TCT(0,C%16*3-34, 302[C%16*2+GTT]
)); AAA; G(CG>( G)TCA); GA CG^ GTCA(C+3,A-1,CG); }
G CGAC( CT T,G
A,G C,G AA , G
AG){ GA(AA &&( CA
=4)&&(CGAC(1+T,1+A,C,--AA,AG)?CGAC(ACG[T],
AG,0,C,A):ACG[T]&&TCT(AG,A,ACG[T])),C);
} CT TGA(G A){ CT
T=1; CT C=- T; *AA=
A; *GT=3; G (++C^T){
G((TA=AA[C])/2&!(TT=(TG=
GT[ C]+16)&15))
GA TG>>4;
CA=4; AAG= TA>>2
*TT; A(GC( )?(AA[T]=
TA^1<<2*TT<<AT(AAG),GT[T++]
=TG^ CTG>> AC) :2; )} GA 0; } G
ACC(){ G T= 4; G A=
1; G C=1; TC=TGA
(GG=CCC); G((A*=
2)<C||(C<<=A=1)<T||(T*=C=2)){ G(TGA(AG=GG^T^C
^A)>TC) { G((TC=TGA (GG=AG))> CAA){ CAA=TC; CAT;
} G( TC >> 6 )
GA 1 ; C=1; T
= 2; } G(1+CC)
GA 1; } GA 0; } GAT{ AGT=GCC=GTT; G(( T=*++GCC))64-
(72&T)?1:(*AGT ^=T/4%2<<A%8, 7&(A+=5))?-1:(*++AGT=
CAA=C=0 ); ATG AC
(4 ); G (!ACC());
AC (2); G(C+1){ G(
!C){ C=TG=3; CG=1; TA=GG; TC=CAA; } GCA;
TT=TG; A(A(A(A(++TT; A=CG^=(TT&=15)&
3?1 :2; CTT= TT/4;
CGA=CTT %2*3^3^TT%4
;AAG=TA >>2*TT; A=CG^
AAG; GG (TT ^TG,
GTC=TT)CGAC
(GTC&&A&2 ?134
:138,TT& 0,6,6,A&1?0
:5); CGAC (128|A %2*3,
A&2?3:0,11,3,0); ))))CAT; G(TA/
2&!TG)GA GTCA(GCA,CAA/4&16,TCA); )
C = CC- 114; TT=0;
A(G(GC ()&&TC&&C+
114 == (CA&2?AGG)
){ --TC; A^=TG%2* (2-AT(A)); C=TCA; A(A(T=0; {
GG(1,TG); A(A(A(A(A(A(G C=TT/2^TG%2?2:1; TCT(T%6,
T% 11, 32+ 55*(
ACG[11 *AT(TT)
+22*AT( A)+ ((A
^2)&C?65-T:T)%11]>>((A|C)%4/3?T:65-T)%6&1)); T++;
)))))) TT++; AAA; } C+=1<<16; G(C>(G) TCA); ))
CG^=CA; TA ^=1
<<AT(AAG) <<TG *2;
TG^=CTG>> AC; } )}
GA TAG; }
As you can tell from the shape of the source code, this program was designed to run a genetic algorithm. The program actually does several different things, each of which required a good deal of cleverness and effort to include:
cc night.c -o night -Wall -lcurses -O3
Then run it with "./night". The controls are: arrow keys to move, q to quit and r to restart. The judges asked for entries to come with remarks, to tell people about the program. Here's what I wrote:
This program solves an optimization problem, namely, generating a challenging maze. It uses a very simple genetic algorithm: a maze layout's DNA is represented as a 32-bit integer, and mutations consist of flipping three different bits. The fitness function is the number of moves required to solve the maze. The algorithm is simple in that there's no sexual reproduction, only mutations, and a population size of 1. So much for diversity!
This particular optimization problem has, I believe, a unique maximum: there is but one maze out of 4,294,967,296 possibilities that requires 64 moves to solve. The program will run until finding this global maximum, but if you get bored, you can accept a sub-optimal solution by pressing any key. On my system, it takes about 5 minutes to find the maximum, whereas a random search would take about a day.
Lest you're not convinced that the maze generated takes as long as the program says it does, you can try to solve it yourself. The goal is to traverse from the upper-left to the upper-right and out the top, where the number of remaining moves appears. Use the arrow keys to move. q quits and r restarts. Oh, and the maze changes as you move through it, in a predictable way. You'll just have to figure out the pattern yourself. For best results, use a display with bold-text capabilities and color.
Finally, in the world of DNA, the medium is truly the message. There's a short message encoded in the source that will only appear when you complete the optimal maze in the required 64 moves.
This video shows Landon Noll discussing the winning entries. My entry is discussed between 05:08 and 08:44.
[ Front page | About/contact | Copyright waived | Valid HTML ]