mix22.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)
	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
end

def mx2(n)
	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] }

	mx = {'mx' => 0, 'mw' => 0, 'mi' => 0, 'mc' => 0}
	l[0..cm].each_with_index \
	{
		|n, i|

		mx = [mx, {'mx' =>  mx2(n), 'mw' => i - mx['mi'], 'mi' => i, 'mc' => mx['mc'] + 1}].max_by { |x| x['mx'] }
	}
	
	return x.merge({'cm' => cm, 'c' => l.size, 'nl' => x['ns'].length}).merge(mx)
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 opt(w, k)

	h = init(w)
	
	
	n = c = c2 = 0
	mx2 = nil
	d = 1000
	loop \
	{
		t = rand(h.size - 2) + 2
		
		case (x = rand(5))
			when 0
				ns1 = get(h, t)
				ns = ns1.dup
				i = rand(t - 1) + 1
				ns[i, 1] = (ns1[i, 1].to_i ^ 1).to_s
				
			when 1
				ns1 = get(h, t)
				ns2 = get(h, t)
				ns = ''
				t.times \
				{
					|i|
					ns[i, 1] = [ns1[i, 1], ns2[i, 1]][rand(2)]
				}
				
			when 2
				ns1 = get(h, t)
				ns2 = get(h, t)
				i = rand(t)
				ns = ns1[0...i] + ns2[i..-1]
			
			when 3
				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 4
				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}
				
				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
				end
					
				mx2 = mx
				if (x2[k] < x) then
					a['n2'] = n
					c += 1
				end
				
				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;" 
					) if (!a.values.select { |x| x != 0 }.empty?)

			end
		end
	
		n += 1
	}
	return h[1..-1].map { |x| x.first }
	
end

def review(fn, k)

	l = File.open(fn).readlines.map { |x| Kernel.eval(x) }
	out2('out.txt', l.map { |x| x.select { |x, | [k, 'mw', 'cm', 'c'].member?(x) } },
	["(column('#{k}')) with line axes x1y2",
	"(column('mw')) with line",
	"(column('cm')) with line",
	"(column('c')) with line"], 'set key top left;')
	exit
end

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

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