Skip to content

Instantly share code, notes, and snippets.

@vznvzn
Created August 26, 2020 20:13
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save vznvzn/7f5392c01b38e59a2c75b63a3833d2de to your computer and use it in GitHub Desktop.
def f2(n)
return n.odd? ? (n * 3 + 1) / 2 : n / 2
end
def seq(n)
l = [n]
while (n != 1)
n = f2(n)
l << n
end
return l
end
def addgap(i)
a, b = $x[i, 2]
d = b - a
$g[d] = $g.fetch(d, []) + [[a, b]]
$mx = [$mx, d].compact.max
end
def rmgap(a, b)
d = b - a
$g[d] -= [[a, b]]
if ($g[d].empty?) then
$g.delete(d)
$mx = $g.keys.max if (d == $mx)
end
end
def recalc(r)
r.to_a.select { |x| x >= 0 }.each \
{
|x|
$gd[$x[x]] = [x > 0 ? $x[x - 1] : nil, $x[x + 1]].compact.map { |x1| ($x[x] - x1).abs }.max
}
end
def gap(z)
i = (0...$x.size).bsearch { |x| $x[x] >= z }
if (i.nil?) then
$x << z
return if ($x.size == 1)
addgap($x.size - 2)
recalc(($x.size - 2)..($x.size - 1))
return
end
return if ($x[i] == z)
rmgap(*$x[i - 1, 2]) if (i > 0)
$x[i, 0] = z
addgap(i)
addgap(i - 1) if (i > 0)
recalc((i - 1)..(i + 1))
end
def gapmx(z)
gap(z)
x = $gd[z]
return x.nil? ? 0 : x
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 hist(l)
a = {}
l.each { |x| a[x] = a.fetch(x, 0) + 1 }
return a
end
def hdiff(h1, h2)
d = 0
(h1.keys | h2.keys).each { |x| d += (h1.fetch(x, 0) - h2.fetch(x, 0)).abs }
return d
end
def hdiff2(h2a, h2b)
return hdiff(h2a[0], h2b[0]) + hdiff(h2a[1], h2b[1])
end
def hist2(ns)
l1, l0 = len01(ns)
return hist(l0), hist(l1)
end
def runsd(a = nil, s1 = nil)
return {'x' => 0, 'x2' => 0, 'l' => [], 'c' => 20} if (a.nil?)
a['l'] << s1
a['x'] += s1
a['x2'] += (s1 ** 2)
if (a['l'].size == a['c'] + 1) then
x1 = a['l'].shift
a['x'] -= x1
a['x2'] -= (x1 ** 2)
end
a1 = a['x'] / a['l'].size
z = a['x2'] / a['l'].size - a1 ** 2
z = 0 if (z < 0)
sd = Math.sqrt(z)
z1 = s1 == 0 ? 1 : sd / s1
return z1
end
def hdiff1(l1)
l = []
t = 1
th = 0
c = 20
sd = runsd()
while (t < 100)
ns = l1[t - 1].to_s(2)
t01 = $h[nw = ns.length]
hd = hdiff2(hist2(ns), t01) / t01[2]
th += hd
s1 = th / t
l << {'t' => t, 's1' => s1, 'nw' => nw}
z1 = runsd(sd, s1)
l[-1]['z1'] = z1
break if (t >= c && z1 < 0.005)
t += 1
end
return {'h' => l[-1]['s1'], 't2' => t}
end
def count(ns, l2 = [])
l = seq(n = ns.to_i(2))
cg = l.index { |x| x < l[0] }
cg = l.size - 1 if (cg.nil?)
cm = (0..cg).max_by { |x| l[x] }
c = l.size
ha = hdiff1(l)
return {'ns' => ns,
'c' => c,
'cg' => cg,
'cm' => cm,
'l' => l
}.merge(ha).merge({'g' => gapmx(ha['h'])})
end
def out(fn, a, d, a2 = {}, t = nil)
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?)
f2.puts("'#{fn}' using (column('t')):(column('#{x}')) every #{d} with line title '#{x}' #{a2[x]}, \\")
}
f2.puts
f2.close
end
$f1.puts(a.values_at(*k).join("\t"))
$f1.flush
end
def rank(x)
return -x['z']
end
def adj(x, wt, km)
z = 0
km.keys.each { |k| z += (x[k] - wt["#{k}_a"]) / wt["#{k}_sd"] * km[k] }
x['z'] = z
raise [x, wt].to_s if (!z.finite?)
return x
end
def fmt(a)
['ns', 'l'].each { |x| a.delete(x) }
return a
end
def add(bs, km, k, h, ns, l1, wt, t, d)
j = ns.length
h[j] = [] if (!h.member?(j))
x = adj(count(ns), wt, km)
a, b = [h[j][0], h[j][-1]]
return if (h[j].map { |x| x['ns'] }.member?(x['ns']))
x['t'] = t
h[j] << x
h[j].sort_by! { |x| rank(x) }
h[j][bs..-1] = [] if (h[j].size > bs)
x1 = x.dup
x1.delete('l')
out('out.txt', x1, d, x1y2().merge({'ns' => nil}))
l1 << x.dup if (!l1.nil?)
end
def init(w, m)
return '1' * w
end
def initd(w, m)
d = m.to_f / w
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 initb(w, m)
r = m.to_f / w
return '1' + (1...w).map { rand < r ? '0' : '1' }.join
end
def initw(w, m)
s = initd(w, w / 2)
i = rand(w - m) + 1
m = [w - i, m].max
s[i, m] = rand(2).to_s * m
return s
end
def mut(ns)
ns = ns.dup
i = rand(ns.length - 1) + 1
ns[i, 1] = (ns[i, 1].to_i ^ 1).to_s
return ns
end
def inner(ns1, ns2)
a, b = [ns1, ns2].sort_by { |x| x.length }
d = b.length - a.length
i = rand(d + 1)
c = b.dup
c[i, a.length] = a
ns1.replace(b)
ns2.replace(c)
end
def mix(ns1, ns2)
ns1 = ns1.dup
ns2 = ns2.dup
inner(ns1, ns2)
return (0...ns1.length).map { |x| [ns1, ns2][rand(2)][x, 1] }.join
end
def cut(ns1, ns2)
ns1 = ns1.dup
ns2 = ns2.dup
inner(ns1, ns2)
i = rand(ns1.length)
return ns1[0...i] + ns2[i..-1]
end
def ext(ns)
ns = ns.dup
(rand(3) + 1).times { ns[rand(ns.length) + 1, 0] = rand(2).to_s }
return ns
end
def short(ns)
return ns if (ns.length == 1)
ns = ns.dup
(rand([ns.length - 1, 3].min) + 1).times { ns[rand(ns.length - 1) + 1, 1] = '' }
return ns
end
def top(h1)
return h1[rand([h1.size / 4, h1.size].max)]
end
def stat(l)
return 0, 1.0 if (l.empty?)
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 a, sd
end
def dist(km, h, wt)
l = h.values.flatten
km.keys.each \
{
|k|
a, sd = stat(l.map { |x| x[k] })
sd = 1.0 if (sd == 0)
wt.merge!({"#{k}_a" => a, "#{k}_sd" => sd})
}
end
def nonnil(x, y)
return x.nil? ? y : x
end
def opt(km, w1, k, l1, n)
h = {}
ops = ['init0', 'initd0', 'initb0', 'initw0', 'mut1', 'mix2', 'cut2']
# ops += ['ext1', 'short1']
bs = 500
bc = 50
t = 0
d = n / 2000
d = 1 if (d == 0)
wt = {}
n.times \
{
if (t % 100 == 0) then
dist(km, h, wt)
h.values.flatten.each { |x| adj(x, wt, km) }
end
opc = ops[rand(ops.size)]
c = opc[-1..-1].to_i
op = opc[0..-2]
ks = h.keys.sort_by { |x| rank(h[x][0]) }
ks = ks[0...[ks.size, ks.size / 4].max]
case (c)
when 0
w = ks.empty? ? w1 : ks[rand(ks.size)]
ns = send(op, w, rand(w))
when 1, 2
redo if (h.empty?)
h.delete(ks.pop) if (ks.size > bc)
arg = (0...c).map { ks[rand(ks.size)] }
l = arg.map { |x| top(h[x])['ns'] }
ns = send(op, *l)
ns[0, 1] = '1'
end
ns[-1, 1] = '1'
add(bs, km, k, h, ns, l1, wt, t, d)
if (t % 100 == 0) then
kmx = nonnil(h.values.flatten.max_by { |x| x[k] }, {}).dup
h0 = nonnil(h.fetch(ks[0], [])[0], {}).dup
k0 = "#{k}_0"
msg = Hash[[['t', 'hmn', 'hmx', 'hc', 'h_0', k0], [t, ks.min, ks.max, h.size, h0, kmx]].transpose]
['h_0', k0].each { |x| fmt(msg[x]) }
$stderr.puts(msg)
end
t += 1
}
return h
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 key top left opaque; set title '#{t}'; ")
f.puts("set ytics nomirror; set y2tics;")
f.puts("plot \\")
k, ct = [k - ['t'], "(column('t')):"] if (k.member?('t'))
k.each \
{
|x|
next if (a.member?(x) && a[x].nil?)
opt = a.fetch(x, '')
opt += ' lw 2 ' if (!opt.include?('lw'))
opt += ' with line ' if (!opt.include?('with') && !opt.include?('pt'))
f.puts("'$dat' using #{ct}(column('#{x}')) #{opt} title '#{x}',\\")
}
f.puts
# f.puts("reset; pause -1;")
end
def outafn(l, a = {}, fn = nil, t = '')
outa(f = File.open(fn.nil? ? 'gnuplot.cmd' : fn, 'w'), l, a, t)
f.close
end
def d(s)
c = s.split('').select { |x| x == '1' }.size
d = c.to_f / s.length
return d
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 e(ns)
return len01(ns).flatten.size.to_f / ns.length
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 right opaque;\\")
f.puts("plot \\")
f.puts("[0:#{l.size - 1}][0:#{w}] '-' matrix using 2:1:3 with image title '', \\")
f.puts("'-' using (column('d')) with line axes x1y2 dt 2 lw 3, \\")
f.puts("'-' using 1 with line title 'e' axes x1y2 dt 2 lw 3")
l1 = []
l.each_with_index \
{
|z, i|
l1 << [d(z), e(z)]
c = w - z.length
z[z.length...w] = '0' * c
f.puts(z.split('').join(' '))
}
f.puts("eof")
f.puts("eof")
f.puts("d")
l1.each { |x| f.puts(x[0]) }
f.puts("eof")
l1.each { |x| f.puts(x[1]) }
f.puts("eof")
end
def grid(l, fn, t)
f = File.open(fn, 'w')
f.puts("set palette negative grayscale; unset colorbox; set title '#{t}';")
fmt1(l.map { |x| x.reverse }, f)
f.close
end
def sample(l, c)
return l if (l.size < c)
r = l.size / c
l2 = *(0...l.size).select { |x| x % r == 0 }
l2[c..-1] = []
return l.values_at(*l2)
end
def convert(l)
x2 = nil
l2 = []
l.each_with_index \
{
|x, j|
next if (x == x2)
l2 << [j, x]
x2 = x
}
return l2
end
def convert1(l, x)
l << convert(len(x, /0+/).sort)
end
def outd(f, l, n = '')
f.puts("$dat#{n} << eof")
k = l[0].keys
f.puts(k.join("\t"))
l.each { |x| f.puts(x.values.join("\t")) }
f.puts('eof')
return k
end
def triplets(l1, f, n = '')
l2 = []
l1.each_with_index \
{
|l, t|
l.each { |x, y| l2 << {'x' => x, 'y' => y, 't' => t}}
l2 << {}
}
$stderr.puts(l2.size)
outd(f, l2, n)
end
def hist1(l)
l2 = []
l.reverse.each_with_index \
{
|ns, j|
convert1(l2, ns)
}
fn, t = plotfn("hist")
f = File.open(fn, 'w')
triplets(l2.reverse, f, 1)
f.puts("reset; plot $dat1 using (column('x')):(column('y')):(column('t')) with line linecolor palette lw 2")
f.close
end
def plotfn(t)
$n = 1 if ($n.nil?)
fn = "gnuplot#{$n}.cmd"
$stderr.puts("#{fn} <- #{t}")
$n += 1
return fn, t
end
def mx01(l)
l2 = []
l.each_with_index \
{
|ns|
mx1 = len(ns, /0+/).max
mx0 = len(ns, /1+/).max
l2 << {'mx1' => mx1, 'mx0' => mx0}
}
outafn(l2, {}, plotfn('mx01')[0])
end
def rwalk(l)
fn, = plotfn("rwalk")
f = File.open(fn, 'w')
l2 = []
l.each_with_index \
{
|ns, j|
c = 0
l1 = []
ns.reverse.split('').each_with_index { |x1, i| l1 << [i, (c += [-1, 1][x1.to_i])] }
l2 << l1
}
triplets(l2, f)
f.puts("reset; plot $dat using (column('x')):(column('y')):(column('t')) with line linecolor palette lw 2")
f.close
end
def seqs(l)
l2 = []
l.each \
{
|n|
l = seq(n)
l2 << (0...l.size).map { |x| [x, Math.log(l[x]) / Math.log(2.0)] }
}
fn, = plotfn("seq")
f = File.open(fn, 'w')
triplets(l2, f)
f.puts("reset; plot $dat using (column('x')):(column('y')):(column('t')) with line linecolor palette lw 2")
f.close
end
def axes2(x2)
return x2.inject({}) { |h, x| h.merge({x => 'axes x1y2' }) }
end
def x1y2()
$a2 = axes2(['h', 'g', 'z']) if ($a2.nil?)
return $a2
end
def graphs(k, h, l1)
l1.sort_by! { |x| x[k] }
l = h.values[0]
outafn(l.map { |x| fmt(x.dup) }.sort_by { |x| x['t']}, x1y2(), *plotfn("h(#{l.size}) by t"))
a = {'t1' => nil}.merge(x1y2())
outafn(l1.map { |x| x1 = fmt(x.dup); x1['t1'] = x1.delete('t'); x1 }, a, *plotfn("by #{k}"))
# l = sample(l1, 250)
l = l1[-250..-1].map { |x| x['ns'] }
grid(l, *plotfn("grid_{de} by #{k}"))
hist1(l)
mx01(l)
rwalk(sample(l1, 50).map { |x| x['ns'] })
seqs(sample(l1, 25).map { |x| x['ns'].to_i(2) })
end
def g(x)
gap(x)
p({'x' => x, '$x' => $x, '$g' => $g, '$gd' => $gd})
end
def testgap()
[5, 6, 1, 2, 9, 1, 3].each { |x| g(x) }
exit
end
def loadh()
f = File.open(fn = 'adapt7.txt')
$h = f.readlines.map { |x| Kernel.eval(x) }
f.close
$stderr.puts([fn, $h.size].inspect)
end
def ina(fn = 'out.txt')
l = (f = File.open(fn)).readlines
f.close
k = l.shift.split
return l.map { |x| Hash[[k, x.split.map { |x| Kernel.eval(x) }].transpose] }
end
def review()
l1 = ina()
p(l1.size)
k = 'h'
l1.sort_by! { |x| x[k] }
a = {'t1' => nil}.merge(x1y2())
$n = 8
l = l1[-250..-1].map { |x| x['ns'].to_s }
grid(l, *plotfn("grid_{de} by #{k}"))
x = ARGV[0].to_i
p(l1[x])
ns = l1[x]['ns'].to_s
l2 = seq(n = ns.to_i(2))
grid(l2.map { |x| x.to_s(2) }, *plotfn(n.to_s))
$stderr.puts(n)
exit
end
# review()
loadh()
$x = []
$g = {}
$gd = {}
#testgap()
c = 2e3
h = opt({'g' => 1}, 200, nil, l1 = [], c.to_i)
graphs('h', h, l1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment