On February, 13th, 1995 the 1. Int'l Kaiserslautern Shortest C Contest (ShoCC) was announced. Its subject was to write a C program that counts from a given number i1 upto or downto a second given number i2. The program consisting of the fewest characters (including space and newline chars) was to win the contest. For full details see the contest rules at
http://www.unix-ag.uni-kl.de/~conrad/shocc/shocc_en.htmlUntil the deadline of Wednesday, February, 23rd, 1995, 23:59:59 MET we received 375 submissions from 184 participants. Six of the 375 entries did not compile on our testsuite and 45 had runtime errors during a test process.
Unfortunately most of the programs did not fulfil one of the specifications made in the announcement, but our automated check script did not discover this violation of the rules: Many programs computed a difference of i1 and i2, decremented or incremented it according to the sign of this difference and terminated their loop when this difference was zero. As you can see the sign of this difference is important. Unfortunately the difference of two signed integers does not in every case fit into a signed int: Obviously
(MAXINT - -5) > MAXINTand does not fit into a signed integer variable, but is interpreted as a negative number and will break the program. This is especially true if the program is invoked with
$ foo MAXINT MININTWe didn't include this case in our test scripts because of the long running time of this command. Michael Bischoff <mbi@mo.math.nat.tu-bs.de> even asked if the program had to work correctly when the difference was greater than MAXINT. We confirmed this, not overseeing the implications of this question. We discovered this pathologic case only when the contest deadline was over.
Since we had already confirmed the successful testing of these programs we finally decided to declare submissions correct even if this overflow error occured. We apologize to Michael that we have to contradict our former answer in this case.
With this in mind, there are 19 victorious submissions all with a length of 69 bytes of code (including a trailing newline):
In no particular order:
[01] main(a,y,d)int*y;{for(a=atoi(y[1]);o(a),d=atoi(y[2])-a;)a+=(d|1)%2;}
[02] main(c,v,x)int*v;{for(c=atoi(v[1]);o(c),x=atoi(v[2])-c;c+=(x|1)%2);}
[03] main(a,v)int*v;{for(a=atoi(*++v);o(a),*v=atoi(v[1])-a;a+=*v>>31|1);}
[04] main(i,v,j)int*v;{for(i=atoi(v[1]);o(i),j=atoi(v[2])-i;i+=(j|1)%2);}
[05] main(c,d){int*v=d;for(c=atoi(v[1]);o(c),d=atoi(v[2])-c;c+=d>>31|1);}
[06] main(d,O,_)int*O;{for(_=atoi(O[1]);o(_),d=_-atoi(O[2]);_-=d>>-1|1);}
[07] main(a,v)int*v;{for(a=atoi(v[1]);o(a),*v=atoi(v[2])-a;a+=*v>>31|1);}
[08] main(a,b)int*b;{for(a=atoi(*++b);o(a),*b=atoi(b[1])-a;a+=(*b|1)%2);}
[09] main(a,b)int*b;{for(a=atoi(b[1]);o(a),*b=atoi(b[2])-a;a+=*b>>31|1);}
[10] main(J,_)int*_;{for(J=atoi(*++_);o(J),*_=atoi(_[1])-J;J+=(*_|1)%2);}
[11] main(i,b,j)int*b;{for(i=atoi(b[1]);o(i),j=i-atoi(b[2]);i-=j>>31|1);}
[12] main(k,j,i)int*j;{for(k=atoi(j[1]);o(k),i=atoi(j[2])-k;k+=(i|1)%2);}
[13] main(n,a,e)int*a;{for(n=atoi(a[1]);o(n),e=atoi(a[2])-n;n+=e>>31|1);}
[14] a;main(c,d)int*d;{for(a=atoi(d[1]);o(a),c=atoi(d[2])-a;a+=(c|1)%2);}
[15] main(n,c,d)int*c;{for(n=atoi(c[1]);o(n),d=atoi(c[2])-n;n+=d>>31|1);}
[16] main(d,a)int*a;{for(d=atoi(a[1]);o(d),*a=atoi(a[2])-d;d+=(*a|1)%2);}
[17] *p;main(i,x){for(i=atoi((p=x)[1]);o(i),x=atoi(p[2])-i;x>0?i++:i--);}
[18] main(c,v,d)int*v;{for(c=atoi(v[1]);o(c),d=atoi(v[2])-c;c+=d>>31|1);}
[19] main(c,v,d)int*v;{for(c=atoi(v[1]);d;o(d>0?c++:c--))d=atoi(v[2])-c;}
These are the winners of the 1. Int'l Kaiserslautern Shortest C Contest
(the numbers refer to the programs above):
[01] Lars C. Hassing <lch@cci.dk>
[02] Stefan Bock <sbock@informatik.uni-kl.de>
[03] Heather Downs <heathbar@natasha.tele.iastate.edu>
[04] Patrick Seemann <tele@tubul.limmat.net.ch>
[05] Roland Nagel <nagel@informatik.uni-kl.de>
[06] Klaus Singvogel <kssingvo@immd4.informatik.uni-erlangen.de>,
Michael Schroeder <mlschroe@faui43.informatik.uni-erlangen.de>,
Markus Kuhn <mskuhn@cip.informatik.uni-erlangen.de>
[07] Markus Simmer <simmer@iml.fhg.de>
[08] Willy Seibert <ws@osix.materna.de>
[09] Oliver Bianzano <oli@ap-pc818c.physik.uni-karlsruhe.de>
[10] Jens Schweikhardt <jenssch@ibhinfo.hemminger-gdv.de>
[11] Thomas Omerzu <omerzu@quantum.de>,
Matthias Sachs <sachs@quantum.de>,
Udo Salewski <salewski@quantum.de>
[12] Jahn Rentmeister <WIJARE@wi.uni-muenster.de>
[13] Gregor Hoffleit <flight@mathi.uni-heidelberg.de>
[14] John Rochester <jr@cs.mun.ca>
[15] Markus Siegert <siegertm@nemeter.dinoco.de>
[16] Siegmar Zaeske <zaeske@detlef.informatik.uni-dortmund.de>
[17] Arnd Gerns <gerns@informatik.uni-hildesheim.de>,
Dirk Eiden <eiden@informatik.uni-hildesheim.de>,
Steffen Moeller <moeller@informatik.uni-hildesheim.de>
[18] James C. Hu <jxh@pride.cs.wustl.edu>
[19] Frank Neblung <neblung@informatik.uni-kl.de>
Congratulations to the winners and all other contestants for the very
inspiring submissions. Here is the distribution of the TOP 15 ranks:
RANK # PROGRAMS LENGTH
--------------------------
1 19 69 Bytes
2 21 70 Bytes
3 6 71 Bytes
4 14 72 Bytes
5 15 73 Bytes
6 10 74 Bytes
7 3 75 Bytes
8 9 76 Bytes
9 5 77 Bytes
10 6 78 Bytes
11 10 79 Bytes
12 7 80 Bytes
13 4 82 Bytes
14 6 83 Bytes
15 1 84 Bytes
We hope we did not forget your submission. If you mailed a
submission to us but got no ack, mail us again and we'll try to figure
out what happened.
274 de Germany 35 com all over the world, mostly USA and Germany 20 net dito 19 edu mostly USA 18 org all over the world, mostly Germany and USA 8 dk Denmark 7 uk United Kingdom 6 su Former Sovjet Union, here: Usbekistan 5 fr France 4 nl Netherlands 4 ch Switzerland 4 ca Canada 2 it Italy 2 gov USA 2 at Austria 2 se Sweden 1 sg Singapore
Total number of analyzed entries: 365
for 277 while 50 do 7 goto 6 other 16
atoi 99% atol 1 scanf 5 *++v 57 v[1] 301 1[v] 8
int main() 11
void main() 7
main(int c, ... 127
..., char **) 90
..., int **) 28
k&r char **v 51
k&r int **v 47
k&r int *v 120
used *v as int 35
k&r long *v 1
no explicit type declaration 1
global int variables 18
global *int variables 1
additional functions (recursion): 4
declaration of o() 2
#include <stdio.h 16 #include <stdlib.h> 16 #define i=atoi(T[1]) and variants 12 other defines 3
Total 271 Definitions of positions: for (A; B; C) D; A: called atoi() once 120 called atoi() twice 67 called o() 65 B: o(a), b=atoi(v[2])-a construct 70 no atoi(), a-b termination 99 no atoi(), o(a) 87 C: empty 15 a<b?a++:a-- variants 92 a<0?d++:d-- variants 29 l+=l<i?1:-1 variants 69
atoi() 355 printf() 40 abs() 13 scanf() 4 exit() 2 system() 1 atol() 1
if 39 else 13 return 13
^ 15 %2 14 >> 17 |1 32 ?: 283 /, /= 8 += 141 -= 22
200 v 15 s 3 X 193 a 12 z 2 g 170 c 11 O 2 S 161 b 10 p 2 L 103 i 9 f 2 I 92 d 9 argv 2 B 80 j 9 argc 2 A 39 n 8 l 1 nr 36 x 6 t 1 arg 32 y 5 J 1 T 25 k 3 w 1 K 24 h 3 r 23 _ 3 q 17 e 3 mNote that there are all lower case characters used except of 'u'!
*v;main(a,b){for(a=atoi(1[v=b]);o(a),b=atoi(v[2])-a;a+=(b|1)%2);}
1st price: Markus Freericks <mfx@cs.tu-berlin.de>
main(b,v,a)char**v;{b=atoi(v[2]);o(b+((a=atoi(v[1]))^b&&sprintf(*v,
"%s %d %d",*v,a,b+(b>a?-1:1))&&system(*v),0));}
2nd price: Hans-Christoph Wirth <hansi@dianoia.mayn.sub.de>
#define m(x,y)x=atoi(y[(int*)b]),
main(a,b,i){a-3?(o(i),(i-b)&&main(a,b,i+a)):(m(i,1)m(b,2)
main(i<b?1:-1,b,i));}
3rd price: Arnd Gerns, Steffen Moeller, Dirk Eiden
*p;main(i,x){for(i=atoi((p=x)[1]);o(i),x=atoi(p[2])-i;x>0?i++:i--);}
4th price: Jens Gebhard <gebharj@goedel.uni-muenster.de>
main(c,v,i)int*v;{c-i?main(v?atoi(v[1]):c+2*(o(c),c<i)-1,0,
v?atoi(v[2]):i):o(c);}
Note that the line breaks at the obvious places were inserted by us
for better readability in newsreaders only.
URL: http://www.unix-ag.uni-kl.de/~conrad/shocc/shocc.htmlWe will also make a tar archive containing this information along with some more or less useful "AI"-scripts that helped us evaluate the submissions.
Disclaimer: And now kids, be nice and go back to your normal programming habits that you learned from Uncle Dijkstra and the SE courses ;-}