makeplex salon: 麻雀の問題

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

をやってみた。

言語はHaskell。

たぶん、あってる。根拠はない。
とりあえず、各牌が無限にあると思うと、以下のシンプルなコードで良いと思う。
デカルトさんは言いました「困難は分割せよ」と。

もし、「頭」も「待ち」もなければ、牌は順子と刻子の組に分ければ良いだけ。

というわけで、「頭」と「待ち」を決める部分と、順子、刻子に分割する部分に分けて実装。

import Data.List

mpart [] = [[]]
mpart hs@(a:b:c:ds) = ms1 ++ ms2
    where ms1 | a == b && b == c = map ([a,b,c]:) $ mpart ds 
              | otherwise        = []
          ms2 | null $ [a+1,a+2] \\ hs = map ([a,a+1,a+2]:).mpart $ hs \\ [a,a+1,a+2] 
              | otherwise              = []

machi n hs os | null $ os \\ hs = concat [map ([os,a]++).mpart $ hs' \\ a | a 

ただ、実際は各牌は高々4枚だった記憶がある。つまり、[1,1,1,1,…] という牌を持っている状況では(11)を頭にして、[11]を待ちにするのは

ダメ。1が5枚あれば良いのだが。

というわけで、結構面倒な場合分けが必要な気がする。

その、各牌が4枚しかないことを考慮したコード。

import Data.List ((\\), group, nub)

-- 順子、刻子のみの組合せに分割
mpart :: [Int] -> [[[Int]]]
mpart [] = [[]]
mpart hs@(a:b:c:ds) = ms1 ++ ms2
    where ms1 | a == b && b == c = map ([a,b,c]:) $ mpart ds 
              | otherwise        = []  -- 刻子無し
          ms2 | null $ [a+1,a+2] \\ hs = map ([a,a+1,a+2]:).mpart $ hs \\ [a,a+1,a+2] 
              | otherwise              = [] -- 順子無し

-- 「待ち」と頭の候補の列挙
candidates :: Int -> [Int] -> [([Int], [Int], [Int])]
candidates n hs = ts ++ ks ++ ss1 ++ ss2
    where ts = [([a], [], hs \\ [a]) | (a:_) <- filter ((4>).length).group $ hs] -- 単騎待ち
          ks = [([a,a], [b,b], hs \\ [a,a,b,b]) | a <- xs, b <- xs \\ [a]] -- 刻子での待ち
              where xs = map head.filter ((1<).length).group $ hs
          ss1 = [([a,a+1], [b,b], hs \\ [a,a+1,b,b]) | a <- nub hs, elem (a+1) hs, b <- nub hs, null $ [a,a+1,b,b] \\ hs, ((4>).length.filter (a+2==) $ hs) || ((4>).length.filter (a-1==) $ hs)]
          -- 順子での待ち、その1
          ss2 = [([a,a+2], [b,b], hs \\ [a,a+2,b,b]) | a <- nub hs, elem (a+2) hs, b <- nub hs, null $ [a,a+2,b,b] \\ hs, (4>).length.filter (a+1==) $ hs]
          -- 順子での待ち、その2

machi :: Int -> [Int] -> [[[Int]]]
machi n hs = filter (not.null).map f $ candidates n hs
    where f (os,as,hs) = concatMap ([os,as]++).mpart $ hs

main :: IO ()
main = mapM_ print $ machi 9 [1,1,1,2,3,4,5,6,7,8,9,9,9]

場合わけの問題か。リストの内包表記がヒドイことになっている。効率?入力長は固定ですよ。