backtrack11b.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 seq(n)

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

def remove(a, ks)
	a = a.dup
	ks.each { |x| a.delete(x) }
	return a
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] }
	npo = Math.log(l[ns.length])
	
	return {
		'ns' => ns, 
		'cm' => cm,
		'cm1' => cm1,
		'ls' => l.size.to_f / 10,
		'cg' => cg,
		'nl' => Math.log(n),
		'npo' => npo
		}
end

def sum(l)

	t = 0.0
	l.each { |x| t += x }
	return t
end

def avg(l)
	return nil if (l.empty?)
	return sum(l) / l.size
end


def trend(n)
	
	l = (l1 = back(n)).map { |x| {'mn' => Math.log(x.min), 'mx' => Math.log(x.max), 'r' => Math.log(x.max) - Math.log(x.min), 'av' => avg(x.map { |x1| Math.log(x1) })} }
	mn = l.map { |x| x['mn'] }.min
	mx = l.map { |x| x['mx'] }.max
	rmn = l.map { |x| x['r'] }.min
	rmx = l.map { |x| x['r'] }.max
	
	return {'n' => n,
		'n3' => n % 3,
		'n2' => n % 2,
		'mn' => mn,
		'mx' => mx,
		'rmn' => rmn,
		'rmx' => rmx,
		'rrmn' => mn / Math.log(n),
		'l1' => l1,
		'l' => l
		}.merge(count(n.to_s(2)))
end

def graph(k, f, l2)
	l2.sort_by! { |x| x[k] }

	f.puts("$dat << eof")
	f.puts(l2[0].keys.join("\t"))

	j = 0
	l2.each_with_index \
	{ 
		|x, c| 
		l = x['l']
		w = x['n'].to_s(2).length
		l.each_with_index \
		{
			|x1, i|
			f.puts([i, x1['mn'] / w, c].join("\t"))
		}
		f.puts
	}

	f.puts('eof')

	f.puts('plot $dat using 1:2:3 with line linecolor palette lw 1')
	f.puts('pause -1')
end

l2 = []

100.times { l2 << trend(dense(100, 0.5).to_i(2)) }

# l2.each { |x| p([x['cm'], x['cg']].join("\t")) }; exit


f = File.open('gnuplot.cmd', 'w')

graph('cm', f, l2)
graph('cg', f, l2)

f.close