backtrack29.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 seed(w, w2)
	ns = dense(w, 0.5)

	i = rand(w - w2 + 1)
	ns[i, w2] = '1' * w2

	return {'w' => w, 'ns' => ns, 'n' => ns.to_i(2), 'c' => 0}
end

def lcs(s)

	mx = nil
	s.length.times \
	{
		|i|
		((i + 1)...s.length).each \
		{
			|j|
			n = 0
			n += 1 while (i + n < j && s[i + n, 1] == s[j + n, 1])
			mx = [[n, [i, j]], mx].compact.max
		}
	}
#	p([s[i, n - 1], s[j, n - 1]])
	return mx
end

def backtrack(t)
	
	w = 100
	w2 = 50
	x = seed(w, w2)
	n = x['n']

	l = []
	t.times \
	{
		|i|
		m = n % 3	
		if ((n - 1) % 3 == 0 && ((n - 1) / 3).odd?) then
			n = (n - 1) / 3 
		else
			n *= 2
		end

		s = n.to_s(2).reverse
		mx = lcs(s)
#		p([i, m, s, mx])
		n1, i, j = mx.flatten
		l << n1
		break if (m == 0)
	}
	return l
end

def datasets(n)
	c = 20
	l1 = []
	t = 0
	begin
		l = backtrack(c)
		t += 1
		next if (l.size != c)
		l1 << l.map { |x| { 'x' => x } }
		$stderr.puts([l1.size, t].inspect)
	end while (l1.size < n)
	return l1
end

def sum(l)
	return l.inject { |t, x| t + x }
end

def avg(l)
	return l.empty? ? 0 : sum(l).to_f / l.size
end

def stat(k, l)
	
	t = l.inject { |a, x| a + x }
	t2 = l.inject(0) { |a, x| a + (x ** 2) }
	
        c = l.size
        a = t.to_f / c
        z = t2.to_f / c - a ** 2
        sd = Math.sqrt(z < 0 ? 0 : z)
        raise if (sd.nan?)
	
        return {"#{k}_a" => a, "#{k}_s" => sd}
end

def avgs2(l)

        ks = l[0][0].keys
        l1 = []
        l[0].size.times \
        {
                |i|
                l1[i] = {}
		ks.each \
		{
			|k|
			l1[i].merge!(stat(k, l.map { |x| x[i][k] }))
		}
        }
        return l1

end

def outa(f, l, a = {}, t = '')
	f.puts('$dat << eof')
	k = l[0].keys
	
	f.puts(k.join("\t"))
	l.each { |x| f.puts(x.values.join("\t")) }

	f.puts('eof')
	f.puts("set colors classic; set ytics nomirror; set y2tics; set title '#{t}'; plot \\")
	f.puts("'$dat' using (column('x_a')):(column('x_s')) with errorbars lw 2,\\")
	f.puts("'$dat' using (column('x_a')) with line lw 2 notitle,\\")
	f.puts
#	f.puts("reset; pause -1;")

end

outa((f = File.open('gnuplot.cmd', 'w')), avgs2(datasets(100)), {'x' => 'lw 2'})
f.close