data37.rb

def f2(n, o2, e)

	while (n.odd?)
		n = (n * 3 + 1) / 2
		break if (o2)
	end

	while (n.even?) do
		n /= 2 if (n.even?)
		break if (e)
	end
	
	return n

end

def adv(x)
	
	n1 = n = x['n']
	x['t'].times { n = f2(n, x['o2'], x['e']) }
	return d(n.to_s(2))
	
end

def ratio(x)
	
	n1 = n = x['n']
	x['t'].times { n = f2(n, x['o2'], x['e']) }
	return n.to_s(2).length.to_f / n1.to_s(2).length	
end

def coef(x, y)

        x1 = x2 = y1 = y2 = xy = 0.0

        n = x.size
        n.times \
        {
                |i|

                x1 += x[i]
                y1 += y[i]
                xy += x[i] * y[i]
                x2 += x[i] ** 2
                y2 += y[i] ** 2
        }

        d = n * x2 - x1 ** 2
        b = (y1 * x2 - x1 * xy) / d
        m = (n * xy - x1 * y1) / d

	b = 1 if (b.nan?)
	m = 1 if (m.nan?)
        return b, m
end

def sum(l)

	t = 0.0
	l.each { |x| t += x }
	return t
end

def av(l)
	return nil if (l.empty?)
	return sum(l) / l.size
end

def corr(l, y1, yp)
	
	xav = av(l.map { |x| x[y1] })
	yav = av(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 dense(x)
	w, d, o = x.values_at('w', 'd', 'o')
	w2 = w - (o ? 2 : 1)
	
	a = (0...w2).to_a
	s = '0' * w2
	(1..(d * w - (o ? 2 : 1))).map { a.delete_at(rand(a.size)) }.each { |x| s[x, 1] = '1' }
	return ('1' + s + (o ? '1' : '')).to_i(2) 
	
end

def d(s)
        c = s.split('').select { |x| x == '1' }.size
	d = c.to_f / s.length
        return d
        
end

def test(t, w, o, o2, e)
	c = 500

	l = []
	(c + 1).times \
	{
		|i|

		d =  i.to_f / c
		n = dense({'d' => d, 'w' => w, 'o' => o})
		a = {'n' => n, 'o2' => o2, 'e' => e, 't' => t}
		d2 = adv(a)
		r = ratio(a)
		l << {'d' => d, 'd2' => d2, 'wr' => r}
	}
	return l
end

def fit(l, k, a)
	b, m = coef(l.map { |x| x['d'] }, l.map { |x| x[k]})
	l.each { |x| x['y'] = m * x['d'] + b }

	a.merge!(k => {'m' => m, 'b' => b}.merge!(corr(l, k, 'y')))
end

def model(w)
	l = test(1, w, *[false, true, true])

	a = {}
	fit(l, 'd2', a)
	fit(l, 'wr', a)
	return a.merge!({ 'w' => w })
end

def rnum(f)
	return [rand(), rand() * [-1, 1][rand(2)]][f]
end

def detect(a, d, w, k, c, z)
	i = 0
	c.times \
	{
		break if (w < z)

		w1 = w.to_i
		w1 = [w1, 100].min
		
		ed = a[w1]['d2']['e_m']
		ew = a[w1]['wr']['e_m']
		
		d2 = d * a[w1]['d2']['m'] + a[w1]['d2']['b'] + k * ed
		w2 = d * a[w1]['wr']['m'] + a[w1]['wr']['b'] + k * ew

		d = d2
		d = [0.0, d].max
		d = [1.0, d].min
		w *= w2
		
		i += 1
#		puts([i, d, w].join("\t"))
	}
#	puts
	$stdout.flush
	return i
end

def scan(a, k, z)
	
	c = 500
#	c = 10
	d = 0.0
	m = 500
	
	t = t2 = 0
	w = 100
	while (d <= 1.0)
		d += 1.0 / c
		x = detect(a, d, w, k, m, z)
		t += (x == m) ? 1 : 0
		t2 += x
	end
	return t, t2
	
end

def trans(a, lo, hi, z)

	c = 100
	i = 0
	g = (hi - lo) / 100
	loop \
	{
		k = lo + 0.5 * (hi - lo)
		$stderr.puts([i, k].inspect)
		x, t = scan(a, k, z)

		if (x > 0)  then
			hi = k
		else 
			lo = k
		end
		if (hi - lo < g) then
			$stdout.puts([i, k, x, t, z].join("\t"))
			break
		end
		
		i += 1
	}
	$stdout.flush
end

def errors(z)
		
	a = []

	(z..100).each \
	{ 
		|w| 
		a[w] = model(w) 
		$stderr.puts([w, a[w]['d2']['e_m'], a[w]['wr']['e_m'], a[w]['d2']['r'], a[w]['wr']['r']].inspect)
	}

	return a

end

srand(0)

z = 20

a = errors(z)

(z..80).each { |z| trans(a, 0.10, 0.15, z) }