Problem 208

208 Robot Walks

問題のサイズなどから、動的計画法を使うのが良さそうではあるが、

気になるのは、何を状態とするか、ということ。

現在の座標と向きではうまくいかなそう。

円で考えるから、難しくなる。直線で考えれば、

移動は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 (, 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  snd.find (closedPath.fst).toList.(!!n).
iterate (filterWithKey feasible.step) $ singleton (, replicate 5 ) 1
where  feasible (_,ms) _ = all (<= div n 5) ms
main :: IO ()
main = print.p208 $ 70

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

コンテンツ