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