outline5.rb

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

end

def adj(x, m, n, s2, p2, p, x3)
	s2.replace(p[0...x] + (x3 % 2).to_s)
	m = (s2[x, 1] == p[x, 1])
	n = p2.reverse.to_i(2)
	p2[x, 1] = m ? '11' : '01'
	return m, n, x3
end

def terras121(p)
	
	p2 = ['01', '11'][p[0, 1].to_i]
	n = 1
	n3 = 0
	m = p2 == '11'
	x3 = (p2.reverse.to_i(2)) >> 1

	(1...p.length).each \
	{
		|x|

		if (!m)
			ns = n.to_s(2)
			ns[0, 1] = ''
			m1 = x3 - 3**n3
			n1 = f2(m1)
		end

		n3 = p[0...x].split('').select { |z| z == '1' }.size
		
		s2 = ''
		m, n, x3 = adj(x, m, n, s2, p2, p, m ? (f2(x3) + 3**n3) : (n1 + 3**n3))
	}

	n = p2.reverse.to_i(2)

	return n
end

def seq(n, c)
	l = [n]
	
	while (n != 1 && l.size < c)
		n = f2(n)
		
		l << n
		
	end
	raise if (l.size != c)
	return l
end

def dense(w, d)
	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 sum(l)
	return l.inject { |t, x| t + x }
end

def avg(l)
	return (l.nil? || l.empty?) ? 0 : sum(l).to_f / l.size
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 runavg(l, k, c)

	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

	return l2
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 features(ns)
	d = d(ns)
	e = e(ns)
	
	nw = ns.length
	nw2 = nw / 2
	nshi = ns[0...nw2]
	nslo = ns[nw2..-1]
	
	dlo = d(nslo)
	dhi = d(nshi)
	elo = e(nslo)
	ehi = e(nshi)
	mp = midpt(ns)
	return {
		"d" => d,
		"e" => e,
		"ea" => (0.5 - e).abs,
		"da" => (0.5 -d).abs,
		"dlo" => dlo,
		"dhi" => dhi,
		"elo" => elo,
		"ehi" => ehi,
		"mp" => mp,
		"nw" => ns.length
	}
end

def data(a, l)
	l2 = l.map { |x| features(x.to_s(2)) }
	a1 = {}
	l2[0].keys.each \
	{
		|k|
		l1 = runavg(l2, k, l2.size - 1)
		
		a1[k] = l1[-2]
		a1["#{k}2"] = l1[-1]
	}
	a1['nw21'] = a1['nw2'].to_f / a1['nw']
	return a1.merge(a)
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 outa(f, l, a = {}, t = '')
	
	k = outd(f, l)
	f.puts("set colors classic; set key top right opaque; set title '#{t}'; ")
	f.puts("set ytics nomirror; set y2tics;")
	f.puts("plot \\")
	ct = ''
	k, ct = [k - ['t'], "(column('t')):"] if (k.member?('t') && !hide(a, 't'))
	k.each \
	{ 
		|x| 
		next if (hide(a, x))
		opt = a.fetch(x, '')
		opt += ' with line lw 2 ' if (!opt.include?('with'))
		f.puts("'$dat' using #{ct}(column('#{x}')) #{opt} title '#{x}',\\") 
	}
	f.puts
#	f.puts("reset; pause -1;")

end

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

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

	l.each_with_index \
	{
		|x1, j|
		next if (x == x1)
		next if (x1.member?('x'))
		
		z = 0
		['d', 'e', 'da', 'ea', 'dlo', 'dhi', 'elo', 'ehi', 'mp'].each \
		{
			|k1|
			
			k = "#{k1}#{k2}"
			z += (x[k] - x1[k1]) ** 2
		}
		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]}) }
end

def predict(l1)
	e1 = 0
	l1.each { |x| x['nn'] = []; x.delete('er2') }
	
	l1.each \
	{
		|x|
		l = near(x, l1, '2')
		j = x['j']
		et = 0
		l.each \
		{
			|x1|
			e = (x1['nw21'] - x['nw21']).abs
			x1['nn'] << {'er' => e, 'j' => j, 'z' => x1['z']}
			et += e
		}
		x['er1'] = et / l.size
		e1 += x['er1']
	}
	
	l1.each \
	{ 
		|x| 
		next if (x.member?('x'))
		next if (x['nn'].empty?)
		l = x['nn'].map { |x1| x1['er'] }
		x['er2'] = avg(l)
	}
	x = l1.max_by { |x1| x1.fetch('er2', 0) }
	l1[x['j']]['x'] = nil
	a = {'ea' => e1 / l1.size, 'er2max' => x['er2']}
	$stderr.puts(a.inspect)
	return a
end


a = 0.0
b = 1.0
c1 = 250
c2 = 10
w = 200

l1 = []
c1.times \
{
	|j|

	ns = dense(w, j.to_f / (c1 - 1))
	n = ns.to_i(2)
	
#	n = terras121(ns)

	l = seq(n, c2)
	
	a = data({'j' => j}, l)
	l1 << a
}
l2 = []
(c1 * 3.0 / 5).to_i.times { l2 << predict(l1) }
l2.each { |x| x['r'] = x['ea'] / l2[0]['ea'] }
outafn(l2, {'r' => 'axes x1y2'})