backtrack12.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 {
		'n' => n,
		'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 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['av'] / 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

def dist(k)
	s = {}
	l = []
	1e4.to_i.times \
	{
		ns = dense(100, 0.5)
		x = count(ns)
		next if (s.member?(x[k]))
		s[x[k]] = nil
		l << x
	}
	return l.sort_by { |x| x[k] }
end

def trend(x)
	n = x['n']
	
	l = (l1 = back(n)).map { |x| {'av' => avg(x.map { |x1| Math.log(x1) })} }
	
	return x.merge({'l' => l})
end

k = 'cm'

l = dist(k)

l2 = l.map { |x| trend(x) }



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

graph(k, f, l2)

f.close