普通のゴルフは、ボールをカップに入れるまでのストローク数をいかに少なくするかを競います。code golf(コードゴルフ)は、目的の出力をするプログラムをいかにすくないストローク数で作成するかを競います。つまり、「ソースコードが短い方が勝ち」です。
そんなの面白いのか？と思われるかもしれませんが、やってみるとなかなか奥が深く、中毒性がありますよ。
このページでは、そんなcode golfのC言語での入門ページです。「C言語での」と書いた理由は、code golfは目的の出力が得られればよいわけですから、言語はなんでもよいのです。なので、このページでは「C言語でいかにコードを短縮するか」の入門をしていきます。
ちなみに、code golfの言語はなんでもよいと書きましたが、異なる言語間では勝負が成り立ちませんので、通常はC言語はC言語同士で勝負します(例えば、必ず main と書かねばならないC言語はperlやrubyなどに比べて不利)。柔道やレスリングの体重別階級のようなものですね。体重別に階級のあるスポーツと同じく、どんな言語を使ってもいいからとにかく短く！といった無差別級もあります。
注意！ このページを作った人および、この後紹介するC言語でのcode golfコンテストが開かれているサイトでは、コンパイラに gcc を、CPUにx86互換のものを使っています。code golfはできる限り省略した書き方などをするため、非常にコンパイラ依存性が高いコードが多いです。ですから、VisualC++やBorlandC++Compilerではコンパイルできない、または実行結果が違うといったことがあるかもしれません。またCPU依存性が出る場合もあります。IntelのCPUのほとんど(Itanium, Itanium2以外)を32bitモードで使っている場合や、AMDのCPUを32bitモードで使っている場合はx86互換ですので問題ありません。PowerPCやOpteronを使っていたり、またCore2Duoを64bitモードで使っていたりすると動作が異なる可能性があります。
code golfはあまり「有用」ではないので、そのコンテストサイトは普通のプログラミングコンテストのサイトよりも残念ながら少ないです。
おそらく最大級だと思われるところは次のサイトです。
このサイトは各問題に対して無差別級のランキングと、言語別のランキングが表示されます。ただし、残念ながらC言語は扱っていません。
C言語を扱っていて、このページを作った人がよく遊んでいるのはこちらのサイトです。
このサイトはものすごくたくさんの言語を扱っています(2008年11月現在65言語)。サイトにも"The purpose of this server is not serious competition"(このサーバーは本気の競争を目的としたものではない)とあるように、さきほどのサイトほど縛りが厳格ではありません(例えば、ジョーク問題が多々あったり、正解すべき入力が全て分かっているのである特殊な場合だけできればよかったり、など)。しかし、中にはいろいろな要素がつまった良問もあり、やりがいがあります。
それでは、実際にコード短縮の方法をやっていきます。
コード短縮の方法には、主に二つあります。
アルゴリズムの改善とは、例えば1からnまでの和を出せといわれたときに、
int i,s=0;
for(i=1;i<=n;i++)
s+=i;
printf("%d",s);
とするのを、和の公式を使って
printf("%d",n*(n+1)/2);
とするようなものです(答えを出す「やり方」を変える)。
小手先の業とは、例えばさきほどのコードの for(...) の行を
for(i=n;i--;)
などとすることです。
この例でもそうですが、たいていの場合アルゴリズムを改善したほうが劇的にコードは短くなります。小手先の業では、もともとのコードの長さにもよりますが、せいぜい10%～40%程度しか減りません。しかし、小手先の業は「どんな問題にも普遍的に適用できる」という利点があります。アルゴリズムの改善はその問題ごとに考えていかねばなりません。なので、このページでは主に小手先の業を紹介し、アルゴリズムについては余裕があればケーススタディの形で取り扱いたいと思います。
これは基本中の基本です。いらないスペース、改行は全てなくしましょう。
ただし、このページでは読みやすさのためにコード例は全て改行とスペースを削らないで書きます。
普段まじめにプログラムを書いている方は、main関数を
int main(){
...
}
あるいは
int main(void){
...
}
などと書いていると思います(返り値の型をintではなくてvoidとしてる方もおられるかもしれません)。
しかし、C言語の入門書の最初の方によく書いてあるように、int, voidを省略して
main(){
...
}
と書いても問題ありません。
さて、一つ前で関数の型が省略できると書きましたが、これは「型が省略されたグローバル識別子はint型だとみなされる」からです。ということは、変数も型を省略してオッケーということです。例えば、
main(){
int i,j;
...
}
というコードは、
i,j;
main(){
...
}
としてよいことになります。残念ながら型を省略できるのはグローバル変数のみですが、code golfでは読みやすさや安全性などは興味の対象ではありませんので、全ての変数をグローバルにしてしまえばよいです。
さらに、jをmainの仮引数にしてやると、こちらも型は省略できて、
i;
main(j){
...
}
となって、iとjを結んでいた , の分が1文字へります。
ちなみに、「グローバル変数は0で初期化される」ので、こうすると後の0初期化用コードなども削れることがあります。ついでに、上の例の場合はjにはコマンドライン引数の数+1が入ります(int main(int argc, char *argv[]){ ... }としたときの argc と同じ)。
普通にプログラムを書く時、forループは
for(i=0;i<n;i++){
...
}
のように書くと思います。ここで、C言語の条件評価について思い出してみましょう。「0は偽、0以外は真」ですね。これを使って、
for(i=n;i;i--){
...
}
とすれば、1からnがnから0になったという違いはあるものの、ほぼ同じループをより短く表現できました。
しかし、iをグローバル変数にしていて0で初期化されている場合はこの必要はなく、 for(;i<n;i++) で充分ですね。上の例は例えば二重ループの内側のように毎回初期化が必要なときに用いると効果的です。
次もfor文についてです。ここではiが(グローバル変数にして)0で初期化されているとして、次のようなfor分を作ったとします。
for(;i<n;i++)
printf("%d\n",i);
これを次のようにします。
for(;i<n;)
printf("%d\n",i++);
これで1文字減り、出力もまったく同じです。このように、for分の一番最後のi++やi--は多くの場合省略できます。forに続く文中にiが登場しない場合でも、
for(;i<n;i++)
printf("A\n");
を
for(;i++<n;)
printf("A\n");
とすることで短縮できます。