いつも絶妙で楽しい問題を提供してくださっている@Nabetaniさん。すでに第5回の募集と参考問題の公開が始まっています。興味のある方はぜひ参加して、また問題を解いてみてください。問題の絶妙さが実感できます。
今回の参考問題では、@nidouchiさんがRubyでエレガントな解答を披露してくださいました。
この解答には学ぶことが多かったので、そのことをまとめてみました。
ひとりで左右を見張る
今回の問題は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") ]