tree3b.rb

#!/usr/bin/ruby1.8

def fwd(x, b, fsm)

        s, i, o = x

        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 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 seq2(fsm, l)
        l3 = []
        l0 = l.dup

        loop \
        {
                x = [0, '', '']
                l.each \
                {
                        |b|
                        x = fwd(x, b, fsm)
                        break if (x.nil?)
                }
		if (x.nil?)  then
			l3 << -1
			break
		end

                l2 = x[2].split('').map { |y| y.to_i }
#                p([l.join, '=>', l2.join, x[0]])
                l3 << x[0]
                l = l2
                break if (l.empty?)
				
        }
	s = [bin2(l0), '=>', l3]
        return l3, s
end

def less(a, b)

        return true if (b.nil?)
        return false if (a.size > b.size)
        return true if (a.size < b.size)
        return (a <=> b) == -1
end

def findmin(l)

        min = [nil, nil]
        l.each_with_index \
        { 
                |x, i|
                min = [x[1], i] if (min[0].nil? || less(x[1], min[0]))
        }
        i = min[1]
#l.each { |x| p(x[1]) }
#p(i)
#p(l[i])

        t = l[0]
        l[0] = l[i]
        l[i] = t

end

def fmt(l)

  l.reverse.map { |x| x / 20 }

end

def tree2(fsm, e)

        l = [[[], []]]
        t = {}
        l2 = []
        loop \
        {
                break if (l.empty?)
                findmin(l)

                x = l.shift
                x, s2 = x
		break if (s2.size == e)

		lx, s = seq2(fsm, x)
                p = s[-1].dup
                h = t.member?(p)
                next if (h)

                y = fmt(s2)
                l2 << y if (l2[-1] != y)
#               puts(s2.size.to_s + "\t" + s.inspect)

                t[p] = nil

                l << [x + [1, 1], p]
                l << [x + [1, 2], p]
#		l << [x + [2], p] #	if (!x.empty?)	
        }
        return l2
end

def cmp(a, b)

        return (a.size <=> b.size) if (a.size != b.size)
        return a <=> b
end

def out(l)
	return lsort(l).each { |x| puts(x.size.to_s + "\t" + x.inspect) }
	
end

def lsort(l)
	return l.sort { |a, b| cmp(a, b) }
end

def expand(l)

	l2 = []
	l.each \
	{ 
		|x| 
		y = 6
		y = 5 if ([5, 7].member?(x[-1]))
			
		l2 << (x + [4]) << (x + [y]) << (x + [7])
	}
	return l2 #.sort
end

def verify(n)

	fsm = fsm()

	l = tree2(fsm, n)
	out(l1 = l.select { |x| x.size == (n - 1) })

	l2 = l.select { |x| x.size == 2 }

	(2...(n-1)).each { l2 = expand(l2) }

	puts
	out(l2)

	puts(lsort(l1) == lsort(l2))

end

n = 3
n = ARGV[0].to_i if (!ARGV[0].nil? && ARGV[0].to_i >= 3)
puts("n=#{n}")
verify(n)

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