mix4.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 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, c.to_f
end

def stat2(l, t, n)
	l1 = stat(l)
	
	return Hash[[["a#{n}", "sd#{n}", "mx#{n}", "c#{n}", 
		"a#{n}s", "sd#{n}s", "mx#{n}s", "c#{n}s"], 
		l1 + l1.map { |x| x / t }].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("\t\th #{seen['h']} ss #{seen.size}") if (seen['h'] % 10000 == 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)
	l = ns.split(/1+/)[1..-1]
	l = [] if (l.nil?)
	asdm0 = stat2(l.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, k, t)
	
	n = z['n']
	n1 = n
	l = []
	mx = nil
	begin
		x = data(n)
		['a', 'sd', 'mx', 'c'].each \
		{
			|k|
			['', 's'].each { |s| x["#{k}#{s}mx"] = [x["#{k}0#{s}"], x["#{k}1#{s}"]].max }
		}
		return if (x[k] >= t)
		mx = [mx, x[k]].compact.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, k => 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, k, t)
	
	c = 0
	l = []
	n = 200
	n.times \
	{
		|i|
		c += 1
		m = rand(w)
		ns = nil
		case (r = rand(3))
			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)}, k, t)
		redo if (z.nil?)
		
		l << z
	}
	z = l.last
	$stderr.puts("\t" + {'i' => n, 'c' => c, k => z[k], 'zc' => z['c']}.inspect)
	return l
end

def opt(w, k, t)

	l = init(w, k, t)
	
	j = 0
	
#	50.times \
	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)}, k, t)
		
		redo if (z.nil?)
#		p(z.select { |k, | k != 'l' })

		l.pop if (l.size > 500)
		l << z
	}
	return l.max_by { |x| x['c'] }
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

def plot1(k, x, y, t = y)
	
	return "'out_#{k}.txt' using (column('#{x}')):(column('#{y}')) with line title '#{t}',\\"
	
end

def graph(hi1, hi2, g, at, w = nil)
	
	
	f = File.open('gnuplot.cmd', w ? 'w' : 'a')
	f.puts("set key #{at}; plot [0:#{hi1}][0:#{hi2}]\\")
	g.each { |x| f.puts(x) }
	f.puts
	f.puts("pause -1")
	f.close
	
end

def plot(ks, hi1, hi2)

	g1 = []
	g2 = []
	ks.each \
	{
		|k|
		g1 << plot1(k, 't', "#{k}0_c")
		g1 << plot1(k, 't', "#{k}1_c")
		g1 << plot1(k, 't', "#{k}mx_c")
		
		g2 << plot1(k, 'ts', "#{k}0s_c")
		g2 << plot1(k, 'ts', "#{k}1s_c")
		g2 << plot1(k, 'ts', "#{k}smx_c")
	}
	
	chi = 700
	
	graph(hi1, chi, g1, "bottom right", true)
	graph(hi2, chi, g2, "bottom right")


	g3 = []
	g4 = []
	
	ks.each \
	{
		|k|
		
		g3 << plot1(k, 't', "#{k}0_#{k}0", "#{k}0s")
		g3 << plot1(k, 't', "#{k}1_#{k}1", "#{k}1s")
		g3 << plot1(k, 't', "#{k}mx_#{k}mx", "#{k}smx")

		g4 << plot1(k, 'ts', "#{k}0s_#{k}0s", "#{k}0s")
		g4 << plot1(k, 'ts', "#{k}1s_#{k}1s", "#{k}1s")
		g4 << plot1(k, 'ts', "#{k}smx_#{k}smx", "#{k}smx")
	}
	
	graph(hi1, hi1, g3, "top left")
	graph(hi2, hi2, g4, "top left")
	
end

def sample(k, t)
	
	z = opt(100, k, t)
	z.delete('l')
	
	return Hash[[z.keys.map { |x| "#{k}_#{x}"}, z.values].transpose]
		
end


lo1 = 2
hi1 = 100

lo2 = 0.05
hi2 = 1


ks = ['a', 'sd', 'mx', 'c']

plot(ks, hi1, hi2)


ks.each { |k| File.open("out_#{k}.txt", 'w').close }

c = 20
(c + 1).times \
{
	|x|

	a = {}
	
	ks.each \
	{
		|k|
		$stderr.puts([k, x, c, Time.now.to_s].inspect)
		r = x.to_f / c
		[0, 1].each \
		{
			|y|
			s = ['', 's'][y]
			lo, hi = [[lo1, hi1], [lo2, hi2]][y]
			t = lo + r * (hi - lo)
			
			a["t#{s}"] = t
			
			a.merge!(sample("#{k}0#{s}",t))
			a.merge!(sample("#{k}1#{s}", t))
			a.merge!(sample("#{k}#{s}mx", t))
		}
		out("out_#{k}.txt", a)
	}
}