sides.rb

def f1(n)
        n = (n * 3 + 1) / 2 while (n % 2 == 1)
        n /= 2 while (n % 2 == 0)
        return n
end

def seq(n)
	l = [n]
	begin
		l << (n = f1(n))
	end while (n != 1)
	return l
end

def seq2(n)
	l = [n]
	n1 = n
	begin
		l << (n = f1(n))
	end while (n >= n1 && n != 1)
	return l
end

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

def stat(l)
        return 0, 0 if (l.empty?) 
        t = t2 = 0
        l.each \
        {
            |x|
            t += x
            t2 += x ** 2
        }
        c = l.size
        a = t.to_f / c
        z = t2.to_f / c - a ** 2
        sd = Math.sqrt(z < 0 ? 0 : z)

        return a, sd
end

def mono(l, z)

	return if (l.empty?)

	c = 0
        m = l[0]
	mx = nil
	j = 0
        l2 = []
        (1...l.size).each \
        { 
                |i| 
                c += 1 if (l[i] < l[i - 1])
                if (l[i] < m) then
                        l2 << i - j
                        m, j = [l[i], i] 
                end
                mx = [mx, i - j].compact.max
        }
	
        r = c.to_f / l.size
	a, sd = nil, nil # stat(l2)
	
	return {'r' => r, 'mx' => mx.nil? ? l.size : mx, 'c' => l2.size, 
		'd' => l2.size.to_f / l.size, 'a' => a, 'sd' => sd, 
		'mn' => l.min.abs, 'cn' => l.select { |x| x < 0 }.size.to_f / l.size
		}.merge(z)
end

def mx(l, lr)
	z = mono(l, {})
	
	return [z.nil? ? 0 : z['mx'], l.size, lr]
end

def mx2(n)
	l = seq2(n)
	
	m = (0...l.size).max_by { |x| l[x] }
	
	mx1 = mx(l[0..m].map { |x| -x }, 'l')
	mx2 = mx(l[m..-1], 'r')
	
	case ARGV[0].to_i
		when 1
			mx = mx1
		when 2
			mx = mx2
		when 3
			mx = [mx1, mx2].max
	end
	
	d = d(n.to_s)
	return {'by' => [-mx[0], d], 'fmt' => ([n.to_s(2).length] + mx).join("\t")}
end

def mx1(n)
	z = mono(seq(n), {})
	mx = z['mx']
	d = d(n.to_s)
	return {'by' => [-mx, d]}
end
	
def mx_(n)
	return mx2(n)
end

def hard(c)
		
		
	l = [{'n' => 1, 'p' =>0}.merge(mx_(1))]
	
	loop \
	{
		l.sort_by! { |x| x['by'] }

		fmt = l[0]['fmt']
		return l[0] if (l.size == c)
		
		x = l.delete_at(rand([l.size, 50].min))
		
		
		p = x['p'] + 1
		n = x['n']
		
		x1 = x.dup
		x1['p'] = p
		l.push(x1)
		
		x2 = {}
		n |= (1 << p)
		
		x2['n'] = n
		x2['p'] = p
		x2.merge!(mx_(n))
		l.push(x2)
		
		$f.puts([l.size, fmt, x2].join("\t"))
		$f.flush
		
	}
	
	
end

$f = File.open("out#{ARGV[0]}.txt", 'w')

hard(10000)