compress10.rb

def compress(l)
		
	s = 'a'
	l1 = []
	a = {}
	c = 1
	
	loop \
	{
		l2 = (0...l.size).sort_by { |x| l[x..-1] }
		
		z = (0...(l2.size - 1)).to_a.map \
		{
			|x|
			
			n = 1
			m = [-1]
			while (x + n < l2.size)
				i, j = l2[x], l2[x + n]
				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)
				m = [m, [t, i, j]].max
				n += 1
			end
			
			m
		}.sort.last
		
		t, i, j = z
		break if (z.nil? || t <= 1)
		
		s2 = l[j, t]
		l1 << [s, s2]

		l[j, t] = s
		l[i, t] = s
		
		i = 0
		while (i + t < l.size)
			l[i, t] = s if (s2 == l[i, t])
			i += 1
		end

		a[s] = c
		s = s.succ
		c += 1
	}
	
	$x = 0 if ($x.nil?)
	
	l.reverse.each { |x| puts([$x, a[x]].join("\t")) if (a.member?(x)); $x += 1 }

	$x += 50
	
	$stdout.flush
end

def out(l)
	
	l = l.sort_by { |x| x['n'] }.map { |x| x['b'] + ['_'] }.flatten
	compress(l)

end


l = [{'n' =>1, 'b' => ["1"], 'd' => 0, 'p' => []}]
seen = {1 => nil}

22.times \
{
	|i|
	$stderr.puts(i)
	
	l2 = []
	
	l.each \
	{
		|x|
		n, b, d, p = x['n'], x['b'], x['d'], x['p']
		
		([n * 2] + (((n % 3 == 1) && (y = (n - 1) / 3).odd?) ? [y] : [])).each_with_index \
		{
			|x, i|
			next if (seen.member?(x))
			seen[x] = nil
			
			z = {'n' => x, 'b' => x.to_s(2).split(''), 'd' => d + 1, 'p' => p + [i.to_s]}
			
			l2 << z
		}
	}
	
	l = l2
	out(l)
}