mix23.rb

def f1(n)
	n = (n * 3 + 1) / 2 while (n.odd?)
	n /= 2 while (n.even?)
	return n
end

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 d(s)
        c = s.split('').select { |x| x == '1' }.size
	d = c.to_f / s.length
        return d
        
end


def mx1(n)
	
	ns = n.to_s(2)
	nl = ns.length
	l1 = ns.split(/0+/).map { |x| x.length }
	l0 = [ns.split(/1+/)[1..-1]].compact.flatten.map { |x| x.length }
#	return l0.max, l1.max
	return l0.max.to_f / nl, l1.max.to_f / nl
end

def mx2(n)
#	return mx1(n)[0].to_i
	return mx1(n).compact.max
end

def count(x)
	n = n1 = x['n']
	i = 0
	l = [n]
	
	while (n >= n1 && n != 1)
		n = f2(n)
		l << n
	end

	cm = (0...l.size).max_by { |x| l[x] }

	return x.merge({'cm' => cm, 'c' => l.size, 'nl' => x['ns'].length})
end


def init1(w, m)

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

def init2(w, m)

	return dense(w, m.to_f / w)
end

def init3(w, m)
	r = m.to_f / w
	return '1' + (1...w).map { rand < r ? '0' : '1' }.join
	
end


def init(w)
	
	l = []
	
	(1..w).each \
	{
		|w|
		3.times \
		{
			|i|
			m = rand(w)
			ns = nil
			case (i)
				when 0
					ns = init1(w, m)
				when 1
					ns = init2(w, m)
				when 2
					ns = init3(w, m)
			end
			
			z = count({'ns' => ns, 'n' => ns.to_i(2)})
			redo if (z.nil?)
			
			l << z
		}
	}
	h = (0..w).map { [] }
	l.each { |x| h[x['nl']] << x }
	
	
	return h
end

def get(h, i)
	
	m = h[i].size
	r = h[i].size / 4
	
	return h[i][rand(r == 0 ? m : r)]['ns']
end

def out2(fn, l, l2, s)
	
	$fn = {} if ($fn.nil?) 
	
	if (!$fn.member?(fn)) then
		$fn[fn] = File.open(fn, 'w') 
		$fn[fn].puts(l[0].keys.join("\t"))
		
		f = File.open('gnuplot.cmd', 'w')
		f.puts("set colors classic; #{s} plot \\")
		l2.each \
		{
			|x|
			f.puts("'#{fn}' using #{x}, \\")
		}
		f.puts
		f.close
	end
	
	f = $fn[fn]
	l.each { |x| f.puts(x.values.join("\t")) }
	f.flush
	
end

def order(h)
	
	return Hash[h.sort_by { |k, v| v }.reverse]
end

def opt(w, k)

	h = init(w)
	
	
	n = c = c2 = m = 0
	mx2 = nil
	ops1 = {}
	ops2 = {}
	loop \
	{
		t = rand(h.size - 2) + 2
		
		case (op = ['mut', 'mix', 'cut', 'cut2', 'up'][rand(5)])
			when 'mut'
				ns1 = get(h, t)
				ns = ns1.dup
				i = rand(t - 1) + 1
				ns[i, 1] = (ns1[i, 1].to_i ^ 1).to_s
				
			when 'mix'
				ns1 = get(h, t)
				ns2 = get(h, t)
				ns = ''
				t.times \
				{
					|i|
					ns[i, 1] = [ns1[i, 1], ns2[i, 1]][rand(2)]
				}
				
			when 'cut'
				ns1 = get(h, t)
				ns2 = get(h, t)
				i = rand(t)
				ns = ns1[0...i] + ns2[i..-1]
			
			when 'cut2'
				ns1 = get(h, t)
				ns2 = get(h, r = rand(t - 1) + 1)
				ns = ns1.dup
				r2 = rand(r - 1) + 1
				ns1[-r2..-1] = ns2[-r2..-1]
				
			when 'up'
				r = rand(t - 1) + 1
				ns1 = get(h, r)
				ns = '1' + (0...(t - r - 1)).map { rand(2).to_s }.join + ns1
				
		end
		
		z = count({'ns' => ns, 'n' => ns.to_i(2)})

		nl = z['nl']
		raise if (nl != t)
		
		if (h[nl].index { |x| x['n'] == z['n'] }.nil?) then
		
			x = z[k]
			h[nl] << z
			h[nl].sort_by! { |x| [-x[k], x['d']] }
			if (h[nl].size > 100) then
				x2 = h[nl].pop 
				
				a = {'c2' => 0, 'n2' => 0}


				if (x2[k] < x) then
					a['n2'] = n if (n % 20 == 0)
					c += 1
					ops1[op] = ops1.fetch(op, 0) + 1
				end

				mx = h[1..-1].map { |x| x.first[k] }
				if (mx == mx2) then
					c2 += 1
					break if (c2 > 1e5)
				else
					a['c2'] = n
					c2 = 0
					ops2[op] = ops2.fetch(op, 0) + 1
				end
					
				mx2 = mx
				
				if (!a.values.select { |x| x != 0 }.empty?) then
					
					out2('out.txt', 
						[a.merge({'n' => n, 'nl' => nl, 'c' => c})],
						["(column('n')):(column('nl')) pt 7 ps 0.5 title 'nl'",
						"(column('n')):(column('c')) with line lw 3 axes x1y2",
						"(column('n2')):(0) pt 5 ps 0.5",
						"(column('c2')):(1) pt 5 ps 0.5",
						], "set ytics nomirror; set y2tics; set key center right box opaque;" 
						)
					m += 1
				end

			end
		end
	
		$stderr.puts([{'n' => n + 1, 'm' => m, 'c2' => c2}, order(ops1), order(ops2)].inspect) if ((n + 1) % 5e4 == 0)
	
		n += 1
	}
	return h[1..-1].map { |x| x.first }
	
end

def adv(x)
	n = n1 = x['n']
	i = 0
	l = [n]

	j = jl = jr = 0
	while (n >= n1 && n != 1)
		if (n.odd?) then
			j += 1 
			l.size < x['cm'] ? jl += 1 : jr += 1
		end
	
		n = f2(n)
		l << n
	end

	x.merge!({'j' => j, 'jl' => jl, 'jr' => jr})
end

def review(fn, k)

	l = File.open(fn).readlines.map { |x| Kernel.eval(x) }
	l.each { |x| adv(x) }
	
	l1 = [k, 'j', 'c', 'jl', 'jr']
	
	l2 = l1.map { |x| "(column('#{x}')) with line" }
	l2 += ["(column('cm') - column('j')) with line title 'cmj' lt 7"]
	l2 += ["(column('cm') - column('jl')) with line title 'cmjl' lt 8"]
#	l2 += ["(column('cm') / column('jl')) with line title 'cmjl2' axes x1y2"]
	out2('out.txt', l.map { |x| x.select { |x, | l1.member?(x) } },
	l2, 'set key top left;')
	exit
end


fn = 'mixdb.txt'
k = 'cm'
review(fn, k) if (File.exist?(fn))

l = opt(100, k)
f = File.open(fn, 'w')
l.each { |x| f.puts(x.inspect) }
f.close