「オフラインリアルタイムどう書く第四回の参考問題」を解いてみた

twitter に流れていたので、解いてみた。

お題 : http://qiita.com/items/9c514267214d3917edf2

以下のような方針

• 格子状のグラフを作る。グラフ内の辺は、方向によって別個のものとする（例えば頂点 A と頂点 Bの間には A→B と、B→Aの二つの辺がある）。
• 一度通ったノードを再び通る事はできないという制約を、そのノードに向かう辺をグラフから削除する事で表現する。
• 内部的には a 〜 y ではなく、整数でグラフを表現する（最初のグラフ作成が楽なので）。
• ゴールに到達すると 1、行き詰まると 0として、再帰的に集計する。
• 入力で指定された辺を初期状態のグラフから取り除いてから、始点からブルートフォースする。

コードはこんな感じ。
基本的にリストとタプルと再帰だけで、Haskell で素朴に実装してみた。

import Data.List
import Data.Tuple
import System

size  = 5 :: Int
start = 0
goal  = size^2 - 1

makeReversible = concatMap (\t->[t, swap t])

initialGraph = makeReversible
             $ concat [[(a*size+b, (a+1)*size+b), (b*size+a, b*size+a+1)] |
                      a<-[0..size-2], b<-[0..size-1]]

countRoutes graph node
    | node == goal   = 1
    | null nextNodes = 0
    | otherwise      = sum $ map (countRoutes newGraph) nextNodes
  where nextNodes    = map snd $ filter ((==node).fst) graph
        newGraph     = filter ((/=node).snd) graph

solve s = countRoutes filteredGraph start
  where
    filteredGraph       = initialGraph \\ (makeReversible $ toEdges s)
    toEdges             = (map toEdge).words
    toEdge (from:to:[]) = (toDigit from, toDigit to)
    toDigit ch          = fromEnum ch - fromEnum 'a'

main = getArgs >>= (print.solve.head)

帰りの電車で黙想1時間強 ＋ 書いて動作確認まで20分くらい ＋ リファクタに1時間強 ≒ 3時間弱。

面白かった。

計算時間は、空文字列を渡して最大値 8512 を得るのに 145 ミリ秒、size = 6 で 1262816 を得るのには 25.0 秒かかった。それ以上は、件の動画を見た後では、おそろしくて実行できない。

それにしても、もともとの『フカシギの数え方』の方は、どうやったら計算時間を爆発させずに数えられるのだろう。ちょっとググってみたけど、簡単な解説がなかなか見当たらない。難しい解説は見つけたが正直理解できなかった(註1)。問題自体はあれほどシンプルなのに、解の方はあんなになっちゃうから驚く。

(註1: 流石に４・５年も経つと Simpath もわかるようになってたので書き直した(2018/1/3追記))