tree5.rb

#!/usr/bin/ruby1.8

def fwd(x, b)

    fsm = $fsm
    
        s, i, o = x
    s = 0 if (s.nil?)
    
        return nil if (fsm[s][b].nil?)

        s2, i2, o2 = fsm[s][b]

        while (!fsm[s2][0].nil?)
                s2, i3, o3 = fsm[s2][0]
                o2 += o3

        end

        y = [s2, i + i2, o + o2]
#       p([x, b.to_s + '=>', y])

        return y

end

def fsm()

        fsm = {}
        File.open('fsm3nb.txt').each \
        {
                |ln|

                l = ln.split
                l[0] = l[0].to_i
                fsm[l[0]] = [] if (fsm[l[0]].nil?)
                next if (l.size == 1)
                l[1] = l[1].to_i
                l[3] = '' if (l[3] == '0')
                fsm[l[0]][l[2].to_i] = l[1..3]
        }

        return fsm
end

def prefix(s, x)
    
    y = x[0]
    z = x[1]
    return [s + y,  [s + z[0]] + z[1..-1]]
end

def middle(x)
    
    return (x.split('').size.even?)

end

def bin2(l)

        l = l.dup
        s = ''
        while (!l.empty?)
                l.shift
        return s + '.' if (l.empty?)

        s << (l.shift - 1).to_s
        end
        return s
end

def fmt(x)
    return '' if (x.nil?)
    return ([bin2(x[0].split('').map { |x| x.to_i}.reverse)] + x[1]).inspect
end
    
def adv(x)

    z = x[1]
    l1 = []

    if (middle(x[0])) then
    
        l1 << prefix('11', x)
        l1 << prefix('21', x)
        l1 << prefix('2', x)

        return l1 if (z[0].empty?)
    end

#    return l1
    

    z2 = z.dup
    j = 0
    while (z[j].empty?)
        j += 2
    end
#    p([j, x])
    
    s = z[j].dup
    i = s[-1].to_i
    s[-1] = ''
    
    l = [z[j + 1], '', '']
    l = fwd(l, i)
    
    return [] if (l.nil?)

    s2 = z[j + 2]
    s2 = '' if (s2.nil?)
    s2 = l[2].reverse + s2
    
    z2[j] = s
    z2[j + 1] = l[0]
    z2[j + 2] = s2 if (!s2.empty?)
    x2 = [x[0], z2]
    
#    puts(fmt(x) + "\t=>\t" + fmt(x2))
    
    l1 << x2
    
    return l1
    
end

def adv2(x)
    l = adv(x)
#    puts(fmt(x) + "\t=>\t")
    l.each \
    {
        |x|
#        puts(fmt(x))
    }
    return l
end

def seen(x)
    y = x[1].dup
    z = y.dup
    while (y[0].empty? && y[1] == 30)
        y.shift
        y.shift
    end
    
    
    
    if ($seen.member?(y)) then
#        puts("xxx")
        return true 
    end
    $seen[y] = nil
    return false
    
end

def rank1(x)
    
    l = x[1].dup
    c = 0
    l2 = []
    while (!l.empty?)
        l2 << l.shift.size
        c += l2[-1]
        l.shift
    end
    
    return [{true=>1,false=>0}[middle(x[0])], x[0].size, x[1].size, c, x[0]]
end

def rank2(x)
    return [x[0].size, x[0]]
end

def rank3(x)
    
    l = x[1].dup
    c = 0
    l2 = []
    while (!l.empty?)
        l2 << l.shift.size
        c += l2[-1]
        l.shift
    end
    
    return [{true=>1,false=>0}[middle(x[0])], c, x[0]]
    
end

def fmt2(x)
    p(x)
    return fmt(x[0]) + x[1].inspect
    
end

def rank(x)
    return rank3(x)
    
end

$fsm = fsm()
$seen = {}

l = [['', ['', 0]]]

n = 0
loop \
{
    n += 1
    
    puts
    i = (0...l.size).to_a.sort_by { |x| rank(l[x]) }
    p([n, l.size, $seen.size, i[0]])
    
    i.each { |x| printf("%-30s %s\n", rank(l[x]), fmt(l[x])) } 
    
    x = l.delete_at(i[0])
#    p([rank(x), x])

    l2 = adv2(x)
    l2.each \
    {
        |y|
        next if seen(y)
    
        l << y
    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s