extend36.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, r)
	
	l = [z]
	p = z['p'] + 1
	
	l << adv({'n'=>z['n'] + 2**p, 'p'=>p})
	l << z.merge({'p'=>p})
	
	if (!r.empty?) then
		x = l[1]
		z = 0
		r.keys.each \
		{
			|k|
			z += (x[k] - r[k]['a']) / r[k]['sd']
		}
		x['z'] = z
	end
	
	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
end

def rank(l, w, i, r)

	if ((i + 1) % 100 == 0) then
		w.each \
		{
			|k|
			a, sd = stat(l.map { |x| x[1][k] })
			r[k] = {'a' => a, 'sd' => sd}
		}
	end
		
	l.sort_by! { |x| x[1]['z'].nil? ? x[1]['ls'] : x[1]['z'] }
	l.reverse!
	
end

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


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

i = 0
w = ['ls', 'c', 'ns', 'r']

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