「HaskellでProject Euler(Problem 67～69)」ブログ用

euler67.hs

main = do triangle <- readFile "triangle.txt"
          print $ maximumPath $ map toInts $ reverse $ lines triangle

maximumPath :: (Ord a, Num a) => [[a]] -> a
maximumPath nss = head $ foldl1 (zipWith (+) . largerList) nss

toInts :: String -> [Int]
toInts line = map read $ words line

largerList :: Ord b => [b] -> [b]
largerList l = zipWith max l $ tail l

euler68.hs

main = print $ maxMagic5GonRing

maxMagic5GonRing :: Int
maxMagic5GonRing = maximum $ map read $ filter (\s -> length s == 16) $ map (toStr . concat) magic5GonRing
  where toStr = foldl (\acc n -> acc ++ (show n)) ""

magic5GonRing :: [[[Integer]]]
magic5GonRing = [[[n1, n2, n3], [n4, n3, n5], [n6, n5, n7], [n8, n7, n9], [n10, n9, n2]] |
  (n1, ns1) <- select [1..10],
  (n2, ns2) <- select ns1,
  (n3, ns3) <- select ns2,
  let sum = n1 + n2 + n3,
  (n4, ns4) <- select ns3, n4 > n1,
  (n5, ns5) <- select ns4,
  n4 + n3 + n5 == sum,
  (n6, ns6) <- select ns5, n6 > n1,
  (n7, ns7) <- select ns6,
  n6 + n5 + n7 == sum,
  (n8, ns8) <- select ns7, n8 > n1,
  (n9, ns9) <- select ns8,
  n8 + n7 + n9 == sum,
  (n10, _) <- select ns9, n10 > n1,
  n10 + n9 + n2 == sum]

select :: [a] -> [(a, [a])]
select xs = map select' [0..(length xs) - 1]
  where select' i = let (ys, z:zs) = splitAt i xs in (z, ys ++ zs)

euler69.hs

import Data.List (maximumBy)
import Data.Ord (comparing)
import Data.Ratio ((%))
import Zaneli.Euler (primeFactors)

main = print $ fst $ maximumBy (comparing snd) $ map (\n -> let t = totient n in (n, n % t)) [1..1000000]

totient :: Integral a => a -> a
totient 1 = 1
totient n = product $ map (\(p, m) -> (p-1) * p ^ (m-1)) $ primeFactors n