db2.rb

#!/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 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 max_by_n(l)

        i = -1
        return l.map { |x| i += 1; [x, i] }.max[1]

end

def max_by2(l)

        i = max_by_n(l.map { |x| x[0] })
        return l[i][1]

end

def widthdiff(x, y)
        x.to_s(2).length - y.to_s(2).length
 
end

def widthratio(x, y)
        x.to_s(2).length.to_f / y.to_s(2).length
end

def f(x)

        n = n1 = x['n'] 
        c = 0
        l = [n]
        cg = nil

        while (n != 1)

                n = f1(n)

                l << n
                c += 1

                cg = c if (cg.nil? && n < n1)

        end
        cm = max_by_n(l)

        return x.merge!({'cm' => cm,
                'cg' => cg.nil? ? 0 : cg, 
                'm' => l[cm].to_s(2).length,
                'w' => widthdiff(l[cm], n1),
                'r' => widthratio(l[cm], n1),
                'c' => l.size,
                'd' => (0.5 - dense(n1)).abs})
 
end

def long(m, w)

        x = {'k' => w}

        return f(x.merge!({'n' => (n = rand(2 ** (s = m * 1000)) | 1), 's' => s, 'p' => n.to_s(2).length})) if (w == 'z') 

        l = [f(x.merge!({'n' => 1, 'p' => 1}))]

        s = nil
        e = 2000

        loop \
        {
                l = l.sort_by { |x| [x[w], -x['d']] }.reverse
 
                x = l.delete_at(rand([l.size, 20].min))
 
                l << x.dup.merge!({'p' => x['p'] + 1})
 
                l << f(x.dup.merge!({'n' => x['n'] + 2 ** x['p'], 'p' => x['p'] + 1}))
 
                s = l.size.to_f / e 

                break if (s >= m)
        }

        if (w == 'r') then
                z = max_by2(l.sort_by { |x| x['n'] }.reverse[0...100].map { |x| [x['r'], x] })
        else
                z = max_by2(l.map { |x| [x[w], x] })
        end

        return z.merge({'s' => s})
 
end

def hard(k, m, x)

        if (x.empty?) then
                x['k'] = k
                x['a'] = {}
                x['c'] = 0
        end

        begin

                z = long(m, k)

                x['c'] += 1

                n = z['n']
        end while (x['a'].member?(n))

        x['a'][n] = nil

        $f.puts(z.inspect)
        $f.flush

        $stderr.puts([x['c'], x['a'].size, k, z['s'], n.to_s(2)].inspect)
end


p = ['w', 'p', 'c', 'm', 'cg', 'cm', 'r', 'z']

$f = File.open('db.txt', 'w')

c = 100

p.each { |k| x = {}; c.times { |j| hard(k, j.to_f / c, x) } }