Problem 178

http://projecteuler.net/index.php?section=problems&id=178
状態で考えると状態は今までの最小数字、最大数字、最後の数字で表現できる。
状態数は高々10^3。

import Data.Map (Map,unionWith,filterWithKey,mapKeysWith,fold,fromList)

type State = (Int,(Int,Int))

up,down :: State -> State
up (d,(l,u)) = (d+1,(l,max u $ d+1))
down (d,(l,u)) = (d-1,(min l $ d-1,u))

next :: Map State Integer -> Map State Integer
next m = unionWith (+) (next' up m) (next' down m)
         where next' f = filterWithKey isStep.mapKeysWith (+) f
               isStep (d,_) _ = 0<=d && d <=9

count :: Map State Integer -> Integer
count = fold (+) 0 .filterWithKey (\(_,(l,u)) _ -> l==0 && u==9)

p178 :: Int -> Integer
p178 n = sum.map count.take n.iterate next.fromList $ [((d,(d,d)),1) | d <-[1..9]]

簡潔に書けた（と思ってる）。