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 widthdiff(x, y)
	x.to_s(2).length - y.to_s(2).length
end

def widthratio(x, y)
	x.to_s(2).length.to_f / y.to_s(2).length
end

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

end

def count(x)
	n = n1 = x['n']
	l = [n]
	cg = nil
	l1 = []
	i = nil
	while (n >= n1 && n != 1)
		l1 << d(n.to_s(2)) - 0.5
		n = f1(n)
		cg = l.size if (cg.nil? && n < n1)
		l1.shift if (l1.size == 3)
		i = l.size if (i.nil? && l1.size == 2 && l1[0] * l1[1] < 0)
		l << n
	end
	ns = n1.to_s(2)
	cm = (0...l.size).max_by { |x| l[x] }
	return x.merge!({'cm' => cm,
		'cg' => cg.nil? ? 0 : cg,
		'm' => l[cm].to_s(2).length,
		'w' => widthdiff(l[cm], n1),
		'r' => widthratio(l[cm], n1),
		'c' => l.size,
		'd' => (0.5 - d(ns)).abs,
		'l' => l,
		'nl' => ns.length,
		'i' => i.nil? ? 0 : i,
		'j2' => i.nil? ? 0 : cm - i})
end

def out(a)

	fn = 'out.txt'
	if ($f.nil?) then
		$f = File.open(fn, 'w')
		$f.puts(a.keys.join("\t"))

		f2 = File.open('gnuplot.cmd', 'w')
		f2.puts('set colors classic; set key top left; plot \\')
		(a.keys - ['t']).each \
		{
			|x|
			z = (x == 'j2') ? 'lt 7' : ''
			f2.puts("'#{fn}' using (column('t')):(column('#{x}')) with line title '#{x}' #{z}, \\")
		}
		f2.puts
		f2.close
	end
	$f.puts(a.values.join("\t"))
	$f.flush
end

def next2(z, l, l2, w)
	out(z.select { |k, | !['l', 'n', 'd', 'r', 'p', 'c'].member?(k)}) if (z['t'] % 8 == 0)
	p = z['p'] + 1
	l << [z, count({'n'=>z['n'] + 2 ** p, 'p'=>p}), z.merge({'p'=>p})]
	l2 << z if (z['nl'] == w)
end


def hard(k)

	l = []
	l2 = []
	w = 100
	next2(count({'n' => 1, 'p' => 0}).merge({'t' => 0}), l, l2, w)

	j = 0
	n = 1
	c2 = nil
	loop \
	{
		l1 = (0...l.size).sort_by { |x| [-l[x][1][k], l[x][1]['d']] }

		if (j % 100 == 0) then
			a = l[l1[0]][1].select { |k, | !['l', 'n'].member?(k)}
			c1 = l.select { |x| x[1]['nl'] > w}.size

			$stderr.puts({'j' => j, 'c1' => c1, 'l2' => l2.size}.merge(a))
			return if (j >= 100 && a['cg'] <= 5)

			n += 1 if (l2.size != 0 && l2.size == c2)
			c2 = l2.size

			break if (n == 5)
		end

		i = l1[rand([l1.size, 20].min)]
		z = l.delete_at(i)

		next2(z[1].merge({'t' => j}), l, l2, w)
		next2(z[2].merge({'t' => j}), l, l2, w)

		l.delete_at((0...l.size).min_by { |x| l[x][0][k] }) if (l.size > 2000)
		j += 1
	}
	return l2
end

def restart(k)
	l = nil
	l = hard(k) while (l.nil?)
	return l
end

l = restart('j2')
f = File.open('mixdb.txt', 'w')
l.each { |x| f.puts(x.select { |k, | k != 'l' }.inspect) }
f.close