partner.rb

#!/usr/bin/ruby1.8
 
 
def dense(n)
 
        s = n.to_s(2)
        c = 0
        s.length.times \
        {
                |i|
                c += s[i, 1].to_i
        }
        return c.to_f / s.length
 
end
 
def f(n)
 
        n1 = n
        c = 0
        m = 0
	
        while (n != 1 && n >= n1)
                n = n * 3 + 1 if (n % 2 == 1)
                n /= 2 while (n % 2 == 0)
                m = [m, n].max
                c += 1
        end
	
        return {'w' => widthdiff(m, n1), 
		'c' => c, 
		'd' => (0.5 - dense(n1)).abs,
		'm' => m}
 
end
 
def long(m)
 
        l = [{'n' => 1, 'p' => 0}.merge(f(1))]
 
        loop \
        {
                l = l.sort_by { |x| [x['w'], x['d']] }.reverse
 
                break if (l[0]['w'] >= m)
 
                x = l.delete_at(rand([l.size, 10].min))
 
                p2 = x['p'] + 1
                n2 = x['n'] + 2 ** p2
 
 
                x1 = x.dup
                x1['p'] = p2
                l << x1
 
                x2 = {'n' => n2, 'p' => p2}.merge(f(n2))
                l << x2
        }
 
        l = l.sort_by { |x| -x['w'] }
        return l.first, l.size
end
 
def widthdiff(x, y)
 
        x.to_s(2).length - y.to_s(2).length
 
end
 
def two(p)
 
        x, c = long(p)
	
        xn = x['n']

	ns = xn.to_s(2)
        yn = ('1' + ns[2..-1]).to_i(2)
 
	y = f(yn)
	
	xm = x['m']
	ym = y['m']
 
        return widthdiff(xm, ym), x['w'], y['w'], c
 
end
 
(1..1000).each \
{
        |p|
        puts([p, two(p), Time.now].join("\t"))
        $stdout.flush
}