extend19.rb

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

def stat(l)
        return 0, 0, 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, l.max.to_f, l.min.to_f
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
        }
	return if (c == 0 || mx.nil? || l2.empty?)
	
        r = c.to_f / l.size
	a, sd = stat(l2)
	
	return {'r' => r, 'mx' => mx, 'c' => l2.size, 
		'd' => l2.size.to_f / l.size, 'a' => a, 'sd' => sd
		}.merge(z)
end

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

def f2(n)

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

end


def adv(x, w1)

	n1 = n = x['n']
	ns = n.to_s(2)
	x['d'] = d(ns)
	l = [n]
	
	while (n >= n1 && n != 1)

		n = f2(n)
		l << n
	end
	
	j = (0...l.size).max_by { |x| l[x] }
	
	mx1 = mx(l[0..j].map { |x| -x })
	mx2 = mx(l[j..-1])
	
	x['mx'] = [mx1, mx2].max
	
	x['mx1'] = mx1
	x['mx2'] = mx2
	
	x['ns'] = ns.length
	x['ls'] = l.size
	x['j'] = j


	x['z'] = x.values_at(*w1)
	return x


end

def next2(z, w1)
	
	l = [z]
	p = z['p'] + 1
	
	l << adv({'n'=>z['n'] + 2**p, 'p'=>p}, w1)
	l << z.merge({'p'=>p})
	return l
end

def val(l, a, x)
	
	t = 0
	l.size.times \
	{
		|y|
		next if (x == y)
		
		i, j, s = x < y ? [x, y, 1] : [y, x, -1]
		t += a[[i, j]] * s
	}
	return t
end

def val2(l, a)
	return (0...l.size).map { |x| val(l, a, x) }
end

def insert(l, a, r, z)
	
	l << z
	(l.size - 1).times \
	{
		|j|
		t = 0
		l[0].size.times { |i| t += l[j][i] <=> l[-1][i] }
		a[[j, l.size - 1]] = t
	}
	r << val(l, a, l.size - 1) if (!l.empty?)
	(l.size - 1).times \
	{
		|j|
		r[j] += a[[j, l.size - 1]]
	}

end

def delete(l, a, r, x)

	r.size.times \
	{
		|y|
		next if (x == y)
		i, j, s = x < y ? [x, y, 1] : [y, x, -1]
		
		r[y] += a[[i, j]] * s
	}
	r.delete_at(x)

	l.delete_at(x)
	(0...x).each \
	{
		|i|
		(x..(l.size)).each \
		{
			|j|
			a[[i, j]] = a[[i, j + 1]]
		}
	}
	(x..l.size).each \
	{
		|i|
		((i + 1)..(l.size)).each \
		{
			|j|
			a[[i, j]] = a[[i + 1, j + 1]]
		}
	}
	l.size.times { |j| a.delete([j, l.size]) }
	
end

def test(w, w1)
	
	puts(w.join("\t"))
	File.open('db.txt').readlines.map { |x| Kernel.eval(x) }.each_with_index \
	{
		|x, i|
		puts(adv(x, w1).values_at(*w).join("\t"))
		puts if ((i + 1) % 100 == 0)
	}
end


w = ['mx', 'mx1', 'mx2', 'ns', 'ls', 'j']
w1 = ['mx1', 'mx2']

# test(w, w1); exit


l = [next2({'n'=>1, 'p'=>0}, w1)]
l1 = [l[0][1]['z']]

a = {}
r = []

puts('# ' + Time.now.to_s)
puts((['ls'] + w).join("\t"))
t = Time.now.to_i

5000.times \
{
	|i|
	$stderr.puts([i, sprintf('%.1fm', (Time.now.to_i - t) / 60.0), Time.now.to_s].join("\t")) if (i % 100 == 0)
	
	l2 = (0...l.size).sort_by { |x| r[x] }.reverse
	
	j = l2[rand([l.size, 100].min)]
	
	z = l.delete_at(j)
	delete(l1, a, r, j)
	
	l << next2(z[1], w1)
	insert(l1, a, r, l[-1][1]['z'])
	
	l << next2(z[2], w1)
	insert(l1, a, r, l[-1][1]['z'])
	
	puts([l.size, z[1].values_at(*w)].join("\t"))
	$stdout.flush
	
#	p(val2(l1, a) == r)
}

puts('# ' + Time.now.to_s)