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

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

問題文はこちら

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

◆注意

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

解説1はこちら

◆上級の壁突破・最短コードへ

上級の壁のボーダーは120バイトに設定していました。やってみた方はよくわかると思いますが、このラインを突破するにはいろいろと努力が必要になります。

・'%d'多すぎ

コードをパッと見て、scanfの部分が明らかに長いですから、ここを何とかしましょう。scanfは整数値を1つだけ読み込み、ループカウンタを設置して、ループ回数が6の倍数になったところで出力するようにします。…が、この方法では分岐が多くなり、短く書くのは難しそうに見えます。

i;
main(n,a,b,c,d,e,f)
{
  for(gets(a);~scanf("%d",&n);)
  {
    ???
  }
}

・リレー方式

6回ループして、読み込んだ値をそれぞれa,b,e,c,d,fに割り当てるために、こんなコードを書いてみます。

i;
main(n,a,b,e,c,d,f)
{
  for(gets(b);~scanf("%d",&f);)
  {
    a=b,b=e,e=c,c=d,d=f;
    if(++i%6==0)printf(...);
  }
}

変数fに値を読み込み、それを手前の変数に渡していきます。こうすると、最初に読み込んだ値は6回目でaまでリレーされて、分岐は出力判定だけになります。

また、さりげなくではありますが、グローバル変数iが0で初期化されていることも利用しています。

・getsを消す

最初の行を読み飛ばすといっても、そこに書かれているデータは整数が1つだけですので、まとめてscanfで処理します。カウンタは6の倍数で判定するしかありませんので、出力部分のif文を工夫します。

i;
main(a,b,e,c,d,f)
{
  for(;~scanf("%d",&f);++i)
  {
    a=b,b=e,e=c,c=d,d=f;
    if(i!=0 && i%6==0)printf(...);
  }
}

これでgetsを取り除くことができました。if文の条件式は、式の値が0ならfalse、0でなければtrueになりますので、次のように書き換えます。

    !i|i%6||printf(...);

'!'で0を1に、非0を0にすることができます。つまり、iが0のときは!i=1、i%6=0で和が1になり、iが非0のときは!i=0、i%6=0になります。論理的OR演算子'||'は、左辺値が0のときのみ右辺値を評価しますので、iが0ではなく、かつ6の倍数のときのみprintfが呼び出されることになります。

i;
main(a,b,e,c,d,f)
{
  for(;~scanf("%d",&f);!i++|i%6||printf(...))
    a=b,b=e,e=c,c=d,d=f;
}

iを後置インクリメントにしてまとめてしまいます。!i++|i%6と書くのか、!i|i++%6と書くのか、だいぶ怪しくなってきましたね。このあたりは未定義動作ですので、実際に動かしてみてうまく動きそうなパターンを探してみてください。（ちなみに、今回は未定義動作によってうまく動かないコードでもインクリメントの位置を変えただけで動く場合は、一応記録として認定し、該当の方には後から再提出をお願いしました。）これで130バイトは切ることができるようになりましたが、それでも代入式が冗長に感じます。

・main再帰

代入式を避ける方法の一つとして、代入したい値を引数として関数呼び出しを行うというものがあります。

i;
main(a,b,e,c,d,f)
{
  ~scanf("%d",&f)&&main(b,e,c,d,f,!i++|i%6||printf(...));
}

main関数の引数をa,b,e,c,d,fと宣言しておいて、main(b,e,c,d,f,*)のように再帰的に呼び出すと、かなりスッキリと書くことができます。'&&'を利用してscanfが成功したときのみmain関数を呼び出すようにしておけば、無限ループに陥ることもありません。

見た目にも美しい、コード短縮テクニックです。

・printfの部分を短縮してみよう。

このあたりで、計算と出力部分を本気で短縮します。

printf("%d %d¥n",(d*e-b*f)/(a*d-b*c),(a*f-c*e)/(a*d-b*c));

ad-bcが重複していますから、適当に別の変数を使って

k=a*d-b*c;
printf("%d %d¥n",(d*e-b*f)/k,(a*f-c*e)/k);

のように短縮可能です。しかしこれで十分でしょうか？今回の問題は、『入力データはすべて整数』と書いてありましたが、配布された値を注意深く見てみると、『0』が含まれていません。ここを突いて短縮してみましょう。

x,yのうち、y=(af-ce)/kを計算してしまいます。さらに、これをfについて解くと、f=(ky+ce)/aとなり、これをx=(af-ce)/kに代入して整理すると、x=(e-b*y)/aとなります（途中計算略）。aでの除算が入りますから、テストデータに0が含まれている場合は0除算のエラーが起こるのですが、0を含まないデータであることを確認済みであれば、これでも問題ないはずです。

printf("%d %d¥n",(e-b*f)/a,f=(a*f-c*e)/(a*d-b*c));

新たに変数を用意せず、変数fを使いまわします。ここで、yの値を先に計算するには理由があります。関数の引数に、式を埋め込んだ場合、式が評価される順番は厳密に決まっているわけではありませんので、処理系によって変わる可能性がありますが、gccの場合は後ろの式から評価されるようになっています。ですので、xを先に計算すると引数の部分に式を埋め込むことができず、少しロスが出てしまうのです。

しかしこのコードは多項式の乗除が多く、括弧を使わねばならないというところが気になります。そこで、次のように書き換えます。

f=a*f-c*e;
printf("%d %d¥n",(e-b*f)/a,f/=a*d-b*c);

式が一つ増えますが、追加する文字数が括弧に必要な文字数よりも少なくて済むので、結果としてコードが短くなります。

さて、ここまでのテクニックを総合すると、次のようなコードに仕上がります。

i;
main(a,b,e,c,d,f)
{
  ~scanf("%d",&f)&&main(b,e,c,d,f,!i++|i%6||printf("%d %d¥n",(e-b*f)/a,f/=a*d-b*c))f=a*f-c*e;
}

f=の部分をまとめて計算すると括弧が必要になってしまいますので、分割することでさらに短縮できます。これで112バイト、120バイトの壁も超えることができました。

◆最短コードへ〜ガチゴルファーのテクニック〜

main再帰を使って読み込み部分を短縮しましたが、上級のCゴルファーはもっとダイレクトな方法を使います。 変数の宣言を行うと、各変数のアドレスは連続しており、scanf("%d",&a+k)のような形で、基準となる変数のアドレスに適当な値を加えることで直接読み込むことができます。つまり、

a,b,e,c,d,f;
main(i)
{
  for(;~scanf("%d",&d-i);i=--i/6?!printf("%d %d¥n",(f-b*a)/d,a/=d*c-b*e):i)
    a=d*a-e*f;
}

このように書くことができます。変数のアドレスは連続する場合が多いですが、変数名等のちょっとした違いで変わってしまいます。たとえばIdeone.comで動くようにしようと思えば、変数名をa,b,e,c,d,fとした場合にどういう順序で配置されるかを事前に調べておいて、式をそれに合わせて変形します。これは面倒な作業で、ここまでやる人は頭おか…じゃなくて熱いショートコーディング魂を持っているということでしょう。

ちなみに、main再帰を使っても同じサイズのコードが書けます。

a,b,e,c,d,f;
main(i)
{
  ~scanf("%d",&d-i--)
    &&main(i/6?!printf("%d %d¥n",(f-b*a)/d,a/=d*c-b*e,a=d*a-e*f):i);
}

ともかくも、これで104バイト、110バイトの壁まで打ち破り最短コードに達しました！！（※これらのコードはいずれもIdeone.com 仕様です）