construct135.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 nilzero(x)
	return x.nil? ? 0 : x
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 [k, l, a, z, sd].inspect if (sd.nan?)
	
        return {"a#{k}" => a.nan? ? 0 : a, 
	"s#{k}" => sd.nan? ? 0 : sd,
	"mx#{k}" => nilzero(l.max),
	"mn#{k}" => nilzero(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 {'d' => d(ns),
		'e' => (l1 + l0).flatten.size.to_f / ns.length}
		.merge(stat2('1', l1, ns.length))
		.merge(stat2('0', l0, ns.length))
	
end

def seqa(l)
	n = l[-1]
	while (n != 1)
		n = f2(n)
		l << n
	end

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)
		
		seqa(l)
		
		ns = n.to_s(2)
		l1 << {'n' => n, 
		'cg' => l.size, 
		'ns' => ns, 
		'd' => d(ns),
		'l' => l}
		
	}

	return l1
end

def sample(l, c)
	return l if (l.size < c)
	r = l.size / c
	l2 = *(0...l.size).select { |x| x % r == 0 }
	l2[c..-1] = []
	return l.values_at(*l2)
	
end

def data(c, w)
		
	l = glides(10, 100)
	l1 = l.map { |x| x['l'] }

	l = []
	c1 = c2 = 0
	c0 = [0] * 2
	c.times \
	{
		l2 = l1[rand(l1.size)]
		i = rand(l2.size - w)
		n1 = l2[i]
		n2 = l2[i + w]

		c1x = n1 > n2 ? 1 : 0
		c2x = 1 - c1x
		
		if (c1 + c1x > c / 2 || c2 + c2x > c / 2) then
			c0[c1x] += 1
			redo
		end
				
		c1 += c1x
		c2 += c2x
		l << {'n1' => n1, 'd1' => l2.size - i, 's1' => etc(n1.to_s(2)),
		'n2' => n2, 'd2' => l2.size - (i + w), 's2' => etc(n2.to_s(2))}
	}
	
	return {'l' => l, 'c0' => c0}
end

def dist(x, y)

	z = 0
	x.keys.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 nearest(l)

	l2 = l.map { |x| [{'n' => x['n1'], 'd' => x['d1'], 's' => x['s1']}, {'n' => x['n2'], 'd' => x['d2'], 's' => x['s2']}] }.flatten

	z = {}
	(0...(l2.size - 1)).each \
	{
		|i|
		(i...l2.size).each \
		{
			|j|
			z[[i, j]] = dist(l2[i]['s'], l2[j]['s'])
		}
	}

	d1 = {}
	l2.size.times \
	{
		|i|
		l1 = []
		l2.size.times \
		{
			|j|
			next if (j == i)
			ij = [i, j].sort
			l1 << {'z' => z[ij], 'd' => l2[j]['d']} if (z[ij] != 0)
		}
		l1.sort_by! { |x| x['z'] }
		d = avg(l1[0...10].map { |x| x['d'] })
#		puts([i, l2[i]['d'], d].join("\t"))
		d1[l2[i]['n']] = d
	}
	
	c = 0
	c2 = 0
	l.each \
	{
		|x|
		c += d1[x['n1']] > d1[x['n2']] ? 1 : 0
	}
	return c
	
end

w = 1

loop \
{
	x = data(500, w)

	l = x['l']
	
	l1 = nearest(l)
	
	puts([w, l1, x['c0']].join("\t"))
	$stdout.flush
	w += 5
}