Created
May 3, 2016 04:09
-
-
Save vznvzn/4aebcb2264ae451945d73aa89db2586b 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 f1(n) | |
n = (n * 3 + 1) / 2 while (n % 2 == 1) | |
n /= 2 while (n % 2 == 0) | |
return n | |
end | |
def stat(l) | |
return 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 | |
end | |
def sum(l) | |
t = 0 | |
l.each { |x| t += x } | |
return t | |
end | |
def coef(x, y) | |
x1 = x2 = y1 = y2 = xy = 0.0 | |
n = x.size | |
n.times \ | |
{ | |
|i| | |
x1 += x[i] | |
y1 += y[i] | |
xy += x[i] * y[i] | |
x2 += x[i] ** 2 | |
y2 += y[i] ** 2 | |
} | |
d = n * x2 - x1 ** 2 | |
a0 = (y1 * x2 - x1 * xy) / d | |
a1 = (n * xy - x1 * y1) / d | |
a0 = 1 if (a0.nan?) | |
a1 = 1 if (a1.nan?) | |
return a0, a1 | |
end | |
def err(x, y) | |
a0, a1 = coef(x, y) | |
t = 0 | |
x.size.times \ | |
{ | |
|i| | |
y2 = a0 + a1 * x[i] | |
d = (y[i] - y2) | |
t += d ** 2 | |
} | |
return a0, a1, t / x.size | |
end | |
def d(s) | |
c = s.split('').select { |x| x == '1' }.size | |
d = c.to_f / s.length | |
return d, (0.5 - d), (0.5 - d).abs, s.length, c, s.size - c | |
end | |
def d2(s) | |
return [0, 0, 0] if (s.length == 0) | |
d(s)[0..2] | |
end | |
def weight(n, l) | |
s = n.to_s(2) | |
d1, d2, d3, w, c1, c0 = d(s) | |
m = s.length / 2 | |
da = d2(s[0...m]) | |
db = d2(s[m..-1]) | |
m1 = w ** 2 | |
m2 = w ** 0.5 | |
a1, sd1 = stat(s.split('/0+/').map { |x| x.length }) | |
a0, sd0 = stat(s.split('/1+/').map { |x| x.length }) | |
l2 = [m1, m2, d1, d2, d3, w, c0, c1, a1, sd1, a0, sd0] + da + db | |
t = 0.0 | |
l2.each_with_index { |x, i| t += x * l[i] } | |
raise(l2.join(' ')) if (t.nan?) | |
return t | |
end | |
def seq(w, z) | |
n = z['n'] | |
l = [n] | |
while (n != 1) | |
l << n | |
n = f1(n) | |
end | |
return l | |
end | |
def adv2(w, z) | |
l = seq(w, z) | |
return [stat2(l, z), stat2(seq(w, z).map { |n| weight(n, w) }, z)] | |
end | |
def adv(w, z) | |
return stat2(seq(w, z).map { |n| weight(n, w) }, z) | |
end | |
def stat2(l, z) | |
c = 0 | |
m = l[0] | |
mx = 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].max | |
} | |
r = c.to_f / (l.size + 1) | |
a, sd = stat(l2) | |
return {'r' => r, 'mx' => mx, 'c' => l2.size, | |
'd' => l2.size.to_f / (l.size + 1), 'a' => a, 'sd' => sd, | |
}.merge(z) | |
end | |
def rand1() | |
return rand() * [-1, 1][rand(2)] | |
end | |
def fit(i) | |
l = $a[i]['l'] | |
a = {} | |
x = l.map { |z| z['n'].to_s(2).length } | |
$d1.keys.each \ | |
{ | |
|k| | |
y = l.map { |z| z[k] } | |
a0, a1, d = err(x, y) | |
a[k] = a1 | |
a['zd_' + k] = d | |
} | |
a['zc'] = l.size | |
a['zb'] = sum(x) | |
$a[i]['f'] = a | |
end | |
def cmp(i, j) | |
r1 = $a[i]['f'] | |
r2 = $a[j]['f'] | |
c = [0] * 3 | |
$d.keys.each \ | |
{ | |
|k| | |
raise [k, i, j, r1, r2].inspect if (r1[k].nil? || r2[k].nil?) | |
d = (r2[k] <=> r1[k]) * $d[k] | |
c[d] += 1 | |
} | |
$cm[[i, j]] = c | |
end | |
def apply(w) | |
# i = rand($db.size) | |
i = [0, 400, 500, 600][rand(4)] + rand(50) | |
x = Kernel.eval($db[i]) | |
n = x['n'] | |
z = adv(w, {'n' => n, 'k' => x['k'], 'i' => i}) | |
return z | |
end | |
def new(w, t, l, h) | |
ai = {} | |
l.each { |x| ai[x['i']] = x } | |
a = {} | |
a['l'] = ai.values | |
a['w'] = w | |
a['j'] = (n = $a.size) | |
a['h'] = h.nil? ? trace(nil) : h | |
$a << a | |
fit(n) | |
a['f']['zi'] = l.size | |
(0...n).each { |i| cmp(i, n) } | |
$l << n | |
l2 = rank() | |
i = l2.map { |x| x[1] }.index(l2.size - 1) | |
$l = l2.map { |x| $l[x[1]] } | |
r = sprintf("%.2f", i.to_f / $l.size) | |
o = File.open('out2.txt', 'a') | |
o.puts(["$a#= #{$a.size}", "r= #{r}", "$l#= #{$l.size}", "t= #{t}", "i= #{i}", "l#= #{l.size}", "ai#= #{ai.size}", "h= #{a['h'].inspect}"].join("\t")) | |
o.close | |
if (i == 0) then | |
a = $a[$l[0]] | |
o = File.open($fn, 'a') | |
o.puts(a.inspect) | |
o.close | |
f = a['f'] | |
l = a['l'] | |
p(['c', $c += 1, 'a#', $a.size, Time.now]) | |
p(['zc', 'zi', 'zb'].map { |x| [x, f[x]] }.flatten) | |
l1 = a['l'].map { |x| [x['k'], x['n'].to_s(2).length, x['i']] } | |
l1 = l1.transpose | |
p(['k', l1[0]]) | |
p(['ns', l1[1]]) | |
p(['i', l1[2]]) | |
p(['h', a['h']]) | |
puts | |
end | |
return i < t | |
end | |
def add(t, w) | |
return new(w, t, (1..3).map { apply(w) }, nil) | |
end | |
def rank() | |
l = [] | |
$l.each_with_index \ | |
{ | |
|j, k| | |
t = [0] * 3 | |
$l.each \ | |
{ | |
|i| | |
next if (i == j) | |
c = $cm[[i, j].sort] | |
c = c.values_at(0, -1, 1) if (i > j) | |
3.times { |x| t[x] += c[x] } | |
} | |
l << [t[1] - t[-1], k, t] | |
} | |
return l.sort_by { |x| x[0] }.reverse | |
end | |
def apply2(w, l) | |
return l.map \ | |
{ | |
|x| | |
adv(w, {'n' => x['n'], 'k' => x['k'], 'i' => x['i']}) | |
} | |
end | |
def extract() | |
l1 = File.open($fn).readlines | |
z = ARGV.empty? ? l1.size - 1 : ARGV[0].to_i | |
x = Kernel.eval(l1[-1]) | |
w = x['w'] | |
$stderr.puts(["l1#= #{l1.size}", "z= #{z}"].inspect) | |
f = File.open("out_#{z}.txt", 'w') | |
f2 = File.open("out_#{z}b.txt", 'w') | |
$db.each_with_index \ | |
{ | |
|z, i| | |
x = Kernel.eval(z) | |
z, z2 = adv2(w, {'n' => x['n'], 'k' => x['k'], 'i' => i, z['n2'] => x['n'].to_s.length }) | |
if (i == 0) then | |
z.keys.each_with_index \ | |
{ | |
|x, j| | |
$stderr.puts([j + 1, x, $d1[x]].inspect) | |
} | |
end | |
f.puts(z.values.join("\t")) | |
f.flush | |
f2.puts(z2.values.join("\t")) | |
f2.flush | |
} | |
f.close | |
f2.close | |
end | |
def trace1(l) | |
return $a.size.to_s if (l.nil?) | |
i, j = l | |
return ($a[i]['h'] + '*') if (j.nil?) | |
s = '(' + $a[i]['h'] + '+' + $a[j]['h'] + ')' | |
return s if (s.length < 1000) | |
return s[0, 1000] | |
end | |
def trace2(l) | |
return [0, 0, [$a.size]] if (l.nil?) | |
i, j = l | |
if (j.nil?) then | |
l2 = $a[i]['h'].dup | |
l2[0] += 1 | |
l2[2] |= [$a.size] | |
return l2 | |
end | |
l1 = $a[i]['h'] | |
l2 = $a[j]['h'] | |
return [l1[0] + l2[0], l1[1] + l2[1] + 1, l1[2] | l2[2] | [$a.size]] | |
end | |
def trace(l) | |
return trace2(l) | |
end | |
$db = File.open('db.txt').readlines | |
$d1 = {'mx' => -1, 'a' => -1, 'c' => 1, 'd' => 1, 'sd' => -1, 'r' => 1} | |
$fn = 'out.txt' | |
if (File.exists?($fn)) then | |
extract() | |
exit | |
end | |
$d = $d1.merge('zc' => 1, 'zb' => 1) | |
# $d1.keys.each { |k| $d['zd_' + k] = -1 } | |
$cm = {} | |
$a = [] | |
$l = [] | |
$c = 0 | |
c = 0 | |
z = 10 | |
loop \ | |
{ | |
f = add(z, (1..18).map { rand1() }) | |
c = f ? 0 : c + 1 | |
break if (c == z) | |
} | |
c = $l.size / 2 | |
f = nil | |
loop \ | |
{ | |
$l.pop if (f || $l.size >= 250) | |
f ? c -= 1 : c += 1 | |
c = [c, 2].max | |
c = [c, $l.size].min | |
if (rand(2) == 0) then | |
i = $l[rand(c)] | |
w = $a[i]['w'].dup | |
j = rand(w.size) | |
w[j] *= rand() * 2.0 * [-1, 1][rand(2)] | |
h = trace([i]) | |
f = new(w, c, apply2(w, $a[i]['l']) + [apply(w)], h) | |
else | |
l = (0...c).to_a | |
x, y = (1..2).map { l.delete_at(rand(l.size)) } | |
i = $l[x] | |
j = $l[y] | |
w1 = $a[i]['w'] | |
w2 = $a[j]['w'] | |
w = [w1, w2].transpose.map { |x| x[rand(2)] } | |
h = trace([i, j]) | |
l2 = $a[i]['l'] + $a[j]['l'] | |
m = [i, j].map { |x| $a[x]['l'].size }.max | |
l3 = [] | |
m.times { l3 << l2.delete_at(rand(l2.size)) } | |
f = new(w, c, apply2(w, l3), h) | |
end | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment