ザネリは列車を見送った ブログという名の備忘録

数値12345を各桁の数値のリスト[1,2,3,4,5]にする関数numToListとその逆の関数listToNum、
これまでも度々使用していて今回の3問全てでも使用したので個人用ライブラリ zaneli-euler に追加した。

Problem 34. Digit factorials(桁の階乗)

fact関数は始めfact n = foldl (*) 1 [1..n]としていたが、
よりシンプルな書き方を教えてもらいそちらに変更。
問題文に上限が定められていないので、まずlimit関数で上限を算出することにした。
自分自身と各桁の数の階乗の和を比較し、ある数までは後者が大きいがそれを超えると前者のほうが大きくなるようになるので、
そこまで調べればよいことになる。
厳密にやるともっと範囲を絞れそうな気もするが、とりあえずこんな感じで。
あとはリスト内包表記で、各桁の数の階乗の和が自分自身と一致する数のみのリストを作る。
1!と2!は含めないため、3からlimit関数で算出した値まで。
内包表記の中で毎回各桁に対してfact関数を呼ぶのは効率的ではないので、
予め0～9の階乗を作り、内包表記の中でその値を参照することにした。
最初、リストfacts = map fact [0..9]を作ってmap (facts !!) $ numToList nとしていたが、
Data.Arrayを使ったほうがわずかに速かったのでこちらを採用。

Problem 35. Circular primes(巡回素数)

処理の高速化に苦戦した…。
100万未満までの素数を取得するのには以前作成していたprimesLimitNumを利用した。
circularsは、元の数の先頭桁数を末尾に追加した数値を作る、という操作を元の数と一致するまで続けることで
巡回数を作成している。
高速化のミソになったのがunprocessedで、作成した巡回数の中に元の値より小さいものがあれば
その数は処理済みとみなす判定を入れてみた。
他にも色々やり方は思いついたが、
条件に合致する数を保持しておいてnot (elem m cps)で処理済みかどうかを判定すると100秒以上かかり、
unprocessed (n:ns) = all (\m -> (m >=n) || (m==0)) nsのように先頭の数値より以降の数値が小さい場合に
処理済みとみなすようにすることも検討したが
113と131では前者とTrueとし後者をFalseとするような上手い処理を思いつかず断念、
このような形に落ち着いた。
これでも13秒くらいかかるが…。
巡回数を作成して初めて処理済みかどうかの判定ができるのがイマイチな気がする…。

※2014/3/15追記

こちらのコメントを元に修正してみた。
containEvenで事前にチェックすることで、全体の処理が10秒以上かかっていたのが2～3秒で終わるようになった！
isCircularPrimeのガードは、containEven numList || processed m cirs = Falseと一つにすることもできたが、
こちらのほうが見通しが良いかな、と思い分けてみた。(どちらが一般的なんだろうか？)

Problem 36. Double-base palindromes(二種類の基数による回文数)

工夫したところといえばtoBinaryをunfoldrで作るようにしたことくらいか。
前問での巡回数作成関数もそうだが、unfoldrの使い方が分かるようになってきたのが嬉しい。