fit13.rb

def f2(n)
	
	n = (n * 3 + 1) / 2 while (n % 2 == 1)
	n /= 2 while (n % 2 == 0)
	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'] * $g).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 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 stat(l)
	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 dist(l)
	
	l2 = []
	l.each_with_index \
	{
	|x, i|
	h = x[1]['h2']
	l2[h] = [] if (l2[h].nil?)
	l2[h] << i
	}
	l1 = (0...l2.size).sort_by { |i| l2[i].nil? ? 0 : l2[i].size }
	
	return l2, l1
	end
	
	def rank(l1, l2)
	
	l1h, l1s = dist(l1)
	l2h, l2s = dist(l2)
	
	j = l1s.find { |x| !l2h[x].nil? && (l1h[x].nil? || l1h[x].size < $n) }
	
	j = l2h.size - 1 if (j.nil?)
	k = l2s.find { |x| !l2h[x].nil? }
	
	l = (0...l2.size).to_a
	l = l.sort_by { |x| l2[x][1]['ls'] }
	k = l.find { |x| x != j }
	
	
	return l2h[j][rand(l2h[j].size)], k
	
	end
	
	def opt(c)
	
	l = []
	l1 = []
	
	insert(l, next2({'n'=>1, 'p'=>0}))
	
	
	puts('# ' + Time.now.to_s)
	t = Time.now.to_i
	
	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)
	
	j, k = rank(l1, l)
	
	if (l.size > 1000) then
	
	z2 = delete(l, [j, k].max)
	z1 = delete(l, [j, k].min)
	
	l1 += [z1, z2]
	z = j < k ? z1 : z2
	else
	z = delete(l, j)
	l1 += [z]
	end
	
	insert(l, next2(z[1]))
	insert(l, next2(z[2]))
	
	$stdout.flush
	}
	
	puts('# ' + Time.now.to_s)
	return l1.map { |x| x[1] }
	end
	
	def stat2(l, t)
	return stat(l).map { |x| x / t }
	end
	
	def stat1(l)
		l1 = stat(l)
		l1 = l1.map { |x| sprintf("%.3f", x).to_f }
		return {'a' => l1[0], 'sd' => l1[1], 'mx' => l1[2], 'mn' => l1[3] }
	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 { |y| y.length }, nl)
	
	l1 = ns.split(/1+/)
	l1.shift
	asdm0 = stat2(l1.map { |y| y.length }, nl)
	
	return [nl, x['ls'], x['h2'], d(ns), d(nsh), d(nsl), asdm1].flatten
	end
	
	def out(fn, l)
	
	f = File.open("#{fn}.txt", 'w')
	l.each { |x| f.puts(x.join("\t")) }
	f.close
	
	end
	
	def sample(c)
	
	l = opt(c)
	
	a = {}
	h = {}
	l.each \
	{
	|x|
	n = x['n']
	h2 = x['h2']
	
	h[h2] = h.fetch(h2, {}).merge!({ n => nil })
	a[n] = x
	}
	# h.sort.each { |k, v| p([k, v.size]) }; exit;
	
	
	l3 = []
	
	c1 = 10
	
	h1 = h.select { |k, v| v.size >= c1 }.sort
	
	h1.each_with_index \
	{
	|kv, n|
	
	k, v = kv
	l1 = v.keys.sort
	
	c1.times \
	{
	|i|
	n = l1[(i.to_f / (c1 - 1) * (l1.size - 1)).to_i]
	l3 << a[n]
	}
	}
	
	l2 = l3.map { |x| data(x) }
	
	return l2
	
	end
	
	def av(l)
	return nil if (l.empty?)
	return sum(l) / l.size
	end
	
	def d0(p, d)
		
		r = (0...p.size)
		r0 = r.select { |x| !d[x].finite? }

		return sum(r0.map { |x| p[x][$c] }) / r0.size if (!r0.empty?) 

		t = sum(d)
		w = d.map { |x| x / t }
		
		z = 0
		r.each { |x| z += (w[x] * p[x][$c]) }
		return z
		
	end
	
	def d1(p, d)

		return p[0][$c] if (d.size == 1)
		
		t = sum(d)
		
		return av(p.map { |x| x[$c] }) if (t == 0)
		w = d.map { |x| 1.0 - x / t }

		t2 = sum(w)
		
		z = 0
		p.size.times { |x| z += (w[x] / t2 * p[x][$c]) }
		return z
		
	end
	
	def near2(l, j, a)
	
	l3 = a['l']
	l2 = []
	l.size.times \
	{
	|i|
	next if (i == j)
	next if ($b[i] != 'a')
	d = 0
	l3.each { |x| d += (l[i][x] - l[j][x]) ** 2 }
	l2 << {'i' => i, 'd' => d}
	}
	l2 = l2.sort_by { |x| x['d'] }
	
	r = (0..a['r'])
	p = r.map { |x| l[l2[x]['i']] }
	
	return a['d'] == 0 ? d0(p, r.map { |x| 1.0 / l2[x]['d'] }) : d1(p, r.map { |x| l2[x]['d'] })
	end
	
	
	def inc(x, y)
	x['t'] += y
	x['c'] += 1
	return x
	end
	
	def avg(x)
	return x['t'] / x['c']
	end
	
	def near(l, l3)

	s = {'t' => 0.0, 'c' => 0}
	
	e2 = {'a' => s.dup, 'b' => s.dup}
	l2 = []
	l.size.times \
	{
	|i|
	x = near2(l, i, l3)
	e = (l[i][$c] - x) ** 2
	inc(e2[$b[i]], e)
	l2 << x
	}
	return Hash[e2.keys.map { |x| [x, avg(e2[x])] }].merge({'l2' => l2, 'l' => l3['l']})
	end
	
	def abc(n)
		
	$b = []
	a = {'a' => 2, 'b' => 2}
	
	t = sum(a.values)
	a.each \
	{
		|k, v|
		$b += [k] * (v.to_f / t * n).to_i
	}
	$b[$b.size...n] = ['c'] * (n - $b.size)
	
	end

	
	$n = 40
	$g = 50
	l = sample(1000)
	$stderr.puts("ls=#{l.size}")

	l.shuffle!
	abc(l.size)
	
	m = l.size / 2
	
	
	# out('out', l)
	
	
	$c = 2
	
	$s = {}
	$s0 = {}

	l3 =  (($c + 1)...l[0].size).to_a
	a = {'l' => l3, 'd' => 1, 'r' => 10}

	l1 = []
	
	(2 ** l3.size).times \
	{
		|n|
		
		l3b = []
		n2 = n
		
		l3.size.times \
		{
			|j|
			l3b << l3[j] if (n2 & 1 == 1)
			n2 >>= 1
		}
		
		l1 << near(l, a.merge({'l' => l3b}))
		$stderr.puts([l1[-1]['a'], l1[-1]['b'], l3b.reverse, n.to_s(2)].inspect)
	}
	
	out('out', l1.sort_by { |x| x['a'] }.map { |x| [x['a'], x['b'], x['l'].size] })