bitwise42b.rb

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

end

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

def keys(ks2)

	ksmn = ks2.select { |x| x.end_with?('-') }
	
	ksmx = ks2 - ksmn
	
	ksmn.each { |x| x.replace(x.chop) }
	
	x = {'ks' => ksmn + ksmx, 'ksmx' => ksmx, 'ksmn' => ksmn}
	
	$stderr.puts(x.inspect)

	return x
	
end

def order(l, ks2)
	l2 = (0...l.size).map { {} }

	$k = keys(ks2) if ($k.nil?)
	
	$k['ks'].each \
	{
		|k|
		
		l1 = (0...l.size).map { |x| {k => l[x][k], 'i' => x} }

		s = $k['ksmx'].member?(k) ? -1 : 1
		
		l1.sort_by! { |x| s * x[k] }

		(0...l1.size).each { |x| l2[l1[x]['i']][k] = x }
	}
	l2.each { |x| x['z'] = x.values.inject(0) { |t, x| t + x } }
	
	return (0...l2.size).sort_by { |x| l2[x]['z'] }
end

def out(a, a2 = {}, t = nil, ct = "(column('t')):")

	fn = $fn.nil? ? 'out.txt' : $fn
	k = a.keys
	
	if ($f1.nil?) then
		$f1 = File.open(fn, 'w')
		$f1.puts(k.join("\t")) 
		
		f2 = File.open('gnuplot.cmd', 'w')
		st = t.nil? ? 'unset title; ' : "set title \"#{t}\"; "
		
		f2.puts("set ytics nomirror; set y2tics; set colors classic; set key bottom right box opaque; #{st}; plot \\")
		(a.keys - ['t']).each \
		{
			|x|
			next if (a2.member?(x) && a2[x].nil?)
			m = a2.fetch(x, '')
			m += ' with line' if (!m.include?('with'))
			f2.puts("'#{fn}' using #{ct}(column('#{x}')) title '#{x}' #{m}, \\")
		}
		f2.puts
		f2.close
	end
	$f1.puts(a.values_at(*k).join("\t"))
	$f1.flush
end

def remove(a, ks)
	a = a.dup
	ks.each { |x| a.delete(x) }
	return a
end

def seq(n)

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

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

def count(ns)

	nw = ns.length

	l = seq(ns.to_i(2))
	cm1 = (0...l.size).max_by { |x| l[x] }
	cg = l.index { |x| x < l[0] }
	cg = l.size - 1 if (cg.nil?)
	
	cm = (0..cg).max_by { |x| l[x] }
	c = l.size

	n = ns.to_i(2)
	
	return {
		'da' => (d(ns) - 0.5).abs,
		'nw' => nw, 
		'cm' => cm,
		'cm1' => cm1,
		'cg' => cg,
		'c' => c,
		'l' => l,
		'ns' => ns, 
		'n' => n,
		'w' => widthdiff(l[cm], n)
		}
end

def fmt(x)
	return remove(x, ['l'])
end

def axes2(x2)
	return x2.inject({}) { |h, x| h.merge({x => 'axes x1y2' }) }
	
end

def add(l, ns, x2)
	
	$t = 0 if ($t.nil?)
	$t += 1
	
	x = count(ns).merge({'t' => $t})
	l << x
	
	x = fmt(x)
	
	out(remove(x, ['ns']), x2) if ($t % $d == 0)
		
	$stderr.puts(x.inspect) if ($t % 200 == 0) 

end

def adj(ns)

	ns1 = ns.dup
	ns1[0, 1] = '10'
	
	ns2 = ns.dup
	ns2[0, 1] = '11'
	
	return ns1, ns2
end

def opt(ks, c, x2)

	$d = c / 2000
	
	add(l = [], '1', x2)

	(c / 2).times \
	{
		l1 = order(l, ks)

		i = l1[rand([l1.size, 50].min)]
		
		x = l.delete_at(i)

		ns1, ns2 = adj(x['ns'])
		
		add(l, ns1, x2)
		add(l, ns2, x2)
		
	}

	return l[order(l, ks)[0]]
end

def dp(x)
	d(x.to_s(2)) >= 0.5
end

def sum(l)
	return l.inject { |t, x| t + x }
end

def runavg(l, k, c)

	l1 = l.map { |x| x[k] }

	t = sum(l1[0...c])
	l2 = (['-'] * (c - 1)) + [t.to_f / c]
	while (l1.size > c)
		t -= l1.shift
		t += l1[c - 1]
		l2 << (t.to_f / c)
	end
	ka = "#{k}a"
	
	l.each_with_index { |x, i| x[ka] = l2[i] }
	
end

def review(ks)
	l = (f = File.open('out.dat')).readlines
	f.close
	x = Kernel.eval(l[0])
	
	$stderr.puts(fmt(x).to_s)
	n1 = n = x['n']
	l = seq(n)
	
	i = 0
	yi = yj = 0
	zi = zj = 1.0
	l1 = []
	l.each_with_index \
	{
		|x, j|
		dpx, dpn = [dp(x), dp(n)]
		m = {true => 1, false => 0}[dpx == dpn]
		i += m
		yi += {true => 1, false => -1}[dpx]
		yj += {true => 1, false => -1}[dpn]
		zi = {true => zi * 3 + 1, false => zi / 2}[dpx]
		zj = {true => zj * 3 + 1, false => zj / 2}[dpn]
		a = {'ij' => i.to_f / (j + 1), 
#		'yi' => yi, 
#		'yj' => yj, 
		'x' => x.to_s(2).length, 
#		'zi' => Math.log(zi), 
#		'zj' => Math.log(zj)
		'i' => i,
		'm' => m
		}
		l1 << a
		n *= 3 if (x.odd?)
	}
	
	$fn = 'out2.txt'
	
	runavg(l1, 'm', 20)
	
	t = remove(fmt(x), ['ns']).to_s
	t.sub!('"n"', '\\n"n"')
	t.gsub!('"', '\"')
	t.sub!('{', '')
	t.sub!('}', '')
	
	l1.each { |a| out(a, axes2(['ij', 'ma']).merge({'m' => nil}), t, '') }
	
	exit
	
end

ks = ['w', 'da-']
ks = ['cm', 'da-']

x2 = axes2(['da'])
x2['n'] = nil

x = opt(ks, 5e3.to_i, x2)
$stderr.puts("\n" + fmt(x).inspect)
f = File.open('out.dat', 'w')
f.puts(x.inspect)
f.close

$f1.close; $f1 = nil

review(ks) if (File.exist?('out.txt'))