71 lines
1.4 KiB
Ruby
71 lines
1.4 KiB
Ruby
STX = "\u0002"
|
|
ETX = "\u0003"
|
|
|
|
def bwt(s)
|
|
for c in s.split('')
|
|
if c == STX or c == ETX then
|
|
raise ArgumentError.new("Input can't contain STX or ETX")
|
|
end
|
|
end
|
|
|
|
ss = ("%s%s%s" % [STX, s, ETX]).split('')
|
|
table = []
|
|
for i in 0 .. ss.length - 1
|
|
table.append(ss.join)
|
|
ss = ss.rotate(-1)
|
|
end
|
|
|
|
table = table.sort
|
|
return table.map{ |e| e[-1] }.join
|
|
end
|
|
|
|
def ibwt(r)
|
|
len = r.length
|
|
table = [""] * len
|
|
for i in 0 .. len - 1
|
|
for j in 0 .. len - 1
|
|
table[j] = r[j] + table[j]
|
|
end
|
|
table = table.sort
|
|
end
|
|
for row in table
|
|
if row[-1] == ETX then
|
|
return row[1 .. -2]
|
|
end
|
|
end
|
|
return ""
|
|
end
|
|
|
|
def makePrintable(s)
|
|
s = s.gsub(STX, "^")
|
|
return s.gsub(ETX, "|")
|
|
end
|
|
|
|
def main
|
|
tests = [
|
|
"banana",
|
|
"appellee",
|
|
"dogwood",
|
|
"TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
|
|
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
|
|
"\u0002ABC\u0003"
|
|
]
|
|
for test in tests
|
|
print makePrintable(test), "\n"
|
|
print " --> "
|
|
|
|
begin
|
|
t = bwt(test)
|
|
print makePrintable(t), "\n"
|
|
|
|
r = ibwt(t)
|
|
print " --> ", r, "\n\n"
|
|
rescue ArgumentError => e
|
|
print e.message, "\n"
|
|
print " -->\n\n"
|
|
end
|
|
end
|
|
end
|
|
|
|
main()
|