Problem 227

Project Euler Haskell

227 The Chase
Problem 227 - Project Euler
サイコロゲームの終了までの期待ターン数を求める．
サイコロがあちこちに動くので，一見複雑だが…
ひとつのサイコロの位置を基準にして考えれば，簡単なマルコフ連鎖であることが分かる．
あとは各状態について，期待値の等式をたて，その連立一次方程式を解けばよい．
しかし，その連立一次方程式を解くのに苦労した．
自分で実装してもよいのだが，車輪の再発明はあまりよろしくないと思っている．
ライブラリがあるなら，それを使うべき．
ということで，Haskellで行列計算するライブラリhmatrixを入れた．

import Numeric.LinearAlgebra (Matrix, fromLists, linearSolve, (@@>))

coef :: Int -> Matrix Double
coef n = fromLists.(top :).take (n-1).map (take n).iterate (drop (n - 1)).tail $ base
    where base = cycle $ [-1, -8, 18, -8, -1] ++ replicate (n - 5) 0
          top  = 1:replicate (n - 1) 0

rightSide :: Int -> Matrix Double
rightSide n = fromLists $ [0] : replicate (n - 1) [36]

p227 :: Int -> Double
p227 n = linearSolve (coef n) (rightSide n) @@> (div n 2, 0)

main :: IO ()
main = print $ p227 100

それにしても行列要素へのアクセスが"@@>"って変な記号なのが気になる．