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

c = 500

l2 = []
c.times \
{
	n = (ns = dense(200, 0.5)).to_i(2)
	l = seq(n)
	l1 = l.map { |x| x.to_s(2) }
	i = l1.index { |x| x.length == 100 }

	l2 << stats(l[i])
}
a1 = avg1(l2)

l2 = []
c.times \
{
	l2 << stats(dense(100, 0.5).to_i(2))
}
a2 = avg1(l2)


a1.keys.each \
{
	|k|
	p(k)
	p(a1[k])
	p(a2[k])
}