スポンサーサイト

  • --/--/--(--) --:--:--

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

挑戦状を見かけたので……

  • 2010/04/06(火) 08:32:06

どうも( ノ゚Д゚)こんにちわ

あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定
http://www.itmedia.co.jp/enterprise/articles/1004/03/news002.html

なんか、こんな記事見っけた。
面白そうだったので
IPCPやTopCoderっぽい問題だなぁと思いつつ寝る前に解いてみた。

結果
解法:2分以内につかんだ
解法の計算量検証:開始5分
コードとりあえず実装:開始25分
バグ探し:80分/(^o^)\→眠たくなって撃沈

おまけにまだバグ残ってるし……
原因は探索ルーチンところでイージーミス……
自分バグ周りの能力に問題あんのかなぁ?とは思った。

自分が考えた解法は
・牌を1個加える
・頭を除去
・シュンツ、コーツを探索

の順番で探索していく解法を考えました。

計算量推測してたいした量じゃないなと思ったので
そのまま探索かけました。

解いたソースコードを書いておきました
ちなみに
・問題読み間違いで、出力フォーマット間違えてる(間違えて頭を[]でくるんでいる。まぁ、直すのメンドクサイ)
・チートイツのことをすっかり忘れてて、撃墜/(^o^)\
・眠たくなって放置したので、バグとれてないかもw

あと、分からなかったのは
・(333)(333)なことは起こらないのか?(全部1色って3色を1色に置き換えたのか、そもそも1色しか使わないのか)
・「面前かつ槓子は存在しない前提でOKです」ってどういう事だろう?


あと、気になったのは
こんなの役に立たない。ってコメントを見かけたこと。
……学生なんで分からないですが、使わないの?こういうの。

以下コード


///


/// 麻雀の手牌が与えられた時の待ちの計算問題
///

class Program
{
//方針
//1.待ちを足す
//2.頭を抜く
//3.パターンを作る

//引数1に待ちの文字列が入っていると想定
static void Main(string[] args)
{
/*
if (args.Length == 0)
{
Console.WriteLine("引数がありません");
}*/
args = new string[5]{
"1112224588899",
"1122335556799",
"1112223335559",
"1223344888999",
"1112345678999"
};
foreach (var s in args)
Calc(s);
}

private static void Calc(string s)
{
s = s.Trim();
if (s.Length != 13)
return;
//数字に変換
int[] pieces = new int[14];
int[] pieces2 = new int[14];
int pos = 0;
foreach (char c in s)
{
pieces[pos++] = Convert.ToInt32(Convert.ToString(c));
}
//1つ足す
List resultPool = new List();
for (int mati = 1; mati <= 9; mati++)
{
pieces[13] = mati;
Array.Copy(pieces, pieces2, 14);
char c = Convert.ToString(mati)[0];
//待ちを含めた解を出力
string[] results = SeparateHead(pieces2);
foreach (var result in results)
{
//待ちを除去
for (int i = 0; i < result.Length; i++)
{
if (result[i] == c)
{
//(333)で3待ちで3つ追加されないようにする。
//麻雀のルール的に(333)(333)は無いはず……。
if (resultPool.Count==0 || result.Substring(0, i) + result.Substring(i + 1) != resultPool.Last())
resultPool.Add(result.Substring(0, i) + result.Substring(i + 1));
}
}
}
}
resultPool.Sort();
//答えを全出力
string temp = "";
//Console.WriteLine(s + "の出力結果");
foreach (var str in resultPool)
{
if (str != temp)
{
Console.WriteLine(str);
temp = str;
}
}
}
//頭を分けてパターン器にかける
private static string[] SeparateHead(int[] pieces)
{
//理牌
Array.Sort(pieces);
//頭除いて出力
List result = new List();
for (int i = 1; i <= 9; i++)
{//1~9まで頭チェック
//頭が作れるかチェック
int headPos = -1;
for (int j = 0; j < pieces.Length; j++)
{
if (pieces[j] < i)
continue;
if (pieces[j] == i)
{
if (pieces.Length > j + 1 && pieces[j + 1] == i)
headPos = j;
break;
}
if (pieces[j] > i)
break;
}
if (headPos == -1)
continue;//作れなかったので次
//頭製作
string oneresult = "[" + i.ToString().Trim() + i.ToString().Trim() + "]";
//頭除去した配列生成
int[] pieces2 = new int[pieces.Length - 2];
Array.Copy(pieces, pieces2, headPos);
Array.Copy(pieces, headPos + 2, pieces2, headPos, pieces2.Length - headPos);
bool check;
string[] pattern = MakePattern(pieces2, out check);
if (check)//頭除去したのでパターン生成できたので
foreach (var s in pattern)
result.Add(s + oneresult);
}
return result.ToArray();
}
//パターン器
private static string[] MakePattern(int[] pieces2,out bool check)
{
//数字ごとの個数に分解
int[] counts = new int[9];
Array.Clear(counts, 0, 9);
foreach (var i in pieces2)
counts[i - 1]++;
check = false;
foreach (var i in counts)
if (i > 4) return new string[0];//待ち入れて5個以上になっているパターン排除
//1から順にパターン生成
List> temp = ReCall(counts, 0, new List(), out check);
List result = new List();
foreach (var i in temp)
{
i.Sort();
string s = "";
foreach (var j in i)
{
s += j;
}
if (result.Count == 0 || result.Last() != s)
result.Add(s);//この探索方だと同じパターンは前後に出るのでこれで行けるはず
}
check = true;
return result.ToArray();
}
private static List> ReCall(int[] counts, int NowNum, List NowStr, out bool check)
{
List> result = new List>();

if (counts[NowNum] >= 3)
{//333パターン
List nextStr = new List();
nextStr.AddRange(NowStr);
nextStr.Add("(" + (NowNum + 1).ToString().Trim() + (NowNum + 1).ToString().Trim() + (NowNum + 1).ToString().Trim() + ")");
int nextNum = NowNum;
counts[NowNum] -= 3;//同じハイを3つ減らしてみる
bool flag = false;
while (counts[nextNum] == 0)
{
nextNum++;
if (nextNum >= counts.Length)
{//全部牌を使い切った
flag = true;
break;
}
}
bool incheck;
if (flag)
result.Add(nextStr);//答え
else
result.AddRange(ReCall(counts, nextNum, nextStr, out incheck));
counts[NowNum] += 3;
}
if (NowNum < 7 && counts[NowNum] >= 1 && counts[NowNum + 1] >= 1 && counts[NowNum + 2] >= 1)
{//123パターン
List nextStr = new List();
nextStr.AddRange(NowStr);
nextStr.Add("(" + (NowNum + 1).ToString().Trim() + (NowNum + 2).ToString().Trim() + (NowNum + 3).ToString().Trim() + ")");
int nextNum = NowNum;
--counts[NowNum];
--counts[NowNum+1];
--counts[NowNum+2];
bool flag = false;
while (counts[nextNum] == 0)
{
nextNum++;
if (nextNum >= counts.Length)
{//全部牌を使い切った
flag = true;
break;
}
}
bool incheck;
if (flag)
result.Add(nextStr);//答え
else
result.AddRange(ReCall(counts, nextNum, nextStr, out incheck));
++counts[NowNum];
++counts[NowNum + 1];
++counts[NowNum + 2];
}
check = result.Count > 0;
return result;
}
}
スポンサーサイト

この記事に対するトラックバック

この記事のトラックバックURL

この記事にトラックバックする(FC2ブログユーザー)

この記事に対するコメント

春休みの宿題

ぼくはしょうがくせいです
ぼくがかんがえたあるごりずむです

全ての牌をユニーク「a~m」だと仮定すると6227020800通りの牌の設置パターンが有ります。
テンパイしてるかどうかの判定パターンは3パターン有ります
つまり18,681,062,400を総ナメすれば答えが出ます!!
恐ろしく簡単(アホ)なアルゴリズムで!!!!

[a]単騎の時([b=c-1=d-2]or[b=c=d])ならOK以下[klm]までチェック
[a=b]頭有りの時([c=d]or[c=d-1])であり[e=f-1=g-2]or[e=f=g]ならOK以下[klm]までチェック
[a=b-1]両面の時[c=d]であり[e=f-1=g-2]or[e=f=g]なら以下[klm]までチェック

最後にそれぞれのパターンを数字順で並べ替え、同一のものを排除。
残ったパターンが「待ち」です。

さすがしょうがくせい。



  • 投稿者: 小学生
  • 2010/04/07(水) 20:50:30
  • [編集]

コメント投稿

管理者にだけ表示を許可する

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。