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

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)

end

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

end


def mx3(n)
	ns = n.to_s(2)
	nl = ns.length
	l1 = ns.split(/0+/).map { |x| x.length }
	l0 = [ns.split(/1+/)[1..-1]].compact.flatten.map { |x| x.length }

	mx = [l0.max, l1.max].compact.max
	return {'mx' => mx, 'mxs' => mx.to_f / nl}
end

def count(x, k)
	n = n1 = x['n']
	i = 0
	l = [n]
	l1 = []
	i = nil

	while (n >= n1 && n != 1)
		n = {'packed' => true, 'unpacked' => false}[$w] ? f1(n) : f2(n)
		l << n

		l1 << d(n.to_s(2)) - 0.5 if (k == 'j2nl')
		l1.shift if (l1.size == 3)
		i = l.size if (i.nil? && l1.size == 2 && l1[0] * l1[1] < 0)

	end


	nl = x['ns'].length
	cm = (0...l.size).max_by { |x| l[x] }
	j2 =  i.nil? ? 0 : cm - i

	j = jl = jr = 0
	if (['cm', 'jlcm', 'cmjl'].member?(k)) then

		l.each_with_index \
		{
			|n, i|
			next if (!n.odd?)

			j += 1
			i < cm ? jl += 1 : jr += 1
		}

		return nil if (k == 'jlcm' && n1 >= 10 && jl == cm)
		x.merge!({'j' => j,
			'jl' => jl,
			'jr' => jr,
			'cmj' => cm - j,
			'cmjl' => cm - jl,
			'jlcm' => jl.to_f / (cm == 0 ? 1 : cm)})
	end

	if (['mc', 'mcs'].member?(k)) then

		mx = {'mx' => 0, 'mxs' => 0, 'mw' => 0, 'mi' => 0, k => 0}
		k2 = {'mc' => 'mx', 'mcs' => 'mxs'}[k]
		l[0..cm].each_with_index \
		{
			|n, i|

			mx = [mx, mx3(n).merge({'mw' => i - mx['mi'], 'mi' => i, k => mx[k] + 1})].max_by { |x| x[k2] }
		}
		x.merge!(mx)
	end

	return x.merge({
		'd' => (0.5 - d(x['ns'])).abs,
		'cm' => cm,
		'c' => l.size,
		'nl' => nl,
		'j2nl' => j2 - nl})
end


def init1(w, m)

	l = []
	b = 1
	while (w > 0)
		t = [w, m].min
		r = (t <= 1) ? 1 : rand(t) + 1
		l << [b] * r
		b ^= 1
		w -= r
	end
	s = l.flatten.join
	return s
end

def init2(w, m)

	return dense(w, m.to_f / w)
end

def init3(w, m)
	r = m.to_f / w
	return '1' + (1...w).map { rand < r ? '0' : '1' }.join

end


def init(w, k)

	l = []

	(1..w).each \
	{
		|w|
		3.times \
		{
			|i|
			m = rand(w)
			ns = nil
			case (i)
				when 0
					ns = init1(w, m)
				when 1
					ns = init2(w, m)
				when 2
					ns = init3(w, m)
			end

			z = count({'ns' => ns, 'n' => ns.to_i(2)}, k)
			redo if (z.nil?)

			l << z
		}
	}
	h = (0..w).map { [] }
	l.each { |x| h[x['nl']] << x }


	return h
end

def get(h, i)

	m = h[i].size
	r = h[i].size / 4

	return h[i][rand(r == 0 ? m : r)]['ns']
end

def out1(fn, l, l2)

	$fn = {} if ($fn.nil?)

	if (!$fn.member?(fn)) then
		$fn[fn] = File.open(fn, 'w')
		$fn[fn].puts(l[0].keys.join("\t"))

		f = File.open('gnuplot.cmd', 'w')
		l2.each { |x| f.puts(x) }
		f.close
	end

	f = $fn[fn]
	l.each { |x| f.puts(x.values.join("\t")) }
	f.flush

end

def fmt(s, fn, l2)

	return ["#{s} plot \\"] + l2.map { |x| "'#{fn}' using #{x}, \\" } + ['']

end

def out2(fn, l, l2, s)

	out1(fn, l, fmt(s, fn, l2))

end


def order(h)

	return Hash[h.sort_by { |k, v| v }.reverse]
end

def opt(w, k)

	h = init(w, k)


	n = c = c2 = m = 0
	mx2 = nil
	ops1 = {}
	ops2 = {}
	mxc = 1e5
#	mxc = 1e3
	loop \
	{
		t = rand(h.size - 2) + 2

		case (op = ['mut', 'mix', 'cut', 'cut2', 'up'][rand(5)])
			when 'mut'
				ns1 = get(h, t)
				ns = ns1.dup
				i = rand(t - 1) + 1
				ns[i, 1] = (ns1[i, 1].to_i ^ 1).to_s

			when 'mix'
				ns1 = get(h, t)
				ns2 = get(h, t)
				ns = ''
				t.times \
				{
					|i|
					ns[i, 1] = [ns1[i, 1], ns2[i, 1]][rand(2)]
				}

			when 'cut'
				ns1 = get(h, t)
				ns2 = get(h, t)
				i = rand(t)
				ns = ns1[0...i] + ns2[i..-1]

			when 'cut2'
				ns1 = get(h, t)
				ns2 = get(h, r = rand(t - 1) + 1)
				ns = ns1.dup
				r2 = rand(r - 1) + 1
				ns[-r2..-1] = ns2[-r2..-1]

			when 'up'
				r = rand(t - 1) + 1
				ns1 = get(h, r)
				ns = '1' + (0...(t - r - 1)).map { rand(2).to_s }.join + ns1

		end

		z = count({'ns' => ns, 'n' => ns.to_i(2)}, k)


		if (!z.nil? && h[nl = z['nl']].index { |x| x['n'] == z['n'] }.nil?) then

			x = z[k]
			h[nl] << z
			h[nl].sort_by! { |x| [-x[k], -x['cm']] }
			if (h[nl].size > 100) then
				x2 = h[nl].pop

				a = {'n2' => 0, 'cn' => 0}


				if (x2[k] < x) then
					a['n2'] = n if (n % 20 == 0)
					c += 1
					ops1[op] = ops1.fetch(op, 0) + 1
				end

				mx = h[1..-1].map { |x| x.first[k] }
				if (mx == mx2) then
					c2 += 1
					break if (c2 > mxc)
				else
					a['cn'] = n
					c2 = 0
					ops2[op] = ops2.fetch(op, 0) + 1
				end

				mx2 = mx

				if (!a.values.select { |x| x != 0 }.empty?) then

					l = ['c', 'c2'].map \
					{
						|x|
						[
						"(column('n')):(column('#{x}')) with line lw 3 lc 2 axes x1y2",
						"(column('n')):(column('nl')) pt 7 ps 0.5 lc 1 title 'nl'",
						"(column('n2')):(0) pt 5 ps 0.5",
						"(column('cn')):(1) pt 5 ps 0.5",
						]
					}

					out1('out.txt',
						[a.merge({'n' => n, 'nl' => nl, 'c' => c, 'c2' => c2.to_f / mxc * 100})],
						fmt("set colors classic; set ytics nomirror; set y2tics; set key center right box opaque;",
						'out.txt',
						l[0]) + fmt('pause -1;', 'out.txt', l[1]))
					m += 1
				end

			end
		end

		$stderr.puts([{'n' => sprintf("%.3g", n + 1), 'm' => m, 'c2' => (c2.to_f / mxc * 100).round(1)}, order(ops1), order(ops2)].inspect) if ((n + 1) % 5e4 == 0)

		n += 1
	}
	return h[1..-1].map { |x| x.first }

end

def adj(x, l1, l2, y)
	return if ((i = l1.index(x)).nil?)
	l2[i] += ' ' + y
end

def review(fn, k)

	l = File.open(fn).readlines.map { |x| Kernel.eval(x) }

	l1 = [k, 'cm', 'c'].uniq

	l1 += ['j', 'jl', 'jr'] if (['jlcm', 'cmjl', 'cm'].member?(k))
	l1 += ['cmj', 'cmjl'] if (['cm'].member?(k))
	l1 += ['mx', 'mw'] if (['mc', 'mcs'].member?(k))

	l2 = l1.map { |x| "(column('#{x}')) with line" }

	adj('jlcm', l1, l2, 'axes x1y2 lw 2')

	l2[5, 0] = "0 lt bgnd title ''" if (!l2[5].nil?)

	adj('mc', l1, l2, 'axes x1y2')
	adj('mcs', l1, l2, 'axes x1y2')
	adj('mx', l1, l2, 'axes x1y2')


	out2('out.txt', l.map { |x| x.select { |x, | l1.member?(x) } },
	l2, 'set colors classic; set ytics nomirror; set y2tics; set key top left box opaque;')
	exit
end


fn = 'mixdb.txt'

$x = 'unpacked'

# k = 'cmjl'
# k = 'jlcm'
# k = 'j2nl'; $x = 'packed'
# k = 'mc'
# k = 'mcs'
k = 'cm'

review(fn, k) if (File.exist?(fn))

l = opt(100, k)
f = File.open(fn, 'w')
l.each { |x| f.puts(x.inspect) }
f.close