backtrack4b.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 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 mx01x(ns)
	l1, l0 = len01x(ns)
	return (l1 + l0).max
end

def add(l, mxp, n, x)

	p = (n % 2).to_s + x['p']
	
	return if (mx01x(p) >= mxp)
	
	
	w = n.to_s(2).length

	l1 = [n] + x['l']

	c = x['c'] + (n.even? ? 1 : 0)
	l << {'n' => n, 
		'p' => p, 
		'w' => n.to_s(2).length,
		'r' => c.to_f / w,
		'l' => l1,
		'c' => c}
end

def back(ns)
	
	mxp = 4
	add(l = [], mxp, ns.to_i(2), {'p' => '', 'l' => [], 'c' => 0})
	
	mx = nil
	k = 'c'
	t = 0
	
	loop \
	{
		return if (l.empty?)
		break if (!mx.nil? && mx[k] >= mx['w'])
		
		l.sort_by! { |x| -x[k] }
		mx = [l[0], mx].compact.max_by { |x| x[k] }
		
		x = l.delete_at(rand([l.size, 50].min))
		
		$stderr.puts([t, x[k]].join("\t")) if (t % 100 == 0)
		n = x['n']
	
		add(l, mxp, (n - 1) / 3, x) if ((n - 1) % 3 == 0 && ((n - 1) / 3).odd?)
		add(l, mxp, n * 2, x)
		
		t += 1
	}
	return mx
	
end

def seq(n)
	l = [n]
	while (n != 1)
		n = f2(n)
		l << n
	end
	return l
	
end

def out(l, c, f)
	l.each_with_index \
	{
		|x, j|
		f.puts([j, x.to_s(2).length, c].join("\t"))
	}
	f.puts
end

def av(l)
	return l.inject(0.0) { |t, x| t + x } / l.size
end

def corr(l, y1, yp)
	
	xav = av(l.map { |x| x[y1] })
	yav = av(l.map { |x| x[yp] })

	tx = ty = txy = e = 0.0
	m = nil
	l.each \
	{
		|z|
		
		x = z[y1]
		y = z[yp]
		
		txy += (x - xav) * (y - yav)
		tx += (x - xav) ** 2
		ty += (y - yav) ** 2
		e1 = (x - y).abs
		e += e1
		m = [m, e1].compact.max
	}
	r = txy / (Math.sqrt(tx) * Math.sqrt(ty))
	e /= l.size
	return {'r' => r, 'e_a' => e, 'e_m' => m}
	
end

def slopecorr(l, l2)
	return 1.0 if (l.nil? || l.empty?)
	
	l = l.map { |x| Math.log(x) }
	
	a, b = [l[0], l[-1]]
	
	l2.replace((0...l.size).map \
	{
		|x|
		
		y1 = a + x.to_f / (l.size - 1) * (b - a)
		y2 = l[x]
		{'y1' => y1, 'y2' => y2}
	})
	
	return corr(l2, 'y1', 'y2')['r']
end

def construct(w, t, c, f, f2, l1)
	
	x = nil
	begin
		ns = dense(w, 0.5)
		
		ns[t, w - t] = '1' * (w - t)

		x = back(ns)

	end while (x.nil?)


	x.delete('l')
	$stderr.puts(x.inspect)
	n = x['n']
	
	l = seq(n)
	out(l, c, f)
	
	sc = slopecorr(l[n.to_s(2).length..-1], [])
	f2.puts([w, sc].join("\t"))

	f.flush
	f2.flush

	l1 << n
end

def d(s)
        c = s.split('').select { |x| x == '1' }.size
	d = c.to_f / s.length
        return d
        
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.map { |x| x.to_s(2).reverse }, f)
	f.close

end



f = File.open('out.txt', 'w')
f2 = File.open('out2.txt', 'w')

l = []
40.times { |c| construct(100 + 10 * c, 10, c, f, f2, l) }


grid(l)