Tree構造を利用して問題を解いてみる・その２（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

答えは前回と同じです。