construct79.rb

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

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 seq(n)

	n1 = n
	l = []
	begin
		l << n
		n = f2(n)
	end while (n != 1)
	
	return l
end

def stat(l)
	return 0, 0, 0 if (l.empty?)
	
	t = l.inject { |a, x| a + x }
	t2 = l.inject { |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, sd, l.max
end

def stat2(l, n)
	return Hash[[["a#{n}", "sd#{n}", "mx#{n}"], stat(l)].transpose]
end

def lenx(ns, p)
	l = ns.split(p)
	l = [] if (l.nil?)
	l.shift if (l[0] == '')
	return l.map { |x| x.length }
end

def len01x(ns)
	return lenx(ns, /0+/), lenx(ns, /1+/)
end

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

def stats(x)

	l1, l0 = len01x(x.to_s(2))
	return stat2(l1, '1').merge(stat2(l0, '0'))
end

def stat1(l)
	a, sd, mx = stat(l)
	return {'a' => a, 'sd' => sd, 'mx' => mx}
end

def avg1(l)
	a = {}
	l[0].keys.each \
	{
		|k|
		a[k] = stat1(l.map { |x| x[k] })
	}
	return a
end

def convert(l)
	
	x2 = nil
	l2 = []
	l.each_with_index \
	{ 
		|x, j| 
		next if (x == x2)
		l2 << [j, x]
		x2 = x
	}
	return l2
end

def scale(l, m)

	l1 = l.map { |x| x[m] }
	mn = l1.min
	mx = l1.max
	l.each { |x| x[m] = (x[m].to_f - mn) / (mx - mn) }
end

def out(l, c)
	l = convert(l)
#	scale(l, 0)
#	scale(l, 1)
	l.each \
	{
		|x, y|
		puts([x, y, c].join("\t"))
	}
	puts
end


c = 1000


l2 = []
l1b = []
w = 100

c.times \
{
	n = (ns = dense(w, 0.5)).to_i(2)
	l = seq(n)
	l1 = l.map { |x| x.to_s(2) }
	i = l1.rindex { |x| x.length == w / 2 }

	l2 << stats(l[i])
	ns1 = l1[i]
	l1, l0 = len01x(ns1)
	l1b += l1
}
a1 = avg1(l2)

out(l1b.sort, 1)


l2 = []
l1b = []

c.times \
{
	l2 << stats((ns = dense(w / 2, 0.5)).to_i(2))
	l1, l0 = len01x(ns)
	l1b += l1
	
}
a2 = avg1(l2)

out(l1b.sort, 2)


a1.keys.each \
{
	|k|
	$stderr.puts(k)
	$stderr.puts(a1[k].inspect)
	$stderr.puts(a2[k].inspect)
}