extend35.rb

def d(s)
        c = s.split('').select { |x| x == '1' }.size
	d = c.to_f / s.length
        return d
        
end

def out(x)
	if ($x.nil?) then
		$x = {'fn' => 1, 'c' => 0}
	else
		$x['c'] += 1
		if ($x['c'] == 5000) then
			$x['f'].close()
			$stderr.puts($x['fn'])
			$x['c'] = 0
			$x['fn'] += 1
		end
	end
	if ($x['c'] == 0) then
		$x['f'] = File.open("tmp/out_#{$x['fn']}.txt", 'w') 
		$x['f'].puts(x.keys.join("\t"))
	end
	
	$x['f'].puts(x.values.join("\t"))
	$x['f'].flush
end

def adv(x)
	
	n1 = n = x['n']

	l = [n]
	d2 = 0
	c = nil
	while (n != 1) 
		d = d(n.to_s(2)) - 0.5
		c = l.size if (c.nil? && d * d2 < 0)
		d2 = d
		n = (n * 3 + 1) / 2 while (n.odd?)
		n /= 2 while (n.even?)
		l << n
	end

	x['ls'] = l.size
	x['c'] = c.nil? ? 0 : c
	x['ns'] = n1.to_s(2).length
	x['r'] = x['c'].to_f / x['ns']
	out(x)
	return x
	
end

def next2(z)
	
	l = [z]
	p = z['p'] + 1
	
	l << adv({'n'=>z['n'] + 2**p, 'p'=>p})
	l << z.merge({'p'=>p})
	return l
end

def stat(l)
	l = [0] if (l.empty?)
        t = t2 = 0
        l.each \
        {
		|x|
		t += x
		t2 += x ** 2
        }
        c = l.size
        a = t.to_f / c
        z = t2.to_f / c - a ** 2
        sd = Math.sqrt(z < 0 ? 0 : z)

	return a, sd, l.max.to_f, l.min.to_f
end

def rank(l)
	
	l.sort_by! { |x| x[1]['r'] }
	l.reverse!
	
end

File.delete(*Dir['tmp/*'])


l = [next2({'n'=>1, 'p'=>0})]

loop \
{
	rank(l)
	z = l.delete_at(rand([l.size, 50].min))
	l.pop if (l.size > 1000)
#	p(z[1])
	
	l << next2(z[1])
	l << next2(z[2])
}