« "Python + Psyco" vs "Ruby 1.9" ?? | トップページ | Project Euler - Problem 61 : 0.06s (Ruby 1.9) »

2009年9月15日 (火)

Project Euler - Problem 60 : 私のこだわり

問題はこちらをご覧ください。


私には、Project Euler の問題を解くに当たって、こだわっていることがあります。それは「探索範囲の決め方」です。

問題文の中に探索範囲が明示されていない場合、数学的な考察で探索範囲を絞り込めない場合、探索範囲を設定せずに解けるようなアルゴリズムを考えるようにしています。

この問題も、その方針に従って、探索範囲の上限を決めずに答えを求められるような解き方を考えました。

そのため、答えが出るまで Ruby 1.9 で 30 秒近くかかってしまいました。


ネットで探してみると、結構多くの人が適当に上限を決めた上でこの問題を解いていました。

探索範囲を勝手に決めることで、かなり速く答えが出るものありましたが、そういった解き方に限って、最初の探索範囲の設定を変えると答えが出なかったり、間違った答えが出るものが多いようでした。

「試行錯誤をしながら探索範囲を決めていく」というやり方も間違いではないのでしょうが、私はそういった解き方が嫌いなので、今回はこの解法で良としました。


require 'prime' require 'math_tool' def concat_prime?(s1, s2) return ((s1 + s2).to_i.prime? and (s2 + s1).to_i.prime?) end def find_chain(arr, rest) if rest.size == 5 ans = rest.map{|i| i.to_i} print "#{ans.inject(:+)} : #{ans}\n" exit else arr.each do |i| arr1 = arr & $primes[i] find_chain(arr1, rest + [i]) end end end $primes = Hash.new Prime.each do |n| n_str = n.to_s arr = Array.new $primes.each do |key, val| arr.unshift(key) if concat_prime?(n_str, key) end if arr.size >= 4 find_chain(arr, [n_str]) end $primes[n_str] = arr end

少しだけコードの解説を……。

素数を小さい順に求めていって、その素数を「キー」にした $primes とうハッシュテーブルを作ります。(後の処理を考えて、すべて文字列にしてあります)

それぞれの「キー」には、「キー」の数字未満の素数で「キー」の数字と連結して別の素数を生成することができる素数の集合が「値」として関連付けられています。

例えば、

{"2"=>[],"3"=>[],"5"=>[],"7"=>["3"],... "109"=>["7", "3"],...}

といった具合です。

ここで「キー」が "109" の場合に注目してもらうと、その「値」は ["7", "3"] となっています。そして「キー」が "7" の時の「値」は ["3"] となっています。

これをみて分かるとおり、ある「キー」の「値」の中の数字を「キー」としてみた場合、それぞれの「値」に同じ数字が含まれていた場合、その数字はそれぞれの「キー」の数字と連結して別の素数を生成できます。

そこで、ある「キー」の「値」が 4 個以上になった場合、その「値」に含まれる数字が「キー」となる値をチェックしていくことによって、この問題の条件に合う数字が見つけられます。


最初に考えたコードでは、同じようなループが入れ子状態になっていて、不格好だったのですが、頑張って "find_chain" という再帰的な処理にすることが出来ました。これでコード自体がすっきりしたと思います。

« "Python + Psyco" vs "Ruby 1.9" ?? | トップページ | Project Euler - Problem 61 : 0.06s (Ruby 1.9) »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/46220213

この記事へのトラックバック一覧です: Project Euler - Problem 60 : 私のこだわり:

« "Python + Psyco" vs "Ruby 1.9" ?? | トップページ | Project Euler - Problem 61 : 0.06s (Ruby 1.9) »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ