« Project Euler - Problem 42 | トップページ | Project Euler - Problem 44 : 3.8s (Ruby 1.9) »

2009年7月30日 (木)

Project Euler - Problem 43 : 0.09s (Ruby 1.9)

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


実はこの問題は以前、Scheme で解いたときに記事を投稿しているのですが、改めて Ruby 版として投稿します。

素直に解くと次のようになるでしょうか?

(自作の "math_tool.rb" に関してはこちらをご覧ください)

require 'math_tool' Div_List = [nil, 2, 3, 5, 7, 11, 13, 17] def check(arr) 7.downto(1) do |i| return false unless (arr[i, 3].to_i % Div_List[i]) == 0 end return true end ans = Array.new (0 .. 9).to_a.permutation do |num_arr| next if num_arr[0] == 0 ans.push(num_arr.to_i) if check(num_arr) end puts ans.inject(:+)

素直に解いたと言っても、Pandigital な数だけを探索の対象とするために "Array#permutation" を使ったり、早く候補を絞り込めるように、割る数を大きい方から適用したりしています。

このコードでは Ruby 1.9 で約 13 秒ほどで答えが出ます。


ところで総当たりって無駄なことしてると思いませんか?

10 桁目が 0 になる場合を除いても、10 桁の Pandigital な数は全部で 3265920 個もあります。でも d8d9d10 に当てはまる整数は 44 個しかありません。

そこで、まず d8d9d10 に当てはまる数を配列に入れておいて、その数を元に d7 に入る数、d6 に入る数……と順に探していくことにします。

ただし、途中に 0 が来ても桁落ちをしないようにそれぞれの数自体を配列の形で保持しておきます。

# -*- coding: utf-8 -*- require 'math_tool' # require 'pp' Seq_List = (0 .. 9).to_a class Array # * 配列の左に数字を 1 個つけ足す。 # * 新しい配列を数字と見なした時、上位 3 桁が d で割りきれる # ものを選ぶ。 def make_new_array(d) arr = (Seq_List - self).map{|i| [i] + self} return arr.select{|a| a[0, 3].to_i % d == 0} end # * d1 を決め、条件に合う Pandigital 数を完成させる。 # * d1 が 0 の場合は 0 を返す。 def finish arr = Seq_List - self return 0 if arr == [0] return (arr + self).to_i end end # d8d9d10 の候補を ans に収めていく。 ans = Seq_List.permutation(3).select{|arr| arr.to_i % 17 == 0} # pp ans # ans のデータを元に条件に合う配列を作っていく。 [13, 11, 7, 5, 3, 2].each do |d| ans = ans.map{|a| a.make_new_array(d)}.flatten(1) # pp ans end ans = ans.map{|a| a.finish} # pp ans puts ans.inject(:+)

この方法だと、最初に考える数が少ない上に、次第に候補が絞り込まれていくのでかなり短い時間で答えが出ます。(コメントアウトされているコードの "#" を外して実行すると、実際に候補が絞り込まれていく様子が眺められます)

自分の環境では、Ruby 1.9 で約 0.1 秒ほどで答えが出ます。

Problem 37 と同様に、アプローチの仕方を変えるととんでもなく速くなる問題でした。

« Project Euler - Problem 42 | トップページ | Project Euler - Problem 44 : 3.8s (Ruby 1.9) »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler - Problem 43 : 0.09s (Ruby 1.9):

« Project Euler - Problem 42 | トップページ | Project Euler - Problem 44 : 3.8s (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            
フォト

最近のトラックバック

無料ブログはココログ