Begin forwarded message:

> From: "Jes Gabriel y Gal" <jgabrielygalan / gmail.com>
> Date: April 21, 2007 5:01:15 PM CDT
> To: james / grayproductions.net
> Subject: Re: [QUIZ] Morse Code (#121)
>
> On 4/20/07, Ruby Quiz <james / grayproductions.net> wrote:
>> 1.  Please do not post any solutions or spoiler discussion for  
>> this quiz until
>> 48 hours have passed from the time on this message.
>
> Hi James, I'm not sure when the 48 hours expire, but as tomorrow I  
> will not
> be able to access email and I wanted to send as early as possible I  
> would
> appreciate if you could forward my "solution" as soon as you see fit.
>
> I say "solution" since it's late here (I'm in Spain) and I'm tired,  
> so I haven't
> made formal tests, just some manual tests and I think it's correct.
>
> Sorry if this is not appropriate, as this is my first try at Ruby Quiz
> and my first post to ruby-talk :-).
>
> Also, I'm fairly new to Ruby, only programming little things to learn,
> but nothing serious. So  I'd appreciate any feedback you have on my
> Ruby. For example I had a little of hard time to get the dups right,
> because I was always storing the same string so other iterations were
> modifying the same object: hope I have it right !!
>
>> Morse code is a way to encode telegraphic messages in a series of  
>> long and short
>> sounds or visual signals.  During transmission, pauses are used to  
>> group letters
>> and words, but in written form the code can be ambiguous.
>>
>> This week's quiz is to write program that displays all possible  
>> translations for
>> ambiguous words provided in code.
>
> OK. So here's my solution. I just start slicing characters from the
> begining of the input to check all the combinations that match with a
> letter, then try everything that can match the starting of the rest,
> etc, until there's no rest to match. I have stored the mapping between
> Morse characters and the letters in a hash to look them up easily:
>
> letters = {".-" => "A", "-..." => "B", "-.-." => "C", "-.." => "D",
> "." => "E", "..-." => "F", "--." => "G", "...." => "H", ".." => "I",
> ".---" => "J", "-.-" => "K", ".-.." => "L", "--" => "M", "-." => "N",
> "---" => "O", ".--." => "P", "--.-" => "Q", ".-." => "R", "..." =>
> "S", "-" => "T", "..-" => "U", "...-" => "V", ".--" => "W", "-..-" =>
> "X", "-.--" => "Y", "--.." => "Z"}
>
> input = ARGV[0]
> # Start a queue with the empty translation and the input as rest to  
> translate
> queue = [["", input]]
>
> # Calculate the min and max length of the keys to
> # slice from the rest to translate only from min to max
> sorted_keys = letters.keys.sort_by {|x| x.length}
> min_length = sorted_keys[0].length
> max_length = sorted_keys[-1].length
>
> answers = []
>
> while (!queue.empty?) do
> 	process = queue.shift
> 	translation = process[0]
> 	rest = process[1]
> 	# Try to slice from the min key length to the max key length
> 	# but not more than the resting length
> 	up_to = (max_length < rest.length ? max_length : rest.length)
> 	min_length.upto(up_to) do |length|
> 		current_rest = rest.dup
> 		current_translation = translation.dup
> 		# Get the first characters from the rest that may form a letter
> 		next_morse = current_rest.slice!(0..length-1)
> 		letter = letters[next_morse]
> 		if (letter)
> 			# If there is a letter corresponding to those characters add it
> 			# to the translation
> 			current_translation << letter
> 			# If there's nothing left to translate we have an answer
> 			if (current_rest.empty?)
> 				answers << current_translation
> 			# Else add what's left to translate to the queue
> 			else
> 				queue << [current_translation, current_rest]
> 			end
> 		end
> 	end
> end
>
> puts answers
> -------------------------------
>
> Thanks.
>
> Jesus Gabriel y Galan.