The portland erlang group is considering some of the ruby quizzes to dive into erlang. If you're not used to programming recursively, you'll probably want to start with simpler problems like implementing the
Here's a sequential, recursive solution in erlang to ruby quiz #121: morse code. It's not *tail* recursive so it could maybe blow out some stack given a really long morse code word. (I assume morse code is translated one word at a time, with spaces between words.)
A tail recursive implementation... hmm... would be a bit more complicated. The two "stacks" are the dots and dashes yet to be decoded and the codes to be considered with each undecoded substring. So one way would be to manage the stacks explicitly in one recursive "loop". Another way would be to use continuation passing style.
Here's (I think) a fairly straight-forward recursive style, morse.erl...
member function, factorial, or
-module(morse).
-export([codes/0, decode/1]).
-import(lists, [prefix/2, reverse/1]).
-import(string, [len/1, substr/2]).
%% http://www.rubyquiz.com/quiz121.html
%%
%% decode/1 when given a string of dots and dashes returns a list of
%% all possible decodings using morse code.
%%
%% Examples:
%%
%% morse:decode(".-").
%% ["ET","A"]
%%
%% lists:member("SOFIA", morse:decode("...---..-....-")).
%% true
%%
%% lists:member("SOPHIA", morse:decode("...---..-....-")).
%% false
%%
%% lists:member("EUGENIA", morse:decode("...---..-....-")).
%% true
%%
%% length(morse:decode("...---..-....-")).
%% 5104
codes() ->
[{$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, "--.."}].
decode("") ->
[];
decode(String) when is_list(String) ->
decode(String, "", [], codes()).
decode("", "", Results, _Codes) ->
Results;
decode("", PartialDecoding, Results, _Codes) ->
[reverse(PartialDecoding) | Results];
decode(_String, _PartialDecoding, Results, []) ->
Results;
decode(String, PartialDecoding, Results, [{Char, Code} | Rest]) ->
MoreResults =
case prefix(Code, String) of
true ->
decode(substr(String, 1 + len(Code)), [Char | PartialDecoding], Results, codes());
false ->
Results
end,
decode(String, PartialDecoding, MoreResults, Rest).
Saturday, September 08, 2007
Morse Codes in Erlang
Subscribe to:
Post Comments (Atom)
4 comments:
Interesting! I wish I'd known of the lists:prefix method - that would have made life easier for me. For some reason I didn't think you could do f(g()) in Erlang. I've been writing X = g(), f(X). The -import syntax is handy too.
"All possible decodings"
That's the assumption which is incorrect. Properly transmitted morse code has an inter-character "space" which prevents, operator (or computerized sender) willing, two characters from being interpreted as a third, i.e.
. + .. != ...
de VE7WV
"For some reason I didn't think you could do f(g()) in Erlang."
The one place, oddly, that function calls do not work at all is the "if" expression. That uses "guards" which cannot be function calls. So...
B = function_returning_boolean(Foo),
if
B ->
do_something_true();
true ->
do_something_false()
end.
I don't like that so much, which is why I used the "case" expression in the morse code example.
'Properly transmitted morse code has an inter-character "space"'
Yeah, but that's no fun. :-)
Post a Comment