#contents
*code golfとは [#t0360dfa]
普通のゴルフは、ボールをカップに入れるまでのストローク数をいかに少なくするかを競います。code golf(コードゴルフ)は、目的の出力をするプログラムをいかにすくないストローク数で作成するかを競います。つまり、「ソースコードが短い方が勝ち」です。
そんなの面白いのか？と思われるかもしれませんが、やってみるとなかなか奥が深く、中毒性がありますよ。
*このページは？ [#g8ffa0d1]
このページでは、そんな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のサイト紹介 [#d7b371fa]
code golfはあまり「有用」ではないので、そのコンテストサイトは普通のプログラミングコンテストのサイトよりも残念ながら少ないです。
おそらく最大級だと思われるところは次のサイトです。
>http://codegolf.com/
このサイトは各問題に対して無差別級のランキングと、言語別のランキングが表示されます。ただし、残念ながらC言語は扱っていません。
C言語を扱っていて、このページを作った人がよく遊んでいるのはこちらのサイトです。
>http://golf.shinh.org/
このサイトはものすごくたくさんの言語を扱っています(2008年11月現在65言語)。サイトにも"The purpose of this server is not serious competition"(このサーバーは本気の競争を目的としたものではない)とあるように、さきほどのサイトほど縛りが厳格ではありません(例えば、ジョーク問題が多々あったり、正解すべき入力が全て分かっているのである特殊な場合だけできればよかったり、など)。しかし、中にはいろいろな要素がつまった良問もあり、やりがいがあります。
*code golfの本の紹介 [#m09e3fdf]
このページと同じくC言語でのcode golfを扱った本がすでにあります。[[Short Coding:http://www.amazon.co.jp/dp/4839925232]]という本で、非常に評判がよいです(このページを作った人は貧乏なので買ってませんから、口コミ情報ですが)。
このページは「code golf''入門''」なので基礎的なところしか扱っていませんが、こちらの本は常人には考え付かないような、ものすごく高度なことをやっておられるそうです。ですから、このページを見てcode golfに興味が沸いた方はぜひとも読んでみるとよいと思います。このページを書いた人も近々購入しようと思っています。
*コード短縮術 [#l28729e1]
**はじめに [#oa2310e3]
それでは、実際にコード短縮の方法をやっていきます。
コード短縮の方法には、主に二つあります。
-アルゴリズムを改善する
-小手先の業でちまちま削る
アルゴリズムの改善とは、例えば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%程度しか減りません。しかし、小手先の業は「どんな問題にも普遍的に適用できる」という利点があります。アルゴリズムの改善はその問題ごとに考えていかねばなりません。なので、このページでは主に小手先の業を紹介し、アルゴリズムについては余裕があればケーススタディの形で取り扱いたいと思います。
**小手先の業 [#xd2b12dc]
***スペース、改行は削る [#x52865d9]
これは基本中の基本です。いらないスペース、改行は全てなくしましょう。
(ただし、このページでは読みやすさのためにコード例は全て改行とスペースを削らないで書きます。)
さて、いらないスペースを削るのは当然ですが、「いると思っているスペース」でも実はいらないことがあります。
入力が標準入力から
1 2
と与えられるとき、scanfを使うならば(code golfではscanfは非常によく使います)たいていは
scanf("%d %d",&a,&b);
とすると思います。
しかし、2つの%dの間のスペースは必要なく、
scanf("%d%d",&a,&b);
でも期待通り動作します。
また、ポインタを宣言するときには、通常
int *a; // 標準的な書き方
int * a; // これもたまに見かける
int* a; // 「ポインタ型」を強く意識した書き方
のようにどこかにスペースを1つ以上いれますが、これも
int*a;
として問題ありません。
***#includeはいらない [#v0266aba]
C言語入門のときは「おまじない」といわれ、いつのまにか「ヘッダファイル(.h)をincludeすることでそのライブラリが使えるようになる」という理解にすりかわってしまいがちな #include ですが、実は「''C言語ではプロトタイプ宣言は必要ない''」ので、いりません(そもそも初期のCにはプロトタイプ宣言はありませんでした)。
じゃあなんのためにヘッダファイルをincludeしてるの？という話ですが、実はプロトタイプ宣言をしておくと、誤った型の引数で関数を呼び出した時などにチェックしてくれます。しかし、code golfではそんなことおかまいなしなのでincludeはしません。
ヘッダファイルをincludeする他の理由として、ヘッダファイルでdefineされている定数(例えばEOFやstdinなど)を使いたいこともあります。この場合EOFなどの決まった値はその値を直接書くことで解決します。stdinなどはなるべくその定数を明示しなくてもよい関数を利用するようにし、どうしても必要な場合にのみincludeします。(実はstdinといえどもファイルポインタ、突き詰めれば値なので、数字を直接書けば解決する(こともある)のですが、それはおいおいやっていきます。)
***mainの宣言は型なし、引数なしで [#p9262b3c]
普段まじめにプログラムを書いている方は、main関数を
int main(){
...
}
あるいは
int main(void){
...
}
などと書いていると思います(返り値の型をintではなくてvoidとしてる方もおられるかもしれません)。
しかし、C言語の入門書の最初の方によく書いてあるように、int, voidを省略して
main(){
...
}
と書いても問題ありません。
***変数はグローバル宣言、うち1つはmainの仮引数に [#k921238b]
さて、一つ前で関数の型が省略できると書きましたが、これは「''型が省略されたグローバル識別子は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 と同じ)。
***なるべく短い名前の関数を使う [#bf3f0152]
code golfでは、安全性や統一性(読みやすさにつながる)よりも、短さが第一です。なので、普段はあんまり使わないような関数もじゃんじゃん使います。
以下に、普段使うライブラリ関数と、それと似たような機能で名前が短い関数をまとめました。
|普段使う関数|似た関数|違い|
|printf|[[puts:http://www.linux.or.jp/JM/html/LDP_man-pages/man3/puts.3.html]]|putsは最後に改行が入る。またputs("%d",i)などとはできず、決まった文字列を出力するだけ。|
|fgets|[[gets:http://www.linux.or.jp/JM/html/LDP_man-pages/man3/gets.3.html]]|getsは読み込む長さを指定できない。また標準入力からしか受け取れない。「危険なので使うな」と書いてあるが、code golf的にはおかまいなし。|
|strchr|[[index:http://www.linux.or.jp/JM/html/LDP_man-pages/man3/index.3.html]]|なし。ただし、システムによってはindexは存在しない。|
|strrchr|[[rindex:http://www.linux.or.jp/JM/html/LDP_man-pages/man3/index.3.html]]|なし。ただし、システムによってはrindexは存在しない。|
|strcpy|[[strdup:http://www.linux.or.jp/JM/html/LDP_man-pages/man3/strdup.3.html]]|関数名の長さは同じ。ただし、strcpyはコピー先に自分で領域を確保しなければならないのに対し、strdupは関数内で領域を確保してくれるのでその分コードが減ることが多い。|
|strncmp|[[bcmp:http://www.linux.or.jp/JM/html/LDP_man-pages/man3/bcmp.3.html]]|なし。ただし、システムによってはbcmpは存在しない。また、長さを指定しない場合はstrcmpを使ったほうが短い(または長さが同じ)。|
***forはiを減らす可能性も考えて [#k5e8754b]
普通にプログラムを書く時、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++ はムダ！ [#gc5c60bb]
次も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");
とすることで短縮できます。
***複文 { ... } は使わない [#p9b279f4]
複文とは、{ } で囲まれた文のことです。ここでもforを例にとります。例えば、次のようなコード
for(;i++<n;){
j--;
printf("This is the %dth loop\n",i);
}
があったとします。しかし、forの文法をよく思い出すと、
for(式;式;式)
文
なのです。しかし、通常は文1つでは収まらないので { } でくくって複数の文を1つまとめて(上の例のように)使っています。さて、つまり { } を省略するにはこの二つを1つの文にしてしまえばよいということです。この二つは式であり、「''式はカンマでつないで連続して書ける''」ので、
for(;i++<n;)
j--,printf("This is the %dth loop\n",i);
とできます。
さて、式だ文だと難しそうなことを書きましたが、基本的に評価して結果が返るもの(変数に代入できるもの)は全て式、それ以外は文です。ちなみに、式⊂文ですので、式であれば同時に文でもあります。forの文法が
for(式;式;式)
文
なのに、文のところに式(j--,printf(...))を入れられるのはこのためです。(逆に、式のところに文は入れられず、if(...)は文(i=if(a==1);とかできない)なので、for(;if(a==1);){ ... } などとはできません。）
ややこしくなってしまいましたが、最初は「カンマでつないでみて、コンパイルエラーになったら諦める」くらいの気持ちでいいでしょう。
***for文の空欄を利用する [#o487c016]
さて、さきほどの例ですが、実はもう1バイト減らせます。for(A;B;C) の C の部分を利用するのです。
for(;i++<n;printf("This is the %dth loop\n",i))
j--;
これでprintのセミコロンのぶんだけ減らすことができました。一般に、
for(a;b;)
c,d;
を
for(a;b;d)
c;
とすることで1バイト減らせます。ただし、dを入れるところが空欄でなかった場合、例えばeが入っていた場合には for(a;b;e,d) となって , が1文字増えるので結局同じ長さとなります。
このように、forはあいたところにいろいろ入れることができる(さらに、while()とfor(;;)で長さが同じ)なのでwhileよりも多用されます。
***ifは使わない [#l430a30f]
ifを使わずに条件分岐(のようなもの)を実現する方法は、二つあります。
- ? を使う
- &&, || を使う
?は普通の使い方と同様なので、簡単ですね。例えば
if(x>0)
y=x;
else
y=-x;
を、
y=x>0?x:-x;
とします。通常のプログラミングなら見やすさのためにカッコをつけて (x>0?x:-x) とするところですが、つけなくてもプログラム的には問題ありません。
次に && または || を使う方法です。[[C言語のページ:http://vipprog.net/wiki/prog_lang/c.html#l13d9672]]にも書いてあるように、&&および||はそれ以上評価する必要がなくなるとそこで評価を中止します。このことを用いて、例えば
if(n>0)
a++;
puts("test");
を、
n>0&&a++;
などとします。これは a+=n>0?1:0; より2文字短く、先ほどの ? とうまく使い分けてより短いコードを生成できます。
n>0&&puts("test");
などとしますこれは n>0?puts("test"):0; より1文字短く、先ほどの ? とうまく使い分けてより短いコードを生成できます。
*** ==演算子は使わない [#s3299e15]
前にも書いたように、「''0は偽、0以外は真''」です。これを利用して、
a==n
の形の条件式を短くできます。具体的には、
a-n
とするのです。例えば、
a==5&&puts("5"); // aが5なら"5"と出力
を、
a-5||puts("5");
とします。ただし、a==nはaとnが等しいとき真、a-nはaとnが等しいとき0(つまり偽)ですから、論理を逆転させないといけません。
他にも(==演算子ではありませんが)、 n<5とn-5は長さが同じですが、n>-5はn+5よりも1文字長いので、
for(;i-->-5;)
...
を、
for(;i--+5;)
...
とできたりもします。ラッキーなことに、--と+の間にかっこはいりません。
***文字コードは数字で直接書く [#z4bbb775]
これは非常によく使います。例えば、Xの文字コードは10進数で88ですから、
putchar('X');
よりも
putchar(88);
としたほうが1文字短くなります。
printf("X") のが短いじゃないか・・・と思われるかもしれませんが、例えばiが偶数ならX, 奇数ならYを出したいとすると、
printf(i%2?"Y":"X");
putchar(i%2?89:88); // 1文字短い
putchar(88+i%2); // iが偶数なら88+0, iが奇数なら88+1=89
などのように、putcharのほうがかなり縮みます。これはprintfが毎回 " " をつけねばならないこと、また文字コードは数字であるので足したり引いたりで別の文字にできること(printfの場合、"X"+1は"Y"ではありませんのでむり)によります。
ちなみに、文字コードは
printf("%d",'調べたい文字');
で調べられます。例えば、
printf("%d",'X');
とすれば 88 が表示されます。
***gccの拡張を利用する [#m957d2a7]
gccにはさまざまな拡張(標準のCにはない機能)があり、[[こちらのサイト:http://cms.phys.s.u-tokyo.ac.jp/~naoki/CIPINTRO/gccextend.html]]に詳しくまとめられています。
数あるgcc拡張の中でも、特に有用なのは以下の二つです
-三項演算子における中間項(a?b:c の b の部分)の省略
-大きい方、小さい方を表す演算子
です。前者は、例えばnが0以上に限られているとして
a=n?:-1; // nが非0ならa=n, そうでなければa=-1
などと使えそうです。
後者は
x=i>?-i;
のようにするとiの絶対値が標準ライブラリ関数のabs()を使うよりも1バイト短くもとまります。ただ、こちらはc++でしか使えないのが残念なところです。
***trueの否定の否定は1 [#hfbeab0f]
例えば、x=100のとき、xはtrue, !xはfalse, そして!!xはもちろんtrueです。しかし、値としては、
x: 100
!x: 0
!!x: 1
となるのです。0以外の数は真なので!0はなんでもいいのですが、たいていの処理系で1となります。(~0とは違います。「''!は論理否定、~はビットごとの否定''」です。)
例えば、yはxがtrueなら1、falseなら0としたいとき、
y=x?1:0; // 三項演算子を利用
x&&y=1; // ifは使わない の章を参照
y=!!x;
のように、!!xを利用するのが一番短くなります。ちなみに、xの最下位ビットが必ず1である(⇔xは0以外ではかならず奇数)なら
y=x&1;
でもできますが、長さが同じですし!!xならどんなxにでも使えます。
***返り値をうまく利用する [#h53cc0f1]
たいていのライブラリ関数はなんらかの値を返します。しかし、普段はその値を無視してしまうことがあります。もったいないのでうまく利用しましょう。
以下に、普段は返り値を無視してしまいがちな関数をまとめました。
|関数|返り値|
|puts|非負の数とあるが、たいがいは出力した文字数(末尾の改行を含む)を返す。|
|printf|出力した文字数を返す。|
|scanf|%で指定した型と一致した個数(正しく代入できた個数)を返す。入力が何もなかった場合は、EOF(-1)を返す。|
|read, write|読み込み or 書き込みしたバイト数を返す。|
特に、scanfは、頻繁に以下のように使われます。
for(;~scanf("%d%d",&a,&b);)
...
入力が2つの整数(の複数行)の場合にこのようにするとどうなるか考えてみましょう。入力があったときには、scanf(...)の返り値は2(2進数で10)ですから、~2で1111･･･01となり、trueです。入力の最終行に達すると、scanf(...)で-1(二進数で1111･･･1)が返り、~-1は0となってforを抜けます。つまりこの条件文は入力の最後に達したかどうかを判定しているのです。
***続く [#lb4e06ed]
続く
**アルゴリズムの改善 - ケーススタディ [#p801e95c]
余裕があればやります
