data6b.rb

def f2(n)

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

end

def adv(x)

	n1 = n = x['n']
	l = [n]
	while (n >= n1 && n != 1)
		
		n = f2(n)
		l << n
	end
	

	x['l'] = l
	x['ls'] = l.size
	
	x['ns'] = x['n'].to_s(2).length
	x['h'] = x['ls'].to_f / x['ns']
	x['h2'] = (x['h'] * 50).to_i
	
	return x
	
end

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

def stat(l)
	l = [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 range(l, s)
	
	['ls', 'ns', 'h2'].each \
	{
		|k|
		a, sd = stat(l.map { |x| x[1][k] })
		s[k] = {'a' => a, 'sd' => sd}
	}
	
end

def next1(x, r)
	x = next2(x)
	return x if (r.empty?)
	['ls', 'ns', 'h2'].each \
	{
		|k|
		
		x[1][k + 'z'] = (x[1][k] - r[k]['a']) / r[k]['sd']
	}
	x[1]['z'] = x[1]['lsz'] + x[1]['nsz'] + x[1]['h2z']
	return x
end

def opt(c)
	
	l1 = []
	l2 = []
	
	l1 << next2({'n'=>1, 'p'=>0})

	puts('# ' + Time.now.to_s)
	t = Time.now.to_i

	r = {}
	w = ['z', 'h2', 'ls', 'ns', 'h2b', 'r']
#	w = ['h2b']
	
	c.times \
	{
		|i|
		$stderr.puts([i, sprintf('%.1fm', (Time.now.to_i - t) / 60.0), Time.now.to_s].join("\t")) if (i % 100 == 0)
		
		range(l1, r) if (w.include?('z') && (i + 1) % 100 == 0)

		w.push(w.shift)
		
		if (['z', 'h2', 'ls', 'ns'].include?(w.first)) then
			k = {0 => 'z', 1 => 'h2', 2 => 'ls', 3 => 'ns'}[w.first]
			l1 = l1.sort_by { |x| x[1][k].nil? ? 0 : x[1][k] }.reverse
			j = rand([50, l1.size].min)
		elsif (w.first == 'h2b')
			h1 = dist(l1.map { |x| x[1] }, 'h2')
			h2 = dist(l2.map { |x| x[1] }, 'h2')
			
			h3 = Hash[h1.keys.map { |x| [x, h2.fetch(x, [])] }]

			k, = h3.select { |k, v| v.size < 100 }.min_by { |k, v| v.size }
			k, = h3.max if (k.nil?)

			v = h1[k]
						
			j = v[rand(v.size)]['i']
			
#			puts([l1[j][1]['h2'], l1[j][1]['ls']].join("\t"))
#			$stdout.flush
		else
			j = rand(l1.size)
		end
		
		z = l1.delete_at(j)

		l1.delete_at((0...l1.size).min_by { |x| l1[x][1]['ls'] }) if (l1.size > 500)
		
		l2 << z
		l1 << next1(z[1], r)
		l1 << next1(z[2], r)
	}

	return l2.map { |x| x[1].reject { |k, v| k == 'l' } }
end

def out(fn, l)
	
	f = File.open("#{fn}.txt", 'w')
	f.puts(l[0].keys.join("\t"))
	l.each { |x| f.puts(x.values.join("\t")) }
	f.close
	
end

def dist(l, k)
	
	h = {}
	l.each_with_index \
	{
		|x, i|
		y = x[k]
		h[y] = [] if (!h.member?(y))
		h[y] << x.merge({'i' => i})
	}
	return h
end

def slice(h, k, l2)
	
	c = 10
	h.select { |x, v| v.size >= c }.sort.each \
	{
		|x, v|

		l = h[x].map { |x| x[k] }
		mn = l.min
		mx = l.max
		
		c.times \
		{
			|y|
			k1 = mn + (y.to_f / (c - 1)) * (mx - mn)
			x1 = h[x].min_by { |z| (z[k] - k1).abs }
			next if (x1.member?('.'))
			x1['.'] = nil
			l2 << x1
		}
	}
end

def sample(c)

	l2 = []
	l1 = []
	3.times \
	{
		l = opt(c)
		l1 += l
#		out('out', l)
		h = dist(l, 'h2')
		slice(h, 'ls', l2)
		slice(h, 'ns', l2)
	}
#	out('out2', l2)

	h = dist(l1.select { |x| x['ls'] >= 20 }, 'h2')
	l3 = []
	slice(h, 'ls', l3)
	slice(h, 'ns', l3)
#	out('out3', l3)
	l4 = l3.sort_by { |x| x['h2'] }
#	out('out4', l4)
	return l4
end

def stat2(l, t)
	return Hash[[['a', 'sd', 'mx' , 'mn'], stat(l).map { |x| x / t }].transpose]
end

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

def data(x)
	
	n = x['n']
	ns = n.to_s(2)
	nl = ns.length
	m = nl / 2
	
	nsh = ns[0..m]
	nsl = ns[m..-1]
	
	asdm1 = stat2(ns.split(/0+/).map { |x| x.length }, nl)
	
	l1 = ns.split(/1+/)
	l1.shift
	asdm0 = stat2(l1.map { |x| x.length }, nl)
	
	return {'nl' => nl, 'ls' => x['ls'], 'h2' => x['h2'], 'd' => d(ns), 'dh' => d(nsh), 'dl' => d(nsl)}.merge(asdm1)
end


out('data', sample(5000).map { |x| data(x) })