左右がつながっている場合、左右の番兵はひとりで兼任できる

いつも絶妙で楽しい問題を提供してくださっている@Nabetaniさん。すでに第5回の募集と参考問題の公開が始まっています。興味のある方はぜひ参加して、また問題を解いてみてください。問題の絶妙さが実感できます。

• 第5回 オフラインリアルタイムどう書く : ATND
• Rails on Tiles 〜 横へな 2012.11.9の参考問題

今回の参考問題では、@nidouchiさんがRubyでエレガントな解答を披露してくださいました。

• オフラインリアルタイムどう書く第5回の参考問題をRubyで解く - Qiita

この解答には学ぶことが多かったので、そのことをまとめてみました。

ひとりで左右を見張る

今回の問題は3x3のマスを使った問題ですが、このような問題のばあい周囲のマスと内部のマスを同一視して扱えるように番兵を配置することがあります。今回は3x3なので単純に周囲に番兵を巡らすと、番兵を加えて5x5のマスになります。
次の図の下の図は5x5のマスを1次元配列であらわしたときの様子です。上の段の右の番兵と下の段の左の番兵が隣り合っています。ちょっともったいない。

このようなばあい、次の図のように描いてみると隣り合う番兵をひとりにしても番兵としての機能を果たしてくれることがわかります。また左上と右下の番兵も不要とわかります。
これらの工夫のおかげで、周囲全体に番兵を配置するよりもすっきりと解くことができるようになりました。

Haskellに翻訳

よいお手本を得たので、Haskellに翻訳してみました。Qiitaで書いたコードをこちらにも再録します。

import Data.Char
import Test.HUnit

board = "----ABC-DEF-GHI----"

move 0   4  =  4
move 0 (-4) = -4
move 0   1  =  1
move 0 (-1) = -1
move 1   4  =  1
move 1 (-4) = -1
move 1   1  =  4
move 1 (-1) = -4
move 2   4  = -1
move 2 (-4) =  1
move 2   1  = -4
move 2 (-1) =  4

solve xs = solve' 5 4
    where
        solve' pos mv
            | pat !! pos < 0 = []
            | otherwise      = let mv'  = move (pat !! pos) mv
                                   pos' = pos + mv'
                               in  (board !! pos):(solve' pos' mv')
        pat = replicate 4 (-1) ++ (pat' $ map ((subtract 48).ord) xs)
        pat' []        = replicate 4 (-1)
        pat' (a:b:c:t) = a:b:c:(-1):(pat' t)

main = do
    runTestTT $ test $ map (\(e, a) -> e ~=? solve a) testPattern
    return ()

testPattern = [ ("BEDGHIFEH",   "101221102")
              , ("BEH",         "000000000")
              , ("BCF",         "111111111")
              , ("BAD",         "222222222")
              , ("BEFIHEDGH",   "000211112")
              , ("BADGHIFEBCF", "221011102")
              , ("BEHIFCBADEF", "201100112")
              , ("BEFIH",       "000111222")
              , ("BC",          "012012012")
              , ("BEDABCFI",    "201120111")
              , ("BADEHGD",     "220111122")
              , ("BADG",        "221011022")
              , ("BCFIHEBA",    "111000112")
              , ("BEFI",        "001211001")
              , ("BCFEHIF",     "111222012")
              , ("BADEHI",      "220111211")
              , ("BCFEBAD",     "211212212")
              , ("BEFC",        "002112210")
              , ("BEF",         "001010221")
              , ("BEFIHG",      "100211002")
              , ("BEFCBAD",     "201212121")
              ]