compress8.rb

def compress(l)
		
	s = 'a'
	l1 = []
	
	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

		s = s.succ

	}
#	p(l)
#	p(l1)
#	return l1.size
	return (l + l1.flatten).size

end

def entropy(l)
	
#	l = l.map { |x| x['b'] + x['p'] }
#	l = l.map { |x| x['p'] }
#	l = l.sort
	l = l.last['p']
	return compress(l.sort.flatten)
	
end


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

t = c = a = 0

loop \
{
	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))
			z = {'n' => x, 'b' => x.to_s(2).split(''), 'd' => d + 1, 'p' => p + [i.to_s]}
			
			z['e'] = entropy(l + [z])
			l2 << z
		}
	}
	
	l2.sort_by! { |x| [x['e'], x['d']] }
	
	x = l2.shift
	e, n, b, d, p = x['e'], x['n'], x['b'], x['d'], x['p']
	
	l << {'n' => n, 'b' =>b, 'd' => d, 'p' => p}
	seen[n] = nil
	
	l2 = l2.map { |x| x['d'] }

	t += e
	c += 1
	a = t.to_f / c
	
	puts({'n' => n, 'e' => e, 't' => sprintf("%.2f", a), 'd' => d, 'mn' => l2.min, 'mx' => l2.max, 'd' => l2.empty? ? 0 : l2.max - l2.min, 'p' => p.join}.map { |x| "#{x[0]}= #{x[1]}" }.join("\t"))
	$stdout.flush
	
}