outline18b.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
	
	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 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 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 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 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


$c3 = 250
$k = 'hg'

io(l = [])