http://nabetani.sakura.ne.jp/hena/orde11tredis/

yhpg_e11.rb

class Node
  attr_accessor :val, :children, :parent, :index

  def self.divisors(n)
    (1..Math.sqrt(n).ceil).flat_map { |x| if n/x == n.to_f/x then [x, n/x] else nil end}.uniq.reject(&:nil?).sort
  end

  def child_values
    self.class.divisors(@val).map{ |x| x + 1 }.select { |x| x > 2 && x < @val }
  end

  def generate_children
    vals = self.child_values
    if vals.size > 0
      @children = vals.map { |v| Node.new(v) }
    end
    @children.map { |c| c.parent = self}
  end

  def give_children_index
    @children.each_with_index do |c, i|
      c.index = c.parent.index + [i]
      c.give_children_index
    end
  end

  def initialize(val, parent = nil)
    @val = val
    @children = []
    @parent = parent
    @index = [0]
    generate_children
    give_children_index
  end

  def find(n)
    if n == @val
      return [self]
    elsif n > val
      return nil
    else
      @children.flat_map { |c| c.find(n) }.reject(&:nil?)
    end
  end
end

def diff(a,b)
  for i in 0..a.length-1 do
    if a[i] != b[i]
      return i
    end
  end
  a.length
end

def test(s, res_s)
  val_s, two_nums = s.split(":")
  num1_s, num2_s = two_nums.split(",")
  val = val_s.to_i
  num1 = num1_s.to_i
  num2 = num2_s.to_i
  res = res_s.to_i

  n = Node.new(val)
  targets1 = n.find(num1)
  targets2 = n.find(num2)

  distances = targets1.product(targets2).map do |x|
    n1, n2 = x.map(&:index)
    n1.length + n2.length - 2 * diff(n1, n2)
  end

  min_distance = distances.min

  p min_distance
  p res
  p min_distance == res
  puts "-----"
end

def run
  test( "50:6,3", "1" )
  test( "98:5,11", "4" )
  test( "1000:33,20", "7" )
  test( "514:9,18", "8" )
  test( "961:5,4", "3" )
  test( "1369:1369,3", "2" )
  test( "258:16,12", "5" )
  test( "235:13,3", "2" )
  test( "1096:19,17", "8" )
  test( "847:7,17", "6" )
  test( "1932:3,5", "2" )
  test( "2491:4,8", "3" )
  test( "840:421,36", "2" )
  test( "1430:37,111", "3" )
  test( "496:17,9", "2" )
  test( "891:6,10", "1" )
  test( "1560:196,21", "2" )
  test( "516:20,12", "5" )
  test( "696:30,59", "2" )
  test( "1760:5,441", "2" )
  test( "1736:11,26", "5" )
  test( "1518:17,34", "4" )
  test( "806:63,16", "5" )
  test( "1920:3,97", "2" )
  test( "1150:13,22", "4" )
  test( "920:116,5", "1" )
  test( "2016:7,337", "2" )
  test( "408:9,25", "2" )
  test( "735:36,8", "2" )
  test( "470:5,31", "2" )
  test( "2100:12,351", "3" )
  test( "870:36,10", "1" )
  test( "1512:253,13", "2" )
  test( "697:12,15", "3" )
  test( "1224:5,14", "2" )
  test( "986:125,17", "3" )
  test( "864:12,13", "3" )
  test( "500:21,51", "2" )
  test( "819:33,21", "4" )
  test( "594:55,3", "2" )
  test( "638:17,24", "3" )
end