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,_) _ = <=d && d <=9
count :: Map State Integer -> Integer
count = fold (+)  .filterWithKey ((_,(l,u)) _ -> l== && u==9)
p178 :: Int -> Integer
p178 n = sum.map count.take n.iterate next.fromList $ [((d,(d,d)),1) | d <-[1..9]]

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