hybrid26b.rb

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

end

def count(ns, l2 = [])
	
	n = n1 = ns.to_i(2)
	l = [n1]
	
	while (n != 1)
		n = f2(n)
		
		l << n
		
	end

        cg = l.index { |x| x < l[0] }
        cg = l.size - 1 if (cg.nil?)
        cm = (0..cg).max_by { |x| l[x] }

        cm1 = (0...l.size).max_by { |x| l[x] }
        cg1 = l.rindex { |x| x >= l[0] }

        c = l.size
	
	return {'ns' => ns,
		'cm' => cm,
		'cg' => cg,
		'cm1' => cm1,
		'cg1' => cg1,
		'c' => l.size,
		'l' => l
		}
end

def initd(w, m)

	d = m.to_f / w
	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 initb(w, m)
	r = m.to_f / w
	return '1' + (1...w).map { rand < r ? '0' : '1' }.join
	
end

def initw(w, m)
	s = initd(w, w / 2)
	
	i = rand(w - m) + 1
	m = [w - i, m].max
	s[i, m] = rand(2).to_s * m
	return s
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 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 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 out(fn, a, d, a2 = {}, t = nil)

	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 top 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
	$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 add(bs, km, k, h, ns, l1, wt, t, d)
	j = ns.length
	h[j] = [] if (!h.member?(j))

	x = adj(count(ns), wt, km)
	
	a, b = [h[j][0], h[j][-1]]
	
	return 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)

	out('out.txt', x1 = remove(x, ['ns', 'l']).merge({'n' => x['ns'].to_i(2)}), d, {k => 'axis x1y2', 'n' => nil})
	l1 << x1
	
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 = ['initd0', 'initb0', 'initw0', 'mut1', 'mix2', 'cut2']
#	ops += ['ext1', 'short1']

	bs = 50
	bc = 50
	
	t = 0
	d = n / 2000
	d = 1 if (d == 0)
	
	wt = {}
	n.times \
	{
		if (t % 100 == 0) then
			dist(km, h, wt)
			h.values.flatten.each { |x| adj(x, wt, km) }
		end

		opc = ops[rand(ops.size)]

		c = 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 (c)
			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...c).map { ks[rand(ks.size)] }
				l = arg.map { |x| top(h[x])['ns'] }
				ns = send(op, *l)
				ns[0, 1] = '1'
				
		end
		
		
		add(bs, km, k, h, ns, l1, wt, t, d)

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

end

def fmt1(l, f)

	w = l.max_by { |x| x.length }.length
	
	f.puts("set colors classic; set key top left opaque;\\")
	f.puts("plot \\")
	f.puts("[0:#{w}][0:#{l.size - 1}] '-' matrix using 1:2:(1-$3) with image title ''")
	l.each_with_index \
	{
		|z, i|
		
		c = w - z.length
		z[z.length...w] = '0' * c
		
		f.puts(z.split('').join(' '))
	}
	f.puts("eof")
	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.reverse }, f)
	f.close

end

def sample(l, c)

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

end

def seq(n)

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

def lsb(ns)
	r = ns.split('').rindex("0")
	r = 0 if (r.nil?)
	c1 = ns.length - r
	return c1
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 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 top left; set title '#{t}'; ")
#	f.puts("set ytics nomirror; set y2tics;")
	f.puts("plot \\")
	k.each \
	{ 
		|x| 
		next if (a.member?(x) && a[x].nil?)
		f.puts("'$dat' using (column('#{x}')) with line #{a.fetch(x, '')} lw 2,\\") 
	}
	f.puts
#	f.puts("reset; pause -1;")

end

def values(x)
		ns = x['n'].to_s(2)

		c1 = lsb(ns)
		l1 = seq(x['n'])
		mx1 = nil
		mx2 = nil
		l1[c1..-1].each \
		{ 
			|x1| 
			l2 = lenx(x1.to_s(2), /0+/)
			mx1 = [mx1, l2[-1]].compact.max
			mx2 = [mx2, l2].flatten.compact.max
		}
		return {'cg' => x['cg'], 
			'mx1' => mx1, 
			'mx2' => mx2, 
			'c' => l1.size, 
			'c1' => c1}
end

def review()
	l = File.open('out.txt').readlines
	nc = l[0].split.index('n')
	ncg = l[0].split.index('cg')

	l = l[1..-1].map \
	{
		|x|
		l1 = x.split
		{'n' => l1[nc].to_i, 'cg' => l1[ncg].to_i}
	}.sort_by { |x| x['cg'] }

	$stderr.puts({'c' => l.size}.inspect)
	l = sample(l, 200)

	l2 = []
	l.each_with_index \
	{ 
		|x, j| 

		l2 << values(x)
		$stderr.puts(j)
	}
	outa(f = File.open('gnuplot1.cmd', 'w'), l2, {'c' => 'axes x1y2', 'cg' => 'axes x1y2'})
	f.close
exit

end

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


k = 'z'
v = {'cg' => 1}
opt(v, 500, k, l1 = [], 1e4.to_i)