construct116.rb

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

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 adj(x, m, n, s2, p2, p, x3)
	s2.replace(p[0...x] + (x3 % 2).to_s)
	m = (s2[x, 1] == p[x, 1])
	n = p2.reverse.to_i(2)
	p2[x, 1] = m ? '11' : '01'
	return m, n, x3
end

def terras121(p)
	
	p2 = ['01', '11'][p[0, 1].to_i]
	n = 1
	n3 = 0
	m = p2 == '11'
	x3 = (p2.reverse.to_i(2)) >> 1

	(1...p.length).each \
	{
		|x|

		if (!m)
			ns = n.to_s(2)
			ns[0, 1] = ''
			m1 = x3 - 3**n3
			n1 = f2(m1)
		end

		n3 = p[0...x].split('').select { |z| z == '1' }.size
		
		s2 = ''
		m, n, x3 = adj(x, m, n, s2, p2, p, m ? (f2(x3) + 3**n3) : (n1 + 3**n3))
	}

	n = p2.reverse.to_i(2)

	return n
end

def seq(n)

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


def outa(f, l, a = {}, t = '')
	f.puts('$dat << eof')
	k = l[0].keys
	
	f.puts(k.join("\t"))
	l.each { |x| f.puts(x.values.join("\t")) }

	f.puts('eof')
	f.puts("set colors classic; set key top center; set title '#{t}'; ")
#	f.puts("set ytics nomirror; set y2tics;")
	f.puts("plot \\")
	k.each \
	{ 
		|x| 
		next if (a.member?(x) && a[x].nil?)
		f.puts("'$dat' using (column('#{x}')) with line #{a.fetch(x, '')} lw 2,\\") 
	}
	f.puts
#	f.puts("reset; pause -1;")

end

def outafn(fn, l, a = {})
	outa(f = File.open(fn, 'w'), l, a)
	f.close
end

def fmt1(l, f)

	w = l.max_by { |x| x.length }.length
	
	f.puts("set colors classic; set ytics nomirror; set y2tics; set key top left opaque;\\")
	f.puts("plot \\")
	f.puts("[0:#{w}][0:#{l.size - 1}] '-' matrix using 1:2:3 with image title ''")
	l.each_with_index \
	{
		|z, i|
		
		c = w - z.length
		z[z.length...w] = '0' * c
		
		f.puts(z.split('').join(' '))
	}
	f.puts("eof")
	f.puts("eof")
	f.puts("pause -1")
	
end

def grid(l)
	
	f = File.open(fn = "gnuplot1.cmd", 'w')
	f.puts("set palette negative grayscale; unset colorbox;")
	
	fmt1(l.map { |x| x.reverse }, f)
	f.close

end

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


def glides(t)
	
	l2 = []
	e = 0.64

	c = 100
	t.times \
	{

		d = e + rand() * (1.0 - e)

		p = dense(c, d)
		n = terras121(p)


		l = seq(n)

		cg = l.index { |x| x < l[0] }
		next if (cg < c)
		l2 << l[c...cg].map { |x| x % 2}.join
	}

	return l2
end

l2 = glides(20)

l1 = []
(0...l2.size).map { |i| (0...l2[i].size).map { |j| l1 << [i, j] } }

a = {'' => l1}

t = 0
l = []
a1 = nil
loop \
{
	a2 = {}
	a.each \
	{
		|k, l1|
		l1.each \
		{
			|i, j|
			b = l2[i][j + k.length + 1, 1]
			next if (b == '')
			a2[k + b] = a2.fetch(k + b, []) << [i, j]
		}
	}
	l << {'t' => t, 'c1' => a2.keys.size, 'c' => a2.keys.empty? ? 0 : Math.log(a2.keys.size)}
	a1 = a if (a1.nil? && l.size >= 2 && l[-1]['c'] < l[-2]['c'])
	a = a2
	
	p(l[-1])
	break if (a.empty?)
	t += 1
}
z = l.max_by { |x| x['c'] }
$stderr.puts([z, 2**z['t']].inspect)
outafn('gnuplot.cmd', l, {'t' => nil, 'c1' => nil})

p(a1.keys.size)

grid(a1.keys.sort)
outafn('gnuplot2.cmd', a1.keys.map { |x| {'d' => d(x)} }.sort_by { |x| x['d'] })