Problem 227

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

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

コンテンツ