すごすぎるグレイコード

変態すぐる

Gray codeが終了しました。私は結局8位でfinish。ナンバー1は*yuko*さんという方。唯一知らない(;´д｀)ざざっとコードを見た感じ、*yuko*さんとkurimuraさんのを合わせたら90B切れますね。Top10の7名は、謎の3乗*1をやって大幅短縮しているみたいです。私も10進数でまとめて出力できないかなーと一瞬思って難しそうなので諦めたのですが、そうか8進数ならOKですよねー…。というわけで、今回のグレイコード祭りを通して得たアイデアをドドーンとまとめておきたいと思います。

素直なグレイコード

i番目のグレイコードは

i ^ (i>>1)

で簡単に変換できることが知られています。私は色々と悩んだ結果、素直にこの方法で目一杯縮めることにしました。たぶん30回くらい書きました（笑）で、確実に通るので104B

i,k,v;
main(n)
{
  for(gets(&n);printf(i?&v:"Gray code  n=%c",n);)
    v=k?(i^i>>1)>>--k&1|48:~--i>>(k=n%8)?0:10;
}

iが正の整数だと(i^i/2)で大丈夫だったのだけど、負の数だとうまくいかなかったので諦めて普通にシフトした。nバイトのグレイコードを2進表示するためには、改行も含めて(n+1)回のループが必要になるので変数が増えるし、カウンタのリセットが必要になるのでここら辺が限界かなぁ。

kurimuraさんの1B短縮テクニック

Cで確実に通らないコードといえばargvを利用する方法が割と有名で、nをmain関数の第2引数にして

n=~n%9

みたいな使い方をします。最短を狙うなら、この辺の方法でごにょごにょするしかないと思うんですが、kurimuraさんのコードを見てみると、

n%=9u

となっています。そかそか、unsignedにしてやれば良いのね…。これでkurimuraさんに1B負けたのかorz

8進表示のグレイコード

これが思いつかなかった時点で完全に負けたかんじがします。とりあえず以下のコードを実行。

i,j,k;
main()
{
  for(i=0;++i<=32;)
  {
    printf("%o\n",k^=j*j*j);
    j=-i&i;
  }
}

実行結果

SU・GO・I☆

グレイコードとハノイの塔というのは密接に関わっていて、（ハノイで）移動させる円盤の番号と対応するビットを反転していくことでグレイコードになります。円盤の番号は2進で1が現れる最右のビット数と対応しているので、最右の1を得るビット演算

i & -i

を使って短くかけるのでハノイ方式は多分皆が思いつく方法だと思うのですが、8進表示でというところまでにはなかなか考えが至らない。思いついた人カシコー（゜Д゜）

感想

何度となく紹介してますが、
ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

は必読だなぁと思っておりますが、正直今回はこれを読んだ程度じゃ全然アカンのだと痛感しました。2年前にショートコーディング本を書いたとき、たくさんあるアイデアを厳選して厳選して厳選して、気が狂いそうになったのを思い出しますが、当時このアイデアを知っていたなら、絶対コードゴルフのページに書いてただろうナァと思います。ん〜む、奥が深い。

とまあ、色々ありますが、何より今回は参加者が30人超もいてそこそこ盛り上がっていたのが一番ですね。ふぃづばづのときみたく100人以上参加したらもっと面白かっただろうけど^^

*1:testというのは私が名前を間違ってpostしちゃったやつです。スマソ^^;

カメヲラボ

主にプログラミングとお勉強全般について書いてます

すごすぎるグレイコード

変態すぐる

素直なグレイコード

kurimuraさんの1B短縮テクニック

8進表示のグレイコード

感想