backtrack6b.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 back(n)
	
	
	l = [n]
	
	return (1..20).map \
	{
		l = l.map \
		{
			|x|
			l1 = [x * 2]
			l1 << (x - 1) / 3 if ((x - 1) % 3 == 0 && ((x - 1) / 3).odd?)
			l1
		}.flatten
		l
	}
	
end

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

def lenx(ns, p)
	l = ns.split(p)
	l = [] if (l.nil?)
	l.shift if (l[0] == '')
	return l.map { |x| x.length }
end

def len01x(ns)
	return lenx(ns, /0+/), lenx(ns, /1+/)
end

def e(ns)
	return len01x(ns).flatten.size.to_f / ns.length
end

def fmt1(l, f)

	w = l.max_by { |x| x.length }.length
	
	f.puts("set colors classic; set ytics nomirror; set y2tics; set key top right opaque;\\")
	f.puts("plot \\")
	f.puts("[0:#{l.size - 1}][0:#{w}] '-' matrix using 2:1:3 with image title '', \\")
	f.puts("'-' using 1 with line title 'e' axes x1y2 lw 3, \\")
	f.puts("'-' using (column('d')) with line axes x1y2 lw 3 ")
	l1 = []
	l.each_with_index \
	{
		|z, i|
		
		l1 << [d(z), e(z)]
		c = w - z.length
		z[z.length...w] = '0' * c
		
		f.puts(z.split('').join(' '))
	}
	f.puts("eof")
	f.puts("eof")
	l1.each { |x| f.puts(x[1]) }
	f.puts("eof")
	f.puts("d")
	l1.each { |x| f.puts(x[0]) }
	f.puts("eof")
	
	
end

def grid(l)
	
	f = File.open(fn = "gnuplot1.cmd", 'w')
	f.puts("set palette negative grayscale; unset colorbox;")
	
	fmt1(l, f)
	f.close

end

def seq(n)

	n1 = n
	l = []
	begin
		l << n
		n = f2(n)
	end while (n != 1)
	
	return l
end

def count(ns)

	l = seq(n = ns.to_i(2))
	cm1 = (0...l.size).max_by { |x| l[x] }
	cg = l.index { |x| x < l[0] }
	cg = l.size if (cg.nil?)
	cm = (0..cg).max_by { |x| l[x] }
	
	return {
		'ns' => ns, 
		'cm' => cm,
		'cm1' => cm1,
		'ls' => l.size.to_f / 10,
		'cg' => cg,
		'nl' => Math.log(n)
		}
end

def out(a, a2 = {}, t = nil)

	fn = 'out.txt'
	k = a.keys
	
	if ($f1.nil?) then
		$f1 = File.open(fn, 'w')
		$f1.puts(k.join("\t")) 
		
		f2 = File.open('gnuplot.cmd', 'w')
		st = t.nil? ? 'unset title; ' : "set title '#{t}'; "
		f2.puts("set ytics nomirror; set y2tics; set colors classic; set key top left box opaque; #{st}; plot \\")
		(a.keys).each \
		{
			|x|
			f2.puts("'#{fn}' using (column('#{x}')) with line title '#{x}' #{a2[x]}, \\")
		}
		f2.puts
		f2.close
	end
	$f1.puts(a.values_at(*k).join("\t"))
	$f1.flush
end

def remove(a, ks)
	a = a.dup
	ks.each { |x| a.delete(x) }
	return a
end

def test1()
	
	l = []
	200.times \
	{
		l1 = back(n = (ns = dense(200, 0.5)).to_i(2))
		l2 = l1.flatten
		
		t = l2.select { |x1| x1 > n }.size
		r = t.to_f / l2.size
		
		c = l2.size.to_f
		c1 = l1[-1].size
		c2 = l1.map { |x| x.size }.max
		
		l << {'ns' => ns, 
			'c' => c / 10, 
			'c1' => c1, 
			'c2' => c2,
			'c3' => c1.to_f / c,
			'r' => r,
			'm' => (n % 3).to_f / 3}.merge(count(ns))
	}


	l.sort_by! { |x| x['c'] }

	grid(l.map { |x| x['ns'] })


	l.each { |x| out(remove(x, ['ns']), 
		{'r' => 'axes x1y2 lw 3', 
		'c3' => 'axes x1y2',
		'm' => 'axes x1y2 lc 7'}) }

end

test1()