Skip to content

Instantly share code, notes, and snippets.

@vznvzn

vznvzn/backtrack5.rb

Created May 22, 2019
Embed
What would you like to do?
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 ufo(w)
# return dense(w, 0.5).to_i(2)
begin
x = dense(w, 0.5)
p = (1..2).map { rand(w) }
p1, p2 = [p.min, p.max]
w2 = (p2 - p1 + 1)
end while (w2 < w / 2 || w2 > w * 3 / 4)
x[p1..p2] = '1' * w2
$stderr.puts({'w2' => w2}.inspect)
return x.to_i(2)
end
def out(a, a2 = {}, t = nil)
fn = 'out.txt'
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|
f2.puts("'#{fn}' using (column('t')):(column('#{x}')) with line title '#{x}' #{a2[x]}, \\")
}
f2.puts
f2.close
end
$f1.puts(a.values_at(*k).join("\t"))
$f1.flush
end
def add(l, t, n1, m)
c = 0
n = n1
m.times \
{
n = f2(n)
c += 1
break if (n < n1 || n == 1)
}
w = n1.to_s(2).length
l << {'t' => t,
'rmw' => m.to_f / w,
'rcw' => c.to_f / w,
'w' => w,
'n' => n1,
'c' => c,
'm' => m}
end
def back(n1)
add(l = [], 0, n1, 0)
c = 2000
t = 0
k = 0
loop \
{
l.sort_by! { |x| -x['c'] }
x = l[0]
if (!l[0].member?('z')) then
l[0]['z'] = nil
k += 1
x = x.dup
x.delete('n')
x.delete('z')
x['k'] = k.to_f / 100
out(x, {'rmw' => 'axes x1y2', 'rcw' => 'axes x1y2'})
end
x = l.delete_at(rand([l.size, 50].min))
n, m = [x['n'], x['m']]
add(l, t, (n - 1) / 3, m + 1) if ((n - 1) % 3 == 0 && ((n - 1) / 3).odd?)
add(l, t, n * 2, m + 1)
l[c..-1] = [] if (l.size > c)
t += 1
}
end
back(ufo(100))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment