extend10.rb

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

def adv(x1)

	n1 = n = x1['n']
	d2 = nil
	s = ''
	c = i2 = nil
	ns = n.to_s(2)
	w = ns.length
	x1['d'] = d(ns)
	x1['w'] = w
	l = []
	
	
	while (n != 1) #&& n >= n1)

		l << n
		d = d(n.to_s(2))
		c = s.length if (c.nil? && !d2.nil? && (0.5 - d) * (0.5 - d2) < 0)
		d2 = d
		
		if (n.odd?)
			n = n * 3 + 1
			s << '1'
		end
			
		if (n.even?)
			n /= 2
			s << '0'
			w -= 1
			i2 = l.size if (w == 0)
		end
	end
	
	cm = (0...l.size).max_by { |x| l[x] }
	x1['cm'] = cm.nil? ? 0 : cm
	x1['i2'] = i2.nil? ? 0 : i2
	x1['g'] = x1['cm'] - x1['i2']
	
	x1['c'] = c.nil? ? 0 : c
	m1 = m0 = nil
	
	if (!c.nil?) then
		s2 = s[c..-1]
		m1 = s2.split(/0+/).map { |x| x.length }.max
		m0 = s2.split(/1+/).map { |x| x.length }.max
	end
	m1 = 0 if (m1.nil?)
	m0 = 0 if (m0.nil?)

	x1['m1'] = m1
	x1['m0'] = m0
	
	x1['s'] = s
	
	x1['z'] = x1.values_at(*$w)
	return x1


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 val(l, a, x)
	
	t = 0
	l.size.times \
	{
		|y|
		next if (x == y)
		
		i, j, s = x < y ? [x, y, 1] : [y, x, -1]
		t += a[[i, j]] * s
	}
	return t
end

def val2(l, a)
	return (0...l.size).map { |x| val(l, a, x) }
end

def insert(l, a, r, z)
	
	l << z
	(l.size - 1).times \
	{
		|j|
		t = 0
		l[0].size.times { |i| t += l[j][i] <=> l[-1][i] }
		a[[j, l.size - 1]] = t
	}
	r << val(l, a, l.size - 1) if (!l.empty?)
	(l.size - 1).times \
	{
		|j|
		r[j] += a[[j, l.size - 1]]
	}

end

def delete(l, a, r, x)

	r.size.times \
	{
		|y|
		next if (x == y)
		i, j, s = x < y ? [x, y, 1] : [y, x, -1]
		
		r[y] += a[[i, j]] * s
	}
	r.delete_at(x)

	l.delete_at(x)
	(0...x).each \
	{
		|i|
		(x..(l.size)).each \
		{
			|j|
			a[[i, j]] = a[[i, j + 1]]
		}
	}
	(x..l.size).each \
	{
		|i|
		((i + 1)..(l.size)).each \
		{
			|j|
			a[[i, j]] = a[[i + 1, j + 1]]
		}
	}
	l.size.times { |j| a.delete([j, l.size]) }
	
end

def test()
	
	File.open('db.txt').readlines.map { |x| Kernel.eval(x) }.each_with_index \
	{
		|x, i|
		puts(adv(x).values_at(*$w).join("\t"))
		puts if ((i + 1) % 100 == 0)
	}
end

def fmt(x)
	x.values_at(*$w).inspect
end


$w = ['cm', 'i2', 'g', 'm0', 'm1', 'd']
#test(); exit


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

a = {}
r = []

5000.times \
{
	|i|
	$stderr.puts(i) if (i % 100 == 0)
	
	l2 = (0...l.size).sort_by { |x| r[x] }.reverse
	
	j = l2[rand([l.size, 50].min)]
	
	z = l.delete_at(j)
	delete(l1, a, r, j)
	
	l << next2(z[1])
	insert(l1, a, r, l[-1][1]['z'])
	
	l << next2(z[2])
	insert(l1, a, r, l[-1][1]['z'])
	
	$stdout.puts([l.size, z[1].values_at(*($w + ['w'])), z[1]['s']].join("\t"))
	$stdout.flush
	
#	p(val2(l1, a) == r)
}