テンパイ問題 (revised)
@author imajuk
/**
* Copyright imajuk ( http://wonderfl.net/user/imajuk )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/Jyap
*/
package
{
import com.bit101.components.InputText;
import com.bit101.components.PushButton;
import com.bit101.components.Text;
import com.bit101.components.Panel;
import flash.utils.getTimer;
import flash.utils.Dictionary;
import flash.display.Sprite;
/**
* @author imajuk
*/
public class MajangMain extends Sprite
{
private var text:Text;
public function MajangMain()
{
/**
* 「あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定」をやってみた。
* http://headlines.yahoo.co.jp/hl?a=20100404-00000003-zdn_ep-sci
*
* アルゴリズムが思いつかなかったので愚直に解いてみた。
* 中学生が40分で解けたとあるが自分には難しかったよ。
* 一応正解らしきものを出力するがテストが通る気はしないw
*
* # 九蓮宝燈の待ちが足りなかったので修正した.
* # 無駄な探索をしていたのでこれも見直した.
*
* 以下出題より~
* 1112224588899 :
* 単純なケースです。45を軸にする両面の待ちなので、(111)(222)(888)(99)[45]になります。
* 1122335556799 :
* “99”をアタマの両面か“55”“99”のシャボであるので、(123)(123)(555)(99)[67]、(123)(123)(55)(567)[99]、(123)(123)(99)(567)[55]が正解です。
* 1112223335559 :
* 待ちは“9”単騎ですが、(123)(123)(123)(555)[9]と(111)(222)(333)(555)[9]の2つあります。
* 1223344888999 :
* 1-4の“ノベタン”待ちですが、4をアタマにしての[23]待ちと、1単騎、4単騎で3個の答えになります。
* 1112345678999 :
*「九蓮宝燈」という役です。1～9すべてが待ちになっています。これに正しく答えが出るのであれば、プログラムはほぼ正しいでしょう。
*/
//=================================
// UI
//=================================
var panel:Panel = addChild(new Panel(this, 0, 0)) as Panel;
panel.setSize(450, 450);
text = new Text(panel, 0, 20);
text.setSize(450, 430);
var inputText:InputText = new InputText(panel, 2, 0);
inputText.setSize(150, 20);
inputText.text = "1112345678999";
var pushbutton:PushButton =
new PushButton(panel, 153, 0, "START", function():void
{
check(inputText.text);
});
pushbutton.label = "Check!";
pushbutton.width = 100;
}
private function check(tehai:String):void
{
var t:int = getTimer();
//手牌を生成
var pai : Tehai = new Tehai(tehai);
var result : Array = [];
//1~9の牌についてあがりが存在するかどうか判定
for (var m : int = 1; m <= 9; m++)
{
result =
result.concat(hantei(m, pai)
.map(
//結果があれば待ち牌を登録しノーマライズしておく
function(o : Tehai, ...param):Tehai
{
if (!o) return null;
o.mati = m;
o.normalize();
return o;
}
)
);
}
//テンパイ形を取得
var a:Array = [];
result.forEach(function(s:Tehai, ...param):void
{
if (s) a = a.concat(s.getTenpai());
});
//結果を出力
var dic:Dictionary = new Dictionary(true);
a.forEach(function(s:String, ...param):void
{
if (!dic[s])
{
dic[s] = true;
print(s);
}
});
print("\t\t\t" + String(getTimer() - t) + "mSec.\n");
}
private function print(s:String):void
{
text.text += s + "\n";
}
//手牌paiにたいして任意の牌matiであがれるか判定.
//あがれる場合はあがりのバリエーションを全て返す.
private function hantei(mati : int, pai : Tehai) : Array
{
pai = pai.clone();
//待ち牌を配牌された牌に追加
pai.rest += String(mati);
//ノーマライズ
pai.normalize();
var result : Array = [];
//=================================
// 最初に頭があれば抜き出す
//=================================
for (var i : int = 1; i <= 9; i++)
{
var head : String = String(i) + String(i);
if (pai.rest.match(new RegExp(head)))
{
var p : Tehai = pai.clone();
p.extract(head);
//=================================
// アンコ優先探索
//=================================
result.push(searchAgari(p.clone(), true));
//=================================
// シュンツ優先探索
//=================================
result.push(searchAgari(p.clone(), false));
}
}
return result;
}
private function searchAgari(pai : Tehai, anko : Boolean) : Tehai
{
return search(pai.firstPai, pai, anko);
}
//手配の中のメンツを検索
private function search(i : int, pai : Tehai, anko : Boolean) : Tehai
{
if (i > 9)
{
//残りの手牌が0ならあがり
if (pai.rest.length == 0)
return pai;
//そうでなければあがれない
return null;
}
//メンツ検索実行
if (anko)
{
serchAnko(i, pai);
serchSyuntu(i, pai);
}
else
{
serchSyuntu(i, pai);
serchAnko(i, pai);
}
//残りについて繰り返す
return search(i + 1, pai, anko);
}
//アンコを検索
private function serchAnko(p : int, pai : Tehai) : void
{
var s : String = p.toString();
s = s + s + s;
registerMentsu(pai, s, new RegExp(s));
}
//シュンツを検索
private function serchSyuntu(p : int, pai : Tehai) : void
{
//範囲外チェック
if (p > 7) return;
var s : String;
s = p.toString() + (p + 1).toString() + (p + 2).toString();
registerMentsu(pai, s, new RegExp(s.split("").join(".*")));
}
//指定したパターンが手牌の中にあればメンツに登録
private function registerMentsu(pai : Tehai, s : String, pattern : RegExp = null) : void
{
var m : Array = pai.rest.match(pattern);
if (!m) return;
if (m.length > 1) throw new Error(m);
//手配の中の指定されたメンツを全て登録
while(pai.rest.match(pattern))
{
pai.extract(s);
}
}
}
}
class Tehai
{
//待ち牌
public var mati : int;
//未検索の手牌
public var rest :String;
//検索されたメンツ
private var sets : Array = [];
public function Tehai(haipai:String)
{
rest = haipai;
}
//restからpaiを取り出しsetsに移す
public function extract(pai:String):void
{
sets.push(pai);
rest = Util.deleteStr(rest, pai);
}
public function get firstPai() : int
{
return int(rest.charAt(0));
}
//とりうるテンパイの形をすべて返す
public function getTenpai() : Array
{
var r:Array = [];
var match : Array = sets.toString().match(new RegExp("\\d*" + mati + "\\d*", "g"));
if (match)
match.forEach(function(m:String, ...param):void
{
var b:Boolean = true;
var a:Array = sets.concat();
a = a.map(function(s:String, ...param):String
{
if (s == m && b)
{
b = false;
return "[" + Util.deleteStr(s, String(mati)) + "]";
}
else
{
return "(" + s + ")";
}
});
a.sort();
r.push(a);
});
return r;
}
public function normalize() : void
{
rest = rest.split("").sort(Array.NUMERIC).join("");
sets = sets.map(function(s:String, ...param):String
{
return s.split("").sort(Array.NUMERIC).join("");
});
sets = sets.sort(Array.NUMERIC);
}
public function toString() : String
{
return "PAI[" + rest + "/" + sets + "]";
}
public function clone() : Tehai
{
var p : Tehai = new Tehai(rest);
p.sets = sets.concat();
p.mati = mati;
return p;
}
}
class Util
{
public static function deleteStr(string : String, pattern : String) : String
{
if (string == pattern) return "";
var l:int = pattern.length;
for (var i : int = 0;i < l;i++)
{
string = deleteOne(string, pattern.charAt(i));
}
return string;
}
private static function deleteOne(string:String, pattern:String):String
{
var idx : int = string.indexOf(pattern);
var s : String = "";
for (var i:int = 0;i < string.length; i++)
{
if (i != idx)
s += string.charAt(i);
}
return s;
}
}