hybrid38.rb

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

end

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

def initgap()
	$x = []
	$g = {}
	$gd = {}
end

def addgap(i)
	
	a, b = $x[i, 2]
	d = b - a
	$g[d] = $g.fetch(d, []) + [[a, b]]
	$mx = [$mx, d].compact.max
	
end

def rmgap(a, b)
	d = b - a
	$g[d] -= [[a, b]]
	if ($g[d].empty?) then
		$g.delete(d)
		$mx = $g.keys.max if (d == $mx)
	end
end

def recalc(r)
	r.to_a.select { |x| x >= 0 }.each \
	{
		|x|
		$gd[$x[x]] = [x > 0 ? $x[x - 1] : nil, $x[x + 1]].compact.map { |x1| ($x[x] - x1).abs }.max
	}
end
	
def gap(z)

	i = (0...$x.size).bsearch { |x| $x[x] >= z }
	if (i.nil?) then
		$x << z
		return if ($x.size == 1)
		addgap($x.size - 2)
		recalc(($x.size - 2)..($x.size - 1))
		return
	end
	
	return if ($x[i] == z)

	rmgap(*$x[i - 1, 2]) if (i > 0)
	
	$x[i, 0] = z
	addgap(i)
	addgap(i - 1) if (i > 0)
	recalc((i - 1)..(i + 1))
end

def gapmx(z)
	gap(z)
	x = $gd[z]
	return x.nil? ? 0 : x
end

def runsd(a = nil, s1 = nil)

	return {'x' => 0, 'x2' => 0, 'l' => [], 'c' => 20} if (a.nil?) 
	
	a['l'] << s1
	a['x'] += s1
	a['x2'] += (s1 ** 2)
	
	if (a['l'].size == a['c'] + 1) then
		x1 = a['l'].shift
		a['x'] -= x1
		a['x2'] -= (x1 ** 2)
	end
	
	a1 = a['x'] / a['l'].size
	z = a['x2'] / a['l'].size - a1 ** 2
	z = 0 if (z < 0)
	sd = Math.sqrt(z)
	z1 = s1 == 0 ? 1 : sd / s1
	return z1, a['l'].size == a['c'] && z1 < 0.005
	
end

def max01(nw, l = [])

	t = 1
	tmx = 0
	c = 20

	sd = runsd()
	
	while (t < 100)
		ns = dense(nw, 0.5)
		mx = len01(ns).flatten.max
		
		tmx += mx
		
		xma = tmx.to_f / t
		l << {'t' => t, 'xma' => xma}
		
		z1, e = runsd(sd, xma)
		
		l[-1]['z1'] = z1
		break if (e)
		t += 1
	end
	
	return {'xma' => l[-1]['xma'], 't2' => t}
	
	
end

def count(ns)
	
	mx01 = len01(ns).flatten.max
	return if (mx01 >= $mx['xma'])
	
	l = seq(n = ns.to_i(2))
	
        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
	
	mx = l.max.to_s(2).length
	
	m = mx.to_f / (c - cg)
	nw = ns.length
	m2 = l[nw].to_s(2).length.to_f / (c - nw)
	
#	cg1 = l.rindex { |x| x >= l[0] }
#	cm1 = (0...l.size).max_by { |x| l[x] }
	
	return {'ns' => ns,
		'c' => c,
		'cg' => cg,
		'cm' => cm,
		'mx01' => mx01,
		'mx' => mx,
		'cmnw' => cm - nw,
		'm' => m,
		'm2' => m2,
#		'cm1' => cm1,
#		'cg1' => cg1,
#		'l' => l,
		}
end

def out(fn, a, d, a2 = {}, t = nil)

	if ($f1.nil?) then
		$f1 = File.open(fn, 'w')
		$f1.puts(a.keys.join("\t")) 
		$c = 0
	end
	$f1.puts(a.values.join("\t"))
	$f1.flush
	$c += 1
	return if ($c % 1000 != 0)
	
	d = ($c / 2000).to_i
	d = 1 if (d == 0)
	
	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 left box opaque; #{st}; plot \\")
	(a.keys - ['t']).each \
	{
		|x|
		next if (a2.member?(x) && a2[x].nil?)
		f2.puts("'#{fn}' using (column('t')):(column('#{x}')) every #{d} with line title '#{x}' #{a2[x]}, \\")
	}
	f2.puts
	f2.close
	
end

def rank(x)
	return -x['z']
end

def adj(x, wt, km)
	z = 0
	
	km.keys.each { |k| z += (x[k] - wt["#{k}_a"]) / wt["#{k}_sd"] * km[k] }
	
	x['z'] = z
	raise [x, wt].to_s if (!z.finite?)
	return x
end

def add(bs, km, k, h, ns, l1, wt, t, d, r)

	return 0 if ((a1 = count(ns)).nil?)
	a1['r'] = r
	
	j = ns.length
	h[j] = [] if (!h.member?(j))
	
	x = adj(a1, wt, km)
	
	a, b = [h[j][0], h[j][-1]]
	
	return 0 if (h[j].map { |x| x['ns'] }.member?(x['ns']))

	x['t'] = t
	h[j] << x
	
	h[j].sort_by! { |x| rank(x) }
	h[j][bs..-1] = [] if (h[j].size > bs)

	x1 = x.dup
	x1.delete('l')
	out('out.txt', x1, d, x1y2().merge({'ns' => nil}))
	l1 << x.dup if (!l1.nil?)
	return 1
	
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 initd(w, m)

	return(dense(w, m.to_f / w))
end

def initb(w, m)
	r = m.to_f / w
	return '1' + (1...w).map { rand < r ? '0' : '1' }.join
	
end

def initw(w, m)
	s = dense(w, 0.5)
	
	i = rand(w - m) + 1
	
	s[i, m] = rand(2).to_s * m
	return s
end

def initr(w, m)
	
	s = '1'
	b = 0
	while (s.length < w)
		
		z = w - s.length
		
		s += b.to_s * [rand(m - 1) + 1, z].min
		b ^= 1
		
	end
	return s
end

def init(w, m)
	ns1 = dense(w, 0.5)
	ns2 = initr(w, m)

	ns1, ns2 = [ns2, ns1] if (rand(2) == 0)
	
	i = rand(w - m) + 1
	ns1[i, m] = ns2[i, m]
	
	return ns1
end

def mut(ns)

	ns = ns.dup
	i = rand(ns.length - 1) + 1
	ns[i, 1] = (ns[i, 1].to_i ^ 1).to_s
	return ns
	
end

def mutb(ns)

	ns = ns.dup
	
	c = rand(ns.length - 1) + 1
	
	a = (0...ns.length).to_a
	c.times \
	{
		|x|
		i = a[x]
		ns[i, 1] = (ns[i, 1].to_i ^ 1).to_s
	}
	return ns
	
end

def inner(ns1, ns2)
	a, b = [ns1, ns2].sort_by { |x| x.length }
	d = b.length - a.length
	i = rand(d + 1)
	
	c = b.dup
	c[i, a.length] = a
	
	ns1.replace(b)
	ns2.replace(c)
end

def mix(ns1, ns2)

	ns1 = ns1.dup
	ns2 = ns2.dup
	
	inner(ns1, ns2)
	return (0...ns1.length).map { |x| [ns1, ns2][rand(2)][x, 1] }.join
	
end

def cut(ns1, ns2)
	ns1 = ns1.dup
	ns2 = ns2.dup
	
	inner(ns1, ns2)
	i = rand(ns1.length)
	return ns1[0...i] + ns2[i..-1]
end

def ext(ns)

	ns = ns.dup
	(rand(3) + 1).times { ns[rand(ns.length) + 1, 0] = rand(2).to_s }
	return ns
end

def short(ns)
	return ns if (ns.length == 1)
	ns = ns.dup
	(rand([ns.length - 1, 3].min) + 1).times { ns[rand(ns.length - 1) + 1, 1] = '' }
	return ns
	
end

def top(h1)
	return h1[rand([h1.size / 4, h1.size].max)]
end

def stat(l)
	return 0, 1.0 if (l.empty?)
	t = l.inject { |a, x| a + x }
	t2 = l.inject(0) { |a, x| a + x ** 2 }
	
        c = l.size
        a = t.to_f / c
        z = t2.to_f / c - a ** 2
        sd = Math.sqrt(z < 0 ? 0 : z)
        raise if (sd.nan?)
        return a, sd
end

def dist(km, h, wt)

	l = h.values.flatten
	
	km.keys.each \
	{
		|k|
		a, sd = stat(l.map { |x| x[k] })
		
		sd = 1.0 if (sd == 0)
		wt.merge!({"#{k}_a" => a, "#{k}_sd" => sd})
	}
	
end

def nonnil(x, y)
	return x.nil? ? y : x
end

def opt(km, w1, k, l1, n)
	h = {}

	ops = ['init0', 'initd0', 'initb0', 'initw0', 'initr0', 'mut1', 'mutb1', 'mix2', 'cut2']
#	ops += ['ext1', 'short1']

	bs = 500
	bc = 50
	
	t = c1 = 0
	
	wt = {}
	while (c1 < n)
		
		if (c1 % 100 == 0) then
			dist(km, h, wt)
			h.values.flatten.each { |x| adj(x, wt, km) }
		end

		opc = ops[r = rand(ops.size)]

		p = opc[-1..-1].to_i
		op = opc[0..-2]

		ks = h.keys.sort_by { |x| rank(h[x][0]) }
		ks = ks[0...[ks.size, ks.size / 4].max]

		case (p)
			when 0
				w = ks.empty? ? w1 : ks[rand(ks.size)]
				ns = send(op, w, rand(w))
				
			when 1, 2
			
				redo if (h.empty?)
				
				h.delete(ks.pop) if (ks.size > bc)
				
				arg = (0...p).map { ks[rand(ks.size)] }
				l = arg.map { |x| top(h[x])['ns'] }
				ns = send(op, *l)
				ns[0, 1] = '1'
				
		end
		
#		ns[-1, 1] = '1'

		d = (t.to_f / (c1 + 1) * n / 2000).to_i
		
		c1 += add(bs, km, k, h, ns, l1, wt, t, d, r)

		if (t % 100 == 0) then
#			msg = Hash[[['t', 'hmn', 'hmx', 'hc', 'h_0', k0], [t, ks.min, ks.max, h.size, h0, kmx]].transpose]
			
			msg = {'t' => t,
				'c1' => c1,
				'r' => r,
				'hmn' => ks.min,
				'hmx' => ks.max,
				'hc' => h.size}
			h0 = nonnil(h.fetch(ks[0], [])[0], {}).dup
			k0 = "#{k}_0"
			kmx = nonnil(h.values.flatten.max_by { |x| x[k] }, {}).dup
			msg2 = { 'h0' => h0,
				k0 => kmx}
			['h0', k0].each { |x| fmt(msg2[x]) }
			$stderr.puts(msg)
			$stderr.puts("\t" + msg2.inspect) if (t % 1000 == 0)
		end
		
		t += 1
	end
	
	return h

end

def outa(f, l, a = {}, t = '')
	f.puts('$dat << eof')
	k = l[0].keys
	
	f.puts(k.join("\t"))
	l.each { |x| f.puts(x.values.join("\t")) }

	f.puts('eof')
	f.puts("set colors classic; set key bottom left opaque; set title '#{t}'; ")
	f.puts("set ytics nomirror; set y2tics;")
	f.puts("plot \\")
	k, ct = [k - ['t'], "(column('t')):"] if (k.member?('t'))
	k.each \
	{ 
		|x| 
		next if (a.member?(x) && a[x].nil?)
		opt = a.fetch(x, '')
		opt += ' lw 2 ' if (!opt.include?('lw'))
		opt += ' with line ' if (!opt.include?('with') && !opt.include?('pt'))
		f.puts("'$dat' using #{ct}(column('#{x}')) #{opt} title '#{x}',\\") 
	}
	f.puts
#	f.puts("reset; pause -1;")

end

def outafn(l, a = {}, fn = nil, t = '')
	outa(f = File.open(fn.nil? ? 'gnuplot.cmd' : fn, 'w'), l, a, t)
	f.close
end

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

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 convert(l)
	
	x2 = nil
	l2 = []
	l.each_with_index \
	{ 
		|x, j| 
		next if (x == x2)
		l2 << [j, x]
		x2 = x
	}
	return l2
end

def convert1(l, x)
	l << convert(len(x, /0+/).sort)
end

def outd(f, l, n = '')
	f.puts("$dat#{n} << eof")
	k = l[0].keys
	
	f.puts(k.join("\t"))
	l.each { |x| f.puts(x.values.join("\t")) }

	f.puts('eof')
	return k
end

def triplets(l1, f, n = '')
	l2 = []
	l1.each_with_index \
	{
		|l, t|
		
		l.each { |x, y| l2 << {'x' => x, 'y' => y, 't' => t}}
		l2 << {}
	}
	$stderr.puts(l2.size)
	outd(f, l2, n)
end

def hist(l)
	l2 = []
	l.reverse.each_with_index \
	{ 
		|ns, j| 
		convert1(l2, ns)
	}
	return l2
end

def hist1(l)
	l2 = hist(l)
	fn, t = plotfn("hist")
	f = File.open(fn, 'w')
	triplets(l2.reverse, f, 1)
	f.puts("reset; plot $dat1 using (column('x')):(column('y')):(column('t')) with line linecolor palette lw 2")
	f.close
end

def plotfn(t)
	$n = 1 if ($n.nil?)
	fn = "gnuplot#{$n}.cmd"
	$stderr.puts("#{fn} <- #{t}")
	
	$n += 1
	return fn, t
end

def rwalk(l, t)
	
	l2 = []
	l.each_with_index \
	{ 
		|ns, j| 
		c = 0
		l1 = []
		ns.reverse.split('').each_with_index { |x1, i| l1 << [i, (c += [-1, 1][x1.to_i])] }
		l2 << l1
	}
	
	fn, = plotfn(t = "rwalk #{t}")
	f = File.open(fn, 'w')
	triplets(l2, f)
	f.puts("reset; set title '#{t}'; plot $dat using (column('x')):(column('y')):(column('t')) with line linecolor palette lw 2")
	f.close
end

def seqs(l, t)
	
	l2 = []
	l.each \
	{
		|n|
		l = seq(n)
		l2 << (0...l.size).map { |x| [x, Math.log(l[x]) / Math.log(2.0)] }
	}
	
	fn, = plotfn(t = "seqs #{t}")
	f = File.open(fn, 'w')
	triplets(l2, f)
	f.puts("reset; set title '#{t}'; plot $dat using (column('x')):(column('y')):(column('t')) with line linecolor palette lw 2")
	f.close
end

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

def x1y2()
	return $a2 if (!$a2.nil?)
#	$a2 = axes2(['mx01', 'z', 'cg', 'cm', 'cg1', 'mx', 'cm1', 'm', 'm2']) if ($a2.nil?)
	$a2 = axes2(['c']) if ($a2.nil?)
	return $a2
end

def t1(l)
	l.each { |x| x.delete('t') }
end

def fmt(a)
	['ns', 'l'].each { |x| a.delete(x) }
	return a
end

def graphs2(l1, t)
	l2 = l1.map { |x| x['ns'] }
	
	grid(l2, *plotfn("grid_{de} #{t}"))
	rwalk(l2, t)
	seqs(l2.map { |x| x.to_i(2) }, t)
end

def graphs(k, h, l1)
	
	
	h.shuffle!
	h.each { |x| x.delete('l') }
	
	h.sort_by! { |x| x[k] }
	
	t1(h)
	outafn(h, x1y2().merge({'ns' => nil}), *plotfn("h(#{h.size}) by #{k}"))

	graphs2(sample(h, 40), "#{k} sample 40")
	graphs2(h[-40..-1], "#{k} top 40")
	

end


def g(x)
	gap(x)
	p({'x' => x, '$x' => $x, '$g' => $g, '$gd' => $gd})
end

def testgap()
	
	[5, 6, 1, 2, 9, 1, 3].each { |x| g(x) }
	exit
end

def ina(fn = 'out.txt')
        l = (f = File.open(fn)).readlines
	f.close
        k = l.shift.split
        l2 = l.map { |x| Hash[[k, x.split.map { |x| Kernel.eval(x) }].transpose] }
	l2.each { |x| x['ns'] = x['ns'].to_s }
	return l2
end

w = 200
$mx = max01(w, l = [])
$stderr.puts($mx.inspect)
#outafn(l, {'z1' => 'axes x1y2'}); exit



#c = 1e3
#c = 5e3
c = 2e4

k = 'cmnw'
a = {
	k => 1,
	'cm' => 1,
	'c' => 1,
	'mx' => 1,
	'cmnw' => 1,
#	'cm1' => 1,
#	'cg1' => 1
	}
h = opt(a, w, k, l1 = [], c.to_i)


graphs(k, h.values[0], l1)