Skip to content

Instantly share code, notes, and snippets.

@vznvzn
Created November 5, 2020 23:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vznvzn/c123b68b6f8543ddb4e37576a0be4a0a to your computer and use it in GitHub Desktop.
Save vznvzn/c123b68b6f8543ddb4e37576a0be4a0a 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 initgap()
$x = []
$g = {}
$gd = {}
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 log2(x)
return Math.log(x) / Math.log(2.0)
end
def count(ns)
return if (d(ns) != 0.5)
return if (len1(ns).max > log2(log2(ns.length)))
l = seq(n = ns.to_i(2))
nw = ns.length
cg = l.index { |x| x < l[0] }
cm = (0..cg).max_by { |x| l[x] }
c = l.size
h = l[cm].to_s(2).length
return {
'ns' => ns,
'nw' => nw,
'c' => c,
'cg' => cg,
'cm' => cm,
'h' => h,
'cgh' => cg.to_f / h
}
end
def axes2(x2)
return x2.inject({}) { |h, x| h.merge({x => 'axes x1y2' }) }
end
def x1y2()
return $a2 if (!$a2.nil?)
$a2 = axes2(['z', 'cgh']) if ($a2.nil?)
return $a2
end
def off()
return {'ns' => nil, 'z' => nil}
end
def opts()
return x1y2().merge(off())
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 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 out(fno, a, a2 = {}, t = nil)
$f = {} if ($f.nil?)
if (!$f.member?(fno)) then
$f[fno] = {'fn' => "out#{fno}.txt", 'c' => 0}
$f[fno]['f'] = File.open($f[fno]['fn'], 'w')
end
f = $f[fno]
f['f'].puts(a.keys.join("\t")) if (f['c'] == 0)
f['f'].puts(a.values.join("\t"))
f['c'] += 1
f['f'].flush
return if ((f['c'] - 1) % 1000 != 0)
d = (f['c'] / 2000).to_i
d = 1 if (d == 0)
f2 = File.open("gnuplot#{fno}.cmd", 'w')
fn = f['fn']
st = t.nil? ? 'unset title; ' : "set title '#{t}'; "
k = "key top left box opaque"
f2.puts("set ytics nomirror; set y2tics; set colors classic; set #{k}; #{st}; plot \\")
c1, c2 = ":(column('w'))", 'linecolor palette' if (a.key?('w'))
(a.keys - ['t']).each \
{
|x|
next if (a2.member?(x) && a2[x].nil?)
f2.puts("'#{fn}' using (column('t')):(column('#{x}'))#{c1} every #{d} with line lw 2 #{c2} #{a2[x]} title '#{x}', \\")
}
f2.puts
f2.close
end
def rank(x)
return -x['z']
end
def adj(x, wt, km)
z = 0.0
km.keys.each \
{
|k|
if (!wt.member?("#{k}_a")) then
z += x[k]
next
end
z += (x[k] - wt["#{k}_a"]) / wt["#{k}_s"] * km[k]
}
x['z'] = z
raise [x['z'], wt].to_s if (!x['z'].finite?)
return x
end
def fmt2(x)
x = x.dup
x.keys.each \
{
|k|
x.delete(k) if (k.end_with?('s'))
}
return x
end
def outd(f, l)
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')
return k
end
def hide(a, x)
return (a.member?(x) && a[x].nil?)
end
def outa(f, l, a = {}, t = '')
k = outd(f, l)
k1 = "key top left opaque"
f.puts("set colors classic; set #{k1}; set title '#{t}'; ")
f.puts("set ytics nomirror; set y2tics;")
f.puts("plot \\")
ct = ''
k, ct = [k - ['t'], "(column('t')):"] if (k.member?('t') && !hide(a, 't'))
k.each \
{
|x|
next if (hide(a, x))
opt = a.fetch(x, '')
opt += ' with line lw 2 ' if (!opt.include?('with') && !opt.include?('pt'))
f.puts("'$dat' using #{ct}(column('#{x}')) #{opt} title '#{x}',\\")
}
f.puts
f.puts("set ytics")
# f.puts("pause -1;")
end
def outafn(l, fn = nil, t = '', a = {})
fn = 'gnuplot.cmd' if (fn.nil?)
outa(f = File.open(fn, 'w'), l, a, t)
f.close
$stderr.puts([fn, l.size, t].inspect)
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")
f.puts("set ytics;")
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.puts("set palette; set colorbox; set title;")
f.close
$stderr.puts([fn, l.size, t].inspect)
end
def fn(n2)
return "gnuplot#{$n}-#{n2}.cmd"
end
def out1(h, k, a)
l = h.values.flatten
l.sort_by! { |x| x[k] }
t = a.inspect.sub("{", "\\{").sub("}", "\\}")
outafn(l, fn(1), t, opts().merge({'t' => nil}))
grid(l.map { |x| x['ns'] }, fn(2), t)
end
def add(bs, km, h, ns, l1, wt, t)
return 0 if ((a1 = count(ns)).nil?)
j = ns.length
h[j] = [] if (!h.member?(j))
x = adj(a1, wt, km).merge({'t' => t})
return 0 if (h[j].map { |x1| x1['ns'] }.member?(x['ns']))
j2 = (0...h[j].size).bsearch { |i| h[j][i]['z'] <= x['z'] }
j2 = h[j].size if (j2.nil?)
h[j][j2, 0] = x
h[j][bs..-1] = [] if (h[j].size > bs)
x1 = x.dup
out(1, x1, opts())
l1 << x1 if (!l1.nil?)
return 1
end
def initd(w)
return(dense(w, rand))
end
def initdh(w)
return(dense(w, 0.5))
end
def initb(w)
r = rand
return '1' + (1...w).map { rand < r ? '0' : '1' }.join
end
def initw(w)
s = dense(w, 0.5)
m = rand(w)
i = rand(w - m) + 1
s[i, m] = rand(2).to_s * m
return s
end
def initr(w)
s = '1'
b = 0
m = rand(w - 1) + 1
while (s.length < w)
z = w - s.length
s += b.to_s * [rand(m - 1) + 1, z].min
b ^= 1
end
return s
end
def init(w)
m = rand(w)
ns1 = dense(w, 0.5)
ns2 = initr(w)
ns1, ns2 = [ns2, ns1] if (rand(2) == 0)
i = rand(w - m) + 1
ns1[i, m] = ns2[i, m]
return ns1
end
def initx(w)
return '1' if (w == 1)
ns = dense(w, 0.5)
r1, r2 = (1..2).map { rand(w - 1) + 1 }.sort
w2 = r2 - r1 + 1
s1 = ['01', '10'][rand(2)]
s = (s1 * ((w2 / 2) + 1))[0...w2]
ns[r1..r2] = s
return ns
end
def inity(w)
return '1' * w if (w <= 2)
w2 = w / 2
w1 = rand(w2)
ns = '1' + '0' * (w - w1 - 1) + '1' * w1
l = (1..(w - w1 - 1)).to_a
(w2 - w1 - 1).times { ns[l.delete_at(rand(l.size)), 1] = '1' }
return ns
end
def mark(w, c)
l = (0...w).to_a
ns = '0' * w
c.times { ns[l.delete_at(rand(l.size))] = '1' }
return ns
end
def mark2(w, c2)
w1 = rand(w2 = w / 2)
ns1 = mark(w1, c = rand(w1 + 1))
ns2 = mark(w - w1 - 1, c2 - c)
# p([[ns1, ns1.length, c], [ns2, ns2.length, c2 - c]])
return ns1 + ns2
end
def flip(ns)
ns = ns.dup
ns.length.times { |i| ns[i] = (ns[i].to_i ^ 1).to_s }
return ns
end
def initm(w)
return '1' * w if (w <= 2)
ns = '1' + mark2(w, w / 2 - 1)
return ns
end
def initmf(w)
return '1' * w if (w <= 2)
ns = '1' + flip(mark2(w, w / 2)).reverse
return ns
end
def range(w)
return [1] if (w == 1)
a = (1..w).to_a
l = (1..2).map { a.delete_at(rand(a.size)) }.sort
return (l[0]..l[1]).to_a
end
def scatter(w)
return [1] if (w == 1)
a = (1..w).to_a
c = rand(a.size) + 1
l = (1..c).map { a.delete_at(rand(a.size)) }.sort
return l
end
def mut(ns, l)
ns2 = ns.dup
l.each { |i| ns2[i, 1] = (ns[i, 1].to_i ^ 1).to_s }
return ns2
end
def muta(ns)
return mut(ns, range(ns.length - 1))
end
def mutb(ns)
return mut(ns, scatter(ns.length - 1))
end
def remix(ns, l1)
ns2 = ns.dup
l2 = l1.shuffle
l1.size.times { |i| ns2[l2[i], 1] = ns[l1[i], 1] }
return ns2
end
def remixa(ns)
return remix(ns, range(ns.length - 1))
end
def remixb(ns)
return remix(ns, scatter(ns.length - 1))
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 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, l1)
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}_s" => sd})
}
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 weighted(ops, ar, ar2, ar1)
ops.size.times \
{
|i|
next if (ar1[i] == 0)
ar[ops[i]] = (ar1[i].to_f / ar2[i]).round(3)
}
return rand(ops.size) if (ar.size != ops.size)
ar.replace(Hash[ar.sort_by { |x| -x[1] }])
wt = sum(ar.values)
x = rand() * wt
i = x1 = 0
i, x1 = [i + 1, x1 + ar[ops[i]]] while (x1 < x)
return i - 1
end
def top(l, c)
return l[rand(l.size < c ? l.size : l.size / c)]
end
def opt(km, w1, l1, n, w2 = false, k)
h = {}
ops = ['init', 'initd', 'initb', 'initw', 'initr', 'initx',
'inity',
'initm', 'initmf',
'initdh',
'muta1', 'mutb1', 'remixa1', 'remixb1',
'mix2', 'cut2']
ops += ['ext1', 'short1'] if (w2)
bs = 1000
bc = 50
t = c1 = 0
wt = {}
ar1 = [0] * ops.size
ar2 = ar1.dup
ar = {}
h0 = hk0 = nil
loop \
{
r = weighted(ops, ar, ar2, ar1)
opc = ops[r]
op, p = opc.start_with?('init') ? [opc, 0] : [opc[0..-2], opc[-1..-1].to_i]
ks = h.keys.sort_by { |x| rank(h[x][0]) }
case (p)
when 0
w = ks.empty? ? w1 : ks[rand(ks.size)]
ns = send(op, w)
when 1, 2
redo if (ks.empty?)
arg = (1..p).map { top(ks, 5) }
l = arg.map { |x| top(h[x], 5)['ns'] }
ns = send(op, *l)
ns[0, 1] = '1'
end
raise op if (ns[0, 1] != '1')
c = add(bs, km, h, ns, l1, wt, t)
h.delete(ks.pop) if (ks.size > bc)
c1 += c
ar1[r] += c
ar2[r] += 1
if (c == 1 \
&& (((hs = h.values.flatten.size) < bs && c1 % 5 == 0) \
|| c1 % 250 == 0)) then
dist(km, h, wt, l1)
out(2, {"#{k}_a" => wt["#{k}_a"],
'h0' => h0.nil? ? 0 : h0[k],
"#{k}_0" => hk0.nil? ? 0 : hk0[k],
'hs' => hs,
't' => t}, {'hs' => 'dt 3 axes x1y2'})
h.values.flatten.each { |x| adj(x, wt, km) }
h.each { |k, l| l.sort_by! { |x| rank(x) } }
out1(h, k, km.merge({'k' => k, 'w2' => w2, 'c1' => c1})) if (c1 != 0 && c1 % 2e3 == 0)
end
if (t % 1000 == 0) then
msg = {'t' => t,
'c1' => c1,
'f' => (c1.to_f / t * 100).round(2),
'hmn' => ks.min,
'hmx' => ks.max,
'hc' => h.size}
$stderr.puts(msg)
if (t % 10000 == 0) then
h0 = h.fetch(ks[0], [])[0]
hk0 = h.values.flatten.max_by { |x| x[k] }
tn = nil
[[h0, 'h0'], [hk0, k]].each \
{
|x, v|
x = {} if (x.nil?)
t21 = t - x.fetch('t', 0)
tn = t21 - n
$stderr.puts("\t#{v} -> " + x.merge({'t21' => t21, 'tn' => tn}).inspect)
}
$stderr.puts("\t" + ar.inspect)
$stderr.puts("\t" + wt.inspect)
break if (tn > 0)
end
end
t += 1
}
return h
end
def run(a, w, k)
$n = 0 if ($n.nil?)
$n += 1
$f = nil
c = 5e4.to_i
# c = 1e4.to_i
h = opt(a, w, nil, c, false, k)
end
initgap()
File.delete(*Dir.glob('gnuplot*.cmd'))
a = {'c' => 1, 'cm' => 1, 'cg' => 1}
[100, 120, 140, 160, 180, 200].each { |w| run({(k = 'cgh') => 1}, w, k) }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment