読者です 読者をやめる 読者になる 読者になる

Tree構造を利用して問題を解いてみる(Ruby)

前回実装した Tree構造を使って、プロジェクト・オイラーの問61を解いてみました。問題はこれです。

require 'bundler/setup'
require 'utils'    #自作の野良Gem。下では Float#integer? を使っている
require './tree'

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 Node
  def initialize(num, type)
    @num = num
    @type = type
  end
  attr_reader :type, :num
  
  def upper;  @num / 100; end
  def downer; @num % 100; end
  
  #特定のtypeの全ノードを配列で返す
  def self.select(n, type1)
    n.select {|node| node.type == type1}    #Array:要素はNode
  end
  
  #nodeのあとにselfが続けばtrue、続かなければfalse
  def succeed?(node)
    node.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.type}
  end
end

#typesの配列arにないtypeを配列で返す
def select_unused_types(ar)
  (0..5).to_a - ar
end

## main ##
n = []
for i in 1000..9999
  n << Node.new(i, 0) if triangle?(i)
  n << Node.new(i, 1) if square?(i)
  n << Node.new(i, 2) if pentagonal?(i)
  n << Node.new(i, 3) if hexagonal?(i)
  n << Node.new(i, 4) if heptagonal?(i)
  n << Node.new(i, 5) if octagonal?(i)
end
m = []    #タイプごとに全ノードが入る配列
6.times {|i| m[i] = Node.select(n, i)}

t = Tree.new(:root)
m[5].each {|node| t.add(:root, node)}
#深さ優先探索
t.dfs(:root) do |node, depth|
  if depth == 6    #最下層か
    ar = t.get_nodes(:root, node)
    if ar[1].succeed?(node)    #完全に循環するか
      p ar[1..-1]
      p ar[1..-1].map {|x| x.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 |node1|
      next unless node1.succeed?(node)    #数字の「しりとり」になっているか
      node1 = Node.new(node1.num, node1.type) if t.exist?(node1)
      t.add(node, node1)    #ノードの追加
    end
  end
end

深さ優先探索でトラバースしています。
問題にしてはえらく長いコードに見えますが、実質的なループは最後の 20行くらいです。多くの部分はクラスの設定や初期設定が占めているわけです。


結果は下です。

[(1281, 5), (8128, 3), (2882, 2), (8256, 0), (5625, 1), (2512, 4)]
28684

user      0m0.252s

答えが見つかった時点での Tree は以下です。

-- root -- (1045, 5) -- (4560, 0) -- (6084, 1) -- (8400, 2) 
                     -- (4510, 2) -- (1035, 0) -- (3553, 4) -- (5329, 1) 
                                                            -- (5356, 3) -- (5625, 1) 
                                  -- (1081, 0) -- (8100, 1) 
                                               -- (8128, 3) -- (2809, 1) 
                                                            -- (2839, 4) -- (3969, 1) 
                                  -- (1024, 1) -- (2415, 0) -- (1540, 3) 
                                                            -- (1525, 4) -- (2556, 3) 
                                               -- (2485, 0) 
                                               -- (2415, 3) -- (1540, 0) 
                                                            -- (1596, 0) 
                                                            -- (1525, 4) -- (2556, 0) 
                                  -- (1089, 1) -- (8911, 0) -- (1128, 3) -- (2839, 4) 
                                                            -- (1177, 4) 
                                               -- (8911, 3) -- (1128, 0) -- (2839, 4) 
                                                            -- (1176, 0) 
                                                            -- (1177, 4) -- (7750, 0) 
                                               -- (8910, 4) -- (1035, 0) 
                                                            -- (1081, 0) -- (8128, 3) 
                                                            -- (1035, 3) -- (3570, 0) 
                                  -- (1035, 3) -- (3570, 0) -- (7056, 1) -- (5688, 4) 
                                               -- (3553, 4) -- (5356, 0) -- (5625, 1) 
                                                            -- (5329, 1) -- (2926, 0) 
                                  -- (1071, 4) -- (7140, 0) -- (4096, 1) 
                                                            -- (4005, 3) 
                                               -- (7140, 3) -- (4005, 0) 
                                                            -- (4095, 0) 
                                                            -- (4096, 1) 
                     -- (4560, 3) -- (6084, 1) -- (8400, 2) 
                     -- (4558, 4) -- (5886, 0) -- (8649, 1) -- (4950, 3) -- (5017, 2) 
                                               -- (8626, 2) -- (2601, 1) 
                                               -- (8646, 3) -- (4624, 1) 
                                                            -- (4676, 2) 
        -- (1160, 5) -- (6084, 1) -- (8400, 2) 
        -- (1281, 5) -- (8128, 0) -- (2809, 1) 
                                  -- (2882, 2) -- (8281, 1) -- (8128, 3) -- (2839, 4) 
                                  -- (2850, 3) -- (5041, 1) -- (4187, 2) 
                                                            -- (4141, 4) -- (4187, 2) 
                                               -- (5017, 2) -- (1764, 1) -- (6426, 4) 
                                                            -- (1782, 4) -- (8281, 1) 
                                  -- (2839, 4) -- (3969, 1) -- (6902, 2) 
                                                            -- (6903, 3) 
                     -- (8100, 1) 
                     -- (8177, 2) -- (7750, 0) -- (5041, 1) -- (4186, 3) -- (8614, 4) 
                                                            -- (4141, 4) -- (4186, 3) 
                                  -- (7744, 1) -- (4465, 0) 
                                  -- (7756, 4) -- (5671, 0) -- (7140, 3) -- (4096, 1) 
                                               -- (5625, 1) -- (2556, 0) 
                                                            -- (2556, 3) -- (5671, 0) 
                     -- (8128, 3) -- (2850, 0) -- (5041, 1) -- (4187, 2) 
                                                            -- (4141, 4) -- (4187, 2) 
                                               -- (5017, 2) -- (1764, 1) -- (6426, 4) 
                                                            -- (1782, 4) -- (8281, 1) 
                                  -- (2809, 1) 
                                  -- (2882, 2) -- (8256, 0) -- (5625, 1) -- (2512, 4)
                                                            -- (5688, 4) 
                                               -- (8281, 1) 
                                  -- (2839, 4)