Forum: Ruby [QUIZ] Morse Code (#121)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
MenTaLguY (Guest)
on 2007-04-24 02:16
(Received via mailing list)
I've made no particular effort to make this solution efficient, but I
had fun writing it.

MORSE = Hash[*%w(
  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 --..
)].invert.freeze

class Decoder
  Arc = Struct.new :input, :to, :output
  State = Struct.new :arcs
  Solution = Struct.new :state, :output

  def initialize(code)
    @start = State[[]]
    code.each do |input, output|
      raise ArgumentError, "input cannot be empty" if input.empty?
      branch = input.reverse.unpack("C*").inject(@start) do |state, c|
        string, output = output, ""
        State[[Arc[c, state, string]]]
      end
      @start.arcs += branch.arcs
    end
  end

  def process(input)
    input.unpack("C*").inject([Solution[@start, ""]]) do |solutions, c|
      break [] if solutions.empty?
      solutions.map do |solution|
        solution.state.arcs.select do |arc|
          arc.input == c
        end.map do |arc|
          Solution[arc.to, solution.output + arc.output]
        end
      end.flatten
    end.select do |solution|
      solution.state == @start
    end.map do |solution|
      solution.output
    end
  end
end

Decoder.new( MORSE ).process( gets.chomp ).sort.each do |result|
  puts result
end
MenTaLguY (Guest)
on 2007-04-24 03:51
(Received via mailing list)
Here's a slightly fixed version -- notably, for a Struct, you must use
equal? for object identity rather than == (and the latter can be a bit
deadly if you're dealing with a recursive data structure as we are here
for the state machine).  The changes to initialize are just cosmetic,
though.

MORSE = Hash[*%w(
  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 --..
)].invert.freeze

class Decoder
  Arc = Struct.new :input, :to, :output
  State = Struct.new :arcs
  Solution = Struct.new :state, :output

  def initialize(code)
    @start = State.new
    @start.arcs = code.map do |input, output|
      raise ArgumentError, "input cannot be empty" if input.empty?
      input.reverse.unpack("C*").inject(@start) do |state, c|
        string, output = output, ""
        State[[Arc[c, state, string]]]
      end.arcs
    end.flatten
  end

  def process(input)
    input.unpack("C*").inject([Solution[@start, ""]]) do |solutions, c|
      break [] if solutions.empty?
      solutions.map do |solution|
        solution.state.arcs.select do |arc|
          arc.input == c
        end.map do |arc|
          Solution[arc.to, solution.output + arc.output]
        end
      end.flatten
    end.select do |solution|
      solution.state.equal? @start
    end.map do |solution|
      solution.output
    end
  end
end

Decoder.new( MORSE ).process( gets.chomp ).sort.each do |result|
  puts result
end
This topic is locked and can not be replied to.