def f2(n)
	return n.odd? ? (n * 3 + 1) / 2 : n / 2

end

def dense(w, d)
	w2 = w - 1

	a = (0...w2).to_a
	s = '0' * w2
	(1..(d * w - 1)).map { a.delete_at(rand(a.size)) }.each { |x| s[x, 1] = '1' }
	return ('1' + s).to_i(2)

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 stat2(l, t, n)
	return Hash[[["a#{n}", "sd#{n}", "mx#{n}"], stat(l)[0..2].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(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, 1)

	l1 = ns.split(/1+/)

	l1.shift
	asdm0 = stat2(l1.map { |x| x.length }, nl, 0)

	return {'n' => n, 'ns' => ns, 'nl' => nl, 'd' => d(ns), 'dh' => d(nsh), 'dl' => d(nsl)}.merge(asdm1).merge(asdm0)
end

def sum(l)

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

def count(n)

	n1 = n
	l = [n]
	begin
		n = f2(n)
		l << n
	end while n > n1


	m = (0...l.size).max_by { |x| l[x] }
	r = l[m].to_s(2).length - n1.to_s(2).length

	return {'c' => l.size, 'n' => n1, 'l' => l, 'm' => m, 'r' => r}
end

def load(d)

	l = Dir.glob("#{d}/*").select { |x| x =~ /out\d+.txt$/}
	n = l.size

	i = n - 1
	a = Kernel.eval(File.open("#{d}/out#{i}.txt").readlines[0])

	l = a['lb'].map { |x| x.size }

	raise if (sum(l) != 0)
	return a
end

def dot(x, z)

	t = z['c']

	(z.keys - ['c']).each { |v| t += z[v] * x[v] }
	return t

end

def detect(n, a, seen)

	mx = 500

	if (seen.member?(n)) then
		seen['h'] += 1
		return seen[n]
	end

	x1 = data(n)
	i = 0

	w = 1.0
	x1['wr'] = 1.0
	loop \
	{

		x2 = {}

		(a['v'] + ['wr']).each \
		{
			|vy|

			x2[vy] = dot(x1, a[vy].select { |k, x| (a['v'] + ['c']).member?(k) })
		}

		x1 = x2
		w *= x1['wr']

		i += 1
		break if (w < 1.0)

		if (i == mx) then
			$stderr.puts("limit #{mx} on #{n}")
			break
		end

	}
	seen[n] = i
	return i

end

def dist(c, seen)

	l = []
	3.times {
		l += (0...c).map \
		{
			|i|
			n = dense(100, i.to_f / (c - 1))
			next if (seen.member?(n))
			seen[n] = nil
			count(n)
		}.compact
	}
	l.sort_by! { |x| x['m'] }
	l.reverse!
	return l
end

def mono(l1)

	l = l1.map { |x| x['a'] }
	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, 'ls' => l.size, 'l' => l1}
end

def avg(l2)

	m = 20
	c = 0
	t = 0
	l = []
	l1 = []
	l2.each \
	{
		|x|
		l << x['z']
		t += l[-1]
		t -= l.shift if (l.size > m)
		if (l.size == m) then
			a = t.to_f / l.size
			x['a'] = a
			l1 << {'a' => a, 'w' => x['w'] }
		end
	}
	return mono(l1)

end

def dist2()

	l = []

	seen = {}
	5.times { l += dist(500, seen).select { |x| x['m'] >= 50} }

	return l.sort_by { |x| -x['m'] }
end

def out(fn, l)

	f = File.open(fn, 'w')
	f.puts(l[0].keys.join("\t"))

	l.each { |x| f.puts(x.values.join("\t")) }
	f.close

	f = File.open('gnuplot.cmd', 'w')
	f.print('set colors classic; set ytics nomirror; set y2tics; set y2range [0:1]; plot [][0:] ')

	(l[0].keys - ['j']).each_with_index \
	{
		|x, i|
		z = ['d'].member?(x) ? 2 : 1
		f.puts("'#{fn}' using (column('j')):(column('#{x}')) with line title '#{x}' axes x1y#{z},\\")
	}
	f.puts("0.5 axes x1y2 lt 3")
	f.puts
	f.close

end

def test(d, l)

	a = load(d)

	seen = {'h' => 0}
	seen2 = {}

	l1 = []
	l[0...10].each_with_index \
	{
		|z, j|

		l2 = []
		z['l'][0..z['m']].each \
		{
			|x|

			s = x.to_s(2)
			l2 << {'w' => s.length, 'z' => detect(x, a, seen), 'd' => d(s)}
		}
		l2[0]['a'] = nil
		l1 << avg(l2).merge('l2' => l2)

		if (seen.member?('h')) then
			$stderr.puts("#{j} hits #{seen['h']}")  if (seen['h']  > 0 && !seen2.member?(seen['h']))
			seen2[seen['h']] = nil
		end
	}

	return l1.map { |x| {'d' => d, 'mx' => x['mx'], 'ls' => x['ls'], 'l2' => x['l2'] }}
end

l = dist2()
$stderr.puts("count #{l.size}")

l1 = []
Dir.glob("out/*").sort_by { |x| x.split("/")[1].to_i }.each \
{
	|d|
	l1 << test(d, l)
	$stderr.puts(([d] + l1[-1].map { |x| [x['mx'], x['ls']] }).inspect)
}

l2 = []
j = 0
(0...10).each \
{
	|i|
	z = l1.min_by { |x| x[i]['mx'] }
	p([z[i]['d'], z[i]['mx'], z[i]['ls'], l[i]['n']])

	z[i]['l2'].each \
	{
		|x|
		l2 << { 'j' => j}.merge(x)
		j += 1
	}
	l2 << {}
	j += 20
}

out('out.txt', l2)