thwart.rb

def f2(n)
	return n.odd? ? (n * 3 + 1) / 2 : n / 2

end

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

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].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)
	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)
	
	l1 = ns.split(/1+/)
	
	l1.shift
	asdm0 = stat2(l1.map { |x| x.length }, nl, 0)
	
	return {'n' => n, 'ns' => ns, 'nl' => nl, 'd' => d(ns), 'dh' => d(nsh), 'dl' => d(nsl)}.merge(asdm1).merge(asdm0)
end

def pair2(n, m)
	n1 = n
	
	m.times { n = f2(n) }
	x = {0 => data(n1), 1 => data(n)}

	x[1]['wr'] = x[1]['nl'].to_f / x[0]['nl'].to_f
	return x
end

def pair(d, m)
	w = 100
	return(pair2(dense(w, d), m))
end


def dist(m, c)
		
	w = 100
	d = 0.0
	l = []
	c.times \
	{
		|i|
		
		l << pair(i.to_f / (c - 1), m)
	}
#	$stderr.puts("#{l.size} pts")
	return l
end


def sum(l)

	t = 0.0
	l.each { |x| t += x }
	return t
end

def detect(x1, a, xe = nil)
	
	x1 = x1.dup
	i = 0
	c = $c
	x1['nl'] = 1
	loop \
	{
		x2 = {}
		(a['v'] + ['wr']).each \
		{
			|vy|
			
			x2[vy] = dot(x1, a[vy].select { |k, x| (a['v'] + ['c']).member?(k) }) 
			
			x2[vy] += xe["#{vy}_e"] if (!xe.nil?)
			
			return c if (x2[vy].abs > 1e10)
		}
		x2['nl'] = x1['nl'] * x2['wr']
		x1 = x2
		i += 1
		break if (x1['nl'] < 1 || i == c)
	}
	return i

end

def count2(a, l, l2, l3)
	
	t2 = 0
	l.size.times \
	{
		|i|
		t2 += 1 if (detect(l[i][0], a) == $c)
	}

	t = 0
	l4 = []
	l.size.times \
	{
		|i|
		la = []
		lb = []
		l2.size.times \
		{
			|j|
			x = detect(l[i][0], a, l2[j][1])
			la << x
			lb << j if (x == $c)
		}
		t += lb.size
		l3 << la
		l4 << lb
		$stderr.print("#{i} ") if (i % 10 == 0)
	}
	$stderr.puts
	return {"t" => t, "t2" => t2, "l" => l4}
end

def sample(l, n)
	
	d = (l.size - 1).to_f / n
	l2 = []
	(n + 1).times \
	{
		|i|
		j = (i * d).to_i
		l2 << l[j]
	}
	return l2
end

def opt(m, a)
	l = a['l']

	c = 20
	w = 100
	1000.times \
	{
		|n|
		
		c = l.size / 4
		l.sort_by! { |x| x[1]['wr_e'] }
		l.reverse!
		
		x = rand(c)
		y = rand(c)
		y += 1 if (y == x)
		ns = ns1 = ns2 = nil
		case rand(3)
			when 0
				ns1 = l[x][0]['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][0]['ns']
				ns2 = l[y][0]['ns']
				ns = ''
				w.times \
				{
					|i|
					ns[i, 1] = [ns1[i, 1], ns2[i, 1]][rand(2)]
				}
				
			when 2
				ns1 = l[x][0]['ns']
				ns2 = l[y][0]['ns']
				i = rand(w)
				ns = ns1[0...i] + ns2[i..-1]
		end

		w2 = ns.to_i(2).to_s(2).length
		raise if (w2 != w)
		
		next if (l.map { |x| x[0]['ns'] }.member?(ns))
		
		x = pair2(ns.to_i(2), m)


		(a['v'] + ['wr']).each \
		{
			|vy|
			z = a[vy].select { |k, v| (a['v'] + ['c']).member?(k) }
			
			predict([x], vy, z)
			corr([x[1]], vy)
		}

		l.pop if (l.size > 2000)
		l << x
		
		if (n % 40 == 0) then
			puts([l[0][1]['wr_e'], l[-1][1]['wr_e'], d(ns), ns].join("\t")) 
			l3 = []
			p(count2(a, dist(1, 100), sample(l, 100), l3))
			f = File.open('out.txt', 'w')
			l3.each { |x| f.puts(x.join(" ")) }
			f.close
		end
	
		$stdout.flush
	}
	return l.first
end

def av(l)
	return nil if (l.empty?)
	return sum(l) / l.size
end

def corr(l, y1)
	
	yp = "#{y1}_p"
	ye = "#{y1}_e"
	xav = av(l.map { |x| x[y1] })
	yav = av(l.map { |x| x[yp] })

	tx = ty = txy = e = 0.0
	m = nil
	l.each \
	{
		|z|
		
		x = z[y1]
		y = z[yp]
		
		txy += (x - xav) * (y - yav)
		tx += (x - xav) ** 2
		ty += (y - yav) ** 2
		
		z[ye] = (x - y)
		e1 = z[ye]
		e += e1
		m = [m, e1.abs].compact.max
	}
	r = txy / (Math.sqrt(tx) * Math.sqrt(ty))
	e /= l.size
	return {'r' => r, 'e_a' => e, 'e_m' => m}
	
end

def dot(x, z)

	t = z['c']
	
	(z.keys - ['c']).each { |v| t += z[v] * x[v] }
	return t
		
end

def predict(l, vy, z)
	l.each \
	{
		|x|
		
		x[1]["#{vy}_p"] = dot(x[0], z)
	}
end

def test(l, a)

	(a['v'] + ['wr']).each \
	{
		|vy|
		z = a[vy].select { |k, v| (a['v'] + ['c']).member?(k) }
			
		predict(l, vy, z)
		corr(l.map { |x| x[1] }, vy)
	}
	a.merge!({'l' => l})
	
end

raise if (ARGV[0].nil?)

d = "out/#{ARGV[0]}"
l = Dir.glob("#{d}/*").select { |x| x =~ /out\d+.txt$/}
n = l.size

i = n - 1
a = Kernel.eval(File.open("#{d}/out#{i}.txt").readlines[0])
	
l = a['lb'].map { |x| x.size }

raise if (sum(l) != 0)

test(dist(1, 100), a)
$c = 500
opt(1, a)