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 $ [0,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 = 0 : 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))) (0,1)