fst.rb

def f4(n)

	n1 = n
	n = (n * 3) + 1
	n /= 2 while (n.even?)
	
	puts("f4(#{n1}) = #{n}")
	return n
end

def readfst(fn)

	$fs = {} if ($fs.nil?)

	return $fs[fn] if ($fs.member?(fn))
	
	fs = {}

	(f = File.open(fn)).readlines.each \
	{
		|ln|
		si, so, i, o = ln.split.map{ |x| x.to_i }
		
		fs[[si, i]] = [so, o]
	}
	f.close
	puts("\n\nfst #{fn} #{fs.size}", fs.inspect)

	$fs[fn] = fs
	return fs
end

def bin2sym(n)
	ns = n.to_s(2)
	ns1 = ns.split('').map { |x| {'0' => '11', '1' => '12'}[x] }.reverse + ['2']
	puts("input #{n} => #{ns.inspect} => #{ns1}")
	return ns1
end

def sym2bin(ns)
	
	ns1 = (0..(ns.length / 2)).map { |x| ns[(x * 2)..(x * 2 + 1)] }
	ns1b = ns1.dup
	raise if (ns1b.pop != '2')
	
	ns2 = ns1b.reverse.map { |x| {'11' => '0', '12' => '1'}[x] }.join
	n = ns2.to_i(2)
	puts("output #{ns1.inspect} => #{ns2} => #{n}")
	return n
	
end

def transduce(fs, n)

	s = 0
	ns2 = ''

	bin2sym(n).join.split('').map { |x| x.to_i }.each \
	{
		|x|
		
		s, o = fs[[s, x]]
		ns2 << o.to_s if (o != 0)

		loop \
		{
			p({'s' => s, 'x' => x, 'ns2' => ns2})
			s2, o = fs[[s, 0]]
			break if (s2.nil?)
			s = s2
			ns2 << o.to_s if (o != 0)
		}
		
	}
	raise if (fs[[s, nil]] != [nil, nil])

	n = sym2bin(ns2)

end

def test1(n, fs, f)
	raise if (transduce(fs, n) != f.call(n))
end

def test27(fn, f)

	test1(27, readfst(fn), f)
end

def test3(fn, f)
	fs = readfst(fn)

	3.times \
	{
		|i|
		puts("\n##{i + 1}")
		l = (3..999).to_a
		n = l.delete_at(rand(l.size)) | 1
		test1(n, fs, f)
	}

end

f1 = lambda { |n| f4(n) }
f2 = lambda { |n| f4(f4(n)) }

test27(fn1 = 'fsm3nb.txt', f1)
test27(fn2 = 'fsm2d.txt', f2)


test3(fn1, f1)
test3(fn2, f2)