bunch53.rb

def f1(n)
	n = (n * 3 + 1) / 2 while (n.odd?)
	n /= 2 while (n.even?)
	return n
end

def dense(n)
 
        s = n.to_s(2)
        c = 0
        s.length.times \
        {
                |i|
                c += s[i, 1].to_i
        }
        return c.to_f / s.length
 
end

def widthdiff(x, y)
        x.to_s(2).length - y.to_s(2).length
 
end

def widthratio(x, y)
        x.to_s(2).length.to_f / y.to_s(2).length
end

def f(n, w)
 
        n1 = n
        c = 0
	l = [n]
	cg = nil
	
        while (n != 1)
		n = f1(n)

		l << n
                c += 1
	
		cg = c if (cg.nil? && n < n1)

		break if (!cg.nil? && w != 'c')
        end
	cm = (0...l.size).max_by { |x| l[x] }
	
        return {'cm' => cm,
		'cg' => cg.nil? ? 0 : cg, 
		'm' => l[cm].to_s(2).length,
		'w' => widthdiff(l[cm], n1),
		'r' => widthratio(l[cm], n1),
		'c' => l.size,
		'd' => (0.5 - dense(n1)).abs}
 
end

def long(m, w)
 
	return {'n' => rand(2 ** (s = m * 1000)) | 1, 's' => s } if (w == 'z')
		
        l = [{'n' => 1, 'p' => 0}.merge(f(1, w))]
        t = 0
	e = 2000
	
        loop \
        {
                l = l.sort_by { |x| [x[w], -x['d']] }.reverse
 
                x = l.delete_at(rand([l.size, 20].min))
 
                p2 = x['p'] + 1
                n2 = x['n'] + 2 ** p2
 
 
                x1 = x.dup
                x1['p'] = p2
                l << x1
 
                x2 = {'n' => n2, 'p' => p2}.merge(f(n2, w))
                l << x2
                t += 1
 
		if (w == 'r') then
			z = l.sort_by { |x| x['n'] }.reverse[0...100].max_by { |x| x['r'] }
		else
			z = l.max_by { |x| x[w] }
		end
		z.merge!({ 't' => t, 's' => t.to_f / e })
		
                return z if (z['s'] >= m)
        }
 
end

def test(k, m)
	
	if ($x['c'][k].nil?) then
		$x['c'][k] = 0
		$x['x'] += 1
		$x['a'][k] = {}
		puts
	end
	
	z = long(m, k)
	
	$x['c'][k] += 1
	
	n = z['n']
	return if ($x['a'][k].member?(n))
	
	$x['a'][k][n] = nil
	
	$stderr.puts([$x['c'][k], $x['a'][k].size, k, z['s'], n.to_s(2)].inspect)
	track(n, $x['x'], m)
	$stdout.flush
end

def r2(x)
	sprintf("%.2f", x).to_f
end

def adv1(n)
	l = [n]
	n1 = n
	while (n != 1)
		n = f1(n)
		break if (n < n1)
		l << n
	end
	return l.map { |x| x.to_s(2).length }
end

def nonmono(l)
	
	return 0 if (l.empty?)
	mn = nil
	r = nil
	l.each_with_index \
	{
		|d, i|
		mn = [mn, [d, i]].compact.min
		r = [r, [i - mn[1], mn[1], i]].compact.max
	}
	return r[0]

end

def scale(l)

	return [] if (l.empty?)
	l.each \
	{
		|l1|
		mx = l1.max
		mn = l1.min
		r = mx - mn
		r = 1 if (r == 0)
		l1.map! { |x| (x.to_f - mn) / r }
	}
	
	m = l.map { |x| x.size }.max
	l2 = []
	return [] if (m == 1)
	m.times \
	{
		|j|
		t = 0
		l.each \
		{
			|l1|
			i = (j.to_f / (m - 1) * (l1.size - 1)).to_i
			t += l1[i]
		}
		l2 << t
	}
	return l2
	
end

def track(n, c, z)
	
	s = n.to_s(2)

	l1 = []
	l2 = []
	mx = s.length - 1
	(1..mx).each \
	{
		|i|
		n2 = ('1' + s[i..mx]).to_i(2)
		l = adv1(n2)
		m = (0...l.size).max_by { |x| l[x] }
		l1 << l[0..m]
		l2 << l[m..-1]
	}
	
	l = [c, (c * 2) + z]
	
	l += [nonmono(scale(l1).map { |x| -x }), nonmono(scale(l2))]
	puts(l.join("\t"))
	
end

p = ['w', 'p', 'c', 'm', 'cg', 'cm', 'r', 'z']

$x = {'a' => {}, 'c' => {}, 'x' => -1}


# test('w', 0.5); exit

c = 100

p.each { |k| c.times { |i| test(k, i.to_f / c) } }

$x['c'].keys.each { |k| $stderr.puts("#{k}\t#{$x['a'][k].size}") }