construct133.rb

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

end

def seqg(n)

	n1 = n
	l = [n1]
	while (n != 1 && n >= n1)
		n = f2(n)
		l << n
	end 
	
	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 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 d(s)
        c = s.split('').select { |x| x == '1' }.size
	d = c.to_f / s.length
        return d
        
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 len01(ns)
	return len(ns, /0+/), len(ns, /1+/)
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 {"a#{k}" => a, 
	"s#{k}" => sd,
	"mx#{k}" => l.max,
	"mn#{k}" => l.min}
end

def stat2(k, l, w)
	a = stat(k, l)
	a2 = {}
	a.each { |k, v| a2.merge!({"#{k}s" => v.to_f / w})}

	return a.merge(a2)
end

def etc(ns)
	l1, l0 = len01(ns)
	
	return {'e' => (l1 + l0).flatten.size.to_f / ns.length}
		.merge(stat2('1', l1, ns.length))
		.merge(stat2('0', l0, ns.length))
	
end

def glides(t, nw)
	
	l1 = []
	e = 0.64

	t.times \
	{
		d = e + rand() * (1.0 - e)

		p = dense(nw, d)
		n = terras121(p)

		l = seqg(n)

		redo if (l.size < n.to_s(2).length)
		
		ns = n.to_s(2)
		l1 << {'n' => n, 
		'y' => Math.log(l[40].to_f) / Math.log(l[0]),
#		'y' => l.size,
		'cg' => l.size, 
		'ns' => ns, 
		'd' => d(ns)}.merge(etc(ns))
		
	}

	return l1
end

def dist(x, y, ks)

	z = 0
	ks.each \
	{
		|k|
		z += (x[k] - y[k]) ** 2
	}
	return z
	
end

def avg(l)
	l.inject { |t, x| t + x }.to_f / l.size
end

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

def corr(l, y1, yp)
	
	xav = avg(l.map { |x| x[y1] })
	yav = avg(l.map { |x| x[yp] })

	tx = ty = txy = e = 0.0
	m = nil
	l.each \
	{
		|z|
		
		x = z[y1]
		y = z[yp]
		
		txy += (x - xav) * (y - yav)
		tx += (x - xav) ** 2
		ty += (y - yav) ** 2
		e1 = (x - y).abs
		e += e1
		m = [m, e1].compact.max
	}
	r = txy / (Math.sqrt(tx) * Math.sqrt(ty))
	e /= l.size
	return {'r' => r, 'e_a' => e, 'e_m' => m}
	
end

def weight(xs, zs)

	zt = sum(zs)
	
	return sum((0...xs.size).map { |x| xs[x] * zs[x] / zt })
	
end

def nearest(l1, l2, v, ks)
	l3 = []
	l2.each \
	{
		|x|
		l1.each \
		{
			|y|
			y['z'] = dist(x, y, ks)
		}
		l1.sort_by! { |x| x['z'] }

		mn = l1.map { |x| x['z'] }.select { |x1| x1 != 0 }.min

		l1.each { |x| x['z'] = mn if x['z'] == 0 }
		
		a = {'y' => x['y']}
		v.each { |k, x1| a[k] = avg(l1[0...x1].map { |x| x['y'] }) }

		l3 << a
	}

	a = nil
	v.each { |k, x1| a = corr(l3, k, 'y') }
	return a['r']
	
end

def smooth(l, c)
	l.sort_by! { |x| x['y'] }
	mn = l[0]['y']
	mx = l[-1]['y']
	
	f = File.open('out1.txt', 'w')
	l.each { |x| f.puts(x['y']) }
	f.close
	
	l2 = []
	
	c.times \
	{
		|x|
		z = mn + x.to_f / (c - 1) * (mx - mn)
		
		i = (0...l.size).min_by { |x1| (l[x1]['y'] - z).abs }
		l2 << l.delete_at(i)
	}
	return l2
end

def batch()
	
	l = []
	20.times { |x| l.concat(glides(100, 50 + x)) }


	l = smooth(l, 200)
	return l

end

def data(fn)
	$stderr.puts(fn)
	if (File.exist?(fn)) then
		f = File.open(fn)
		l = f.readlines.map { |x| Kernel.eval(x) }
		f.close
		return l
	end
	
	l = []
	5.times \
	{
		|x|
		l.concat(batch())
		$stderr.puts([x, l.size].inspect)
	}

	l.sort_by! { |x| x['y'] }
	f = File.open('out1.txt', 'w')
	l.each { |x| f.puts(x['y']) }
	f.close
	
	f = File.open(fn, 'w')
	l.each { |x| f.puts(x.inspect) }
	f.close
	
	exit

end

def znorm(l, l2, ks)
	ks.each \
	{
		|k|
		a = stat('', l.map { |x| x[k] })
		l2.each \
		{
			|x|
			x["#{k}z"] = (x[k] - a['a']) / a['s']		
		}	
	}
	ks2 = ks.map { |x| x + 'z' }
end

def index2(l, l2, ks)
	ks.each \
	{
		|k|

		a = {}
		l.size.times { |x| a[l[x][k]] = x }

		l1 = a.values
		l1.sort_by! { |x| l[x][k] }
		

		l2.each \
		{
			|x|
			i = l1.index { |x1| x[k] <= l[x1][k] }
			x["#{k}i"] = i.nil? ? 0 : i + 1
		}
	}
	return ks.map { |x| x + 'i' }
end

def track(x, k)
	$d = {'x' => {}} if ($d.nil?)
	$d[k] = [] if ($d[k].nil?)
	$d[k] << x
	$d['x'][k] = x
	$d['x']["#{k}_a"] = avg($d[k])
end

l = data(File.basename($0, File.extname($0)) + '.txt') 

v = {}
[3].each \
{
	|x|
	n = x * 3 + 1
	v["y#{n}"] = n
}



ks = l[0].keys - ['n', 'ns', 'y', 'cg', 'w']

ks1 = ['ks', 'ks_a', 'ks2', 'ks2_a', 'ks3', 'ks3_a']
f = File.open('gnuplot.cmd', 'w')
f.puts("set key bottom left opaque; plot \\")
ks1.each_with_index \
{
	|k, n|
	dt = n.even? ? 'dt 3' : ''
	f.puts("'out.txt' using (column('#{k}')) with line #{dt} lw 2 lt #{(n / 2) + 1},\\")
}
f.close

f = File.open('out.txt', 'w')
f.puts(ks1.join("\t"))
50.times \
{
	|t|
	l.shuffle!
	l.size.times { |x| l[x]['w'] = (x % 5 == 0) ? 'b' : 'a' }
	l1 = l.select { |x| x['w'] == 'a' }
	l2 = l.select { |x| x['w'] == 'b' }


	track(nearest(l1, l2, v, ks), 'ks')

	ks2 = index2(l1, l, ks)
	track(nearest(l1, l2, v, ks2), 'ks3')

	ks3 = znorm(l1, l, ks)
	track(nearest(l1, l2, v, ks3), 'ks2')

	f.puts($d['x'].values.join("\t"))
	f.flush
}