史上最大のコーディングスキル判定

あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ

普通に書いても面白くないので C の Short Coding で．749B→685B→637B．所要時間は1時間ぐらいです．アルゴリズムも縮め方もあんまり凝ってないです．

条件

仕様がはっきり書いていないので例題から推測して適当に決めました．

• 入力は1~9が昇順に13個並んだ文字列
• 入力される文字列において各々の数字は0〜3個
• 入力は標準入力から行われる
• 七対子は考えない
• カンチャン待ちは考えない
• 32-bit int, LE

コード

k,l,r;u[99999];*p=u+49;char v[99999],*s=v,*z="%s(%d%d)[%d%d]\n";e(n,o){memcpy(p+=9,n,36);memcpy(s+=24,o,24);}f(a,i,j){int d,*n=p,*o=s,b=1,c=i+49;for(r=k=0;k<9;k++)for(l=0;l++<n[k];d=u[1]-u[0])u[r++]=k+1;r<2&&printf("%s[%d]\n",s,u[0]);r==2&&(!d&&printf(z,s,u[0],u[1],a,a),d<3&&printf(z,s,a,a,u[0],u[1]));r>2&&(!a&&n[i]>1&&(e(n,o),p[i]-=2,f(i+1,i+1,j),b=0),i<7&&n[i]*n[i+1]*n[i+2]>0&&(e(n,o),p[i]--,p[i+1]--,p[i+2]--,s[j]=40,s[j+1]=c,s[j+2]=c+1,s[j+3]=c+2,s[j+4]=41,f(a,i,j+5)),n[i]>2&&(e(n,o),p[i]-=3,s[j]=40,s[j+1]=s[j+2]=s[j+3]=c,s[j+4]=41,f(a,i+1,j+5),b=0),b&&i<8&&(e(n,o),f(a,i+1,j)));}main(){for(gets(v);k<13;u[v[k++]]++);f(0,0,0);}

結果

/Users/yuyarin/Program/temp% gcc -m32 majiang.c
majiang.c:1: warning: data definition has no type or storage class
majiang.c:1: warning: data definition has no type or storage class
majiang.c:1: warning: data definition has no type or storage class
majiang.c: In function ‘e’:
majiang.c:1: warning: incompatible implicit declaration of built-in function ‘memcpy’
majiang.c:1: warning: passing argument 2 of ‘memcpy’ makes pointer from integer without a cast
majiang.c:1: warning: passing argument 2 of ‘memcpy’ makes pointer from integer without a cast
majiang.c: In function ‘f’:
majiang.c:1: warning: initialization from incompatible pointer type
majiang.c:1: warning: incompatible implicit declaration of built-in function ‘printf’
/Users/yuyarin/Program/temp% ./a.out < case1   
warning: this program uses gets(), which is unsafe.
(111)(222)(888)(99)[45]
/Users/yuyarin/Program/temp% ./a.out < case2
warning: this program uses gets(), which is unsafe.
(123)(123)(567)(99)[55]
(123)(123)(567)(55)[99]
(123)(123)(555)(99)[67]
/Users/yuyarin/Program/temp% ./a.out < case3
warning: this program uses gets(), which is unsafe.
(123)(123)(123)(555)[9]
(111)(222)(333)(555)[9]
/Users/yuyarin/Program/temp% ./a.out < case4
warning: this program uses gets(), which is unsafe.
(123)(234)(888)(999)[4]
(123)(888)(999)(44)[23]
(234)(234)(888)(999)[1]
/Users/yuyarin/Program/temp% ./a.out < case5
warning: this program uses gets(), which is unsafe.
(345)(678)(999)(11)[12]
(123)(456)(789)(99)[11]
(123)(456)(789)(11)[99]
(123)(456)(999)(11)[78]
(123)(678)(999)(11)[45]
(111)(234)(567)(99)[89]
(111)(234)(567)(999)[8]
(111)(234)(678)(999)[5]
(111)(234)(789)(99)[56]
(111)(345)(678)(999)[2]
(111)(456)(789)(99)[23]
/Users/yuyarin/Program/temp% ./a.out < case6
warning: this program uses gets(), which is unsafe.
(123)(234)(234)(11)[79]
(123)(123)(123)(44)[79]
(111)(222)(333)(44)[79]

解説

手牌のそれぞれの牌の数字の数を数えて，対子，順子，刻子が作れるかどうかを再帰的に調べている．

手牌に残った牌の数字の数は u に 9 つずつ記録，p, n がポインタ．出力する文字列は '\0' 含めて 24 文字なので v に 24 個ずつ記録，s, o がポインタ．対子，順子，刻子が作れる場合は内容を e() でコピーしてポインタを進め，内容をアップデートしている．

// ループ文字
k,l,r;
// 数字 x の牌がいくつ残っているか，u[49] から 9 つずつ使用
// u[0]~u[12] は再帰関数内で残った牌を調べるのに使用
u[99999];
// u[] における現在使用している配列部分へのポインタ
*p=u+49;
// 出力する文字列 24 個ずつ使用
char v[99999],
// v[] における現在使用している配列部分へのポインタ
*s=v,
*z="%s(%d%d)[%d%d]\n";

// メモリコピー処理
e(n,o){
	// u[] 上で現在注目している位置のポインタ n から，
	// 次に調べるために p+9 へ内容をコピーしてポインタを進める
	memcpy(p+=9,n,36);
	// v[] 上で同様
	memcpy(s+=24,o,24);
}

// 再帰処理
// a: 頭になっている牌の数字，無ければ 0
// i: 注目している牌の数字， u[] のインデックスに使用
// j: 出力する文字列の最後の位置，v[] のインデックスに使用
f(a,i,j)
{
	int d,     // 残り２つの牌の差
	*n=p,*o=s, // ポインタ保存
	b=1,       // 次の牌を調べるかフラグ
	c=i+49;    // c = i+1+'0'
	
	// 未処理の牌の数字を小さい順に配列 u[0]~u[8] へ記録
	// ループ終了後 r は未処理の手牌の数になっている
	for(r=k=0;k<9;k++)
		for(l=0;l++<n[k];d=u[1]-u[0])
			u[r++]=k+1;
	
	// 単騎待ち
	// if(r==1)
	r<2 &&
		printf("%s[%d]\n",s,u[0]);
	// 2つ待ち
	r==2 &&
	(
		// if(d==0) つまり if(u[0]==u[1])
		// リャンメン待ちは頭と残りの２通りある
		!d &&
			printf(z,s,u[0],u[1],a,a),
		// if(d<=2) 
		// 残り２つの牌の差が
		// 0: シャボ待ち
		// 1: ペンチャン待ち, リャンメン待ち
		// 2: カンチャン待ち
		d<3 &&
			printf(z,s,a,a,u[0],u[1])
	);
	
	// 牌が3つ以上残っている場合
	r>2 &&
	(
		// 牌 i+1 が頭
		// n[i] は 牌 i+1 の残り数
		!a&&n[i]>1 &&
		(
			e(n,o),       // データのコピーとポインタp,s進め
			p[i]-=2,      // 牌の数を減らす
			f(i+1,i+1,j), // 牌 i+1 を頭にして再帰，牌 i+2 に注目
			b=0           // フラグ
		),
		// 牌 i+1 から順子
		i<7&&n[i]*n[i+1]*n[i+2]>0 &&
		(
			e(n,o),
			p[i]--,p[i+1]--,p[i+2]--, // 牌の数を減らす
			s[j]=40,     // '('
			s[j+1]=c,    // i+1+'0'
			s[j+2]=c+1,  // i+2+'0'
			s[j+3]=c+2,  // i+3+'0'
			s[j+4]=41,   // ')'
			f(a,i,j+5)   // 再帰するが，牌 i+1 に注目したまま
		),
		// 牌 i+1 が刻子
		n[i]>2 &&
		(
			e(n,o),
			p[i]-=3,
			s[j]=40,
			s[j+1]=s[j+2]=s[j+3]=c,
			s[j+4]=41,
			f(a,i+1,j+5), // 牌 i+2 に注目を進めて再帰
			b=0
		),
		// 頭と刻子がなかったら次の牌へ
		b&&i<8 &&
		(
			e(n,o),
			f(a,i+1,j)
		)
	);
}

main(){
	// 標準入力から一行読み込み
	// u[49]~u[57] へ牌の個数を記録
	for(gets(v);l<13;u[v[l++]]++);
	// 初期状態で再帰関数の実行
	f(13,0,0,0);
}

感想

後から他の人のコードを読んでいるとカンチャン待ちというものがあるらしいが，問題例にもなかったのでそれは考えていなかった．あとで付け加えよう．

→付け加えた

史上最大のコーディングスキル判定というからにはもう少し問題定義を明確にして欲しかった．麻雀という単語をいきなり出して専門用語で問題解説することで，麻雀を知らない人がとっつきにくい印象を受けているのを目撃しているので残念．

言語に対するコメント

ご回答いただけた方は、この問題について、自分が用いた言語を使ってよかったなとしみじみ思う部分などをコメントいただければ幸いです。 #makeplex

暗黙の了解で型が int になるのは省スペースでエコで良いですね．ヘッダを #include しなくても組み込み関数が使えるのも良いです．改行が文脈に影響を与えないのも素敵だと思います．でもビット演算子が比較演算子よりも優先順位が低いのは嫌です．

他の Short Coder

300B．．．これぞ本当の Golf ですね．僕のは普通に記述したアルゴリズムを簡単に短くしただけなので．．．

http://b.hatena.ne.jp/kusano_prog/20100405