outline18.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 seqc(n, c)
	l = [n]
	n1 = n
	while (n != 1 && (l.size < c || n >= n1))
		n = f2(n)
		
		l << n
		
	end
	return l
end

def outin(fn)
        l = (f = File.open(fn)).readlines
	f.close
	raise if (l.shift.chop != '$dat << eof')
        k = l.shift.split
	i = l.index("eof\n")
	raise if (i.nil?)
	l[i..-1] = []
        l2 = l.map { |x| Hash[[k, x.split.map { |x| Kernel.eval(x) }].transpose] }
	
	l2.each { |x| x['ns'] = x['ns'].to_s }
	$stderr.puts([fn, l2.size].inspect)
	return l2
end

def load(l1 = (1..5))

	l = []
	l1.each \
	{
		|i|
		l.concat(outin("gnuplot#{i}-1.cmd"))
	}
	return l
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 0 if (ns.empty?)
	return len01(ns).flatten.size.to_f / ns.length
end

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

def midpt(ns)
	w2 = ns.length / 4
	l = ns.split('')
	i = j = 0
	while (i < w2 && j < l.size)
		i += l[j].to_i
		j += 1
	end
	return j.to_f / ns.length
end

def d1(s)
        c = s.split('').select { |x| x == '1' }.size
        return c
        
end

def midpt2(ns)
	w2 = d1(ns) / 2
	l = ns.split('')
	i = j = 0
	while (i < w2 && j < l.size)
		i += l[j].to_i
		j += 1
	end
	return j.to_f / ns.length
end

def log2(x)
	return Math.log(x) / Math.log(2.0)
end

def features(ns)
	
	d = d(ns) - 0.5
	e = e(ns) - 0.5
	
	nw = ns.length
	nw2 = nw / 2
	nshi = ns[0...nw2]
	nslo = ns[nw2..-1]
	
	dlo = d(nslo) - 0.5
	dhi = d(nshi) - 0.5
	elo = e(nslo) - 0.5
	ehi = e(nshi) - 0.5
	mp1 = midpt(ns) - 0.5
	mp2 = midpt2(ns) - 0.5
	
	l0 = len0(ns)
	mx0 = l0.empty? ? 0 : l0.max
	mx1 = len1(ns).max
	mx01 = [mx0, mx1].max
	mx = log2(log2(ns.to_i(2).to_f))
	
	a0 = l0.empty? ? 0 : avg(l0)
	
	a1 = avg(len1(ns))
	a01 = avg(len01(ns).flatten)
		
	return {
		"d" => d,
		"e" => e,
		"ea" => e.abs,
		"da" => d.abs,
		"dlo" => dlo,
		"dhi" => dhi,
		"elo" => elo,
		"ehi" => ehi,
		'mp1' => mp1,
		"mp2" => mp2,
		'mx0' => mx0.to_f / ns.length,
		'mx1' => mx1.to_f / ns.length,
		'mx01' => mx01.to_f / ns.length,
		'a0' => a0 / ns.length,
		'a1' => a1 / ns.length,
		'a01' => a01 / ns.length,
		'a1m' => a1 / mx,
		"nw" => ns.length
	}
end

def smooth(x)

	l = x['l'].map { |x| features(x.to_s(2)) }
	
	(ks = l[0].keys).each { |k| runavg(l, k, l.size, "#{k}_a") }
	
	a1 = Hash[[ks, l[-1].values_at(*ks.map { |x| "#{x}_a" })].transpose]
	
	a = {'ns' => x['ns'],
		$k => x[$k], 
		'cm' => x['cm'],
		'cg' => x['cg'],
		}.merge(a1)
	
	return a
end

def dataset(l)

	return l.map { |x| x.empty? ? {} : smooth(x) }

end

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

def avg(l)
	return sum(l).to_f / l.size
end

def outd(f, l)
	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')
	return k
end

def hide(a, x)
	return (a.member?(x) && a[x].nil?)
end

def plot(f, d, k, a, t = nil)
	f.puts("# #{t}") if (!t.nil?)
	f.puts("set colors classic; set title '#{t}'; ")
#	f.puts("set key top right opaque; ")
	f.puts("set ytics nomirror; set y2tics;")
	f.puts("plot \\")
	k.each \
	{ 
		|x| 
		next if (hide(a, x))
		opt = a.fetch(x, '')
		opt = ' with line ' + opt if (!opt.include?('with'))
		opt += ' lw 2 ' if (!opt.include?('lw'))
		f.puts("#{d} using (column('#{x}')) #{opt} title '#{x}',\\") 
	}
	f.puts
#	f.puts("reset; pause -1;")
end

def outa(f, l, a = {}, t = nil)
	
	k = outd(f, l)
	plot(f, '$dat', k, a, t)
end

def outafn(l, a = {}, fno = nil, t = '')
	
	outa(f = File.open(fn = "gnuplot#{fno}.cmd", 'w'), l, a, t)
	f.close
	$stderr.puts([fn, l.size, t, l[0].keys].inspect)
end

def streamafn(a = nil, a1 = {}, fno = nil, t = nil)
	$f, $n = [{}, 1] if ($f.nil?)
	
	fno = $n if (fno.nil?)
	
	if (a.nil?) then
		$f[$f.keys.last]['f'].close
		$n += 1
		return
	end
	
	if (!$f.member?(fno)) then
		$f[fno] = {'fn' => (fn2 = "out#{fno}.txt"), 
			'f' => File.open(fn2, 'w')}
		$f[fno]['f'].puts(a.keys.join("\t"))
		plot(f = File.open(fn = "gnuplot#{fno}.cmd", 'w'), "'#{fn2}'", a.keys, a1, t)
		f.close
		$stderr.puts([fn, fn2, t, a.keys].inspect)
	end
	
	$f[fno]['f'].puts(a.values.join("\t"))
	$f[fno]['f'].flush
end


def cg(l2)
	cg = l2.index { |x| x < l2[0] }
	return cg
end

def seqg(n)

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

def derive(a)
	a['hm'] = a['cm'].to_f / a['ns'].length
	a['hg'] = a['cg'].to_f / a['ns'].length
	
end

def resample(l, c, l1 = [])

	mn = l[0][$k]
	mx = l[-1][$k]
	l2 = []
	c.times \
	{
		|i|
		y = mn + i.to_f / (c - 1) * (mx - mn)
		j = (0...l.size).min_by { |x1| (l[x1][$k] - y).abs }
		x = l[j]
		next if (l2.member?(x))
		l2 << x 
		l1 << j
	}
	$stderr.puts(['resample', mn.round(3), mx.round(3), c, l2.size].inspect)
	return l2
	
end

def subglides(l, c, c1 = nil)
	c1 = [$c, c1, 50].compact.first
	l3 = []
	l.each \
	{
		|x|
		ns = x['ns']
		l2 = seqg(ns.to_i(2))
		cm = (0...l2.size).max_by { |x| l2[x] }
		
		(0...cm).each \
		{
			|i|
			l1 = l2[i..-1]
			next if (l1.size < c1)
			
			ns = l1[0].to_s(2)
			cg = cg(l1)
			cm = (0..cg).max_by { |x| l1[x] }
			
			a = {'ns' => ns, 'cm' => cm, 'cg' => cg}
			derive(a)
			next if (a['hg'] < 0.05)
			l3 << a.merge({'i' => i, 'l' => l1[0...c1]})
		}
	}
	l3.sort_by! { |x| x[$k] }
	
	l4 = resample(l3, c)
	
	$stderr.puts(['subglides', c1, l3.size, l4.size].inspect)
	return l4
	
end

def keys(l, ks)
	return l.map \
	{
		|x|
		Hash[[ks, x.values_at(*ks)].transpose]
	}
end

def runavg(l, k, c, ka = "#{k}a")

	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
	
	
	l.each_with_index { |x, i| x[ka] = l2[i] }
	
end

def io(l, l3 = [])
	fn = 'outline2.txt'
	if (!File.exists?(fn)) then

		l3.replace(load())
		l1 = subglides(l3, 1000 + 2 * $c3)

		l.replace(dataset(l1))
		f = File.open(fn, 'w')
		l.each { |x| f.puts(x.inspect) }
		f.close
		$stderr.puts(['out', fn, l.size].inspect)
	else
		f = File.open(fn)
		l.replace(f.readlines.map { |x| Kernel.eval(x) })
		f.close
		$stderr.puts(['in', fn, l.size].inspect)
	end
end

def near(x, l, wt, k2 = '', l1 = [])

	l.each_with_index \
	{
		|x1, j|
		next if (x == x1)
		
		z = 0
		['d', 'e', 'da', 'ea', 'dlo', 'dhi', 'elo', 'ehi', 'mp1', 'mp2',
		'mx0', 'mx1', 'mx01', 'a0', 'a1', 'a01', 'a1m'].each \
		{
			|k1|
			
			k = "#{k1}#{k2}"
			z += ((x[k] - x1[k1]) ** 2) * wt.fetch(k, 1.0)
		}
		l1 << [z, j]
	}
	l1.sort_by! { |x| x[0] }
	
	i = 0
	i += 1 while (i + 1 < l1.size && l1[i][0] == l1[i + 1][0])
	return (0..i).map { |x| l[l1[x][1]].merge({'z' => l1[x][0], 'j1' => l1[x][1]}) }
end

def predict(l2, l1, wt = {})
	
	e1 = 0
	l1.each { |x| x['nn'] = []; x.delete('er2') }
	
	ky = $k
	
	l2.each_with_index \
	{
		|x, j|
		next if (x.empty?)
		l = near(x, l1, wt)
		
		et = yt = zt = 0
		x['j1'] = []
		l.each \
		{
			|x1|
			
			e = (x1[ky] - x[ky]).abs
			yt += x1[ky]
			et += e
			zt += x1['z']
			a = {'er' => e, 'j' => j, 'z' => x1['z']}
			x1['nn'] << a
			x['j1'] << x1['j1']
		}
#		$stderr.puts([j, l.size].inspect) if (l.size > 1)
		
		x['y'] = yt / l.size
		x['er1'] = et / l.size
		x['z'] = zt / l.size
		e1 += x['er1']
	}
	et = e1 / l2.size
	return et
end

def stat(k, l)
	
	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 {"#{k}_a" => a, "#{k}_s" => sd, 
		"#{k}_mn" => l.min, "#{k}_mx" => l.max}
end

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

def sample3(l, n)
	
	d = (l.size - 1).to_f / (n - 1)
	l2 = []
	n.times \
	{
		|i|
		j = (i * d).to_i
		j += [-1, 0, 1][rand(3)]
		j = [j, 0].max
		j = [l.size - 1, j].min
		l2 << l[j]
	}
	return l2
end

def nearest(l, l2, c, wt)
	predict(l, l2, wt)
	l.sort_by! { |x| x['z'] }
	
	l1 = l.slice!(0...c)
	return l1
end

def interleave(l0, l2, l3)
	l2.replace(l0.values_at(*(0...l0.size).select { |x| x.odd? }))
	l3.replace(l0.values_at(*(0...l0.size).select { |x| x.even? }))
end

def avgs(l)

        ks = l[0][0].keys
        l1 = []
        l[0].size.times \
        {
                |i|
                l1[i] = Hash[[ks, ks.map { |k| avg(l.map { |x| x[i][k] }) }].transpose]
        }
        return l1

end

def read(fn)
	l = (f = File.open(fn)).readlines.map { |x| Kernel.eval(x) }
	f.close
	$stderr.puts(['read', fn, l.size].inspect)
	return l
end

def buffer(fn, fnm)
	if (!File.exists?(fnm)) then
		l = fn.call
		f = File.open(fnm, 'w')
		l.each { |x| f.puts(x.inspect) }
		f.close
	else
		l = read(fnm)
	end
	$stderr.puts([fn, fnm, l.size].inspect)
	return l
	
end

def run()
	
	c = 750
	n = 250
	
	ks = ['d', 'e', 'da', 'ea', 'dlo', 'dhi', 'elo', 'ehi', 'mp1', 'mp2',
		'mx0', 'mx1', 'mx01', 'a0', 'a1', 'a01', 'a1m']
			
	fn = lambda \
	{
		io(l = [])
		l0 = sample3(l, c)
		
		predict(l0, l0)

		l0.each \
		{ 
			|x| 
			next if (x['nn'].empty?)
			x['er2'] = avg(x['nn'].map { |x1| x1['er'] }) 
			x['z2'] = avg(x['nn'].map { |x1| x1['z'] }) 
		}

		l0 = l0.select { |x| x.member?('er2') }
		l0.sort_by! { |x| x['er2'] }

		runavg(l0, 'z2', 40)
		runavg(l0, 'y', 40)
		outafn(keys(l0, ['er2', 'z2', 'z2a', 'y', 'ya']), 
			{'er2' => 'axes x1y2', 
			'y' => 'axes x1y2',
			'ya' => 'axes x1y2'})
			
		l1 = l0[0...n]
		return l1
	}
	
	l1 = buffer(fn, 'outline3.txt')
	
	c2 = 50
#	c1 = 10
	c1 = 5
	c3 = c1 + c2
	
	l2 = read('db5.txt')
	l2 = l2.select { |x| x['cg'] >= c3 }.sort_by { |x| -x['cg'] }
	$stderr.puts({'l2' => l2.size, 'k' => l2.map { |x| x['k'] }.uniq, 'c3' => c3}.inspect)

	l3 = l2.map \
	{ 
		|x| 
		
		l = seqc(x['n'].to_i, c3)
		(0...c1).map \
		{
			|i|
			
			l2 = l[i..-1]
			next if (l2.size < c2)
			
			ns = l2[0].to_s(2)
			cg = cg(l2)
			cm = (0..cg).max_by { |x| l2[x] }
			
			a = {'ns' => ns, 'cm' => cm, 'cg' => cg, 'l' => l2[0...50], 'k' => x['k']}
			derive(a)
			next if (a['hg'] < 0.05)
			a
		}
	}
	
	l3 = l3.select { |x| x.compact.size == c1 }
	p({'l3' => l3.size, 'k' => l3.map { |x| x[0]['k'] }.uniq})

	c4 = 50
	l3 = l3.select { |l2| l2[0]['ns'].length >= 50 }
	p({'l3' => l3.size, 'k' => l3.map { |x| x[0]['k'] }.uniq, 'c4' => c4})
	
	
	l3.sort_by! { |l2| l2[0][$k] }

	f = File.open('out11.txt', 'w')
	l3.each { |l2| f.puts([l2[0][$k], l2[0]['ns'].length].join("\t")) }
	f.close
	
	f = File.open('out10.txt', 'w')
	
	l4 = []
#	n = 2
	(0...c1).each \
	{
		|i|
		
		l2 = dataset(l3.map { |x| x[i] })
		predict(l2, l1)
		
		ks = [$k, 'y', 'z']
		ks = ['y']
		l4 << keys(l2, ks)
		l2 = avgs(l4[0..i])
#		outafn(l2, {'z' => 'axes x1y2'}, n)
		l2.size.times { |j| f.puts([j, l2[j]['y'], i].join("\t")) }
		f.puts
		n += 1
	}
	f.close
end


$c3 = 250
$k = 'hg'

run()

#plot 'out10.txt' using 1:2:(-$3) with line linecolor palette lw 2,'out11.txt' using 1 axes x1y2 with line lw 2