実践Golf-Coder

以下の内容は部内のwikiに僕が不定期連載していたものを、ケチってすこしでももっと役に立てようと思って公開するものである。

Code Golfとは。

ある目標を達成するために行ったストローク数の少なさを競うという共通点から、
Holeを狙ってGolfBallを打つ回数の少なさを競うイギリスのスポーツ、Golfになぞらえて名づけられたプログラミング。また、その競技。

一般に、そのソースコードの小ささを競う。(キーストロークを競う訳ではない

具体例を示せよ。

e,s,k=10,r,N;f(a,i){for(e=0;i;e+=1<<3*((N=(a%=s*10)/s)?N:(i=e=0)))s=pow(10,--i);return e;}main(i,l){for(k*=i=pow(10,l=getchar()-50);++i<k;r=9)for(;f(r*i,l+2)-f(r,1)-f(i,l+1)?:printf("%dx%d=%d\n",i,r,r*i),r--;);}

これが美しいC-Golf-Codeというものだ。
注:横1400pixでどうにか見れることが確認されています。

まず、普通に書く。

#include<stdio.h>

int
 _pow10(int i){
	int tmp=1;
	while(i--)
		tmp=tmp*10;
	return tmp;
	}

long
core(int target){
	long elem=0;
	int i,NumLt;
	i=(int)log10(target);
	while(i>=0){
		NumLt=target/(int)_pow10(i);
		if(NumLt==0)return -1;
		elem+=1<<3*NumLt;
		target=target%(int)_pow10(i--);}
	return elem;
	}

int
main(){
	int a=0;
	int lo;
	int i=0;
	scanf("%d",&lo);
	i=_pow10(lo-2);
	while(++i<_pow10(lo-1)){
		a=0;
		while(a++!=9)
			if(core(a*i)==core(a)+core(i))
				printf("%d*%d=%d\n",i,a,a*i);
	}
}

そのまま減らす

変数を1字に置き換える。
つぎに、関数を一字におきかえる。
それから、#include文をなくす。(標準ライブラリのみ使用する場合は不要だから(勝手にコンパイラが見てくれる))
また、\tや空白、\nも削減対象だ。
だが、そうして見やすさを減じてしまう前にするべきことがある。

アルゴリズムを見直そう

もう一度上のソースコードを見てみよう。
_pow10()はpow(10,)で置き換えた方が短くなるだろう。
POSIXな関数は使えるときには積極的に使用するべき。
ここで注意すべきなのはGCC(3|4).*を使用している初心者で、
math.hを利用するには(明示的に#include<math.h>していても)-lmオプションをつけなくてはならないということを覚えておこう。

変数の宣言の位置に技あり

main関数の第一引数は、通常の呼び出しを行うとオプションが0要素なので、1が代入されている。これを利用できるなら使おう。
また、グローバル変数は初期化せずとも0が入る。覚えておこう。
型を省略すると、int値として宣言される。

評価式の本質の追求

評価式とは何だろうか。
0であればFalse, 1であればTrueといった説明がなされがちだが、Cにはboolean値がない。
これで、にやっと来た人は実験してみてほしい。
!=演算が二項演算’-‘と同等であることに気がつきました?

(func()-func()-func())?True:False;

と、

if(func(a)==(func(b)+func(c))False;
else True;

は、同等である。

python界隈の飲み場でそれやって海老蔵になっても知らんからなっ!

するってぇと、どうなるんでぃ?

自分で手を動かすことも大切だ。自分でGolfしなければいつまで経ってもParすらでない。
以上のことを踏まえてやってみるとだいぶ縮まるはずだ。
ほら、こんな風に。

a;f(a){T=0;i,N;i=()log10(a);while(i>=0){N=a/()pow(10,i);N?:return -1;T+=1<<3*N;a=a%()pow(10,i--);}return T;}main(i){l;scanf("%d",&l);i=pow(10,l-2);while(++i<pow(10,l-1)){for(a=10;a--;){(f(a*i)-f(a)-f(i))?:printf("%d*%d=%d\n",i,a,a*i);}}}

たかだかこれだけで238byteまで落とし込めた。
注:横1400pixでは正常に見れません。
実際に自分で書いてみることをおすすめします。
コピペなんて駄目よー。

for文にする。

うえのプログラムをみると、while文に付属するiterateeが2文であるので、{}でくくっている。

a;f(a){T=0;i,N;for(i=()log10(a);i>=0;N?:return -1)T+=1<<3*N;a=a%()pow(10,i--),N=a/()pow(10,i);return T;}main(i){l;scanf("%d",&l);i=pow(10,l-2);while(++i<pow(10,l-1)){for(a=10;a--;){(f(a*i)-f(a)-f(i))?:printf("%d*%d=%d\n",i,a,a*i);}}}

このように、for文に直しカンマで連接することで、さらに縮まる。
だが、for()の()内にreturnやforなどの予約語を含む式は入らないお約束になっている。
そこで、return -1;をi=T=-1;としよう。
(この場合、この直後に実行される比較式i>=0に反し、return Tで値(=-1)が返る。)

Post a comment or leave a trackback: Trackback URL.

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です