ショートコーディング入門編【解説1】

本稿はCodeIQで2013年3月14日～同年4月8日に出題された「ショートコーディング入門編」という問題の解法に関する記事です。

問題文はこちら

ショートコーディング入門編【解説1】

◆注意

本問は「ショートコーディング」・「コードゴルフ」と呼ばれる、ソースコードをできるだけ短く書く遊びの一環として出題されたものですので、一般的なプログラミング解説とは少し異なります。

◆中級の壁を突破するために

今回は、簡単な連立方程式を解く問題でした。扱うのは整数値で、解がない場合や無数にある場合は含んでいませんでしたので、それほど難しい問題ではなかったと思います。 まずは普通に書いてみましょう。

・解答例

#include<stdio.h>
 
int main()
{
  int a,b,c,d,e,f,x,y;
  int n;
  int i;
 
  scanf("%d¥n", &n);
  for(i=0; i<n; ++i)
  {
    scanf("%d %d %d¥n", &a, &b, &e);
    scanf("%d %d %d¥n", &c, &d, &f);
 
/*
|a b||x| = |e|
|c d||y|   |f|
 
1/(ad-bc) | d -b||e|
          |-c  a||f|
*/
    x = (d*e-b*f)/(a*d-b*c);
    y = (a*f-c*e)/(a*d-b*c);
 
    printf("%d %d¥n", x, y);
  }
 
  return 0;
}

◆コード短縮の基礎知識

・ビルトイン関数

gccでは、printfやscanfはビルトイン関数として定義されています。 http://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Other-Builtins.html#Other-Builtins

ですので、stdio.hのインクルードは省略することができます（もちろん警告は出ますが）。

・型名の省略とmain関数

gccではグローバル変数・関数の型名を省略すると、自動的にint型として扱われます（もちろん警告は出ますが）。int型を使うのであれば、グローバル変数として使う方が有利な場合があります。

また、引数の型も省略することができますから、main関数の引数として宣言しておくこともできます。ただし、省略する場合はすべて省略しなければエラーになります。

main(a,b){} // ok

main(a,float b){} // error

main関数は

int main(void)

や

int main(int argc, char *argv[])

と等価である必要がある…ということになっていますが、実際はmainというシンボルさえ定義されていれば実行プログラムは生成されますので、

main(a,b,c,e,d,f){}

みたいなコードでもコンパイルされます

・returnの省略

関数の型名を省略するとint型とみなされますから、何らかの整数値をreturnしなければなりませんが、これも省略できます。省略した場合は、実行時にレジスタに残った何らかの値が返ることになります。これを利用したテクニックもありますが、今回は利用しません。

・軽く短縮

main(a,b,c,d,e,f,n,i)
{
  scanf("%d",&n);
  for(i=0;i<n;++i)
  {
    scanf("%d%d%d%d%d%d",&a,&b,&e,&c,&d,&f);
    printf("%d %d¥n",(d*e-b*f)/(a*d-b*c),(a*f-c*e)/(a*d-b*c));
  }
}

色々と省略できる部分を削ってみました。scanf関数の書式にあったスペースや改行を省略しても、値を読み込むとき自動的に読み飛ばしてくれるので問題ありません。printfの引数に計算式を入れてしまっていますが、これには注意が必要です（後述します）。

上記のコードの、空白や改行を取り除くと154バイトあります。これをベースに短縮していきましょう。

・危険なgetsとEOF

テストデータは、最初の行がデータセットの個数になっているのですが、scanfで最後までデータを読み込んでいけば、最終的にEOFにたどり着きます。

つまり、最初の行は読み飛ばし、あとはEOFに達するまでscanfを繰り返せばよいのです。

main()
{
  scanf("%*d");
  for(;scanf(...)!=EOF;)
  {
    ...
  }
}

最初のscanfをgetsに置き換えるとさらに短くなります。gets関数は引数にバッファのポインタを渡さなければなりません。適当な変数を使って、

gets(&k)

のように書くことで、やり過ごすことができますが、もう少し短くするために、main関数の第2引数を使います。

main(a,v)
{
  gets(v);
}

型名を省略することで、vはint型なのですが、その値はargvのアドレスが入っていますので、これをバッファとして使ってしまいます。あるいはgets()みたいに引数自体を省略してしまえば、どこかのアドレスに値が読み込まれることになり、そのアドレスにメモリ保護がかかっていなければ、それで切り抜けられる場合もありますが、大体メモリ違反で落ちます。今回は、最初に呼び出す関数で引数省略すると落ちるので、負荷としておきました。

というわけで、こんな風に書いてみます。

main(n,v)
{
  gets(v);
  for(;scanf(...)!=EOF;)
  {
    ...
  }
}

第1引数は適当に使えば良いし、第2引数自体も最初のgetsで使うだけですので後で使いまわしができ、無駄にはなりません。しかしこのコードでは問題が出てきます。EOFというのはマクロで、これを使うにはstdio.hをインクルードしなければなりません。 EOFを避けるには、EOFの定義を事前に調べておきます。多くの場合（必ずではありません）は-1になっていて、今回のテスト環境では-1になっていました。つまり、ループを抜ける判定には

  for(;scanf(...)!=EOF;)

の代わりに

  for(;scanf(...)!=-1;)

とすることができます。また、cではtrue/falseを整数値で表すと、非0/0となりますので、

  for(;scanf(...)+1;)

と書くと、scanfの戻り値が-1の場合だけ-1+1=0になって、ループを抜けることができます。さらに、-1は2進表記するとすべてのビットが1になっているので、'~'演算子を用いてビット反転してしまえば、0になります。つまり、

  for(;~scanf(...);)

のように書くのが最も短い書き方ということになります。

main(a,b,c,d,e,f)
{
  for(gets(b);~scanf("%d%d%d%d%d%d",&a,&b,&e,&c,&d,&f);)
    printf("%d %d¥n",(d*e-b*f)/(a*d-b*c),(a*f-c*e)/(a*d-b*c));
}

ループ内がprintfだけになり、{}も省略できました。さらに不必要な変数も減り、かなり短くなりました。これで131バイトですが、まだまだ縮めることができます。たとえば、ad-bcは2か所出てきていますから、もう一つ変数を用意して、一度計算したものを保持しておけば、130バイトを切ることができますね。

これくらいまで短縮できれば、中級ゴルファーの仲間入りです。ちなみに、今回は中級のボーダーを150バイトに設定していました。

【解説2】へ続く