Problem 209

209 Circular Logic

Problem 209 – Project Euler

関数 が

どのような振舞をするかを考えれば良いような、気がするが…

少し実験をしてみると、ループになることが分かり、それが閉じていることが分かる。

import Data.List (unfoldr, ())
import Data.Bits (xor, (.&.))
trans :: [Int] -> [Int]
trans (a:b:c:ds) = (b:c:ds) ++ [a `xor` b .&. c]
expand :: [Int] -> [[Int]]
expand x = x:unfoldr trans' (trans x)
where trans' y | y == x    = Nothing
| otherwise = Just (y, trans y)
groups :: Int -> [[[Int]]]
groups n = unfoldr expand' inputs
where inputs = sequence.replicate n $ [,1]
expand' [] = Nothing
expand' (x:xs) = Just (expand x, xs  expand x)
fun :: Int -> Integer
fun n = fib!!(n-1) + fib!!(n+1)
where fib =  : scanl (+) 1 fib
p209 :: Int -> Integer
p209 n = product.map (fun.length).groups $ n
main :: IO ()
main = print.p209 $ 6

unfoldrが大活躍。fibも、その気になれば、

fib = unfoldr ((a,b) -> Just (a,(b,a+b))) (,1)