HaskellでProject Euler(Problem 10～12)

うーむ、何か今回は力技でやっつけた感が…。
もっと効率良くエレガントに実現する方法があるように思うんだけどなぁ。
それから、以前の問題で使用した関数を流用するケースが出てきたからこちらのコメントを参考に
そろそろ共通的に使用できそうな関数を切り出してまとめたりするべきかな。

Problem 10. Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
Problem 10. Summation of primes
10以下の素数の和は 2 + 3 + 5 + 7 = 17 である.
200万以下の全ての素数の和を求めよ.
Problem 10 「素数の和」

素数を求める関数は Problem 7. で作成した euler7-2.hs を流用した。
Problem 7. ではn番目の素数が欲しかったが、今回はn以下の素数が欲しいので、再帰の終了条件を変更している。
最適化オプション「-O」をつけてコンパイルして4秒くらい、か。
多分もっと速くする方法や、もっと綺麗に書く方法もありそうだが…。

Problem 11. Largest product in a grid

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.
The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction
(up, down, left, right, or diagonally) in the 20×20 grid?
Problem 11. Largest product in a grid
上の 20×20 の格子のうち, 対角線に沿って4つの数字が赤くマークされている.
それらの数字の積は 26 × 63 × 78 × 14 = 1788696 となる.
上の 20×20 の格子のうち, 上下左右斜めのいずれかの方向で連続する4つの数字の積のうち最大のものはいくつか?
Problem 11 「格子内の最大の積」 (問題文に掲載されている 20×20 の格子は省略)

何やら数学的にというより、手続きプログラミング的なスタイルで解いてしまった感が。

格子を数値のリストのリストとして表現する。
横一列の4つの数字の積は、mapで一列ずつ処理して、
要素が4つあれば積を求めてそれまでの積の最大値との大きい方を保持することで算出している。
縦一列の4つの数字の積は、四列ずつzip関数で4つ組のタプルのリストにして、
mapでタプルの要素の積を求めて算出している。
斜めの算出方法だが…これがかなり力技というか、あんまりイケてないやり方のように思っているが、
数値のリストのリストを与えて、リストの第一要素からtailのtailのtailのheadを、第二要素からtailのtailのheadを…と
斜めに連続する値を4つ取り、積を求めることで算出している。
Scala の headOption 的な関数が見つからなかったので自前で headMaybe, tailMaybe を作って処理しているが、
標準関数でもっと巧くできそうな気がしている。
一度に右斜めと左斜めの積を求めようとしているが、p2の引数の与え方なんかも強引だし…。

Problem 12. Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers.
So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
Problem 12. Highly divisible triangular number
三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
となる.
最初の7項について, その約数を列挙すると, 以下のとおり.
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
これから, 7番目の三角数である28は, 5個以上の約数をもつ最初の三角数であることが分かる.
では, 500個以上の約数をもつ最初の三角数はいくつか.
Problem 12 「高度整除三角数」

最初、約数の個数は愚直に全ての約数をリストとして返すこんな関数を書いていたが、

divisors :: (Integral a, Num b) => a -> b
divisors n =  divisors' (n `div` 2) 1
  where
    divisors' 0 cnt             = cnt
    divisors' m cnt | isDivisor = divisors' (m - 1) (cnt + 1)
                    | otherwise = divisors' (m - 1) cnt
      where isDivisor = n `mod` m == 0

とてもじゃないが処理が終わらない。
そこで、素因数分解した結果の全ての組み合わせで約数を出す、というやり方にした。
(どうも数学的にもそれがセオリーというか、簡単に約数の個数を出す定番の方法のようだ)

素因数分解を求める関数は Problem 3. で作成した euler3-3.hs を流用した。
Problem 3. では素因数分解の最大値を求めたいので重複する素因数を保持する必要はなかったが、
今回は全ての組み合わせをリストとして保持したい。
そこで、割り切れるまで割るところで割れた回数を cnt として保持しておき、(replicate cnt m) を list に加えるようにしている。
2で2回割れれば[2,2]を、3回割れれば[2,2,2]を先頭に追加する。
素因数分解の全ての組み合わせを出す関数だが、これももっと簡潔に書けるか標準関数を利用できたかもしれない。
全ての組み合わせを出すには、要素一つ一つに対して、
その要素があるパターン((map (\x -> m:x) n) で作る)と無いパターン(n に何も足さずそのまま)を foldl でリストのリストとして作り、
重複を排除した要素数で出している。
(今回は素因数分解の結果が降順にソートされていることが分かっているので nub で重複を排除しているが、
順不同の場合は積を求めてから nub するのがいいんだろうか。