backtrack32.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 d(s)
        c = s.split('').select { |x| x == '1' }.size
	d = c.to_f / s.length
        return d
        
end

def add(l, n, x)

	p = (n % 2).to_s + x['p']
	pd = (d(p) - 0.5).abs
	l << {'n' => n, 'pd' => pd, 'p' => p}

end

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

def len1(ns)
	return len(ns, /0+/)
end

def len0(ns)
	return len(ns, /1+/)
end

def len01(ns)
	return len1(ns), len0(ns)
end

def e(ns)
	return len01(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 (column('d')) with line axes x1y2 dt 2 lw 3, \\")
	f.puts("'-' using 1 with line title 'e' axes x1y2 dt 2 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")
	f.puts("d")
	l1.each { |x| f.puts(x[0]) }
	f.puts("eof")
	l1.each { |x| f.puts(x[1]) }
	f.puts("eof")
	
	
end

def grid(l, t = '', fn = 'gnuplot5.cmd')
	
	f = File.open(fn, 'w')
	f.puts("set palette negative grayscale; unset colorbox; set title '#{t}';")
	
	fmt1(l.map { |x| x.reverse }, f)
	f.close
	$stderr.puts([fn, t, l.size].inspect)
end

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


def back()


	begin
	
		ns = dense(15, 0.5) + '1' * 85

		p(ns)

		l = [{'n' => ns.to_i(2), 'pd' => 0, 'p' => ''}]
	end while (l[0]['n'] % 3 == 0)

	t = 0
	c = 100
	loop \
	{
		return if (l.empty?)
		l.sort_by! { |x| [x['pd'], -x['p'].length] }
		break if (l[0]['p'].length == 1400)
		l[c..-1] = [] if (l.size > c)


		x = l.delete_at(rand([l.size, 50].min))
		n = x['n']
		
		
		add(l, (2 * n - 1) / 3, x) if (((2 * n) % 3) == 1 && ((2 * n - 1) / 3).odd?)
		add(l, 2 * n, x)
		
		t += 1
		p({'t' => t, 'l#' => l.size, 'p' => l[0]['p'].length}) if (t % 100 == 0)
	}
	p(l[0])
	ns = l[0]['n'].to_s(2)
	grid(seq(ns.to_i(2)).map { |x| x.to_s(2) })
end


back()