hybrid15b.rb

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

end

def av(l)
	return l.inject(0.0) { |t, x| t + x } / l.size
end

def corr(l, y1, yp)
	
	xav = av(l.map { |x| x[y1] })
	yav = av(l.map { |x| x[yp] })

	tx = ty = txy = e = 0.0
	m = nil
	l.each \
	{
		|z|
		
		x = z[y1]
		y = z[yp]
		
		txy += (x - xav) * (y - yav)
		tx += (x - xav) ** 2
		ty += (y - yav) ** 2
		e1 = (x - y).abs
		e += e1
		m = [m, e1].compact.max
	}
	r = txy / (Math.sqrt(tx) * Math.sqrt(ty))
	e /= l.size
	return {'r' => r, 'e_a' => e, 'e_m' => m}
	
end

def slopecorr(l, l2)
	return 1.0 if (l.nil? || l.empty?)
	
	l = l.map { |x| Math.log(x) }
	
	a, b = [l[0], l[-1]]
	
	l2.replace((0...l.size).map \
	{
		|x|
		
		y1 = a + x.to_f / (l.size - 1) * (b - a)
		y2 = l[x]
		{'y1' => y1, 'y2' => y2}
	})
	
	return corr(l2, 'y1', 'y2')['r']
end

def adj(x)
	z = 0
	$k.each { |k| z += (x[k] - $w["#{k}_a"]) / $w["#{k}_sd"] * $d[k] }
	x['z'] = z
	raise if (z.nan?)
	return x
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 < n1 }
	cg = 0 if (cg.nil?)
	cm = (0..cg).max_by { |x| l[x] }
	cg1 = l.rindex { |x| x >= n1 }
	cm1 = (0...l.size).max_by { |x| l[x] }

	nl = ns.length
	sc = slopecorr(l[nl..-1], l2)
	
	return adj({'ns' => ns,
		'nw' => ns.length,
		'cm' => cm,
		'cg' => cg, 
		'cm1' => cm, 
		'cg1' => cg,
		'c' => l.size,
		'nl' => nl,
		'sc' => sc
		})
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(m) + 1
	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 add(bs, h, ns, fn)
	j = ns.length
	h[j] = [] if (!h.member?(j))

	x = count(ns)
	
	a, b = [h[j][0], h[j][-1]]
	h[j] << x
	
	h[j].sort_by! { |x| -x['z'] }
	h[j][bs..-1] = [] if  (h[j].size > bs)

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 { |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(h)

	l = h.values.flatten
	$w = {}
	
	$k.each \
	{
		|k|
		
		a, sd = stat(l.map { |x| x[k] })
		
		$w.merge!({"#{k}_a" => a, "#{k}_sd" => sd})
	}
	
end

def opt(w1, fn)
	h = {}

	ops = ['initd0', 'initb0', 'initw0', 'mut1', 'mix2', 'cut2']
	ops += ['ext1', 'short1']

	bs = 50
	bc = 50
	
	msg = {}
	
	t = 0
	loop \
	{
		dist(h) if (t % 100 == 0)
		t += 1
		
		opc = ops[rand(ops.size)]

		c = opc[-1..-1].to_i
		op = opc[0..-2]
		
		ks = h.keys.sort_by { |x| -h[x][0]['z'] }
		ks = ks[0...[ks.size, ks.size / 4].max]
		msg['hmn'], msg['hmx'], msg['hc'] = [ks.min, ks.max, h.size]
		
		msg['z'] = h.fetch(ks[0], [])[0]
		
		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, h, ns, fn)
		
		p(msg.merge($w))
	}


end

$k = ['sc', 'nw']
$d = {'nw' => 1, 'sc' => -1}

opt(50, fn = 'mixdb.txt')