traverse19b.rb

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

end

def seq2(n)

	n1 = n
	l = [n1]
	while (n != 1 && n >= n1)
		n = f2(n)
		l << n
	end 
	
	return l
end

def outa(f1, l, a = {}, t = '')
	f = f1.nil? ? File.open('gnuplot.cmd', 'w') : f1
	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 key top left opaque; set title '#{t}'; ")
	f.puts("set ytics nomirror; set y2tics;")
	f.puts("plot \\")
	k.each \
	{ 
		|x| 
		next if (a.member?(x) && a[x].nil?)
		f.puts("'$dat' using (column('#{x}')) with line #{a.fetch(x, '')} lw 2 title '#{x}',\\") 
	}
	f.puts
#	f.puts("reset; pause -1;")
	f.close if (f1.nil?)

end

def flip(s, n)
	s = s.dup
	s[n, 1] = (s[n, 1].to_i ^ 1).to_s
	return s
end

def lead1(l)
	l2 = []
	l.each \
	{
		|x|
		x1 = x.dup
		x1[0, 1] = '' while (x1[0, 1] == '0')
		l2 << x1 if (!x1.empty?)
	}
	return l2
end

def step(x)

	l = []
	x.length.times { |i| l << flip(x, i) }
	l += [x + '0', x + '1']
	return lead1(l)
end

def distance(x, y)
	z = ((x1 = x.to_i(2)) ^ (y1 = y.to_i(2))).to_s(2)
	
	return z.count('1')
end

def count(ns)
	l = seq2(ns.to_i(2))
	p = l.map { |x| x % 2 }.join
	return {'ns' => ns, 'p' => p, 'pw' => p.length, 'nw' => ns.length}
end

def alike(set, ns, ns2)
	x = set[ns]
	x2 = count(ns2)
	
	dp = distance(x2['p'], x['p'])
	dn = x2['nw']
	
	return x2.merge({'z' => dp + dn, 'dp' => dp, 'dn' => dn})
end

def fmt1(l, f)

	w = l.max_by { |x| x.length }.length
	
	f.puts("set colors classic; set ytics nomirror; set y2tics; set key top left opaque;\\")
	f.puts("plot \\")
	f.puts("[0:#{w}][0:#{l.size - 1}] '-' matrix using 1:2:3 with image title ''")
	l.each_with_index \
	{
		|z, i|
		
		c = w - z.length
		z[z.length...w] = '0' * c
		
		f.puts(z.split('').join(' '))
	}
	f.puts("eof")
	f.puts("eof")
	
	
end

def grid(l)
	
	f = File.open(fn = "gnuplot1.cmd", 'w')
	f.puts("set palette negative grayscale; unset colorbox;")
	
	fmt1(l.map { |x| x.reverse }, f)
	f.close

end

set = {}
dist = {['1', nil] => count('1').merge({'z' => 0, 'dp' => 0, 'dn' => 0})}
seen = {'1' => nil}
l = []

500.times \
{
	|t|
	$stderr.puts({'t' => t, 'd' => dist.size, 's' => seen.size}.inspect) if ((t + 1) % 100 == 0)

	ns12, x = dist.min_by { |k, x1| [x1['z'], x1['nw'], x1['pw'], ] }
	ns1, ns2 = ns12
	dist.delete_if { |ns12, x1| ns12[0] == ns1 }

	set[ns1] = x
#	p(['<-', x])
	l << x
	
	step(ns1).each \
	{
		|ns2|
		next if (seen.member?(ns2))
		
		set.keys.each \
		{
			|ns|
			dist[[ns2, ns]] = alike(set, ns, ns2)
		}
		
#		p(["->", ns2])
		seen[ns2] = nil
	}
}

outa(nil, l, {'ns' => nil, 'p' => nil})

grid(l.map { |x| x['ns'].to_s })