laman(1984, Third place)
spoilers: prints spiralling numbers, laid out in columns
source code:
a[900];b;c;d=1;e=1;f;g;h;O;main(k,
l)char**l;{g=atoi(*++l);for(k=
0;k*k<g;b=k++>>1);for(h=0;h*h<=
g;++h);--h;c=((h+=g>h*(h+1))-1)>>1;
while(d<=g){++O;for(f=0;f<O&&d<=g
;++f)a[b<<5|c]=d++,b+=e;for(f=0;f<O
&&d<=g;++f)a[b<<5|c]=d++,c+=e;e= -e
;}for(c=0;c<h;++c){for(b=0;b<k;++
b){if(b<k/2)a[b<<5|c]^=a[(k-(b+1))
<<5|c]^=a[b<<5|c]^=a[(k-(b+1))<<5|c]
;printf(a[b<<5|c]?"%-4d":" ",a[b<<5
|c]);}putchar('\n');}}/*MikeLaman*/
(贴吧无法输入tab,请见:
https://www.ioccc.org/1984/laman/laman.c )
formatted code:
sample:
shell:
./laman 16
output:
10 9 8 7
11 2 1 6
12 3 4 5
13 14 15 16
赏析:
第6行为g = atoi(argv[1]),即命令行输入的第一个参数被作为打印的数字总数。
第7行计算总列数k和1所在的列b。k = ceil(sqrt(g)), b = (k - 1) / 2。
当列数为偶数时,1应当出现在中间偏右的列,但我们先将1放在偏左的列。理由在随后会说。
第8~10行计算总行数h和1所在的行c。第8~9行先算得h = floor(sqrt(g))。考虑g不是完全平方数,若g > h * (h + 1),说明行列需要相等,否则行数比列数少1。第10行对h进行修正,同时算得c = (h - 1) / 2。
第11~18行做出map。d表示当前的数字,O表示一次循环需要写几个数字,e表示逆序与否。一次while写一行一列。用b << 5 | c来作为简单的hash值,这样我们就建立了一个无冲突的映射。
这里又产生一个问题,写入map的值与打印的位置对不上,列刚好相反了。我们将它与上文遗留的问题(为什么1要放在偏左的列)结合起来,答案将在后文揭晓。
第19~26行我们将其打印出来。第22行是很经典的三异或交换。但是,需要强调的是,这是个未定义行为,因为“若对一个标量对象的副效应与另一个对同一标量对象的副效应相对无顺序,则行为未定义”。
我们将证明在三个副作用以符合直觉的顺序依次发生时,三个^=能够实现两个相异对象的值交换。
我们分别用a和b来表示两个对象,即a ^= b ^= a ^= b;
t = a ^ b
b' = b ^ t = b ^ a ^ b = a
a' = t ^ b' = a ^ b ^ a = b
Q.E.D.
看到这个if和交换,上文的问题就可以解决了。我们反着写入列,又在打印之前将其反回来。
其余的部分都很容易理解,这里不再赘述。