Solution to http://www.therubygame.com/challenges/6 that creates its own FSA

morse_fsa.rb

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 )