mix2.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).to_i(2) 
	
end

def stat(l)
	l = [0] if (l.empty?)
        t = t2 = 0
        l.each \
        {
		|x|
		t += x
		t2 += x ** 2
        }
        c = l.size
        a = t.to_f / c
        z = t2.to_f / c - a ** 2
        sd = Math.sqrt(z < 0 ? 0 : z)

	return a, sd, l.max.to_f, l.min.to_f
end

def stat2(l, t, n)
	return Hash[[["a#{n}", "sd#{n}", "mx#{n}"], stat(l)[0..2]].transpose]
end

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

def data(n)
	
	$seen = {'h' => 0} if ($seen.nil?)
	seen = $seen
	
	if (seen.member?(n)) then
		seen['h'] += 1
		$stderr.puts("h #{seen['h']} ss #{seen.size}") if (seen['h'] % 1000 == 0)
		return seen[n]
	end


	ns = n.to_s(2)
	nl = ns.length
	m = nl / 2
	
	nsh = ns[0..m]
	nsl = ns[m..-1]
	
	asdm1 = stat2(ns.split(/0+/).map { |x| x.length }, nl, 1)
	asdm0 = stat2(ns.split(/1+/)[1..-1].map { |x| x.length }, nl, 0)
	
	x = {'n' => n, 'ns' => ns, 'nl' => nl, 'd' => d(ns), 'dh' => d(nsh), 'dl' => d(nsl)}.merge(asdm1).merge(asdm0)
	seen[n] = x if (seen.size < 100e3)
	return x
end

def count(z)
	
	n = z['n']
	n1 = n
	l = []
	mmx0 = 0
	mmx1 = 0
	begin
		x = data(n)
		mmx0, mmx1 = [[mmx0, x['mx0']].max, [mmx1, x['mx1']].max]
		l << n
		n = f2(n) 
	end while (n > n1)
	
		
	m = (0...l.size).max_by { |x| l[x] }
	r = l[m].to_s(2).length - n1.to_s(2).length
	
	return z.merge({'c' => l.size, 'n' => n1, 'l' => l, 'm' => m, 'r' => r, 'mmx0' => mmx0, 'mmx1' => mmx1, 'mmx' => [mmx0, mmx1].max})
end

def init1(m)

	w = 100
	l = []
	b = 1
	while (w > 0) 
		r = (w == 1) ? 1 : rand([w, m].min) + 1
		l << [b] * r
		b ^= 1
		w -= r
	end
	s = l.flatten.join
	return s
end

def init(m)
	
	c = 0
	l = []
	20.times \
	{
		|i|
		c += 1
		ns = init1(m)
		z = count({'ns' => ns, 'n' => ns.to_i(2)})
		p([i, c, z['mmx'], z['c']])
		redo if (z['mmx'] > m)
		l << z
	}
	return l
end

def opt(l, m)

	w = l[0]['ns'].length
	j = 0
	
	1000.times \
	{
		|n|
		j += 1
		
		l.sort_by! { |x| -x['c'] }
		
		c = l.size / 4
		x = rand(c)
		y = rand(c)
		y += 1 if (y == x)
		ns = ns1 = ns2 = nil
		
		case (rand(3))
			when 0
				ns1 = l[x]['ns']
				ns = ns1.dup
				i = rand(w - 1) + 1
				ns[i, 1] = (ns1[i, 1].to_i ^ 1).to_s
			when 1
				ns1 = l[x]['ns']
				ns2 = l[y]['ns']
				ns = ''
				w.times \
				{
					|i|
					ns[i, 1] = [ns1[i, 1], ns2[i, 1]][rand(2)]
				}
				
			when 2
				ns1 = l[x]['ns']
				ns2 = l[y]['ns']
				i = rand(w)
				ns = ns1[0...i] + ns2[i..-1]
		end
		
		z = count({'ns' => ns, 'n' => ns.to_i(2)})
		
		redo if (z['mmx'] > m)
#		p(z.select { |k, | k != 'l' })

		l.pop if (l.size > 500)
		l << z
	}
	
end

def out(fn, a)
	
	f = File.open(fn, 'a')
	f.puts(a.keys.join("\t")) if (f.size == 0)
	f.puts(a.values.join("\t"))
	f.close
end


f = File.open('gnuplot.cmd', 'w')

f.puts <<eof
set colors classic; set y2tics; set ytics nomirror; set y2range [0:]; plot [][0:] 'out.txt' using (column('t')) with line lw 2,'' using (column('mmx')) with line,\\
'' using (column('c')) with line lw 3 axes x1y2
eof

f.close

File.open(fn = 'out.txt', 'w').close

25.downto(4) \
{
	|t|
	
	4.times { opt(l = init(t), t); out(fn, l[0].select { |k, | k != 'l'}.merge({'t' => t})) }
}