search3.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)

	l = [] if (l.nil?)
	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
        }

	mx = 0 if (mx.nil?)
	
	return {'mx' => mx, 'ls3' => l.size}
end

def f2(n)

	return n

end


def adv(x)

	x['a'] = true
	n1 = n = x['n']
	ns = n.to_s(2)
	x['d'] = d(ns)
	l = [n]

	c = 0
	j2 = nil
	while (n >= n1 && n != 1)

		n = (n * 3 + 1) / 2 while (n.odd?)
		while (n.even?)
			c += 1
			n /= 2 
		end
		j2 = l.size if (j2.nil? && c >= ns.length)
		l << n
	end

	j = (0...l.size).max_by { |x| l[x] }
	
	x['ls'] = l.size
	x['ns'] = ns.length
	x['j'] = j
	x['ls2'] = l.size - j

	j2 = l.size if (j2.nil?)
	return x.merge(mono(l[j2..-1]))
	

end

def insert(l, x)
	l << x
	
end

def delete(l, j)
	z = l.delete_at(j)
	return z
end

def sum(l)

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

def rank(l, w1)
	
	
	l2 = []
	
	l.size.times \
	{ 
		|x| 
		l1 = l[x].values_at(*w1)
		a = {}
		w1.size.times \
		{
			|i|
			a[w1[i]] = l1[i]
		}
		l2 << [x, a]
	}
	
	w1.each \
	{
		|k|
		l1 = l2.map { |x| x[1][k] }
		
		a, sd, = stat(l1)
		
		sd = 1 if (sd == 0)
		l2.each \
		{
			|x|
			x[1][k + 'b'] = (x[1][k] - a) / sd
		}
	}

	b = w1.map { |x| x + 'b' }
	l2.each \
	{
		|x|
		x[1]['z'] = sum(x[1].values_at(*b))
	}

	l2.sort_by! { |x| [x[1]['z'], x[1]['d']] }
	l2.reverse!
		
	return l2.map { |x| x[0] }
	
end

def right(s, c)
	(s.length - c)...s.length
end

def opt(w, w1, c)
	
	l = []

	50.times { insert(l, adv({'n'=>rand(2**20)})) }
	
	puts('# ' + Time.now.to_s)
	puts(w.join("\t"))
	t = Time.now.to_i
	seen = {0=>nil}
	k = 0
	
	loop \
	{
		break if (k == c)
		$stderr.puts([k, sprintf('%.1fm', (Time.now.to_i - t) / 60.0), Time.now.to_s].join("\t")) if (k % 100 == 0)
		
		l2 = rank(l, w1)
		
		begin
			
			i = rand(l2.size / 2)
			
			if (rand(1) == 0) then
				
				j = rand(l2.size / 2)
				j += 1 if (i == j)
				
				l1 = [l[i]['n'].to_s(2), l[j]['n'].to_s(2)]
				
				l1.reverse! if (l1[0].length > l1[1].length)
				
				s2 = 1 + rand(l1[1].length)
				
				s1 = 1 + rand([l1[1].length - s2 + 1, l1[0].length].min)
				
				r1, r2 = [[0...s1, right(l1[1], s2)], [right(l1[0], s1), 0...s2]][rand(2)]
				
				ns = l1[0][r1] + l1[1][r2]
				
			else
				ns1 = l[i]['n'].to_s(2)
				r = rand(ns1.length)
				ns = ns1.dup
				ns[r, 1] = (1 - ns[r, 1].to_i).to_s
			end
			
			n = ns.to_i(2)
		end while (seen.member?(n))
		
		seen[n] = nil
		z = adv({'n' => n})

		insert(l, z)
		l1 = l2.select { |x| l[x]['a'] }
				
		l[l1[0]]['a'] = false if (l1.size > 100)
		puts([l[l1[0]].values_at(*w)].join("\t"))
		$stdout.flush

		if (l.size - l1.size > 500) then
			l1 = l2.select { |x| !l[x]['a'] }
			delete(l, l1[-1])
		end

		k += 1
	}

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

end

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




w = ['ns', 'ls', 'ls2', 'j', 'ls3', 'mx']
w1 = ['ls', 'j', 'ls2', 'ls3']

# test(w); exit

opt(w, w1, nil)