Problem 15

Starting in the top left corner of a grid, there are 6 routes (without backtracking) to the bottom right corner.

(figure is omitted)

How many routes are there through a grid?

訳

の格子の左上隅からスタートして，右下隅に，逆戻りしないで到着するには6通りの経路がある

(図は省略)

では， の格子では何通りの経路があるか．

Haskell

これは受験問題でよくあるもので，単に二項係数を計算すれば，それが答えです．ただし，再帰的に計算しないと値が爆発しますし，再帰的に計算したらそれはそれで再帰回数が爆発するので，キャッシュする必要があります．ということで，Stateモナドの出番です．枠組みそのものはフィボナッチ数列と全く同じです．

{-
Project Euler Problem 15 e15.hs
-}

import Control.Monad.State

type Cache = [((Integer,Integer),Integer)] -- キャッシュ

ccomb:: (Integer,Integer) -> State Cache Integer
ccomb (n,r)
    | n <  0 = return 0 -- パスカルの
    | r <  0 = return 0 -- 三角形の外の値のために
    | r >  n = return 0 -- （正しい引数だけがくるなら不要）
    | n == 0 = return 1
    | r == n = return 1
    | r == 0 = return 1
    | otherwise
          = do cache <- get
               case (lookup (n,r) cache) of
                   Just k  ->  return k
                   Nothing ->  do num <- liftM2 (+) (ccomb (n-1, r)) (ccomb (n-1, r-1))
                                  cache <- get
                                  put (cache++[((n,r),num)])
                                  return num

comb :: (Integer,Integer) -> Integer
comb = flip evalState [] . ccomb

ghciでの処理の結果

*Main> comb (40,20)
137846528820
(0.03 secs, 5674944 bytes)

となりました．キャッシュなしだと悲惨なくらいの時間がかかります．