Skip to content

Instantly share code, notes, and snippets.

@vznvzn
Created November 22, 2016 21:30
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/18d88f5dcb8ccac1be108ff47f9618f1 to your computer and use it in GitHub Desktop.
Save vznvzn/18d88f5dcb8ccac1be108ff47f9618f1 to your computer and use it in GitHub Desktop.
def d(s)
c = s.split('').select { |x| x == '1' }.size
d = c.to_f / s.length
return d
end
def stat(l)
return 0, 0, 0, 0 if (l.empty?)
t = t2 = 0
l.each \
{
|x|
t += x
t2 += x ** 2
}
c = l.size
a = t.to_f / c
z = t2.to_f / c - a ** 2
sd = Math.sqrt(z < 0 ? 0 : z)
return a, sd, l.max.to_f, l.min.to_f
end
def mono(l)
l = [] if (l.nil?)
c = 0
m = l[0]
mx = nil
j = 0
l2 = []
(1...l.size).each \
{
|i|
c += 1 if (l[i] < l[i - 1])
if (l[i] < m) then
l2 << i - j
m, j = [l[i], i]
end
mx = [mx, i - j].compact.max
}
mx = 0 if (mx.nil?)
return {'mx' => mx, 'ls3' => l.size}
end
def f2(n)
n = (n * 3 + 1) / 2 while (n.odd?)
n /= 2 while (n.even?)
return n
end
def adv(x)
n1 = n = x['n']
ns = n.to_s(2)
x['d'] = d(ns)
l = [n]
while (n >= n1 && n != 1)
n = f2(n)
l << n
end
j = (0...l.size).max_by { |x| l[x] }
x['ls'] = l.size
x['ns'] = ns.length
x['j'] = j
x['ls2'] = l.size - j
t = [l.size - 100, 0].max
return x.merge(mono(l[t..-1]))
end
def next2(z)
l = [z]
p = z['p'] + 1
l << adv({'n'=>z['n'] + 2**p, 'p'=>p})
l << z.merge({'p'=>p})
return l
end
def insert(l, x)
l << x
end
def delete(l, j)
z = l.delete_at(j)
return z
end
def sum(l)
t = 0
l.each { |x| t += x }
return t
end
def rank(l, w1)
l2 = []
l.size.times \
{
|x|
l1 = l[x][1].values_at(*w1)
a = {}
w1.size.times \
{
|i|
a[w1[i]] = l1[i]
}
l2 << [x, a]
}
w1.each \
{
|k|
l1 = l2.map { |x| x[1][k] }
a, sd, = stat(l1)
sd = 1 if (sd == 0)
l2.each \
{
|x|
x[1][k + 'b'] = (x[1][k] - a) / sd
}
}
b = w1.map { |x| x + 'b' }
l2.each \
{
|x|
x[1]['z'] = sum(x[1].values_at(*b))
}
l2.sort_by! { |x| [x[1]['z'], x[1]['ls'], x[1]['d']] }
l2.reverse!
j = l2[rand([l2.size, 100].min)][0]
k = l2[-1][0]
return j, k
end
def opt(w, w1, c)
l = []
insert(l, next2({'n'=>1, 'p'=>0}))
puts('# ' + Time.now.to_s)
puts((['i'] + w).join("\t"))
t = Time.now.to_i
g = c / 2000
c.times \
{
|i|
$stderr.puts([i, sprintf('%.1fm', (Time.now.to_i - t) / 60.0), Time.now.to_s].join("\t")) if (i % 100 == 0)
j, k = rank(l, w1)
if (l.size > 1000) then
z2 = delete(l, [j, k].max)
z1 = delete(l, [j, k].min)
z = j < k ? z1 : z2
else
z = delete(l, j)
end
insert(l, next2(z[1]))
insert(l, next2(z[2]))
puts(([i] + z[1].values_at(*w)).join("\t")) if (i % g == 0)
$stdout.flush
}
puts('# ' + Time.now.to_s)
end
def test(w)
puts(w.join("\t"))
File.open('db.txt').readlines.map { |x| Kernel.eval(x) }.each_with_index \
{
|x, i|
puts(adv(x).values_at(*w).join("\t"))
puts if ((i + 1) % 100 == 0)
}
end
w = ['ns', 'ls', 'ls2', 'j', 'ls3', 'mx']
w1 = ['ls', 'j', 'ls2', 'mx']
# test(w); exit
opt(w, w1, 20000)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment