outline16.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 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
	
	mx0 = len0(ns).max
	mx0 = 0 if (mx0.nil?)
	mx1 = len1(ns).max
	mx01 = [mx0, mx1].max
	mx = log2(log2(ns.to_i(2).to_f))
	
	a0 = avg(len0(ns))
	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("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, a1 = {}, fno = 1, t = nil)
	$f = {} if ($f.nil?)
	
	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, 20].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
		l.each { |x| x['ns'] = x['ns'].to_s }
		$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}
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 opt(l2, l1, wt)
	
	et = predict(l2, l1, wt)
	
	l1.each { |x| x['er2'] = avg(x['nn'].map { |x1| x1['er'] }) if (!x['nn'].empty?) }

	i = (0...l1.size).max_by { |x| l1[x].fetch('er2', 0) }
	
	js = (0...l1.size).select { |x| !l1[x].member?('er2') }

	return et, (js + [i]).sort.reverse
end

def run(l, l1, l2, l3, wt)
	
	$stderr.puts([l.size, l1.size, l2.size, l3.size].inspect)
	
	ks = wt.keys


	ds = [0, 1] * ((ks.size + 1) / 2)
	
	i = j = t1 = 0
	s = ['toss', 'weight']
	w = t = 0
	et, js = opt(l2, l1, wt)
	et0 = nil
	et2 = et
	ws = []
	
	loop \
	{
		s2 = nil
		et1 = et
		case (s1 = s[w])
		when 'toss'
			js.each { |i| l << l1.delete_at(i) }
			js.each { l1 << l.delete_at(rand(l.size)) }
			
			j1 = js.size
			et, js = opt(l2, l1, wt)
			if (et < et1) then
				s2 = [j1.to_s]
			else
				w = 1
			end
		
		when 'weight'
			wt2 = wt.dup
			wt2[ks[i]] *= [0.85, 1.15][ds[i]]
			et, js2 = opt(l2, l1, wt2)
			if (et < et1) then
				wt = wt2
				js = js2
				j = 0
				s2 = ['-', '+'][ds[i]] + ks[i]
				ws << s2
			else
				j += 1
			end
			ds[i] = 1 - ds[i]
			i = (i + 1) % ks.size
			w = 0
		end
		et2, t1 = [et, t] if (et < et2)
		
		
		$stderr.puts({'s' => [s1, s2].compact.join(' '), 
			'j' => j, 
			'js' => js.size, 
			'ws' => ws,
			't2' => (t2 = t - t1)}.inspect)
		break if (t2 == 3 * ks.size)
		
		et0, = predict(l3, l1, wt) if (t % 5 == 0)
		raise if (et1.nil?)
		raise if (et0.nil?)
		
		streamafn(wt.merge({'et1' => et1,
				'et0' => et0}), 
			{'et1' => 'axes x1y2 lw 3',
			'et0' => 'axes x1y2 lw 3'}.merge(Hash[[ks, ['dt 3'] * ks.size].transpose]))
		t += 1
	}
	
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 select(l)

	l0 = sample3(l, 500)
	
	ks = ['d', 'e', 'da', 'ea', 'dlo', 'dhi', 'elo', 'ehi', 'mp1', 'mp2',
		'mx0', 'mx1', 'mx01', 'a0', 'a1', 'a01', 'a1m']
		
	r = 0.1
	wt = Hash[[ks, (0...ks.size).map { |x| 1.0 + r * x.to_f / (ks.size - 1) - (r / 2)} ].transpose]

	predict(l0, l0, wt)

	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)
	outafn(keys(l0, ['er2', 'z2', 'z2a']), {'er2' => 'axes x1y2'})
	
	l1 = l0[0...250]
	l1.each { |x| l.delete(x) }

	l0 = nearest(l, l1, 500, wt)
	
	l2 = l0.values_at(*(0...l0.size).select { |x| x.odd? })
	l3 = l0.values_at(*(0...l0.size).select { |x| x.even? })
	
	run(l, l1, l3, l2, wt)
end


$c3 = 250
$k = 'hg'


io(l = [])
select(l)