Tree構造を利用して問題を解いてみる・その2(Ruby)
こことはちがう Tree 構造を使って、プロジェクト・オイラーの Problem 61をもう一度解いてみました(前回)。使った Tree 構造はこちらです。
コードはそれほどちがいません。クラスを増やしただけ複雑になったとみるか、Node の重複を許すためメインループが多少シンプルになったと見るか。どうでしょう。
require 'bundler/setup' require 'utils' require './tree1' def triangle?(a); ((-1 + (1 + 8 * a) ** 0.5) / 2).integer?; end def square?(a); (a ** 0.5).integer?; end def pentagonal?(a); ((1 + (1 + 24 * a) ** 0.5) / 6).integer?; end def hexagonal?(a); ((1 + (1 + 8 * a) ** 0.5) / 4).integer?; end def heptagonal?(a); ((3 + (9 + 40 * a) ** 0.5) / 10).integer?; end def octagonal?(a); ((1 + (1 + 3 * a) ** 0.5) / 3).integer?; end class Number def initialize(num, type) @num = num @type = type end attr_reader :type, :num def upper; @num / 100; end def downer; @num % 100; end #特定のtypeの全numを配列で返す def self.select(n, type1) n.select {|num| num.type == type1} #Array:要素はNode end #numのあとにselfが続けばtrue、続かなければfalse def succeed?(num) num.downer == self.upper end def to_s "(#{@num}, #{@type})" end alias :inspect :to_s end class Tree #node以上のすべてのノード(:rootは除く)のtypeを配列で返す def get_types(node) get_nodes(@root, node)[1..-1].map {|node| node.value.type} end end #typesの配列arにないtypeを配列で返す def select_unused_types(ar) (0..5).to_a - ar end n = [] for i in 1000..9999 n << Number.new(i, 0) if triangle?(i) n << Number.new(i, 1) if square?(i) n << Number.new(i, 2) if pentagonal?(i) n << Number.new(i, 3) if hexagonal?(i) n << Number.new(i, 4) if heptagonal?(i) n << Number.new(i, 5) if octagonal?(i) end m = [] 6.times {|i| m[i] = Number.select(n, i)} t = Tree.new(Root = Node.new(:root, nil)) m[5].each {|num| t.add(Root, num)} t.dfs do |node, depth| if depth == 6 ar = t.get_nodes(Root, node) if ar[1].value.succeed?(node.value) ar[1..-1].each {|x| print "#{x.value} "}; puts p ar[1..-1].map {|x| x.value.num}.inject(:+) t.put_out exit end end next if node == Root select_unused_types(t.get_types(node)).each do |type| m[type].each do |num1| next unless num1.succeed?(node.value) t.add(node, num1) end end end
答えは前回と同じです。