Created
October 2, 2015 18:42
-
-
Save vznvzn/bf301fb5791a3af6212b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/ruby1.8 | |
def dense(n) | |
s = n.to_s(2) | |
c = 0 | |
s.length.times \ | |
{ | |
|i| | |
c += s[i, 1].to_i | |
} | |
return c.to_f / s.length | |
end | |
def f1(n) | |
n = (n * 3 + 1) / 2 if (n.odd?) | |
n /= 2 while (n.even?) | |
return n | |
end | |
def f(n) | |
n1 = n | |
c = 0 | |
l = [] | |
while (n != 1 && n >= n1) | |
n = f1(n) | |
l << n | |
c += 1 | |
end | |
return {'c' => c, 'd' => (0.5 - dense(n1)).abs} | |
end | |
def long(m) | |
l = [{'n' => 1, 'p' => 0}.merge(f(1))] | |
t = 0 | |
loop \ | |
{ | |
l = l.sort_by { |x| [x['c'], -x['d']] }.reverse | |
x = l.delete_at(rand([l.size, 20].min)) | |
p2 = x['p'] + 1 | |
n2 = x['n'] + 2 ** p2 | |
x1 = x.dup | |
x1['p'] = p2 | |
l << x1 | |
x2 = {'n' => n2, 'p' => p2}.merge(f(n2)) | |
l << x2 | |
t += 1 | |
return if (t >= 2000) | |
z = l.max_by { |x| x['c'] } | |
return z['n'] if (z['c'] >= m) | |
} | |
end | |
def adj1(n, m) | |
return n + (m * 2) | |
end | |
def adj2(n, m) | |
n >>= m | |
return n != 0 ? n : 1 | |
end | |
def adj3(n, m) | |
ns = n.to_s(2) | |
ns[0...m] = '0' * m | |
ns[m, 1] = '1' | |
return ns.to_i(2) | |
end | |
def mono(l) | |
y = nil; | |
c = m = 0 | |
l.each \ | |
{ | |
|x| | |
c += 1 | |
m = [m, c].max | |
next if (!(y.nil? || x < y)) | |
y = x | |
c = 0 | |
} | |
return m | |
end | |
def adjn(n, i, w) | |
case w | |
when 1 | |
return adj1(n, i) | |
when 2 | |
return adj2(n, i) | |
when 3 | |
return adj3(n, i) | |
end | |
end | |
def test(n, t, w) | |
l = [n] | |
(t - 1).times { |i| l << adjn(n, i + 1, w) } | |
l2 = [] | |
begin | |
c = 0 | |
l.size.times { |i| l[i] = f1(l[i]); c += l[i].to_s(2).length } | |
l2 << c | |
end while (l.select { |x| x == 1 }.size < l.size) | |
return mono(l2), l2.length | |
end | |
500.times \ | |
{ | |
|c| | |
n = long(c) | |
puts((1..3).map { |w| test(n, 50, w) }.join("\t")) | |
$stdout.flush | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment