vary10.rb

def f2(n)
	return n.odd? ? (n * 3 + 1) / 2 : n / 2

end

def dense(w, d)
	w2 = w - 1
	
	a = (0...w2).to_a
	s = '0' * w2
	(1..(d * w - 1)).map { a.delete_at(rand(a.size)) }.each { |x| s[x, 1] = '1' }
	return ('1' + s)
	
end

def len01(ns)
	nl = ns.length
	l1 = ns.split(/0+/).map { |x| x.length }
	
	l2 = ns.split(/1+/)[1..-1]
	l2 = [''] if (l2.nil?)
	
	l0 = l2.map { |x| x.length }
	return l0, l1
end

def mx01(ns)
	l0, l1 = len01(ns)
	return l0.max, l1.max
end

def put01(w)
		
	ns = dense(w, 0.5)

	r = (0..1).map { rand(w) }.sort

	w1 = r[1] - r[0] + 1
#	p([r, w1])

	s = ('01' * (w1 / 2 + 1))[0...w1]

	ns[r[0]..r[1]] = s

	ns1 = '-' * w
	ns1[r[0]..r[1]] = s

	ns2 = f2(ns.to_i(2)).to_s(2)
#	p(ns1.reverse)
#	p(ns.reverse)
#	p(ns2.reverse)
	return ns, ns2
end

def seq(n)
	l = [n]
	n1 = n
	while (n >= n1)
		n = f2(n)
		l << n
	end
	return l
end

def add(l, ok, n2, x)
#	$seen = {} if ($seen.nil?)
#	raise if ($seen.member?(n2))
#	$seen[n2] = nil
	
#	raise if n2 == 1
	
	return if (n2 == 0 || x['w2'] > x['w1'] * 1.5)
		
	l1 = [n2] + x['l']
	l << {'w1' => x['w1'],
	'n2' => n2,
	'w2' => n2.to_s(2).length,
	'l' => l1}
	
	j = l1.index { |x| x < l1[0] }
	ok << l1 if (j.nil?)
end
	
def avg(l)
	return 0 if (l.nil?)
	l.inject { |t, x| t + x }.to_f / l.size
end

def back(n1)
	l = [{'w1' => n1.to_s(2).length, 
		'n2' => n1, 
		'w2' => n1.to_s(2).length,
		'l' => [n1]
		}]
		
	ok = []
	t = 0
	e = 1e4.to_i
	loop \
	{
		t += 1
		
#		l.sort_by! { |x| -x['l'].size }
		l.sort_by! { |x| x['w2'] }
		
		x = l.delete_at(rand([l.size, 20].min))
		
		n = x['n2']
		
		add(l, ok, (n - 1) / 3, x) if ((n - 1) % 3 == 0 && ((n - 1) / 3).odd?)
		add(l, ok, n * 2, x)
		
		aw2 = avg(l.map { |x| x['w2'] })
		als = avg(l.map { |x| x['l'].size })
		mx = ok.map { |x| x.size }.max
		
		if (t % 1000 == 0 || l.empty? || t == e) then
			z = {'t' => t,
				'l1' => l.size, 
				'aw2' => aw2,
				'als' => als,
				'l10' => l.empty? ? nil : l[0]['l'].size,
				'oks' => ok.size,
				'okmx' => mx}
			$stderr.puts(z.inspect)
			return z if (l.empty?)
			return(z.merge({'oks' => 'e', 'okmx' => 'e'})) if (t == e)
		end
	}
	
end

def make(w)
	l = []
	100.times \
	{

		ns, ns2 = put01(w)
		x0, x1 = mx01(ns)
		y0, y1 = mx01(ns2)

		l << {'d00' => y0 - x0, 'd11' => y1 - x1, 'ns' => ns, 'ns2' => ns2}
	}

	k = 'd11'
	
	l1 = l.sort_by { |x| -x[k] }.select { |x| x[k] > 0 }

	
	x = l1[l1.size / 4]
	$stderr.puts({'l1' => l1.map { |x| x[k] }}.merge(x).inspect)
	return x
end

def x(x)
	x.nil? ? 'x' : x
end

def gp(l, a)
	f = File.open('gnuplot.cmd', 'w')
	f.puts('$dat << eof')
	k = l[0].keys
	f.puts(k.join("\t"))
	l.each { |x| f.puts(x.values.join("\t")) }
	f.puts('eof')
	f.puts('set colors classic; set key right center box opaque; plot \\')
        k.each \
        {
                |x|
                f.puts("$dat using (column('#{x}')) with line #{a.fetch(x, '')},\\")
        }
	f.close
	
end

def review()
	l = File.open('out.txt').readlines.map { |x| x.split }
	c = [0] * 4
	e = [0] * 4
	z = [0] * 4
	
	v = ['rn', 'rc', 'dn', 'dc']
	
	l2 = []
	
	l.each_with_index \
	{ 
		|l1, j| 
		l1.size.times \
		{ 
			|i| 
			c[i] += l1[i].to_f 
			e[i] += 1 if (l1[i] == 'e')
			z[i] += 1 if (l1[i] == 'x')
		}
		
		a = Hash[[v, c.map { |x| x.to_f / (j + 1) }].transpose]
		
		l2 << a.merge({
			'rx' => z[1].to_f / (j + 1),
			'dx' => z[3].to_f / (j + 1),
			're' => e[1].to_f / (j + 1),
			'de' => e[3].to_f / (j + 1)
			})
	}
	gp(l2, {'rc' => 'lw 2', 
		'dc' => 'lw 2',
		'rn' => 'dt 3 lw 3',
		'dn' => 'dt 3 lw 3'})
	exit

end

fn = 'out.txt'
review() if (File.exists?(fn))


#srand(1)

loop \
{

	x1 = back(make(20)['ns'].to_i(2))
	x2 = back(dense(20, 0.5).to_i(2))

	puts([x(x1['oks']), x(x1['okmx']), x(x2['oks']), x(x2['okmx'])].join("\t"))
	$stdout.flush

}