thraxil.org:

Erlang Challenge: Level 2 (2)

by anders pearson Wed 23 Aug 2006 00:48:10

(read [[Erlang Challenge: Level 1]] and [[Erlang Challenge: Level 2]] before reading this one)

First off, I noticed that the challenge levels actually started numbering at 0 so this third level is really Level 2. So I'm fixing the numbering of my posts from here on out to keep it matched with the site.

Level 2's challenge gives you a huge block of text (hidden in the source of the page) that's almost entirely punctuation. It looks sort of like this:

%%$@_$^__#)^)&!_+]!*@&^}@[@%]()%+$&[(_@%+%$*^@$^!+]!&_#)_*}{}}!}_]$[%}@[{_@#_^{*
@##&{#&{&)*%(]{{([*}@[@&]+!!*{)!}{%+{))])[!^})+)$]#{*+^((@^@}$[**$&^{$!@#$%)!@(&
+^!{%_$&@^!}$_${)$_#)!({@!)(^}!*^&!$%_&&}&_#&@{)]{+)%*{&*%*&@%$+]!*__(#!*){%&@++
!_)^$&&%#+)}!@!)&^}**#!_$([$!$}#*^}$+&#[{*{}{((#$]{[$[$$()_#}!@}^@_&%^*!){*^^_$^
]@}#%[%!^[^_})+@&}{@*!(@$%$^)}[_!}(*}#}#___}!](@_{{(*#%!%%+*)^+#%}$+_]#}%!**#!^_
)@)$%%^{_%!@(&{!}$_$[)*!^&{}*#{!)@})!*{^&[&$#@)*@#@_@^_#*!@_#})+[^&!@*}^){%%{&#@

and basically goes on for about 100K. The hint makes it clear that there are a couple letters hidden in there and you need to write a program to pull them out.

I could solve this level in about 3 seconds with grep or slightly longer with a nice regexp in emacs. But as usual, we'll stick with the tools that Erlang gives us since that's the whole point of this exercise.

First, I copy and paste the the data out into a file called 'level2_data.txt'. I suppose that the Erlang program could be written to fetch the data directly off the web and parse it out, but that's a little more advanced than I'd like to get for this early in the challenge. Just figuring out how to read data in from a file will be difficult enough for me.

Once the data's read in, the problem becomes just filtering non-alphabetical characters out of a string. In Python, I would probably use a list comprehension again or just the built in filter() function. Lo and behold, Erlang has a lists:filter/2 function that works like I expect it to. With either approach though, a helper function will be needed to discriminate between letters and everything else:

is_alpha(C) when C >= $a, C =< $z -> true;
is_alpha(C) when C >= $A, C =< $Z -> true;
is_alpha(_) -> false.

If you followed the last entry, this one should be pretty understandable. Simple pattern matching with guards. The only thing new is the '_' variable, which is just a convention in most functional languages for a variable whose value you really don't care about. So the last line is just there to catch any character that didn't match one of the first two conditions.

lists:filter/2 works similarly to lists:map/2 which I explained already. Where map applies a function to every element in a list and returns a list of the results, filter applies a function to every element but only returns the elements for which the function returns true. In other words, it's like grep inside a programming language.

Again, I seem to need an anonymous function to make it work right, but it's still pretty simple:

filter_strip(Msg) -> lists:filter(fun (X) -> is_alpha(X) end, Msg).

I test this from the shell on short strings I type in and it seems to work nicely, so now we just need to pull the real data out of the file and into an Erlang string that we can pass to the filter_strip/1 function.

Another trip through the library documentation and I find the file module which has some familiar sounding functions like open/2 and read/2.

Doing file i/o is the kind of thing that tends to have lots of potential error conditions that you need to handle if you want your code to be robust in a real environment. Here though, we're opening and reading in one file that we know ahead of time will exist, will have the proper permissions, etc. So I'm not going to worry about all those error conditions and just write some fast, brittle code:

get_data() ->
{ok,IoDevice} = file:open("level2_data.txt",[read]),
{ok,Data} = file:read(IoDevice,10000000),
Data.

file:open/2 takes a filename and a list of flags. In our case, we just want to read data from the file so the only flag we give it is 'read'. It returns a tuple consisting of 'ok' (it would be 'error' if something went wrong but we're ignoring that possibility for now) and an IoDevice which represents the open file. file:read/2 takes an IoDevice and the number of bytes to read in. Normally, you'd put this in a loop and read in the data in small chunks until you reach the end of the file. Again, since we're only dealing with one file and we know it's size and we're not trying to do anything very robust or efficient, we can get away with just specifying a big number of bytes so it will just slurp in the entire file in one gulp. It also returns a tuple with 'ok' (or 'error') and Data, which is a string of data. That's exactly what we're looking for, so the function just returns that.

Now, just calling:

filter_strip(get_data()).

gives us the letters stripped out of the file and the level is solved.

I mentioned list comprehensions, so here's the list comprehension equivalent:

lc_strip(Msg) -> [X || X <- Msg, is_alpha(X)].

I really do love list comprehensions :)