[SOLUTION] [QUIZ] Morse Code (#121)

[MenTaLguY]

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, utput
State = Struct.new :arcs
Solution = Struct.new :state, utput

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]

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, utput
State = Struct.new :arcs
Solution = Struct.new :state, utput

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