Skip to content

Instantly share code, notes, and snippets.

@Bill Bill/morse_fsa.rb
Created May 4, 2012

Embed
What would you like to do?
Solution to http://www.therubygame.com/challenges/6 that creates its own FSA
require 'singleton'
# This is a parser pattern based on regexp as lexer.
# Express your tokens as parenthesized regexps separated by
# alternation (|). Erroneous input causes immediate return.
module Parse
def parse( s, p, &block)
i = 0
while i < s.length do
# could pass i to match and use block form in newer lib
m = s[i..-1].match(p)
if m
block.call(m) # call block with match data
i += m.end(0)
else
# unexpected input terminates with no error
i = s.length # extend pattern here to support recovery!
end
end
end
end
class MorseFSA
include Parse
include Singleton # only build the lookup once
def initialize
# 2-d array: DOMAIN+1 x number of states
@table = Array.new
add_state(ERROR_ACTION)
define_word_break
define_morse_codes
# inspect
end
def decode(s)
result = ''
s << ' ' # force output
i = 0
n = s.length
state = START_STATE
while i < n do
state = @table[state + 1 + s[i].ord]
action = @table[state].chr
case action
when NOOP_ACTION
when ERROR_ACTION
puts "ERROR IN INPUT s(#{s}) i(#{i})"
break
else
result << action
state = START_STATE # restart lexer
end
i += 1
end
result
end
private
# how many possibilities on input
DOMAIN = ?..ord + 1 # zero-based
ROW = 1 + DOMAIN # storage for an action plus a "next" array
# special actions
NOOP_ACTION = '-'
ERROR_ACTION = '!'
# otherwise actions contains the character to be output
# oft-used offsets into the table
ERROR_STATE = 0
START_STATE = ROW
END_STATE = 1<<31 # bigger than our table
# returns the offset of the new state
def add_state( action, next_state = ERROR_STATE)
@table.size.tap do
@table << action.ord
@table.concat Array.new( DOMAIN, next_state) # default back to error state on all inputs
end
end
def next_state
@table.size
end
def set_transition( state, input_char, next_state)
@table[state + 1 + input_char.ord] = next_state
end
def define_word_break
state = add_state(NOOP_ACTION)
set_transition( state, ' ', state = add_state(NOOP_ACTION))
set_transition( state, ' ', state = add_state(' ', END_STATE))
state
end
def define_morse_code(m,c)
state = START_STATE
m.each_char do | mc |
# follow existing transitions as far as we can
next_state = @table[state + 1 + mc.ord]
next_action = @table[next_state].chr
# puts "# next state is #{next_state}"
case next_action
when NOOP_ACTION
# just insert a new transition (no new state)
set_transition( state, mc, state = next_state)
when ERROR_ACTION
# insert a state
set_transition( state, mc, state = add_state(NOOP_ACTION))
else
raise "Token conflict: m(#{m}) mc(#{mc}) c(#{c}) next_state(#{next_state}) next_action(#{next_action})"
end
end
set_transition( state, ' ', state = add_state(c, END_STATE))
state
end
def define_morse_codes
@pairs = Hash.new
codes =<<END # http://www.therubygame.com/challenges/6
A .- N -.
B -... O ---
C -.-. P .--.
D -.. Q --.-
E . R .-.
F ..-. S ...
G --. T -
H .... U ..-
I .. V ...-
J .--- W .--
K -.- X -..-
L .-.. Y -.--
M -- Z --..
END
parse(codes, /\A([[:alpha:]])\s+([\.-]{1,4})\s*/) do |m|
@pairs[m[2]] = m[1]
end
@pairs.each{| m, c | define_morse_code(m,c) }
end
end
MorseFSA.instance.decode( morse )
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.