久し振りにブログを書いた。久し振りにオイラーを解いた。
Problem 43. Sub-string divisibility(部分列被整除性)
まず、全てのパンデジタル数の組み合わせのリストを作り、条件に該当するもののみフィルターして答えを求める方法を取ってみた。しかし、これは遅い…。20秒くらいかかった。
最初に
permutations で全てのパンデジタル数を作ってからフィルターを行っている処理に時間がかかっているようだが、これは無駄だろう。
例えば最初の2,3,4桁目が2で割り切れなければその後どのような組み合わせであれ条件には該当しないため、
その時点で2,3,4桁目がその数であるパンデジタル数は全て除外できる。
というわけで、パンデジタル数を1桁ずつ組み立てながら、同時にそれぞれの桁が条件に該当するかのチェックも行う方法を試す。
primes はインデックスから該当する素数を取るためArrayにしてみた。select はリストを与えると、その中の1要素と残りの要素のタプルの全ての組み合わせのリストを返す。
> select ['1'..'5']
[('1',"2345"),('2',"1345"),('3',"1245"),('4',"1235"),('5',"1234")]
addPand は組み立て途中のパンデジタル数とまだ選んでいない残りの数値を与えると、残りの数値から1要素を選んで組み立て途中のパンデジタル数に加えたものと選ばなかった残りの要素のタプルの
全ての組み合わせのリストを返す。
> addPand "1" "2345"
[("12","345"),("13","245"),("14","235"),("15","234")]
これらを使い、subStrDivisSum でパンデジタル数を組み立てながら素数で割り切れるか調べ、割り切れなければ組み立て途中でも即座に0を返し、全て割り切れればそのパンデジタル数を返す、という処理で無駄をなくしている。
euler43-1.hs が約20秒に対し euler43-2.hs は約0.3秒と、大幅に高速化できた！
Problem 44. Pentagon numbers(五角数)
一方こちらは何とか解けたものの凄く遅く、高速化のアイディアも思いつかなかった…。五角数は
unfoldr で無限リストを作るようにした。こういう unfoldr の使い方にもだいぶ慣れてきた、かな？ある数が五角数かどうかの判定はこちらを参考にHaskell版を書いてみた。
割り切れたかどうかの判定に、商を
truncate した値と元の値が一致するかどうかを用いてみたが、もっと良いやり方があるだろうか…。メインの処理は
minimisedPentagonal で行っている。五角数一つずつに対してすでに処理済みの五角数との和と差が五角数になる最大のnを取得し、
(nが最大になれば解としてほしいp-nが最小になる。処理済みの五角数nsは逆順に並んでいるのでfindで最初の一つを取ればいい)
それまでの処理で取得済みの値とp-nのうち小さいほうの値を保持し、
処理済みの五角数newNsの先頭に現在の五角数pを加えて再帰で次の五角数に移る、
という流れになっている。
newNsは
filter (\n -> p - n > newD) nsとしているが、解としてほしい最小のnewDよりp-nが大きいものは、次の五角数以降との差が最小にはなり得ないので対象から外すために行っている。
うーむ…2分もかかってしまう…。
おそらく再帰の終了条件に到達するまでかなりの時間がかかっているのだと思う。
現在のdが最小であることを保証するには、ある五角数とその一つ前の五角数の差がd以上なら確実にそこで処理を打ち切って良し、と考えたが、
もっとうまい方法があるだろうか…。
Problem 45. Triangular, pentagonal, and hexagonal(三角数, 五角数, 六角数)
上記2問に比べると、あまり悩まず素直に解けたように思う。unfoldr で六角数の無限リストを作り、40755の次と言われているのでそこまでを除外し、それ以降の六角数が三角数かつ五角数でもあるものを探すようにした。