vary12.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 len(ns, p)
	l = ns.split(p)
	l = [''] if (l.nil? || l.empty?)
	return l.map { |x| x.length }
end

def len01(ns)
	return len(ns, /0+/), len(ns, /1+/)
end

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

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

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

	w1 = r[1] - r[0] + 1

	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)
	
	return ns, ns2
end

def make(w)
	
	ns = ns2 = r = nil
	t = 0
	loop \
	{
		t += 1
		ns, ns2 = put01(w)

		mx1 = mx01(ns2)[0]

		r = mx1.to_f / w

		break if (r > 0.45 && r < 0.55)
	}

	$stderr.puts([r, t].inspect)
	return ns
	
end

def add(l, n, x)

	p = x['p'] + (n % 2).to_s
	
	l1m, l0m = mx01(p)
	
	return if (l0m >= 20)
	
	l1 = [n] + x['l']
	cm = (0...l1.size).max_by { |x| l1[x] }
	w = n.to_s(2).length
	
	l << {'n' => n, 
		'p' => p, 
		'w' => w, 
		'l' => l1, 
		'cm' => cm,
		'mxi' => l1.size.to_f / w}
end

def back(ns, c)
	
	add(l = [], ns.to_i(2), {'p' => '', 'l' => []})
	
	mx = nil
	k = 'mxi'
	
	500.times \
	{
		|t|
		return if (l.empty?)
		
		l.sort_by! { |x| -x[k] }
		mx = [l[0], mx].compact.max_by { |x| x[k] }
		
		x = l.delete_at(rand([l.size, 20].min))
		
		puts([t, x[k], c].join("\t"))
		n = x['n']
	
		add(l, (n - 1) / 3, x) if ((n - 1) % 3 == 0 && ((n - 1) / 3).odd?)
		add(l, n * 2, x)
	}
	puts
	return mx
	
end

def reverse(w, mk, c)
	t = 0
	x = nil
	loop \
	{
		t += 1
		ns = mk.call(w)
		x = back(ns, c)
		break if (!x.nil?)
	}
#	$stderr.puts([t, x].inspect)
	return x
end

10.times \
{
	|j|
	
	w = (j + 1) * 100
	x = reverse(w, lambda { |w| make(w) }, w)
}