crunch.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 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 len01(ns)
	nl = ns.length
	l1 = ns.split(/0+/).map { |x| x.length }
	
	l2 = ns.split(/1+/)[1..-1]
	l2 = [''] if (l2.nil?)
	
	l0 = l2.map { |x| x.length }
	return l0, l1
end

def mx01(ns)
	return len01(ns).flatten.max
end

def crunch(ns)
	
	i = 0
	ns1 = ns
	mx1 = mx01(ns)
	
	return if (mx1 != 10)
	begin
		ns = f2(ns.to_i(2)).to_s(2)
		mx = mx01(ns)
		i += 1
	end while (mx >= mx1 && ns != '1')
		
	return {'n' => ns1.to_i(2), 'mxc' => i, 'ns' => ns1, 'mx1' => mx1}
	
end

def init(w, n = 200)
	
	c = 0
	l = []
	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 = crunch(ns)
		redo if (z.nil?)
		
		l << z
	}
	return l
end


def mix(w = 1000)
	
	File.open(fn = 'out.txt', 'w').close
	
	l = init(w)
	
	j = j2 = jmx = 0
	jmx2 = 1000
	
	a = nil
	loop \
	{
		l.sort_by! { |x| -x['mxc'] }
		if (l[0] != a)
			a = l[0]
			j2 = 0
			f = File.open(fn, 'a')
			f.puts(a)
			f.close
			jmx2 = [3 * jmx, jmx2].max
		else
			j2 += 1
			jmx = [jmx, j2].max
		end

		p({'mxc' => a['mxc'], 'j' => j, 'j2' => j2, 'jmx' => jmx, 'jmx2' => jmx2})
		
		break if (j2 > jmx2)
		
		c = l.size / 4
		l1 = (0..c).to_a
		
		x, y = (1..2).map { l1.delete_at(rand(l1.size)) }

		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 = crunch(ns)
		j += 1
		
		redo if (z.nil?)

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