Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/09/26

Anarchy Golf 339. Puyo Puyo

| 00:10

http://golf.shinh.org/p.rb?Puyo+Puyo

初めて出題した golf の問題なので解説を書いてみようと思う.

問題

ぷよぷよのスクリーンが与えられるので連鎖後のスクリーンの状態と連鎖数を表示する.

ぷよは r, g, b, y, p で表示される.もちろん赤,緑,青,黄,紫に対応している.

スクリーンのサイズはぷよぷよの通り横6縦13である.

本来のぷよぷよでは13段目はスクリーン外で見えない&消えないという性質を持つので,幽霊連鎖というものが可能だが,今回はこの仕様は省いた.


入出力

入力1

|      |
|      |
|      |
|  g   |
|  yyyr|
|  bbbb|
| rygyr|
| gypgr|
|ggrrpr|
|rrppgb|
|yggrgg|
|grrbbb|
|bgryyg|
+------+

出力1

|      |
|      |
|      |
|      |
|      |
|      |
|      |
|      |
|      |
|      |
|      |
|y     |
|b  yyg|
+------+
9 chains

入力2

|      |
|      |
|      |
|  ygg |
| ryygr|
|rbbbbg|
|gryggb|
|rryygb|
|ybgrbg|
|yrrbgg|
|rgbgyy|
|brbgyr|
|gbyyrb|
+------+

出力2

|      |
|      |
|      |
|      |
|      |
|     r|
|     b|
|g    b|
|ybgrbg|
|yrrbgg|
|rgbgyy|
|brbgyr|
|gbyyrb|
+------+
2 chains

入力3

|gg py |
|grgpbb|
|rbbyrb|
|ybpbyy|
|gbypgr|
|rrbyyr|
|rbyggg|
|grryyr|
|gbybbb|
|gprprr|
|yygybr|
|pypgpp|
|bpggpr|
+------+

出力3

|      |
|      |
|      |
|      |
|      |
|      |
|      |
|      |
|      |
|      |
|      |
|      |
|      |
+------+
19 chains

入力には,なるべく色々なパターンを盛り込んだ.

入力1は凹型でつながって消えるぷよを入れた.最初にスクリーンにそれなりにぷよがあるが連鎖後にぷよが少し残る例にした.

入力2は同時に3色同時に消えるぷよが存在する.p が出現しない4色の例である.ぷよがたくさん残るようにした.

入力3はぷよぷよの醍醐味である19連鎖全消しである.積み方はこちらから拝借した(3:30付近左側).

アプローチ

再帰で探索を行う.基本的な方針は以下のようになる.

  1. あるぷよからスタートして,つながっている同じ色のぷよを選んでいき,個数を数える.
  2. つながっている個数が4個以上であれば印をつけておく.
  3. すべてのぷよに1を行う.
  4. 印のついたぷよを消す.
  5. 宙に浮いたぷよを落下させる.
  6. ぷよが消えていれば,連鎖カウントをインクリメントし,1から繰り返す.

再帰的に探索する際に,探索済みであることを記録しないと無限ループに陥るので注意が必要である.

サンプル出力を作成したコード

このコードはサンプル出力を正確に作るために書いたものなのでかなり冗長である.

  1. つながっているぷよのグループに 1 より大きい番号 g を振り d[y][x] に記録し,f[g] に個数を記録していく.
  2. d[y][x] が 0 より大きければ,探索済みであることが分かる.
  3. 全てのぷよにグループ番号がふられたら f[g] を走査して,4以上であれば,それの番号のぷよを消す(space(asciiで32)を代入).+消した後は宙に浮いたぷよを落とす.
i,j,k,g,f[99],b,c;char s[14][9],d[14][9];

find(y,x)
{
	if(d[y][x]||s[y][x]!=c) return;
	// 個数を数える
	f[g]++;
	// つながったぷよのグループに番号をつける
	d[y][x]=g;
	// 上下左右に再帰的に探索
	find(y,x-1);
	find(y,x+1);
	find(y-1,x);
	find(y+1,x);
}

main()
{
	for(i=0;i<13;i++)
		gets(s[i]);
	
	b=1;
	while(b) {
		// フラグ用配列の初期化
		memset(d,0,14*9);
		memset(f,0,4*99);
		g = 1;
		// 各ぷよについて
		for(i=0;i<13;i++) for(j=1;j<7;j++) {
			c=s[i][j];
			if(c!=32) {
				f[g] = 0;
				// 個数をカウント
				find(i,j);
				if(f[g])g++;
			}
		}
		b=0;
		// 個数が4個以上のグループは消す
		for(g=0;g<99;g++)
			if(f[g]>=4) {
				for(i=0;i<13;i++) for(j=1;j<7;j++)
					if(d[i][j]==g)
						s[i][j]=32;
				b++; // 消えたぷよがあれば次の連鎖を行う (b=trueでよい)
			}
		
		// ぷよを落下させる
		// 各列の下の段から見ていき,空いていれば,
		// それより上にあるぷよのうち最も下にあるものを持ってくる.
		for(j=1;j<7;j++) for(i=12;i>=0;i--)
			if(s[i][j]==32)
				for(k=i-1;k>=0;k--)
					if(s[k][j]!=32) {
						s[i][j]=s[k][j];
						s[k][j]=32;
						break;
					}
	}
	
	for(i=0;i<13;i++)
		puts(s[i]);
	puts(gets(s[i]));
	// 連鎖数は表示していない
}

ゴルフしたコード

C 言語で 275B まで詰めたコードである.

b,f,n;
char*p,*q,s[256],d[256]; // (*1)
r(x)
{
	s[x]/62*s[x]==*p // (*4)
		&& !n^d[x] // (*9)
		&& (
			d[x]=!n, // (*8)
			r(x-1), // (*10)
			r(x+1),
			r(x-9),
			r(x+9),
			n>3 ?
				s[b=0,x]=32 (*7)
			:
				f++ // (*6)
		);
}
main(c)
{
	for(read(0,s,126);!b;c++) // (*2)
	{
		for(b=p=s;*++p;n=f,r(p-s)) // (*3)
			n=f=0,r(p-s); // (*5)
		for(;--p-s;) // (*11)
			for(q=p;*p==32&&q>s;q-=9) // (*12)
				*p=*q,*q=32;
	}
	printf("%s\n%d chains",s,c-2); // (*13)
}

まず2次元配列だった入力を1次元配列に落とした(*1).配列の次元を落とすのは,問題によっては配列に触る部分のコードが大きくなるが,今回は縮めることが可能な例である.

入力配列を1次元に落とし込んだので入力は gets を使わず read で一気に読み込める(*2).

繋がっている個数の判定は再帰関数 r() で行う.r には s からの位置である整数 x を渡す.p を渡すようにすると,引数の型を書かないと dereference できなくなるので,r(char*x) となり 5B 冗長になるからである.

p=s から初めて 入力の終わりまで探索する(*3).これにはもちろん枠である |, +, - や,ぷよが無い場所である space や,改行コードまで探索に含まれることになる.よって r() の先頭でこれらを弾く(*4).

ぷよ以外を弾く方法で最も簡単なものは isalpha(x) である.もちろんこれよりも短く書くことができる.

characterascii
nl10
sp32
+43
-45
b98
g103
p112
r114
y122
124

以上のように文字コードを分析すると,| が 124 であり, - が 45 なので s[x]/62 == 1 でぷよかどうかを判定することができる.(*4) の s[x]/62*s[x]==*p はこの s[x]/62==1 と同じ色かどうかの判定 s[x]==*p を同時に行うことでコードを縮めている.

変数 f, n を 0 で初期化しておく(*5).f はつながったぷよの数を数える(*6).n は f を後に代入する.

一度目の r() の呼び出しでぷよの数を数え(*5),二回目の呼び出し(*3)でぷよを消す(*7).動作切り替えのフラグが n で,二回目の呼び出しの前 n に f を代入する(*3).同じ変数を使ってしまうと一度目の呼び出しの時に動作が切り替わってしまうからである.

一度目の呼び出しの探索済みフラグは d[x]=1,二度目のフラグは d[x]=0 とする(*8). (*9) ではこれらを同時に判定している. d[x]== (n?1:0) と同じである.n は f を代入しているので正の整数を取りうる(ビット演算が困難)が, ! で否定することで 0 か 1 になる.これで ^ でビット演算を行うことでコードを縮めることができる.

r() は前述の通り再帰的に探索を行う.一行に改行込みで 9 文字あるので,左は x-1, 右は x+1,上は x-9,下は x+9 である(*10).

二回目の探索で n が 4 より大きければ,そこにスペースを代入し,連鎖が起こるか,次のループに入るかのフラグ b を 0 にする(*7).この処理は(*10)よりも後に行わなければ(*4)で行っている同じ色かどうかの判定で失敗する.

これでぷよを消すところまでは終わりである.次に宙に浮いたぷよを落下させる.

ポインタ p は最下段の右端まで進んでいるので今度はデクリメントでループを回す(*11).

位置 p のぷよがスペースである場合,p より上にあるぷよで最も下にあるぷよをポインタ q で探索する(*12).通常であれば

for(;--p-s;) if(*p==32)
	for(q=p;q>s;q-=9) if(*q!=32)
	{
		*p=*q,*q=32;
		break;
	}

となるのだが,*p==32 の判定を for 文の継続判定に組込むことで有効にコードを縮めることができる.*q!=32 は不要である.q がスペースであってもスペース同士の交換になり,*p==32 の継続判定も有効になるからである.*p==32 が継続判定に組み込まれることで,p にぷよが代入された場合に自動的にループが終了するので break 文が不要になり {} も必要なくなる.一石三鳥である.

を基準として縦に見ていく.

連鎖の処理が終わるとスクリーンを出力する(*13).手元だと printf("%s%d chains"...) でよかったのだが, anagol だと入力の最後の改行が消されるので printf("%s\n%d chains"...) と改行をいれなくてはいけない.

もっと縮めるには

書いていて短くしたかった部分,嫌だった部分だけど解決できなかった部分が幾つかある.

  1. r() 内での再帰呼び出しが4回あること.
  2. フラグ n と f を分ける必要があった.
  3. 一回の r() でぷよを消すことろまでしたかった.
  4. 探索済みフラグ配列を使いたくなかった.

inaniwa氏のコード

inaniwa 氏が僕のやりたかったことを達成し 248B で書き上げているので紹介したい.以下が整形したコードである.非常にエレガントだ.

http://golf.shinh.org/reveal.rb?Puyo+Puyo/inaniwa_1284380447&c

char*p;t[99];n;d;
f(char*x){
	int c=*x,l=4;
	for(*x=32;l--;*x-c||f(x))
		x+="\xf7\x08\x02\xff"[l];
	n += d||(*x=c);
}

main(z,j,k){
	for(read(0,t,t);k;--z)
		for(j=9;j--;)
			for(k=0,p=t;*++p;n=d=0)
				j ? 
					p[9]-32||(p[9]=*p,*p=32)
				:
					*p/62&1 ?
						f(p),k+=d=n>3,f(p)
					:
						0;
	printf("%s\n%d chains",t,-z);
}

再帰関数 f がうまく設計されている.上下左右の探索を再帰的に呼び出す前に判定を行っている.上下の探索を for ループで行なっている.x+="\xf7\x08\x02\xff"[l] はバイナリで x-=1 (-1), x+=2 (+1), x+=8 (+9), x+=-9 (0) がループで回る.最後が x-=18 (-9) つまり上方でないのは,バグだと思う.このコードでは下のような凹形のぷよに対して探索が失敗する(この例はサンプルに入っていなかった...).正しくは x+="\xee\x08\x02\xff"[l] ではないだろうか. 後に x に代入しているので 0 に戻すので正解.上方 (-9) への探索が意図的に省かれている.すごい.

|      |
| p p  |
| ppp  |
+------+

探索のフラグはスペースを代入することで実現している.これは非常にエレガントである.ローカル変数への値の保存と,再帰探索前の探索するかどうかの判定で実現できる技である.一回目の探索ではスペースに代入されたものは元の値に戻され,二回目の探索では n が 4 以上だと d が 1 になり,消されたぷよはそのままにされる.

main 関数では t の走査を 9 回行い,うち最初の 8 回はぷよの落下である.落下処理は,真下のマスにぷよがなかったら,ぷよを1つ落下させるというものである.上段から探索を行っているので 8 回落下処理が必要になったのだと思われる.こうすることで探索と落下のループを一つにまとめることができ,僕のコードで使ったポインタ q のようなものが必要なくなる.これはお見事.

連鎖数を記録する初期値 1 の z をデクリメントすれば -z で連鎖数が取れるので,僕のコードのインクリメント&c-2より 1B 縮めることができる.

僕のコードでは読み込むバイト数を 126 としたが,大きい正の数字ならば問題ないので read(0,t,t) のようにすればさらに 2B 縮めることができる.

非常に参考になるコードである.

反省

探索する再帰関数引数やローカル変数をケチる意識で縮めることができる可能性を潰してしまった(再帰関数の場合は使ったほうが短くなる傾向がある).

アルゴリズムやテクニックについてはまだまだ勉強の余地がある.

inaniwa3inaniwa3 2010/09/26 21:34 問題おもしろかったです.
私のはバグではなくて,上方の探索を省いて1B稼いでいます.
最後の\xf7は,その後に*x=cというのがあるので,
xを元の場所に戻すために入れてます.

yuyarinyuyarin 2010/09/28 01:08 あ,ほんとですね.確かに上方探索があれば1B増やすだけで良いですね.
そういうケースを入れていなかったのは失敗したなぁと思います.

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/yuyarin/20100926