Problem 208

208 Robot Walks
Problem 208 - Project Euler
問題のサイズなどから、動的計画法を使うのが良さそうではあるが、
気になるのは、何を状態とするか、ということ。
現在の座標と向きではうまくいかなそう。
円で考えるから、難しくなる。直線で考えれば、
移動は5種類しかないことに気づく。

import Data.List (find)
import Data.Map (Map, filterWithKey, unionWith, singleton, toList, mapKeys)

type State = (Int, [Int]) -- (Direction, Moves)

inc :: Int -> [Int] -> [Int]
inc n xs = let (x,y:zs) = splitAt n xs
           in x ++ (y+1):zs

clockWise :: State -> State
clockWise (d, ms) = (d', inc d ms)
    where d' = mod (d-1) 5

antiClockWise :: State -> State
antiClockWise (d, ms) = (d', inc d' ms)
    where d' = mod (d+1) 5

closedPath :: State -> Bool
closedPath (0, m:ms) = all (m==) ms
closedPath _         = False

step :: Map State Integer -> Map State Integer
step m = unionWith (+) m1 m2
    where m1 = mapKeys clockWise m
          m2 = mapKeys antiClockWise m

p208 :: Int -> Integer
p208 n = maybe 0 snd.find (closedPath.fst).toList.(!!n).
         iterate (filterWithKey feasible.step) $ singleton (0, replicate 5 0) 1
    where  feasible (_,ms) _ = all (<= div n 5) ms

main :: IO ()
main = print.p208 $ 70

メモリをたくさん使うなぁ。