compress5.rb

def f(n)
	
	n2 = n
	l = []
	while (n >= n2)
		l << (n % 2).to_s
		n = n.even? ? n / 2 : n * 3 + 1
	end
	return l
end

def compress(l)
	
	return 1 if (l.size == 1)
	s = 'a'

	loop \
	{
		l2 = (0...l.size).sort_by { |x| l[x..-1] }

		z = (0...(l2.size - 1)).to_a.map \
		{
			|x|
			i, j = l2[x], l2[x + 1]
			i, j = [j, i] if (i > j)
			t = 0
			t += 1 while (l[i + t] == l[j + t] && i + t < j && j + t < l2.size)
			[i, j, t]
		}.sort_by { |x| x[2] }.last

		i, j, t = z
		break if (t == 1)
		
		s2 = l[j, t]

		l[j, t] = s
		l[i, t] = s

		s = s.succ

	}

	return l.size

end

def best(a, l)
	
	l3 = []
	
	l.each \
	{
		|n, l2|
		a2 = a.dup
		a2[n] = l2
		l1 = a2.sort.map { |x| x[1] }.flatten
		c = compress(l1)
		l3 << [c, n]
	}
	return l3.min
end

a = {}
n = 3

a[n] = f(n)
n += 2

l = []
j = 0

500.times \
{

	l << [n, f(n)]
	n += 2

	if (l.size == 20) then
		c, n2 = best(a, l)
		puts([j, c, n2].join("\t"))
		$stdout.flush
		j += 1
		i = l.index { |x| x[0] == n2 }
		n2, l2 = l.delete_at(i)
		a[n2] = l2
		
	end
}