bitwise11.rb

def f2(n)
	return n.odd? ? (n * 3 + 1) / 2 : n / 2

end


def widthdiff(x, y)
	x.to_s(2).length - y.to_s(2).length
end

def widthratio(x, y)
	x.to_s(2).length.to_f / y.to_s(2).length
end

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

def adj(x, m, n, s2, p2, p, x3)
	s2.replace(p[0...x] + (x3 % 2).to_s)
	m = (s2[x, 1] == p[x, 1])
	n = p2.reverse.to_i(2)
	p2[x, 1] = m ? '11' : '01'
	return m, n, x3
end

def terras121(p)
	
	p2 = ['01', '11'][p[0, 1].to_i]
	n = 1
	n3 = 0
	m = p2 == '11'
	x3 = (p2.reverse.to_i(2)) >> 1

	(1...p.length).each \
	{
		|x|

		if (!m)
			ns = n.to_s(2)
			ns[0, 1] = ''
			m1 = x3 - 3**n3
			n1 = f2(m1)
		end

		n3 = p[0...x].split('').select { |z| z == '1' }.size
		
		s2 = ''
		m, n, x3 = adj(x, m, n, s2, p2, p, m ? (f2(x3) + 3**n3) : (n1 + 3**n3))
	}

	n = p2.reverse.to_i(2)

	return n
end

def len01(ns)
	nl = ns.length
	l1 = ns.split(/0+/).map { |x| x.length }
	
	l2 = ns.split(/1+/)[1..-1]
	l2 = [''] if (l2.nil?)
	
	l0 = l2.map { |x| x.length }
	return l0, l1
end

def count(x)
	
	n1 = n = terras121(x['x'].to_s(2).reverse)
	
	l = [n]
	while (n != 1)
		n = f2(n)
		l << n
	end
	cg = l.index{ |x| x < l[0] }
	cm1 = (0...l.size).max_by { |x| l[x] }
	
	return x.merge({'n' => n1,
		'cg' => cg, 
		'cm1'	=> cm1, 
		'c' => l.size,
		'w' => widthdiff(l[cm1], n1),
		'r' => widthratio(l[cm1], n1),
		'd' => (0.5 - d(n1.to_s(2))).abs,
		'mx01' => l.map { |x| len01(x.to_s(2)) }.flatten.max
	})
	
end

def out(a, a2)
	
	fn = "out#{$i}.txt"
	k = a.keys.sort - a2.select { |k, v| v.nil? }.keys
	
	if ($f.nil?) then
		$f = File.open(fn, 'w')
		$f.puts(k.join("\t")) 
		
		f2 = File.open('gnuplot.cmd', ($i == 0) ? 'w' : 'a')
		f2.puts('set colors classic; set y2tics; set ytics nomirror; set key top left; ') if ($i == 0)
		f2.puts("set title '#{$i}'; plot \\");
		(a.keys - ['t']).each \
		{
			|x|
			next if (!k.member?(x))
			f2.puts("'#{fn}' using (column('t')):(column('#{x}')) with line title '#{x}' #{a2[x]}, \\")
		}
		f2.puts("; pause -1;")
		f2.close
	end
	$f.puts(a.values_at(*k).join("\t"))
	$f.flush
end

def next2(z, l, add = nil)
	
	x = add.call(z, l) if (!add.nil?)
	return true if (x)
	
	out(z, {'cm' => 'lw 3', 'cm1' => 'lw 3', 
		'l' => nil, 'n' => nil, 'x' => nil, 'p' => nil,
		'd' => 'axes x1y2', 'r' => 'axes x1y2'}) if (z['t'] % 10 == 0)
	
	p = z['p'] + 1
	l << [z, count({'x'=>z['x'] + 2 ** p, 'p'=>p, 't' => z['t']}), z.merge({'p'=>p})]
	return
end


def hard(k, c)

	$f = nil
	l = []
	l2 = []
	next2(count({'x' => 1, 'p' => 0, 't' => 0}), l)

	add = lambda { |x, l| l2 << x; return false; }
	
	t = 0
	a = nil
	c.times \
	{
		l1 = (0...l.size).sort_by { |x| [-l[x][1][k], l[x][1]['d']] }.select { |x| l[x][1]['mx01'] <= 10 }
		return 'none', a, l2 if (l1.empty?)
		
		a = {'t1' => t, 'l1' => l.size, 'l2' => l2.size}.merge(l[l1[0]][1].select { |k, | !['l', 'n'].member?(k)})
		
		if ((t + 1) % 100 == 0) then
			return 'abort', a, [] if (a['cm'] == 0)
			$stderr.puts(a.inspect) if ((t + 1) % 500 == 0)
		end

		i = l1[rand([l1.size, l1.size >= 50 ? 20 : 50].min)]
		z = l.delete_at(i)

		[z[1], z[2]].each { |x| return 'cutoff', a, l2 if (next2(x.merge({'t' => t}), l, add)) }

		l.delete_at(l1[-1]) if (l.size > 2000) 
		t += 1
	}
	return 'end', a, l2
end

def sample(l, c)
	return l if (l.size < c)
	r = l.size / c
	l2 = *(0...l.size).select { |x| x % r == 0 }
	l2[c..-1] = []
	return l.values_at(*l2)
	
end

def review(fn)
	l = File.open(fn).readlines.map { |x| Kernel.eval(x) }.sort_by { |x| x['cm1'] }
	$stderr.puts(l.size)
	l = sample(l, 1000)
	l.each { |x| ['n', 'x', 'p'].each { |v| x.delete(v) }; x['t'] = x['t'] / 10.0 }
	
	f = File.open('gnuplot1.cmd', 'w')
	f.puts("set y2tics; set ytics nomirror; set key top left;")
	f.puts("$dat << eof")
	ks = l[0].keys
	f.puts(ks.join("\t"))
	
	l.each { |x| f.puts(x.values.join("\t")) }
	f.puts('eof')
	f.puts('plot \\')
	ks.each \
	{
		|x|
		z = ''
		z = 'axes x1y2 ' if (['d', 'r'].member?(x))
		z += 'lw 4 ' if (['cm1'].member?(x))
		z += 'dt 3' if (['t'].member?(x))
		f.puts("'$dat' using (column('#{x}')) with line #{z},\\")
	}
	f.close
	
	exit
end

def re(c, h, fn)
	
		
	f = File.open(fn, 'w')

	z = {}
	seen = {}

	n = 0
	c.times \
	{
		|i|
		
		$i = i
		e, a, l2 = h.call
		
		$f.close
		$f = nil
		
		z[e] = z.fetch(e, 0) + 1

		n += l2.size

		l2.each \
		{
			|x|
			next if (seen.member?(x['n']))
			seen[x['n']] = nil
			x.delete('l')
			f.puts(x.inspect)
			f.flush
		}
		$stderr.puts("##{i} -- #{e} / #{n} count / #{seen.size} unique", a.inspect)
#		break if (!l2.empty?)
	}

	f.close
	$stderr.puts(z.merge({'n' => n, 'n1' => seen.size}))

end
fn = 'mixdb.txt'

review(fn) if (File.exists?(fn))
re(10, lambda { hard('cm1', 5000) }, fn)