daily pastebin goal
28%
SHARE
TWEET

Untitled

a guest May 16th, 2018 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def f1(n)
  2.     n = (n * 3 + 1) / 2 while (n.odd?)
  3.     n /= 2 while (n.even?)
  4.     return n
  5. end
  6.  
  7. def f2(n)
  8.     return n.odd? ? (n * 3 + 1) / 2 : n / 2
  9.  
  10. end
  11.  
  12. def dense(w, d)
  13.     w2 = w - 1
  14.    
  15.     a = (0...w2).to_a
  16.     s = '0' * w2
  17.     (1..(d * w - 1)).map { a.delete_at(rand(a.size)) }.each { |x| s[x, 1] = '1' }
  18.     return ('1' + s)
  19.    
  20. end
  21.  
  22. def d(s)
  23.         c = s.split('').select { |x| x == '1' }.size
  24.     d = c.to_f / s.length
  25.         return d
  26.        
  27. end
  28.  
  29.  
  30. def mx3(n)
  31.     ns = n.to_s(2)
  32.     nl = ns.length
  33.     l1 = ns.split(/0+/).map { |x| x.length }
  34.     l0 = [ns.split(/1+/)[1..-1]].compact.flatten.map { |x| x.length }
  35.  
  36.     mx = [l0.max, l1.max].compact.max
  37.     return {'mx' => mx, 'mxs' => mx.to_f / nl}
  38. end
  39.  
  40. def count(x, k)
  41.     n = n1 = x['n']
  42.     i = 0
  43.     l = [n]
  44.     l1 = []
  45.     i = nil
  46.    
  47.     while (n >= n1 && n != 1)
  48.         n = {'packed' => true, 'unpacked' => false}[$w] ? f1(n) : f2(n)
  49.         l << n
  50.        
  51.         l1 << d(n.to_s(2)) - 0.5 if (k == 'j2nl')
  52.         l1.shift if (l1.size == 3)
  53.         i = l.size if (i.nil? && l1.size == 2 && l1[0] * l1[1] < 0)
  54.  
  55.     end
  56.  
  57.  
  58.     nl = x['ns'].length
  59.     cm = (0...l.size).max_by { |x| l[x] }
  60.     j2 =  i.nil? ? 0 : cm - i
  61.    
  62.     j = jl = jr = 0
  63.     if (['cm', 'jlcm', 'cmjl'].member?(k)) then
  64.  
  65.         l.each_with_index \
  66.         {
  67.             |n, i|
  68.             next if (!n.odd?)
  69.            
  70.             j += 1
  71.             i < cm ? jl += 1 : jr += 1
  72.         }
  73.  
  74.         return nil if (k == 'jlcm' && n1 >= 10 && jl == cm)
  75.         x.merge!({'j' => j,
  76.             'jl' => jl,
  77.             'jr' => jr,
  78.             'cmj' => cm - j,
  79.             'cmjl' => cm - jl,
  80.             'jlcm' => jl.to_f / (cm == 0 ? 1 : cm)})
  81.     end
  82.  
  83.     if (['mc', 'mcs'].member?(k)) then
  84.        
  85.         mx = {'mx' => 0, 'mxs' => 0, 'mw' => 0, 'mi' => 0, k => 0}
  86.         k2 = {'mc' => 'mx', 'mcs' => 'mxs'}[k]
  87.         l[0..cm].each_with_index \
  88.         {
  89.             |n, i|
  90.  
  91.             mx = [mx, mx3(n).merge({'mw' => i - mx['mi'], 'mi' => i, k => mx[k] + 1})].max_by { |x| x[k2] }
  92.         }
  93.         x.merge!(mx)
  94.     end
  95.    
  96.     return x.merge({
  97.         'd' => (0.5 - d(x['ns'])).abs,
  98.         'cm' => cm,
  99.         'c' => l.size,
  100.         'nl' => nl,
  101.         'j2nl' => j2 - nl})
  102. end
  103.  
  104.  
  105. def init1(w, m)
  106.  
  107.     l = []
  108.     b = 1
  109.     while (w > 0)
  110.         t = [w, m].min
  111.         r = (t <= 1) ? 1 : rand(t) + 1
  112.         l << [b] * r
  113.         b ^= 1
  114.         w -= r
  115.     end
  116.     s = l.flatten.join
  117.     return s
  118. end
  119.  
  120. def init2(w, m)
  121.  
  122.     return dense(w, m.to_f / w)
  123. end
  124.  
  125. def init3(w, m)
  126.     r = m.to_f / w
  127.     return '1' + (1...w).map { rand < r ? '0' : '1' }.join
  128.    
  129. end
  130.  
  131.  
  132. def init(w, k)
  133.    
  134.     l = []
  135.    
  136.     (1..w).each \
  137.     {
  138.         |w|
  139.         3.times \
  140.         {
  141.             |i|
  142.             m = rand(w)
  143.             ns = nil
  144.             case (i)
  145.                 when 0
  146.                     ns = init1(w, m)
  147.                 when 1
  148.                     ns = init2(w, m)
  149.                 when 2
  150.                     ns = init3(w, m)
  151.             end
  152.            
  153.             z = count({'ns' => ns, 'n' => ns.to_i(2)}, k)
  154.             redo if (z.nil?)
  155.            
  156.             l << z
  157.         }
  158.     }
  159.     h = (0..w).map { [] }
  160.     l.each { |x| h[x['nl']] << x }
  161.    
  162.    
  163.     return h
  164. end
  165.  
  166. def get(h, i)
  167.    
  168.     m = h[i].size
  169.     r = h[i].size / 4
  170.    
  171.     return h[i][rand(r == 0 ? m : r)]['ns']
  172. end
  173.  
  174. def out1(fn, l, l2)
  175.  
  176.     $fn = {} if ($fn.nil?)
  177.    
  178.     if (!$fn.member?(fn)) then
  179.         $fn[fn] = File.open(fn, 'w')
  180.         $fn[fn].puts(l[0].keys.join("\t"))
  181.        
  182.         f = File.open('gnuplot.cmd', 'w')
  183.         l2.each { |x| f.puts(x) }
  184.         f.close
  185.     end
  186.    
  187.     f = $fn[fn]
  188.     l.each { |x| f.puts(x.values.join("\t")) }
  189.     f.flush
  190.  
  191. end
  192.  
  193. def fmt(s, fn, l2)
  194.    
  195.     return ["#{s} plot \\"] + l2.map { |x| "'#{fn}' using #{x}, \\" } + ['']
  196.  
  197. end
  198.  
  199. def out2(fn, l, l2, s)
  200.    
  201.     out1(fn, l, fmt(s, fn, l2))
  202.    
  203. end
  204.  
  205.  
  206. def order(h)
  207.    
  208.     return Hash[h.sort_by { |k, v| v }.reverse]
  209. end
  210.  
  211. def opt(w, k)
  212.  
  213.     h = init(w, k)
  214.    
  215.    
  216.     n = c = c2 = m = 0
  217.     mx2 = nil
  218.     ops1 = {}
  219.     ops2 = {}
  220.     mxc = 1e5
  221. #   mxc = 1e3
  222.     loop \
  223.     {
  224.         t = rand(h.size - 2) + 2
  225.        
  226.         case (op = ['mut', 'mix', 'cut', 'cut2', 'up'][rand(5)])
  227.             when 'mut'
  228.                 ns1 = get(h, t)
  229.                 ns = ns1.dup
  230.                 i = rand(t - 1) + 1
  231.                 ns[i, 1] = (ns1[i, 1].to_i ^ 1).to_s
  232.                
  233.             when 'mix'
  234.                 ns1 = get(h, t)
  235.                 ns2 = get(h, t)
  236.                 ns = ''
  237.                 t.times \
  238.                 {
  239.                     |i|
  240.                     ns[i, 1] = [ns1[i, 1], ns2[i, 1]][rand(2)]
  241.                 }
  242.                
  243.             when 'cut'
  244.                 ns1 = get(h, t)
  245.                 ns2 = get(h, t)
  246.                 i = rand(t)
  247.                 ns = ns1[0...i] + ns2[i..-1]
  248.            
  249.             when 'cut2'
  250.                 ns1 = get(h, t)
  251.                 ns2 = get(h, r = rand(t - 1) + 1)
  252.                 ns = ns1.dup
  253.                 r2 = rand(r - 1) + 1
  254.                 ns[-r2..-1] = ns2[-r2..-1]
  255.                
  256.             when 'up'
  257.                 r = rand(t - 1) + 1
  258.                 ns1 = get(h, r)
  259.                 ns = '1' + (0...(t - r - 1)).map { rand(2).to_s }.join + ns1
  260.                
  261.         end
  262.        
  263.         z = count({'ns' => ns, 'n' => ns.to_i(2)}, k)
  264.        
  265.        
  266.         if (!z.nil? && h[nl = z['nl']].index { |x| x['n'] == z['n'] }.nil?) then
  267.        
  268.             x = z[k]
  269.             h[nl] << z
  270.             h[nl].sort_by! { |x| [-x[k], -x['cm']] }
  271.             if (h[nl].size > 100) then
  272.                 x2 = h[nl].pop
  273.                
  274.                 a = {'n2' => 0, 'cn' => 0}
  275.  
  276.  
  277.                 if (x2[k] < x) then
  278.                     a['n2'] = n if (n % 20 == 0)
  279.                     c += 1
  280.                     ops1[op] = ops1.fetch(op, 0) + 1
  281.                 end
  282.  
  283.                 mx = h[1..-1].map { |x| x.first[k] }
  284.                 if (mx == mx2) then
  285.                     c2 += 1
  286.                     break if (c2 > mxc)
  287.                 else
  288.                     a['cn'] = n
  289.                     c2 = 0
  290.                     ops2[op] = ops2.fetch(op, 0) + 1
  291.                 end
  292.                    
  293.                 mx2 = mx
  294.                
  295.                 if (!a.values.select { |x| x != 0 }.empty?) then
  296.                    
  297.                     l = ['c', 'c2'].map \
  298.                     {
  299.                         |x|
  300.                         [
  301.                         "(column('n')):(column('#{x}')) with line lw 3 lc 2 axes x1y2",
  302.                         "(column('n')):(column('nl')) pt 7 ps 0.5 lc 1 title 'nl'",
  303.                         "(column('n2')):(0) pt 5 ps 0.5",
  304.                         "(column('cn')):(1) pt 5 ps 0.5",
  305.                         ]                      
  306.                     }
  307.                    
  308.                     out1('out.txt',
  309.                         [a.merge({'n' => n, 'nl' => nl, 'c' => c, 'c2' => c2.to_f / mxc * 100})],
  310.                         fmt("set colors classic; set ytics nomirror; set y2tics; set key center right box opaque;",
  311.                         'out.txt',
  312.                         l[0]) + fmt('pause -1;', 'out.txt', l[1]))
  313.                     m += 1
  314.                 end
  315.  
  316.             end
  317.         end
  318.    
  319.         $stderr.puts([{'n' => sprintf("%.3g", n + 1), 'm' => m, 'c2' => (c2.to_f / mxc * 100).round(1)}, order(ops1), order(ops2)].inspect) if ((n + 1) % 5e4 == 0)
  320.    
  321.         n += 1
  322.     }
  323.     return h[1..-1].map { |x| x.first }
  324.    
  325. end
  326.  
  327. def adj(x, l1, l2, y)
  328.     return if ((i = l1.index(x)).nil?)
  329.     l2[i] += ' ' + y
  330. end
  331.  
  332. def review(fn, k)
  333.  
  334.     l = File.open(fn).readlines.map { |x| Kernel.eval(x) }
  335.    
  336.     l1 = [k, 'cm', 'c'].uniq
  337.    
  338.     l1 += ['j', 'jl', 'jr'] if (['jlcm', 'cmjl', 'cm'].member?(k))
  339.     l1 += ['cmj', 'cmjl'] if (['cm'].member?(k))
  340.     l1 += ['mx', 'mw'] if (['mc', 'mcs'].member?(k))
  341.    
  342.     l2 = l1.map { |x| "(column('#{x}')) with line" }
  343.  
  344.     adj('jlcm', l1, l2, 'axes x1y2 lw 2')
  345.  
  346.     l2[5, 0] = "0 lt bgnd title ''" if (!l2[5].nil?)
  347.    
  348.     adj('mc', l1, l2, 'axes x1y2')
  349.     adj('mcs', l1, l2, 'axes x1y2')
  350.     adj('mx', l1, l2, 'axes x1y2')
  351.    
  352.    
  353.     out2('out.txt', l.map { |x| x.select { |x, | l1.member?(x) } },
  354.     l2, 'set colors classic; set ytics nomirror; set y2tics; set key top left box opaque;')
  355.     exit
  356. end
  357.  
  358.  
  359. fn = 'mixdb.txt'
  360.  
  361. $x = 'unpacked'
  362.  
  363. # k = 'cmjl'
  364. # k = 'jlcm'
  365. # k = 'j2nl'; $x = 'packed'
  366. # k = 'mc'
  367. # k = 'mcs'
  368. k = 'cm'
  369.  
  370. review(fn, k) if (File.exist?(fn))
  371.  
  372. l = opt(100, k)
  373. f = File.open(fn, 'w')
  374. l.each { |x| f.puts(x.inspect) }
  375. f.close
RAW Paste Data
Top