Match Hentai
これの麻雀の待ちを求める問題をやってみた
方針は
萬子だけというので
14個の牌でアガリ形を全部列挙できそうじゃね？
とかいう雑な思いつきから
アガリの形の14個のうち1個だけ加工する形で全列挙して一致判定！
みたいな雰囲気？
Haskellで雑に書いてみたけど意外に処理が重いらしく、IDEONEで2秒くらいかかってる…
（なんかぐちゃぐちゃしたコードになってて分かりにくい感じになってしまった…
追記:
バグがあった(笑)。machiListが正しくなかった(このバグは間違った答えを生成しうる
リストの結合を丸括弧でくくる必要があった(演算子の優先順位…)
machiList :: [[[Int]]]
machiList = filter isValidMachi
([[atama, mentsu1, mentsu2, mentsu3, mentsu4]
| atama <- atamaMachiList
, mentsu1 <- mentsuList
, mentsu2 <- mentsuList
, mentsu3 <- mentsuList
, mentsu4 <- mentsuList]
++ [[atama, mentsu1, mentsu2, mentsu3, mentsu4]
| atama <- atamaList
, mentsu1 <- mentsuMachiList
, mentsu2 <- mentsuList
, mentsu3 <- mentsuList
, mentsu4 <- mentsuList])
修正版は実行時間が4秒…
どうもこのisValidMachiのフィルターがボトルネックぽい？
もしかするとtakeMachiのフィルター後に適用すると速くなる？
追記:
当該修正したら1秒強になった(笑)
追記:
説明いる？
module Main (main) whereMainモジュールであると宣言
mainの名前で定義されてるやつをエクスポート
where以降にMainモジュールの中身を定義してくって感じ
て、これらは説明は要らんやつか？
import Data.List (group, nub, sort)Data.Listモジュールからgroup,nub,sortの名前で定義されてるやつインポートして使う宣言
groupは[1,1,2,3,3,3,1,1,1]を[[1,1],[2],[3,3,3],[1,1,1]]と同じ値をグループに分けるやつ
nubは[1,1,2,3,3,3,1,1,1]を[1,2,3]とユニークを抜き出すやつ(計算時間がO(n^2)らしい？)
sortはリストをソートするやつ(まんま)
main :: IO ()
main = do
input <- getLine
if isValid input then
mapM_ putStrLn (takeMachi input)
else if isExitCall input then
putStrLn "bye"
else
putStrLn "invalid" >> mainプログラムのエントリポイントであるmain関数
doはこの場合は一連のIO処理を実行するみたいな感じ？
getLineで標準入力から1行受け取ってinput
isValidで入力が正しいか検査
正しかったら(takeMachi input)で"待ち"のリストを受け取って、各"待ち"に対してputStrLnで標準出力に書き出して、プログラムを終了する
isExitCallはプログラム終了コマンドの文字列か判定する
プログラム終了コマンドが来たらbyeと書き出してプログラムを終了する
putStrLn "invalid" >> mainは入力間違いを示して、main関数をもっかい実行しろってやつ(?)
isValid :: String -> Bool
isValid s = length s == 13
&& all (\c -> '1' <= c && c <= '9') s
&& all (\g -> length g <= 4) (group (sort s))isValidの定義
長さが13で、'1'～'9'の範囲の文字で構成されてて、同じ文字は4文字以下って条件
isExitCall :: String -> Bool
isExitCall s = s == "exit"プログラム終了コマンド判定
まぁシンプルにexitかどうか
atamaList,
atamaMachiList,
juntsuList,
juntsuMachiList,
koutsuList,
koutsuMachiList,
mentsuList,
mentsuMachiList
:: [[Int]]"待ち"の形を作るための構成要素の宣言、かな
atamaListはアタマのリスト
atamaMachiListは待ちのあるアタマのリスト
juntsuListは順子のリスト
juntsuMachiListは待ちのある順子リスト
koutsuListは刻子のリスト
koutsuMachiListは待ちのある刻子のリスト
mentsuListは面子(順子と刻子)のリスト
mentsuMachiListは待ちのある面子(順子と刻子)のリスト
atamaList = [[n, n] | n <- [1 .. 9]]アタマのリストの定義
まぁリスト内包記法(?)ってやつで1～9をそれぞれペアにしてリストにしてる
atamaMachiList = [[n, -n] | n <- [1 .. 9]]待ちのあるアタマのリストの定義
待ちの部分は負数で表現してる
juntsuList = [[n, n+1, n+2] | n <- [1 .. 7]]順子のリストの定義
1,2,3と3連続で並ぶのが順子なので[1,2,3]～[7,8,9]まで練成
juntsuMachiList = [[-n, n+1, n+2] | n <- [1 .. 7]]
++ [[n, -(n+1), n+2] | n <- [1 .. 7]]
++ [[n, n+1, -(n+2)] | n <- [1 .. 7]]待ちのある順子のリストの定義
待ちになってる部分は負数で表現
++の演算子はリストを結合するってまぁ見て分かるか…
koutsuList = [[n, n, n] | n <- [1 .. 9]]刻子のリストの定義
同じパイを３つ並べるのが刻子なので、まんま
koutsuMachiList = [[n, n, -n] | n <- [1 .. 9]]待ちのある刻子のリストの定義
待ちを負数で表現、3つとも同じパイなので1つだけ待ちにすればパターンは足りる
mentsuList = juntsuList ++ koutsuList面子のリストの定義
順子のリストと刻子のリストを結合しただけ
mentsuMachiList = juntsuMachiList ++ koutsuMachiList待ちのある面子のリストの定義
こちらも同様に結合しただけ
isValidMachi :: [[Int]] -> Bool
isValidMachi m = all (\g -> length g <= 4) (group (sort (map abs (concat m))))"待ち"を仮・構成したときに無効な組み合わせになってないか判定するやつ
麻雀において同種のパイは4個しか含まれてないってのを判定してるだけ
待ちである負数をabsで符号除去し、group適用のためにソートして並び替えて、allで全て4個以下であることを求めてる
machiList :: [[[Int]]]
machiList = [[atama, mentsu1, mentsu2, mentsu3, mentsu4]
| atama <- atamaMachiList
, mentsu1 <- mentsuList
, mentsu2 <- mentsuList
, mentsu3 <- mentsuList
, mentsu4 <- mentsuList]
++ [[atama, mentsu1, mentsu2, mentsu3, mentsu4]
| atama <- atamaList
, mentsu1 <- mentsuMachiList
, mentsu2 <- mentsuList
, mentsu3 <- mentsuList
, mentsu4 <- mentsuList]"待ち"を構成したリストの定義
アタマの待ちのリストと面子の待ちのリストをそれぞれ全通りを生成して結合してる
重複や無効な組み合わせなものも含まれるリストになってる(これらの除外は後で行う)
isMatchMachi :: String -> [[Int]] -> Bool
isMatchMachi s m = sort s
== concat (map show (sort (filter (\n -> n > 0) (concat m))))入力で受け取った判定対象の手牌sと"待ち"の構成mが一致するか判定する処理
"待ち"のほうは負数を除去して、ソートして、showでリストの各要素を文字列化して、concatで結合して1つの文字列にしてる
takeMachi :: String -> [String]
takeMachi s = nub (map (\m -> concat (sort (map machiToString m))) (filter isValidMachi (filter (\m -> isMatchMachi s m) machiList)))入力で受け取った判定対象の手牌と一致する"待ち"を待ちのリストから取り出す処理
machiListから対象の手牌と一致するものをfilterのisMatchMachiで抜き出し
続くfilterのisValidMachiで無効な組み合わせの"待ち"を除去し
そののち、各"待ち"の各要素(アタマや面子)をmachiToStringで文字列化してソートしてconcatで結合してnubで重複を除去してる
machiToString :: [Int] -> String
machiToString m =
if any (\n -> n < 0) m then
"[" ++ concat (map show (filter (\n -> n > 0) m)) ++ "]"
else
"(" ++ concat (map show m) ++ ")""待ち"の要素(アタマや面子)を文字列化する処理
負数が存在するときは待ちが存在するので負数を除去して角括弧に
負数が無い場合は丸括弧に
