stepwise10.rb

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

end

def seqg(n)

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

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

def delete(s, n)
	s = s.dup
	s[n, 1] = ''
	return s
end

def insert(s, n)
	s0 = s.dup
	s0[n, 0] = '0'
	s1 = s.dup
	s1[n, 0] = '1'
	return s0, s1
end

def edit1(s)
		
	l = []
	s.length.times \
	{
		|n|
		l << flip(s, n)
		l << delete(s, n)
	}

	(s.length + 1).times \
	{
		|n|
		l += insert(s, n)
	}
	return l.select { |x| x[0, 1] != '0' }
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 len(ns, p)
	l = ns.split(p)
	l = [] if (l.nil?)
	l.shift if (l[0] == '')
	return l.map { |x| x.length }
end

def len1(ns)
	return len(ns, /0+/)
end

def len0(ns)
	return len(ns, /1+/)
end

def len01(ns)
	return len1(ns), len0(ns)
end

def hist(l)
	a = {}
	l.each { |x| a[x] = a.fetch(x, 0) + 1 }
	return a
end

def hdiff(a, b)
	d = 0
	(a.keys | b.keys).each { |x| d += (a.fetch(x, 0) - b.fetch(x, 0)).abs }
	return d
end
	
def hdiff1(ns)
	a0, a1 = $h[ns.length].values_at('h0', 'h1')
	l1, l0 = len01(ns)
	
	b0, b1 = [hist(l0), hist(l1)]
	return hdiff(a0, b0) + hdiff(a1, b1)
end

def hdiff2(ns)

	$h = {} if ($h.nil?)

	if (!$h.member?(nw = ns.length)) then
		
		ns2 = dense(nw, 0.5)
		
		l1, l0 = len01(ns2)
		
		$h[nw] = {'h0' => hist(l0), 'h1' => hist(l1)}
		
		hz = hdiff1(dense(nw, 0.5))
		$h[nw]['hz'] = (hz == 0) ? 1 : hz
	end

	hd = hdiff1(ns)
	return {'hd' => hd, 'hdr' => hd.to_f / $h[nw]['hz']}
	
end

def hdc(l, c)

	t = 0.0
	[c, l.size].min.times { |i| t += hdiff2(l[i].to_s(2))['hdr'] }
	return t / c
end

def count(ns)
	
	l1 = seqg(n = ns.to_i(2))

	cg = l1.size
	nw = ns.length
	cm = (0...l1.size).max_by { |x| l1[x] }

	ch = (nw / 10).to_i + 1
	
	a = {'ns' => ns, 
		'nw' => nw, 
		'cg' => cg,
		'cm' => cm,
		'cmr' => cm.to_f / nw,
		'cmcg' => cm.to_f / cg,
		'hdr' => hdc(l1, ch)}
	return a
end

def out(a, a2 = {}, t = nil, ct = "(column('t')):", w = ' with line ')

	fn = $fn.nil? ? 'out.txt' : $fn
	k = a.keys
	
	if ($f1.nil?) then
		$f1 = File.open(fn, 'w')
		$f1.puts(k.join("\t")) 
		
		f2 = File.open('gnuplot.cmd', 'w')
		st = t.nil? ? 'unset title; ' : "set title '#{t}'; "
		
		f2.puts("set ytics nomirror; set y2tics; set colors classic; set key top left box opaque; #{st}; plot \\")
		(a.keys - ['t']).each \
		{
			|x|
			next if (a2.member?(x) && a2[x].nil?)
			m = a2.fetch(x, '')
			m += w if (!m.include?('with'))
			f2.puts("'#{fn}' using #{ct}(column('#{x}')) title '#{x}' #{m}, \\")
		}
		f2.puts
		f2.close
	end
	$f1.puts(a.values_at(*k).join("\t"))
	$f1.flush
end


def keys(ks2)

	ksmn = ks2.select { |x| x.end_with?('-') }.map { |x| x.dup }
	
	ksmx = ks2 - ksmn
	
	ksmn.each { |x| x.replace(x.chop) }
	
	x = {'ks' => ksmn + ksmx, 'ksmx' => ksmx, 'ksmn' => ksmn}
	
	$stderr.puts(x.inspect)

	$t = x.dup
	$t.delete('ks')
	
	return x
	
end

def order(l, ks2)
	l2 = (0...l.size).map { {} }

	$k = keys(ks2) if ($k.nil?)

	$k['ks'].each \
	{
		|k|
		
		l1 = (0...l.size).map { |x| {k => l[x][k], 'i' => x} }

		s = $k['ksmx'].member?(k) ? -1 : 1
		
		l1.sort_by! { |x| s * x[k] }

		(0...l1.size).each { |x| l2[l1[x]['i']][k] = x }
	}
	l2.each { |x| x['z'] = x.values.inject(0) { |t, x| t + x } }
	
	return (0...l2.size).sort_by { |x| l2[x]['z'] }
end

def sample2(t, c)
	l = (0...t).to_a
	d = (t - 1).to_f / (c - 1)
	
	return (0...c).map { |x| l[(x * d).to_i] }
end

def sample2h(t, c)
	h = {}
	sample2(t, c).each { |x| h[x] = nil }
	return h
end

def adv(l1, ks, m)
	l2 = order(l1, ks)
	
	i = l2[rand([l2.size, 50].min)]
	
	l3 = l2[m..-1]
	l3 = [] if (l3.nil?)
	x = nil
	
	(l3 | [i]).sort.reverse.each \
	{
		|x1|
		x2 = l1.delete_at(x1)
		x = x2 if (x1 == i)
	}
	return x
end

def opt(ks)

	l1 = [count('1')]
	seen = {'' => nil, '0' => nil, '1' => nil}
	l = []

	c = 1e4.to_i
	m = 500

	h = sample2h(c, 2000)
	
	c.times \
	{
		|t|
		$stderr.puts(t) if (t % 100 == 0)
		l << (x = adv(l1, ks, m))
		
		out(x.merge({'t' => t}), 
			{'ns' => nil, 
			'cmr' => 'axes x1y2',
			'hdr' => 'axes x1y2',
			'cmcg' => 'axes x1y2',
			}, $t.inspect) if (h.member?(t))
		
		
		edit1(x['ns']).each \
		{
			|ns|
			next if (seen.member?(ns))
			l1 << count(ns)
			seen[ns] = nil
		}
	}

end



ks = ['cmr', 'hdr-']
ks = ['cmcg', 'hdr-']
ks = ['nw', 'cmcg', 'hdr-']
ks = ['nw', 'cmr', 'hdr-']
ks = ['nw', 'cmr', 'cmcg', 'cg', 'cm', 'hdr-']
ks = ['cmr']
ks = ['nw', 'cmr', 'cg', 'cm', 'hdr-']
opt(ks)