gene12.rb

#!/usr/bin/ruby1.8

def f1(n)
        n = (n * 3 + 1) / 2 while (n % 2 == 1)
        n /= 2 while (n % 2 == 0)
        return n
end

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

        return a, sd
end

def sum(l)

	t = 0
	l.each { |x| t += x }
	return t
end

def coef(x, y)

        x1 = x2 = y1 = y2 = xy = 0.0

        n = x.size
        n.times \
        {
                |i|

                x1 += x[i]
                y1 += y[i]
                xy += x[i] * y[i]
                x2 += x[i] ** 2
                y2 += y[i] ** 2
        }

        d = n * x2 - x1 ** 2
        a0 = (y1 * x2 - x1 * xy) / d
        a1 = (n * xy - x1 * y1) / d

	a0 = 1 if (a0.nan?)
	a1 = 1 if (a1.nan?)
        return a0, a1
end

def err(x, y)

	a0, a1 = coef(x, y)

	t = 0
	x.size.times \
	{
		|i|

		y2 = a0 + a1 * x[i]
		d = (y[i] - y2)
		t += d ** 2
	}

	return a0, a1, t / x.size
end

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

def d2(s)
	return [0, 0, 0] if (s.length == 0)
	d(s)[0..2]
end

def metrics(n, j)
	s = n.to_s(2)

        d1, d2, d3, w, c1, c0 = d(s)

        m = s.length / 2

        da = d2(s[0...m])
        db = d2(s[m..-1])

        m1 = w ** 2
        m2 = w ** 0.5

        asd1 = stat(s.split(/0+/).map { |x| x.length })
        asd0 = stat(s.split(/1+/).map { |x| x.length })
# 0 1 2 3 4 5 6 7
        l2 = [w, m1, m2, d1, d2, d3, c0, c1]
# (8 9) (10 11) (12 13 14) (15 16 17)
	l2.concat(asd1 + asd0 + da + db)
# 18 19 20 21 22 23 24
	l2.push(j, 1.0 / j, j ** 2, j ** 3, j ** 0.5, 1.0, j.to_s(2).length)

	return l2
end

def seq(z)

	n = z['n']
	l = [n]
	while (n != 1)
		n = f1(n)
		l << n
	end
	return l

end

def smoothed2(w, z)
	l = seq(z)
	l1 = []
	l2 = []
	l.size.times \
	{
		|i|
		la = metrics(l[i], i + 1)
		lb = []
		
		t = 0
		la.size.times \
		{ 
			|x| 
			z = la[x] * w[x] 
			lb[x] = z
			t += z
		}
		l1 << (la + [l[i]])
		l2 << (lb + [t])
	}
	return l1, l2
end

def mono(l, z)

	return if (l.empty?)

	c = 0
        m = l[0]
	mx = nil
	j = 0
        l2 = []
        (1...l.size).each \
        { 
                |i| 
                c += 1 if (l[i] < l[i - 1])
                if (l[i] < m) then
                        l2 << i - j
                        m, j = [l[i], i] 
                end
                mx = [mx, i - j].compact.max
        }
	return if (c == 0 || mx.nil? || l2.empty?)
	
        r = c.to_f / l.size
	a, sd = stat(l2)
	
	return {'r' => r, 'mx' => mx, 'c' => l2.size, 
		'd' => l2.size.to_f / l.size, 'a' => a, 'sd' => sd, 
		'mn' => l.min.abs, 'cn' => l.select { |x| x < 0 }.size.to_f / l.size
		}.merge(z)
end

def weight(n, l, j)

	l2 = metrics(n, j)
	
        t = 0.0
        l2.each_with_index { |x, i| t += x * l[i] }
        raise(l2.join(' ')) if (t.nan?) 

        return t

end

def weighted(l, w)

	j = 0
	return l.map { |n| x = weight(n, w, j += 1) }
end

def monoweight(l, w, z)

	return mono(weighted(l, w), z)
end

def smoothed(w, z)

	l = seq(z)

	return monoweight(l, w, z)
end

def rand1()

	return rand() * [-1, 1][rand(2)]
end

def fit(i)

	l = $a[i]['l']
	a = {}

	$d0.keys.each \
	{
		|kn|
		
		k, n = kn.split('_')
		n = n.to_i
		l2 = l.select { |z| z['i'] / 100 == n }

		
		x = l2.map { |z| z['n'].to_s(2).length }
		y = l2.map { |z| z[k] }
		
		avg, sd = stat(y)
		
		a["#{k}_a_#{n}"] = avg
		a["#{k}_sd_#{n}"] = sd
		
		a0, a1, d = err(x, y)
		
		a["#{k}_r_#{n}"] = a1
		a["#{k}_d_#{n}"] = d
	}
	
	a['zc'] = l.size
	a['zb'] = sum(l.map { |z| z['n'].to_s(2).length })

	$a[i]['f'] = a
end

def cmp(i, j)
	r1 = $a[i]['f']
	r2 = $a[j]['f']

	c = [0] * 3
	$d.keys.each \
	{
		|k|

		raise [k, i, j, r1, r2].inspect if (r1[k].nil? || r2[k].nil?)
		d = (r2[k] <=> r1[k]) * $d[k]
		c[d] += 1
	}
	$cm[[i, j]] = c

end

def log(msg)
	
	o = File.open('out2.txt', 'a')
	o.puts(msg)
	o.close
end

def fmth(h)
		h = h.dup
		h['a'] = h['a'].size
		return h

end

def fmt1(x)
	return x if (x.is_a?(Integer))
	return sprintf("% f", x)
end

def fmta(f, ks, c = 3)
	
	j = 0
	ks.each \
	{ 
		|x| 
		printf("#{x}\t#{fmt1(f[x])}\t")
		puts if ((j += 1) % c == 0)
	}
	puts

end

def fmtf(f)
	fmta(f, $d.keys)
end

def fmtw(w)

	a = {}
	w.each_with_index { |x, i| a['w' + i.to_s] = x }
	fmta(a, a.keys, 4)

end

def new(w, t, l, h)

	$c0 += 1
	
	c1 = l.size
	l = l.compact
	
	ai = {}
	ah = [0] * 7
	l.each \
	{ 
		|x| 
		i = x['i']
		next if ($db2[i]['m'].nil?)
		ai[i] = x 
		ah[i / 100] += 1
	}

	if (!ah.select { |x| x < 3 }.empty?) then
		$c1 += 1
		return
	end

	a = {}
	
	a['l'] = ai.values

	a['w'] = w
	a['j'] = (n = $a.size)
	a['h'] = h
	a['t'] = Time.now.to_s
	
	$a << a
	
	fit(n)
	a['f']['zi'] = l.size
	a['f']['zc1'] = c1
	(0...n).each { |i| cmp(i, n) if (!$a[i].nil?) }

	$l << n
	l2 = rank()
	i = l2.map { |x| x[1] }.index(l2.size - 1)
	$l = l2.map { |x| $l[x[1]] }

	r = sprintf("%.2f", i.to_f / $l.size)

	log(["$a#= #{$a.size}", "r= #{r}", "$l#= #{$l.size}", "t= #{t}", 
		"i= #{i}", "$c= #{$c}", "$n= #{$n}", "$c0= #{$c0}", 
		"$c1= #{$c1}", "h= #{fmth(a['h']).inspect}", ].join("\t"))
	
 	if (i == 0) then
		a = $a[$l[0]]
		o = File.open($fn, 'a')
		o.puts(a.inspect)
		o.close
		
		f = a['f']
		l = a['l']
		p(['c', $c, 'a#', $a.size, a['t']])
		fmtf(f)
		fmtw(w)
		
		l1 = a['l'].map { |x| [x['k'], x['n'].to_s(2).length, x['i']] }
		l1 = l1.transpose
		
		p(['h', fmth(a['h'])])
		
		$c += 1
		puts
	end

	return i < t
end

def reapply(w, l)
	return l.map \
	{
		|x|
		smoothed(w, {'n' => x['n'], 'k' => x['k'], 'i' => x['i']})
	}
end

def sample(i)
	
	x = Kernel.eval($db[i])
	
	return {'n' => x['n'], 'k' => x['k'], 'i' => i}
end

def unique(x)
	
	l = (0..24).to_a
	
	return (1..3).map { sample(x * 100 + 25 + l.delete_at(rand(l.size))) }
end

def new2(w, c, l, h)

	if (l.empty?) then
		l = (0..6).map { |x| unique(x) }.flatten
	else
		l += (0..6).map { |x| sample(x * 100 + rand(50)) }
	end
	
	h = trace(nil) if (h.nil?)
	
	x1 = new(w, c, reapply(w, l), h)
	
	h2 = h.dup
	h2['-'] += 1
	w2 = w.map { |x| -x }

	x2 = new(w2, c, reapply(w2, l), h2)
	
	return x1 || x2
end

def add(t, w)

	return new2(w, t, [], nil)
end

def rank()

	l = []
	$l.each_with_index \
	{
		|j, k|
		t = [0] * 3
		$l.each \
		{
			|i|
			next if (i == j)
			c = $cm[[i, j].sort]
			c = c.values_at(0, -1, 1) if (i > j)
			3.times { |x| t[x] += c[x] }
		}
		l << [t[1] - t[-1], k, t]
	}
	return l.sort_by { |x| x[0] }.reverse
end

def load()

	l = File.open($fn).readlines
	l.each_with_index { |x, i| $l[i] = Kernel.eval(x) }
end

def fmt(x)
	return nil if (x.nil?)
	return sprintf("%.3f", x).to_f
end

def out(ln, fn, msg, r)
	
	c = r.is_a?(Range) ? r.max - r.min + 1 : r.size
	
	$stderr.puts((["fn= #{fn}", "$l#= #{$l.size}", "ln#= #{c}"] + [msg]).inspect)
	f = File.open(fn, 'w')
	r.each_with_index \
	{
		|x, i|
		z = ln.call(x)
		next if (z.nil?)
		z.keys.each_with_index { |k, i| f.puts("#\t#{i + 1}\t#{k}") } if (i == 0)
		f.puts(z.values.join("\t"))
		f.puts if ((i + 1) % 100 == 0)
		f.flush
	}
	
	f.close
	
end

def extract1()

	n = ARGV[1].to_i
	i = ARGV[2].to_i
	j = ARGV[3].nil? ? i : ARGV[3].to_i
	
	z = $l[n]
	w = z['w']
	w.each_with_index { |x, t| puts("w#{t}\t#{t + 1}\t#{x}") }
	
	l1 = []
	l2 = []
	(i..j).each \
	{
		|x|
		z = $db2[x]
		la, lb = smoothed2(w, {'n' => z['n'], 'k' => z['k'], 'i' => z['i']})
		l1 += la + [[]]
		l2 += lb + [[]]
	}

	ln = lambda \
	{
		|l1|
		lambda \
		{
			|x|
			a = {}
			return if (l1[x].nil?)
			l1[x].each_with_index \
			{
				|z, i|
				a[i] = z
			}
			return a
		}
	}
	
	out(ln.call(l1), "out_#{n}_#{i}.txt", nil, 0..l1.size)
	out(ln.call(l2), "out_#{n}_#{i}b.txt", nil, 0..l2.size)
	
	
end

def extract2()
	
	$l.each_with_index { |x, i| p(i); fmtf(x['f']); fmtw(x['w']); puts }
	
end

def extract3()
	
	$l.each_with_index \
	{ 
		|x, i|
		p([i, x['w'].map { |z| z != 0 ? 'x' : '.' }.join])
	}
	
end

def extract(n)
	
	z = $l[n]
	
	fmtf(z['f'])
	
	w = z['w']
	fmtw(w)
	
	ln = lambda \
	{
		|i|

		return if ($db2[i]['m'].nil?)
		
		a1 = $db2[i]
		a2 = smoothed(w, {'n' => a1['n'], 'k' => a1['k'], 'i' => a1['i']})
		
		return if (a1.nil? || a2.nil?)
		
		a = {}
		a['i'] = i
		a['c'] = i / 100
		a['n2'] = a1['n2']
		
		$d1.keys.each \
		{
			|k|
			
			x1 = a1['m'][k]
			x1 = 0 if (x1.nil?)
			x2 = a2[k]
			a[k + '1'] = x1
			a[k + '2'] = x2
		}
		
		return a
	}

	out(ln, fn = "out_#{n}b.txt", "n= #{n}", z['l'].map{ |x| x['i']})
	out(ln, fn = "out_#{n}.txt", "n= #{n}", 0...$db2.size)

end

def combine(a, b)

	c = {}
	(a.keys - ['a']).each \
	{
		|k|
		c[k] = a[k] + b[k]
	}
	c['a'] = a['a'] | b['a']
	return c
end

def trace(l)
	return {'1a' => 0, '1b' => 0, 'xa' => 0, 'xb' => 0, 'xc' => 0, '-' => 0, 'a' => [$a.size]} if (l.nil?)
	i, j, k = l
	if (k.nil?) then
		l2 = $a[i]['h'].dup
		l2['1' + j] += 1
		l2['a'] |= [$a.size]
		return l2
	end
	l1 = $a[i]['h']
	l2 = $a[j]['h']

	c = combine(l1, l2)	
	c['x' + k] += 1
	c['a'] |= [$a.size]
	return c
end

def clean(f)
	
	c1 = 250
	c2 = 500
	
	$l.pop if (f)
	$l[c1..-1] = [] if ($l.size >= c1)	
	
	return if (($n += 1) % c2 != 0)
	
	a = {}
	$l.each { |x| a[x] = nil }
	
	$a.size.times { |i| $a[i] = nil if (!a.member?(i)) }
	
	k = $cm.keys
	
	k.each { |x, y| $cm.delete([x, y]) if (!a.member?(x) || !a.member?(y)) }
end

def mkdb()
	
	fdb = "dbb.txt"
	
	return if (File.exists?(fdb))
	$stderr.puts("mkdb")
	f = File.open(fdb, 'w')
	
	f2 = File.open('out_b.txt', 'w')
	
	File.open('db.txt').readlines.each_with_index \
	{
		|x, i|
		z = Kernel.eval(x)
		l = seq(z)
		a = mono(l, {})
		y = {'i' => i, 'n' => z['n'], 'k' => z['k'], 'n2' => z['n'].to_s(2).length, 'm' => a}
		f.puts(y.inspect)
		f2.puts(([i, i / 100] + a.to_a.flatten).join("\t"))
		f2.puts if ((i + 1) % 100 == 0)
	}
	f.close
	f2.close
	
end

def db2()
	l = File.open('dbb.txt').readlines
	l2 = []
	l.size.times \
	{
		|i|
		l2[i] = Kernel.eval(l[i])
	}
	return l2
end

def init()
	
	c = 0
	z = 10
	i = 0
	loop \
	{ 
		f = add(z, (1..$wc).map { rand1() }) 
		c = f ? 0 : c + 1
		x = (c >= z)
		p(["i= #{i}", "l#= #{$l.size}", "c= #{c}", "z = #{z}"] + (x ? ['***'] : [])) if ((i += 1) % 5 == 0 || x)
		break if (x)
	}
	raise 'not 2 seeds after init' if ($l.size < 2)
	
end

def deltas()

	$d1 = {'mx' => -1, 'a' => -1, 'c' => 1, 'd' => 1, 'sd' => -1, 'r' => 1, 'mn' => -1, 'cn' => -1}


	$d0 = {}
	7.times { |x| ['mx', 'cn', 'mn'].each { |k| $d0["#{k}_#{x}"] = nil } }

	$d = {}
	['a', 'sd', 'r', 'd'].each \
	{ 
		|x| 
		7.times \
		{
			|n|
			['mx', 'mn', 'cn'].each \
			{
				|k|
				$d["#{k}_#{x}_#{n}"] = -1
			}
		}
	}
	
	$d.merge!('zc' => 1, 'zb' => 1)

end

mkdb()

$db = File.open('db.txt').readlines
$db2 = db2()

$a = []

$wc = metrics(0, 0).size

deltas()

$fn = 'out.txt'
$l = []

if (File.exists?($fn)) then
	load()
	
	case ARGV[0]
		when 'x'
			extract1(); exit
		when 'z'
			extract2(); exit
		when 'w'
			extract3(); exit
	end
		
	l = ARGV.map { |x| x.to_i }
	l.push($l.size - 1) if (l.empty?)
	l.push(l[0]) if (l.size == 1)

	(l[0]..l[1]).each { |x| extract(x) }
	
	exit
end


$cm = {}
$c = $n = $c0 = $c1 = 0

init()

c = $l.size / 2
f = nil

loop \
{
	clean(f)
	
	f ? c -= 1 : c += 1
	c = [c, 2].max
	c = [c, $l.size].min

	if (rand(2) == 0) then
		i = $l[rand(c)]
		w = $a[i]['w'].dup
		j = rand(w.size)
		z = ['a', 'b'][rand(2)]
		r = rand() * 2.0 * [-1, 1][rand(2)]
		case z
			when 'a'
				w[j] *= r
			when 'b'
				w[j] += r
		end
			
		h = trace([i, z])
		f = new2(w, c, $a[i]['l'], h)
	else
		l = (0...c).to_a
		x, y = (1..2).map { l.delete_at(rand(l.size)) }
		i = $l[x]
		j = $l[y]
		w1 = $a[i]['w']
		w2 = $a[j]['w']
		wt = [w1, w2].transpose
		z = ['a', 'b', 'c'][rand(3)]
		case z
			when 'a' 
				w = wt.map { |x| x[rand(2)] }
			when 'b'
				w = wt.map { |x| x[0] + x[1] }
			when 'c'
				w = wt.map { |x| x[0] - x[1] }
		end

		h = trace([i, j, z])
		l2 = $a[i]['l'] + $a[j]['l']
		m = [i, j].map { |x| $a[x]['l'].size }.max
		l3 = []
		m.times { l3 << l2.delete_at(rand(l2.size)) }
		f = new2(w, c, l3, h)
	end

}