HaskellでProject Eulerに挑戦してみた

HaskellでProject Eulerに挑戦してみた

id:gomi-boxに触発されて、Project Eulerに挑戦してみた。

Project Eulerみたいな、アルゴリズム的なものを書いて一人でくねくねする遊びは、Haskellとの相性が良すぎる。

コードは続きで。

Problem 1

Problem 1 - PukiWiki

1,000 未満の 3 か 5 の倍数になっている数字の合計を求めよ。

prob1 = sum [x | x <- [1..999], (mod x 3 == 0) || (mod x 5 == 0)]

Ans. 233168

リスト内包表記が便利すぎる。

Problem 2

Problem 2 - PukiWiki

(フィボナッチ) 数列の項が400万を超えない範囲で、偶数の項の総和を求めよ。

prob2 = sum [x | x <- takeWhile (< 4000000) fib, even x]
    where fib = 1:2:[x + y | (x, y) <- zip fib (tail fib)]

Ans. 4613732

内包表記++。相変わらずフィボナッチ数列の書きやすさは半端ない。

Problem 3

Problem 3 - PukiWiki

600851475143 の素因数のうち最大のものを求めよ。

prob3 = maximum $ factorize 600851475143 (2:[3,5..])
    where factorize n (x:xs) | n < x * x    = [n]
                             | mod n x == 0 = x:factorize (div n x) (x:xs)
                             | otherwise    = factorize n xs

Ans. 6857

素因数分解してから最大値を取得するだけの簡単なお仕事。

Problem 4

Problem 4 - PukiWiki

3桁の数の積で表される回文数のうち最大のものはいくらになるか。

prob4 = maximum [x * y | x <- [100..999], y <- [100..999], isPalindrome $ show (x * y)]
    where isPalindrome []     = True
          isPalindrome [x]    = True
          isPalindrome [x,y]  = x == y
          isPalindrome (x:xs) = (x == last xs) && (isPalindrome $ init xs)

Ans. 906609

3桁の数の積を総当りして、回文になっているものの最大値を取り出すだけの簡単なお仕事。ただし、重い。

Problem 5

Problem 5 - PukiWiki

1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。

prob5 = foldl1 lcm [2..20]

Ans. 232792560

20までの整数の最小公倍数を求める。簡潔すぎて感動。

Problem 6

Problem 6 - PukiWiki

最初の100個の自然数について和の二乗と二乗の和の差を求めよ。

prob6 = (sum [1..100]) ^ 2 - (sum $ map (^ 2) [1..100])

Ans. 25164150

これも簡潔。

Problem 7

Problem 7 - PukiWiki

10001 番目の素数を求めよ。

prob7 = primes !! 10000
    where primes = f [2..] where f (x:xs) = x:f (filter (\n -> mod n x /= 0) xs)

Ans. 104743

エラトステネスの篩を使って素数の無限リストを得る。しかし、重い。

Problem 8

Problem 8 - PukiWiki

以下の1000桁の数字から5つの連続する数字を取り出してその積を計算する。そのような積の中で最大のものの値はいくらか

import List
prob8 = maximum $ map f $ tails "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
    where f ss = product $ map (read . (: [])) $ take 5 ss

Ans. 40824

重そうな処理に見えて、一瞬で答えが出る。take 5 ssが必ずしも5要素返さないから、最小値を求めようとするとうまくいかないかも。Char型をInt型に変換する関数ってないのかな?(read . (: []))とかやってて少し気持ち悪い。

まとめ

Haskell楽しすぎるー

スポンサーサイト

関連記事

トラックバック URL

http://liosk.blog103.fc2.com/tb.php/138-c5dd8cbc

トラックバック

[Euler]Problem2をHaskellで
問)フィボナッチ数列の項の値が400万より小さい、偶数値の項の総和を求めよ。 よくわからないけどググっで実装してみました。 problem2 = sum [ x | x &lt;- takeWhile ( &lt; 4000000 ) fibs, x `mod` 2 == 0 ]...
  • 2013-06-27
  • 発信元: Aruneko的PCのような何か

コメント

コメントの投稿

お名前
コメント
編集キー