HaskellでProject Euler(Problem 4～6)

おいら頑張るよ！
何だか問題の難度にだいぶムラがあるような…
今回は問題自体易しかったのか、Haskell だから簡単に書けたのか、
気づいていないだけでもっと効率の良い方法があるのか。

Problem 4. Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
Problem 4. Largest palindrome product
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.
Problem 4 「最大の回文積」

リスト内包表記でn～mの全ての組み合わせの積のリストを作り、
それを降順にソートしたリストに対し、
isPalindrome 関数で回文であるかどうかを検査する。
isPalindrome ではまず数値を文字列に変換し、文字列の長さの半分の値を取り、
先頭から半分までの文字列と逆順にしてから先頭から半分までの文字列が一致すれば回文とみなす。
元の文字列と逆順にした文字列が一致すれば回文とみなす。
降順にソートしているため、isPalindrome でフィルタしたリストの head を取れば回文の最大値となる。
始め、sortBy (\x y -> compare y x) でソートせずに積のリストをそのまま使用して
isPalindrome でフィルタした後 head ではなく maximum で最大値を取得していたが、
そのほうが若干遅いようでこのようになった。
愚直なやり方だったけど、これで事足りるような。パフォーマンスも申し分無い。

Problem 5. Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
Problem 5. Smallest multiple
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
Problem 5 「最小の倍数」

この問題、Haskell では最小公倍数を求める関数 lcm があるので、ワンライナーで書ける。

foldl1 lcm [1..20]

しかし、これではあんまりなので、泥臭く自分で書くことに挑戦。

まず、1～19までのリストを作る。
(nを20ずつインクリメントして再帰するため、リストから20を省ける)
次に、リストの中の自分以外の要素で自分を割り切れる数があれば、それを除外したリストを作る。
(18で割り切れるということは2でも3でも6でも9でも割り切れるので、これらの数は検査対象外として良い)
そうして作ったリストの全ての要素で割り切れる数が出現するまで20から20ずつインクリメントして
smallestMultiple' を呼び続ける。
全ての要素で割り切れる数が出現すれば、その値を返す。
期待通り動いてくれてはいるが…これは遅い…20秒くらいかかる。少し修正してこうなった。

divisors は前のバージョンと同じように
自分以外の要素で自分を割り切れる数を除外したリストを作っている。
異なるのは reverse しているところだが、これによってけっこうパフォーマンスに差が出る。
candidates は答えの候補となる数値のリスト。
20 から 20 ずつ増加し、最大値は divisors を全て掛けた値としている。
これらのリストを作り、candidates の中からdivisors 全てで割れるもののみフィルタし、その先頭を解答としている。
19で割れるもののほうが少ないため、reverse して先に19から検査したほうが速くなるのかな。
だいぶマシにはなったけど…それでも8秒くらいかかる。
が、今のところこれより良い案が思いつかなかった…。

Problem 6. Sum square difference

The sum of the squares of the first ten natural numbers is,

1^2 + 2^2 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)^2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
Problem 6. Sum square difference
最初の10個の自然数について, その二乗の和は,

1^2 + 2^2 + ... + 102 = 385
最初の10個の自然数について, その和の二乗は,

(1 + 2 + ... + 10)^2 = 552 = 3025
これらの数の差は 3025 - 385 = 2640 となる.
同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.
Problem 6 「二乗和の差」

ぬーん、何のひねりも無く書いて、実行もほぼ一瞬で終わるので
これでいいか、という感じだが…まだ改善の余地、または別解があるだろうか…。