Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment