« Project Euler - Problem 60 : 私のこだわり | トップページ | Project Euler - Problem 62 »

2009年9月16日 (水)

Project Euler - Problem 61 : 0.06s (Ruby 1.9)

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


まずはコードから……

# -*- coding: utf-8 -*- class Integer def triangle # 三角数 return (self + 1) * self / 2 end def square # 四角数 return self * self end def pentagon # 五角数 return (3 * self * self - self) / 2 end def hexagon # 六角数 return 2 * self * self - self end def heptagon # 七角数 return self * (5 * self - 3) / 2 end def octagon # 八画数 return self * (3 * self - 2) end end def search_ans(arr) arr.each do |flag, old_arr| if old_arr.size == 7 return unless old_arr.first == old_arr.last ans = Array.new 6.times{|i| ans.push(old_arr[i] * 100 + old_arr[i + 1])} print "#{ans.inject(:+)} : #{ans}\n" exit else new_arr = make_new_arr(flag, old_arr) search_ans(new_arr) end end end def make_new_arr(flag, arr) ans = Array.new flag.each_with_index do |bool, i| next if bool vals = $poly_num[i][arr.last] next unless vals vals.each do |n| new_flag = Array.new(flag) new_flag[i] = true ans.push([new_flag, arr + [n]]) end end return ans end func = [lambda{|x| x.octagon }, lambda{|x| x.heptagon}, lambda{|x| x.hexagon }, lambda{|x| x.pentagon}, lambda{|x| x.square }, lambda{|x| x.triangle}] $poly_num = Array.new 6.times do |i| $poly_num[i] = Hash.new 1.upto(1/0.0) do |j| n = func[i].call(j) break if n > 9999 next if n < 1000 key, val = n.divmod(100) $poly_num[i][key] = Array.new unless $poly_num[i][key] $poly_num[i][key].push(val) if val > 9 end end # $poly_num : [{10=>[45], 11=>[60], 12=>[81], 14=>[], ...}, # {10=>[71], 11=>[77], 12=>[88], 14=>[], ...}, # {10=>[35], 11=>[28], 12=>[25], 13=>[26], ...}, # {10=>[80], 11=>[62], 12=>[47], 13=>[35], ...}, # {10=>[24, 89], 11=>[56], 12=>[25, 96], ...}, # {10=>[35, 81], 11=>[28, 76], 12=>[25, 75], ...}] $poly_num[0].each do |key, vals| flag = [true] + Array.new(5, nil) arr = Array.new vals.each{|n| arr.push([Array.new(flag), [key, n]])} search_ans(arr) end

今回はちょっと込み入ったデータを扱うことになってしまいました。

"$poly_num" は 6 個の要素を持つ配列になっています。

それぞれの要素には 4 桁の八角数、七角数、六角数、五角数、四角数、三角数が、上位 2 桁をキーにして下位 2 桁を値にしたハッシュテーブルの形で入っています。

このデータ構造を作るために、"Integer#octagon", "Integer#heptagon" といった一部のメソッドが違うだけで他は同じような処理を書くのが嫌だったので、lambda を使ってメソッドを含むブロックを proc 化したうえで高階関数のような処理をしてみました。

そして、この "poly_num" のデータを使って答えとなる数の組み合わせを探しました。

実際には要素の数が一番少ない八画数のキーから値を取り出し、その値がキーとなるような数字が他の多角数の中にあるかを調べていきました。さらにその値が他の多角数につながるかを調べていって、最終的な答えを導き出しました。

その際に同じ多角数に属する数字を重複して選ばないように、選んだ多角数は "true" 、選ばれていない多角数は "nil" としたフラグを一緒にデータで持たせました。

今回も Problem 60 と同様に、初めは同じような処理が入れ子になったのですが、再帰的な処理にまとめることが出来ました。

データの構造を工夫したのが良かったのか、Ruby 1.9 で約 0.06 秒で答えが出ました。

« Project Euler - Problem 60 : 私のこだわり | トップページ | Project Euler - Problem 62 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler - Problem 60 : 私のこだわり | トップページ | Project Euler - Problem 62 »

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            
フォト

最近のトラックバック

無料ブログはココログ