fit10.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 avg(l)
	return nil if (l.empty?)
	return sum(l) / l.size
	end
	
	
	def near2(l, j, l3)
	
	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..2)
	
	r0 = r.select { |x| l2[x]['d'] == 0 }
	p = r.map { |x| l[l2[x]['i']] }

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

	
	d = r.map { |x| 1.0 / l2[x]['d'] }
	
	
	t = sum(d)
	w = d.map { |x| x / t }
	
	
	z = 0
	r.each { |x| z += (w[x] * p[x][$c]) }
	return z
	
	end
	
	def inc(x, y)
	x['t'] += y
	x['c'] += 1
	return x
	end
	
	def avg(x)
	return x['t'] / x['c']
	end
	
	def reshuffle()
	
		l = $b.select { |x| x != 'c' }.shuffle
		$b[0...l.size] = l
	end
	
	def near(l, l3)

	reshuffle()
	s = {'t' => 0.0, 'c' => 0}
	
	e2 = {'a' => s.dup, 'b' => s.dup, 'c' => 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})
	end
	
	def subset(l2)
		
		l1 = (2..l2.size).to_a
		c = l1.delete_at(rand(l1.size))
		l3 = []
		c.times { l3 << l2.delete_at(rand(l2.size)) }
		return l3
	end
	
	def subset2(l2, f)
		l2 = l2.dup
		x = l2.pop
		return subset(l2) + (f ? [x] : [])
	end
	
	def fmt(l1)
		
	x = {}
	['a', 'b', 'c', 'i', 'l3'].each \
	{
		|k|
		z = l1[k]
		z = sprintf("%.3f", z).to_f if (z.is_a?(Numeric) && z != z.to_i)
		x[k] = z
	}
	$stderr.puts(x.inspect)
	
	end
	
	def stats()
		l = []
		(0..1).each \
		{
			|i2|
			l << stat($l0.select { |x| x['i2'] == i2 }.map { |x| x['a'] })
		}
		$f.puts(l.join("\t"))
		$f.flush
	end
	
	def compare(l)

		m = l[0].size - 1
		l2 = (($c + 1)..m).to_a
		i = 0
		
		begin
			l3 = subset2(l2, (i % 2 == 0))
			
			l3.sort!
			next if ($s0.member?(l3) || $s.member?(l3))
	
			$s0[l3] = nil
			$l0 << near(l, l3).merge({'l3' => l3, 'i2' => i % 2})
			
			i += 1
		end while (i < 40)
		
		stats()
		
		
		$l0 = $l0.sort_by { |x| x['a'] }
		
		a, = stat($l0.map { |x| x['a'] })
		l4 = $l0.select { |x| x['a'] < a }
		
		c = 20
		i = (((c.to_f - $n) / c) * (l4.size - 1)).to_i
		i = 0 if (i < 0)
		i = 0
		
		return $l0.delete_at(i).merge({'i' => i})
	end
	
	def abc(n)
		
	$b = []
	a = {'a' => 2, 'b' => 2, 'c' => 1}
	
	a.each \
	{
		|k, v|
		$b += [k] * (v.to_f / 5 * n).to_i
	}
	$b[$b.size...n] = ['c'] * (n - $b.size)
	
	end
	
	$n = 40
	$g = 50
	l = sample(2000)
	l.shuffle!
	
	$stderr.puts("ls=#{l.size}")
	
	# out('out', l)
	
	abc(l.size)
	
	
	$c = 2
	
	$m = 4

	$s = {}
	$s0 = {}
	$l0 = []
	$f = File.open('out2.txt', 'w')

	$n = 0
	loop \
	{

	l1 = compare(l)
	
	fmt(l1)
	
	puts([l1['l3'].size, l1['a'], l1['b'], l1['c'], l1['i']].join("\t"))
	$stdout.flush

	$s[l1['l3']] = nil

	l = l.transpose
	l << l1['l2']
	l = l.transpose
	$n += 1
	}