Cozy Ozy このページをアンテナに追加 RSSフィード

2015-11-23 tailsさんとclimpetさんのものすごいC

[][]tailsさんのものすごいC tailsさんのものすごいCを含むブックマーク

CodeIQ MAGAZINEの記事にはすべて書けないかもしれませんので、まずはこちらのエントリで。

コードゴルフ参加者の皆さんはすでにランキングとか、angelさんによるシンプル・ライフゲーム tailsさんコード解析Perl最短コード解説を見ておしっこちびってるかもしれませんが、Cの194Bコードも素晴らしいです。コードを見ても全く意味がワカラナイよ!という方もいらっしゃると思いますので、簡単に解説しておきます。

i;j;
char a[1<<16];
main(n,h,w,s,t){
  for(scanf("%d%d%d %[^0]",&n,&h,&w,a),s=++w*h;i/s<n;a[i+s]=a[i++]^4&t)
    for(t=67196,j=17;j;t/=a[--j<9?i/s*s+(i/w-j/3-~h)%h*w+(i%w-j%3+w)%~-w:i]/5-7);
  j/=puts(a+i);
}

基本的なテクニックは、

C言語によるショートコーディング入門編解説その1〜中級の壁を突破するために

C言語によるショートコーディング入門編解説その2〜上級の壁を突破するために

あたりをご覧ください。


データ構造と入出力

Cの上位陣はおそらく共通していると思いますが、文字列データは「(世代数N)×(フィールド縦H)×(フィールド横W+1)」が収まる程度の1次元配列で持ち入力はscanf1回、出力はputs1回で済ませています。W+1としているのは、改行文字の分も必要だからです。

1次元の文字配列は、コピーや書き換えを行わず、世代ごとに新しい領域に書き込んでいきます。

scanf("%d%d%d %[^0]",&n,&h,&w,a)

の部分も工夫されていますね。

%[.*\n]

のように読み込みたい文字に改行文字を含むと複数行をまとめて読み込むことができますが、

%[^X]

のようにX以外の文字を読み込むように指定し、Xを'.', '*', '\n'以外にしておくとうまく読み込むことができますし、改行文字も文字列の中に入っていますから出力はputs関数を1回呼ぶだけで済みます。

forループ2回

普通に書こうとすると、(1)世代数・(2)フィールド縦・(3)フィールド横・(4)近傍上下・(5)近傍左右の5重ループを要するはずですが、(1)(2)(3)と(4)(5)をそれぞれまとめて2重ループに収めています。最初のループは割と書きやすいですが、2番目のループ内では改行文字を上手くかわした上で生死判定を行う必要があり、高度な技術が必要となります。

XOR4

'*'と'.'のASCIIコードはそれぞれ42と46で、4との排他的論理和を取ることで相互に変換が可能です。

a[i+s]=a[i++]^4&t

この部分で、tをフラグとして4のon/offを行う仕組みです。

生死判定

どのような条件でビットのon/offを行うかを整理しておきましょう。

対象のセルが正の場合

周囲に生のセルが2, 3以外、つまり0, 1, 4, 5, 6, 7, 8の場合、死に切り替える

対象のセルが死の場合

周囲に生のセルが3つある場合、生に切り替える

この情報をビットベクトルとして保持したものが、67196という値です。

67196

67196を2進表記すると

10000011001111100

になっています。下位2ビットは4との排他的論理和を得るのに不要ですから、0でも1でもかまいません。もう少しわかりやすく書くと、上位2ビット分の0を補って

00100000 110011111 00

のように左の8文字が死→生、その隣の8文字が生->死のフラグになっています。

t/=a[--j<9?i/s*s+(i/w-j/3-~h)%h*w+(i%w-j%3+w)%~-w:i]/5-7

の部分で、'.'=46, '*'=42, '\n'=10をそれぞれ5で割ると、9, 8, 2(小数点以下は切り捨てられる)となり、さらに7を引くと、2, 1, -5となります。'.'の場合は、計算結果が2で割ることになり、1ビット右シフトを行うのと同様の結果が得られます。'*'の場合は1で割ることになり、ビットシフトを行わない場合と同様の結果が得られます。Perlのコードでは改行文字を気にしなくても良いので、もっと簡単にシフトできるのですが、Cの場合は改行文字を考慮しなければなりません。そこで、改行文字の場合に絶対値が2より大きな値になるようにすることで、tの値が必ず0になるようにしているのです。また、対象のセルが'*'の場合は8回余分に右ビットシフトを行うようにしています。jの初期値が9ではなく17になっているのはこのためです。

[][]climpetさんのものすごいC climpetさんのものすごいCを含むブックマーク

climpetさんも194Bのコードを公開してくださっているので、紹介しておきます。

char z['÷'];
i,j,c,n,w;
main(h){
  scanf("%d%d%d %[^_]",&n,&h,&w,z);
  for(h*=++w;i<n*h;++i)
    for(c=j=9;j--;z[h+i]=~i%w?c-15&&z[i]%c?46:42:10)
      c+=z[(i%w-j%3+w)%~-w+(i/w-j/3-~h)*w%h+i/h*h]%3;
  n=!puts(z+i);
}

全体的にはtailsさんと同じですが、配列サイズに'÷'という定数を用いています。'÷'はUTF-8でC3B7(50103)で、今回はn, h, wの最大値がそれぞれ30, 40, 35ですので、30×40×35=42000あれば良いので十分な大きさです。

特に素晴らしいのはやはり生死判定の部分ですね。カウンタ変数cの初期化コストを抑えるため、近傍走査のためのループ変数jと同じ値(9)をセットしています。'.', '*'のASCIIコードはそれぞれ46, 42で、これらに対してで3の剰余を計算するとそれぞれ1, 0になることから、死んでいるセルをカウントしています。このようにすると、

  • 中心セルが「死」で周囲3セルが「生」の場合、cは6加算
  • 中心セルが「生」で周囲2セルが「生」の場合もcが6加算

されることになります。つまり、これら2つの条件はcが9+6=15であるかどうかの判定だけで済みます。残りの条件の判定を行うため、同じようにcの値を見てみると

  • 中心セルが「生」で周囲3セルが「生」の場合、cは5加算

なので、cの値は9+5=14になります。しかし、今度は14かどうかの判定をしようとすると、

  • 中心セルが「死」で周囲5セルが「生」の場合もcが5加算

となり、14かどうかを調べるだけでは判定できません。これらの区別するのに、'.'と'*'のASCIIコードすなわち46と42を利用しています。

  • 中心セルが「死」の場合はASCIIコードが46で、14で割り切れない
  • 中心セルが「生」の場合はASCIIコードが42で、14で割り切れる

これを上手く利用しています。cの初期値が9であることと、死んでいるセルをカウントするということ、ASCIIコードの値の調和がたまらないコードですね!!

トラックバック - http://d.hatena.ne.jp/Ozy/20151123