「HaskellでProject Euler(Problem 25～27)」ブログ用

euler25-1.hs

import Zaneli.Euler (fib)

main = print $ fst $ head $ dropWhile (\(_, n) -> n < 10^(1000-1)) $ zip [1..] $ map fib [1..]

euler25-2.hs

import Data.List (findIndex)
import Zaneli.Euler (fib)

main = print $ maybe 0 (+1) $ findIndex (\n -> (fib n) >= 10^(1000-1)) [1..]

euler26-1.hs

import Data.List (elemIndex, maximumBy)
import Data.Ord (comparing)

main = print $ fst $ maximumBy (comparing snd) $ map (\d -> (d, recurCycle $ dPart d)) [1,2..999]

-- 単位分数を10進数で表した小数部分の文字列を取得するため、10のbase乗からnを割り、先頭の1を除いた文字列を返す。
dPart :: (Integral a, Show a) => a -> String
dPart n = tail $ show $ 10 ^ base `div` n
  -- 循環節の長さは最大で n-1 なので、最大で n*2 の文字列が循環しているかどうかを見ればよい。
  -- 最後に正数部分の1を除去するため、n*2+1の長さを取る。
  where base = n * 2 + 1

-- 循環節の長さを返す
recurCycle :: Eq a => [a] -> Maybe Int
recurCycle xs = recurCycle' 1 xs
  where
    recurCycle' n xs = recurCycle'' $ (splited n xs) >>= cycleLength
      where
        recurCycle'' Nothing | n <= (length xs - 1) = recurCycle' (n+1) xs    -- 先頭要素と同じ要素が複数ある循環節に対応
                             | length xs > 1        = recurCycle' 1 (tail xs) -- リストの次の要素から始まる循環節に対応
                             | otherwise            = Nothing
        recurCycle'' x = x

-- aの繰り返しがbと等しい場合、aの長さを循環節の長さとして返す
cycleLength :: Eq a => ([a], [a]) -> Maybe Int
cycleLength (a, b) | isCycle   = Just (length a)
                   | otherwise = Nothing
  where isCycle = (length a) <= (length b) && (take (length b) (cycle a)) == b

splited :: Eq a => Int -> [a] -> Maybe ([a], [a])
splited _ [] = Nothing
splited n xs = fmap (flip splitAt xs) $ sameIdx n
  where sameIdx n = fmap (+n) $ elemIndex (head xs) (drop n xs)

euler26-2.hs

import Data.List (elemIndex, maximumBy)
import Data.Ord (comparing)

main = print $ f 999
  where
    f d | isMax $ recurCycle $ dPart $ toInteger d = d
        | otherwise                                = f (d-1)
      where isMax = maybe False (> (d-2))

-- 単位分数を10進数で表した小数部分の文字列を取得するため、10のbase乗からnを割り、先頭の1を除いた文字列を返す。
-- 何故 Integer にしないといけないか分かっていない… (Integral a, Show a) => a -> String だと回答が7になってしまう…
dPart :: Integer -> String
dPart n = tail $ show $ (10 ^ base) `div` n
  -- 循環節の長さは最大で n-1 なので、最大で n*2 の文字列が循環しているかどうかを見ればよい。
  -- 最後に正数部分の1を除去するため、n*2+1の長さを取る。
  where base = n * 2 + 1

-- 循環節の長さを返す
recurCycle :: Eq a => [a] -> Maybe Int
recurCycle xs = recurCycle' 1 xs
  where
    recurCycle' n xs = recurCycle'' $ (splited n xs) >>= cycleLength
      where
        recurCycle'' Nothing | n <= (length xs - 1) = recurCycle' (n+1) xs    -- 先頭要素と同じ要素が複数ある循環節に対応
                             | length xs > 1        = recurCycle' 1 (tail xs) -- リストの次の要素から始まる循環節に対応
                             | otherwise            = Nothing
        recurCycle'' x = x

-- aの繰り返しがbと等しい場合、aの長さを循環節の長さとして返す
cycleLength :: Eq a => ([a], [a]) -> Maybe Int
cycleLength (a, b) | isCycle   = Just (length a)
                   | otherwise = Nothing
  where isCycle = (length a) <= (length b) && (take (length b) (cycle a)) == b

splited :: Eq a => Int -> [a] -> Maybe ([a], [a])
splited _ [] = Nothing
splited n xs = fmap (flip splitAt xs) $ sameIdx n
  where sameIdx n = fmap (+n) $ elemIndex (head xs) (drop n xs)

euler27.hs

import Data.List (findIndex, maximumBy)
import Data.Ord (comparing)
import Zaneli.Euler (isPrime)

main = print $ fst $ maximumBy (comparing snd) $ [(a*b, f a b) | a <- [-999..999], b <- [-999..999]]
  where f a b = maybe 0 id $ findIndex (\n -> not $ isPrime (n^2 + a*n + b)) [0..]