construct99b.rb

def f2(n)
	return n.odd? ? (n * 3 + 1) / 2 : n / 2

end

def seq(n)

	n1 = n
	l = [n1]
	while (n != 1)
		n = f2(n)
		l << n
	end 
	
	return l
end

def lcs(s1, s2)

	l = []
	s1.length.times \
	{
		|i|
		s2.length.times \
		{
			|j|
			n = 0
			n += 1 while (i + n < s1.length && j + n < s2.length && s1[i + n, 1] == s2[j + n, 1] && ['0', '1'].member?(s1[i + n, 1]))
			l << {'n' => n, 'i' => i, 'j' => j} if (n > 0)
		}
	}
	return if (l.empty?)
	l.sort_by! { |x| -x['n'] }
	l.each \
	{
		|x|
		n, i, j = [x['n'], x['i'], x['j']]
		
		a = s1[0...i]
		b = s1[i, n]
		c = s1[(i + n)..-1]

		ari = a.rindex('(')
		cd = c.index(')')
		
		ad = ari.nil? ? nil : a.length - ari

		next if (b.length < 20)
		next if ((!ad.nil? && ad < b.length) && (!cd.nil? && cd < b.length))
		
		s1 = a + '(' + b + ')' + c
	
		return {'n' => n, 'b' => b, 's1' => s1, 's2' => s2, 
			'ad' => ad, 'cd' => cd,
			's0' => a + ' *' + b + '* ' + c}
	}	
	return
	
end

def match(s1, l)

	loop \
	{
		l1 = []
		l.each_with_index \
		{
			|s2, k|
			
			l1 << lcs(s1, s2)
		}
		x = l1.compact.max_by { |x| x['n'] }
		break if (x.nil?)
		s1 = x['s1']
		b = x['b']
		l.each { |x| x.gsub!(b, 'x') }
		p(x)
	}
	puts(l.size)
	return s1
end

def sum(l)
	return l.inject { |t, x| t + x }
end

def size(l)
	return sum(l.map { |x| x.length })
end

def d(s)
        c = s.split('').select { |x| x == '1' }.size
	d = c.to_f / s.length
        return d
        
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 control(l)
	l.each_with_index \
	{
		|s, j|
		w = s.length
		d = d(s)
		s2 = dense(w, d)
		p([j, d, w])
		s.replace(s2)
	}
end

def compress()
	l = File.open('out.txt').readlines.map { |x| Kernel.eval(x)[0] }.sort_by { |x| x.length }.reverse
	#l.each { |x| p(x) }
	#exit
	control(l)

	s1 = size(l)
	(0..(l.size - 2)).each \
	{
		|i|
		l[i] = match(l[i], l[(i + 1)..-1])
	}
	l.each { |x| p(x) }
	s2 = size(l)
	puts({'s1' => s1, 's2' => s2}.inspect)
exit

end

compress() if (File.exists?('out.txt'))

a = {}

(1..2000).each \
{
	|i|
	ns = '1' * i
	l1 = seq(ns.to_i(2))
	cg = l1.index { |x| x < l1[0] }
	cg = l1.size if (cg.nil?)
	cm = (0...cg).max_by { |x| l1[x] }
	
	if (cm > i) then
		s = l1[i..cm].map { |x| x % 2 }.join.reverse
		a[s] = a.fetch(s, []) + [i]
		puts([i, cm - i, a[s]].join("\t"))
		$stdout.flush
	end
	
}

f = File.open('out.txt' , 'w')
a.sort_by { |x| x[0] }.each { |x| f.puts(x.inspect) }
f.close