「ツリーの中の数」の問題 ref: http://qiita.com/nobsun/items/495b0cc478521dd6b60a

F06.hs

module F06 where

import Data.Map
import Data.Function (fix)
import Data.Function.YaMemo (Memo, memo)

ordering :: b -> b -> b -> Ordering -> b
ordering x _ _ LT = x
ordering _ y _ EQ = y
ordering _ _ z GT = z

gcount :: (Integral a, Num b) => a -> (a -> b) -> a -> b
gcount c f x = ordering (f p + f q) 1 0 (compare c x)
  where
    p = (x `div` 2) - 10
    q = (x * 2) `div` 3

type Root = Integer
type Count = Integer

-- | 素朴(非メモ化)版
count :: Integer -> Root -> Count
count = fix . gcount

-- | メモ化版
count' :: Integer -> Root -> Count
count' = memo (undefined :: Memo Map Root Count) . gcount

type Problem = String
type Answer  = String

f06 :: Problem -> Answer
f06 p = show $ count' n r
  where
    (n,r) = case break (','==) p of
      (sr,_:sn) -> (read sn, read sr)

type Test = (Problem, Answer)
{- |
>>> test ( "123,4", "5" )
True
>>> test ( "1,1", "1" )
True
>>> test ( "2,1", "1" )
True
>>> test ( "3,3", "1" )
True
>>> test ( "19,5", "1" )
True
>>> test ( "69,5", "3" )
True
>>> test ( "88,9", "2" )
True
>>> test ( "1,100", "0" )
True
>>> test ( "100,4", "4" )
True
>>> test ( "101,9", "0" )
True
>>> test ( "456,7", "7" )
True
>>> test ( "567,8", "12" )
True
>>> test ( "756,10", "10" )
True
>>> test ( "789,10", "12" )
True
>>> test ( "896,29", "2" )
True
>>> test ( "7764,6", "664" )
True
>>> test ( "1234,56", "3" )
True
>>> test ( "8563,29", "35" )
True
>>> test ( "12345,67", "10" )
True
>>> test ( "72927,51", "263" )
True
>>> test ( "71441,145", "22" )
True
>>> test ( "123456,78", "397" )
True
>>> test ( "123456,789", "1" )
True
>>> test ( "592741,216", "55" )
True
>>> test ( "913826,584", "81" )
True
>>> test ( "1234567,89", "2293" )
True
>>> test ( "10000000,1", "19383507" )
True
>>> test ( "12345678,9", "3567354" )
True
>>> test ( "6215879,358", "2907" )
True
>>> test ( "12345678,90", "79419" )
True
>>> test ( "5745432,1032", "1287" )
True
-}
test :: Test -> Bool
test (p,a) = f06 p == a