数値12345を各桁の数値のリスト[1,2,3,4,5]にする関数
これまでも度々使用していて今回の3問全てでも使用したので個人用ライブラリ zaneli-euler に追加した。
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
の使い方が分かるようになってきたのが嬉しい。