「HaskellでProject Euler(Problem 37～39)」ブログ用

euler37-1.hs

import Zaneli.Euler (numToList, listToNum)

main = print $ sum $ trunPrimes 11

trunPrimes :: Int -> [Int]
trunPrimes limit = trunPrimes' 3 [2] []
  where
    trunPrimes' n primes result
      | length result >= limit = result
      | isPrime n              = trunPrimes' (n + 2) (primes ++ [n]) result'
      | otherwise              = trunPrimes' (n + 2) primes result
      where
        ns = numToList n
        isPrime m = all (\x -> m `mod` x /= 0) $ takeWhile (\x -> x ^ 2 <= m) primes
        isPrime' f = elem  (listToNum $ f ns) primes
        result' | isTrunPrime = (n:result)
                | otherwise   = result
        isTrunPrime | n < 10    = False
                    | (head ns /= 2) && (any even ns) = False
                    | otherwise = all id $ map (\i -> (isPrime' (take i)) && (isPrime' (drop i))) [1..length ns-1]

euler37-2.hs

import Data.List (inits, tails)
import Zaneli.Euler (numToList, listToNum)

main = print $ sum $ trunPrimes 11

trunPrimes :: Int -> [Int]
trunPrimes limit = trunPrimes' 3 [2] []
  where
    trunPrimes' n primes result
      | lengthMoreThan (limit-1) result = result
      | isPrime n                       = trunPrimes' (n+2) (primes ++ [n]) result'
      | otherwise                       = trunPrimes' (n+2) primes result
      where
        ns = numToList n
        isPrime m = all (\x -> m `mod` x /= 0) $ takeWhile (\x -> x^2 <= m) primes
        result' | isTrunPrime = (n:result)
                | otherwise   = result
        isTrunPrime | n < 10                          = False
                    | (head ns /= 2) && (any even ns) = False
                    | otherwise                       = all (flip elem primes) $ trunNums ns

lengthMoreThan :: Int -> [a] -> Bool
lengthMoreThan n ns = not . null . drop n $ ns

trunNums :: Num a => [a] -> [a]
trunNums ns = map listToNum $ (takeMiddle inits ns) ++ (takeMiddle tails ns)
  where takeMiddle f = tail . init . f

euler38.hs

import Data.Char (intToDigit)
import Data.List (nub, sort)
import Data.Maybe (catMaybes)

main = print $ maxConPand 987654321

maxConPand :: (Num a, Show a, Read a, Num b, Read b) => a -> b
maxConPand n = read $ maximum $ catMaybes $ map (flip concatenatedPands digits) [1..limit]
  where
    xs = show n
    digits = length xs
    limit = read $ take (length xs `div` 2 + 1) xs

concatenatedPands :: (Num a, Show a) => a -> Int -> Maybe String
concatenatedPands n digits =  f 2 $ show n
  where
    f m xs | length xs' < digits = proceed
           | isPand digits xs'   = Just xs'
           | otherwise           = Nothing
           where xs' = xs ++ (show $ n*m)
                 proceed | xs == nub xs' = f (m+1) xs'
                         | otherwise     = Nothing

isPand :: Int -> String -> Bool
isPand n xs = ['1'..intToDigit n] == sort xs

euler39-1.hs

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

main = print $ solutions 1000

solutions :: (Enum a, Eq a, Num a) => a -> a
solutions n = fst $ maximumBy (comparing $ length . snd) $ map f [3..n]
  where f n = (n, [ (a, b, c) | a <- [1..n-2], b <- [a..n-1], let c = n - a - b, a^2 + b^2 == c^2])

euler39-2.hs

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

main = print $ solutions 1000

solutions :: Integral a => a -> a
solutions n = fst $ maximumBy (comparing $ length . snd) $ map f [3..n]
  where f n = (n, [ (a, b, c) | a <- [1..(n `div` 3)], b <- [a..((n-a) `div` 2)], let c = n - a - b, a^2 + b^2 == c^2])