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) 
top  = 1:replicate (n - 1) 
rightSide :: Int -> Matrix Double
rightSide n = fromLists $ [] : replicate (n - 1) [36]
p227 :: Int -> Double
p227 n = linearSolve (coef n) (rightSide n) @@> (div n 2, )
main :: IO ()
main = print $ p227 100

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