少し間が空いたが、前回と前々回の補足。
Problem 43 補足
こちらとこちらを参考に。直前の2つの値を
(a, b)
として持っておくことによって、(x, rest') <- select rest
する際に(100 * a + 10 * b + x)
が素数で割り切れるもののみ選ぶことができる。例えば 1406357289 の場合、
a = 0, b = 0, x = 1, m = 1 で 100 * 0 + 10 * 0 + 1 は 1で割り切れる
a = 0, b = 1, x = 4, m = 1 で 100 * 0 + 10 * 1 + 4 は 1で割り切れる
a = 1, b = 4, x = 0, m = 1 で 100 * 1 + 10 * 4 + 0 は 1で割り切れる
a = 4, b = 0, x = 6, m = 2 で 100 * 4 + 10 * 0 + 6 は 2で割り切れる
a = 0, b = 6, x = 3, m = 3 で 100 * 0 + 10 * 6 + 3 は 3で割り切れる
a = 6, b = 3, x = 5, m = 5 で 100 * 6 + 10 * 3 + 5 は 5で割り切れる
a = 3, b = 5, x = 7, m = 7 で 100 * 3 + 10 * 5 + 7 は 7で割り切れる
…
と最後まで条件を満たし、選ばれたxを先頭に追加していくので foldl の処理が完了した時点で逆順の数値のリストが残るようになる。
euler43-2.hs が約0.3秒かかるのに対し、euler43-3.hs は約0.01秒とさらに高速化することができた!
Problem 45 補足
こちらを参考に書き換えてみた。isectは最初自力で実装しようと試みたが、
isect :: Ord a => [a] -> [a] -> [a] isect xs ys = reverse $ isect' xs ys [] where isect' [] _ zx = zx isect' _ [] zx = zx isect' xs@(x:xs') ys@(y:ys') zx | x == y = isect' xs' ys' (x:zx) | x < y = isect' xs' ys zx | x > y = isect' xs ys' zxxs, ys の両方が無限リストの場合終了してくれなかった…。
無限リストでも動作する関数をうまく作れなかったので、
Data.List.Ordered.isectからそのまま使い回す形で作成した。
Problem 48 補足
こちらとこちらを参考に。下limit桁を取るのに、一桁ずつの数値のリストにしてから要素数-limitまでdropする、という関数で求めていたが、
10^limitで割った余りで求めることにした。
確かにこのほうが余計な変換や桁数による場合分けなどがなくてすっきりする。
また、
fold
でselfPower
しながら合計値を足すようにしていたが、map selfPower
でまず各値のべき乗の下10桁を算出してから、和を算出するように変更した。iterate (drop' . (* n)) 1
で1から始めてnをかけて下10桁を取る、という処理を無限に続けているので、そのn番目を取ればべき乗(の下10桁)になる。
> take 10 $ iterate (drop' . (* 3)) 1 [1,3,9,27,81,243,729,2187,6561,19683] > iterate (drop' . (* 3)) 1 !! 3 27