Erlang Challenge: Level 2
By anders pearson 21 Aug 2006
(Read [[Erlang Challenge: Level 1]] first or this post won’t make much sense.)
Level 2 gives you a ciphertext message and a key that basically tells you that it’s a Caesar cipher with a shift of 2. The message looks roughly like this (I’m just going to include the beginning so as not to give it away completely): “g fmnc wms bgblr rpylqjyrc gr zw fylb.”
The hints on the page make it pretty clear that they expect you to solve it with python’s string.maketrans() and string.translate() functions, which do indeed make short work of the problem.
Erlang doesn’t have direct equivalents to those functions so we either have to find another way, or write our own.
Since we’re dealing with text now instead of math, it’s important to understand how Erlang deals with strings. Technically, Erlang doesn’t really have strings. It just has lists of numbers and double quotes are just syntactic sugar. So “hello” is really the same thing as [$h,$e,$l,$l,$o] or [104,101,108,108,111].
It’s kind of similar to how strings in C are really just character arrays and characters are really just 8-bit integers. But Erlang’s are a linked list of 8-byte numbers (yes, byte, not bit). Clearly some string operations in Erlang aren’t going to be as fast or space efficient as in C (but Erlang has libraries for dealing with byte arrays if you really want to go there), but it does let you manipulate strings as easily as any other list and lists are pretty much the core data structure of functional languages so that’s important. It also means that Erlang is sort of unicode compliant from the ground up. At least, it can store and manipulate utf8/16/32 strings without any extra care. Apparently Erlang’s libraries don’t always do the right thing with unicode though, so you do still need to be careful.
Since Erlang strings are just lists of numbers, shifting each letter of a string up two places is roughly just adding two to each number (but not exactly, as we’ll see). Time to write a function. My first attempt:
:::erlang
-module(pychallenge2).
-export([plus2/1]).
plus2 ([H|T]) -> [H + 2 | plus2(T)];
plus2 ([]) -> [].Ah, pattern matching, how I’ve missed you.
If you’ve ever worked in a pattern matching functional language, the code above should be pretty obvious. The first two lines just declare the module that the function’s in and export the single function that’s defined in it. Then the two lines starting with ‘plus2’ define our function. The first of those lines does most of the work, matching a list argument, using ‘|’ to pull apart the head and tail of the list, then returning a list consisting of the head incremented by 2 concatenated with a plus2 called on the tail recursively. The second line just defines the base case so it terminates when it hits the end of the list.
Then we go to the shell and do:
:::erlang
> c(pychallenge2).
> pychallenge2:plus2("g fmnc wms bgblr rpylqjyrc gr zw fylb.").
"i\"hope\"you\"didnt\"tr{nsl{te\"it\"|y\"h{nd0"This actually is good enough to get the answer and proceed to the next level, but obviously not perfect. The Erlang code works fine, but simply adding two to each letter isn’t really enough. The two problems are that we really only want it to add two to alphabetic characters; adding two to the spaces gives us quotes and adding two to the period at the end gives us ‘0’. The other issue is that the cipher really needs to wrap around at the end of the alphabet, so ‘y’ turns into ‘a’, and ‘z’ turns into ‘b’. Above you can see that ‘y’ turned into ‘{‘ because that’s how the ASCII character set is arranged.
To make our code a little smarter, We’ll define a helper function:
:::erlang
trans (C) when C >= $a, C =< $x -> C + 2;
trans (C) when C >= $y, C =< $z -> C - 24;
trans (C) -> C.trans/1 just shifts a single character. It makes use of Erlang’s guards to only shift the letters. The first line handles the case where the letter is between ‘a’ and ‘x’, just returning the letter plus 2. The second line handles the case of ‘y’ or ‘z’ and subtracts 24 to map it back down to the beginning of the alphabet. Those two probably could have been combined with a clever use of modular arithmetic, but I think this is nice and clear. The third line just returns the original letter and handles the default situation when neither of the above conditions match (ie, for punctuation, etc.)
Now our plus2/1 function (which isn’t entirely accurately named anymore) becomes:
:::erlang
plus2 ([H|T]) -> [trans(H) | plus2(T)];
plus2 ([]) -> [].And we can go back to the shell and do:
:::erlang
> c(pychallenge2).
{ok,pychallenge2}.
> pychallenge2:plus2("g fmnc wms bgblr rpylqjyrc gr zw fylb.").
"i hope you didnt translate it by hand."Which is much better.
After I’d already completed Level 2 and was working on a higher level, I remembered reading that Erlang had Haskell style list comprehensions as well. I’m a big fan of list comprehensions and put them all through my Python code, so naturally, I had to do a version of Level 2 using a list comprehension:
:::erlang
decipher(Msg) -> [trans(C) || C <- Msg].Much nicer. Do you see why I’m a fan of list comprehensions? Once your familiar with the basic syntax, I think it makes the function much easier to understand than even the recursive, pattern matching version.
Erlang’s list library also has a map/2 function that can be used to achieve an effect similar to the list comprehensions:
:::erlang
decipher_map(Msg) -> lists:map(fun(C) -> trans(C) end, Msg).
map/2 takes a function and a list as arguments and applies the function to each element in the list and returns a list of the results.
(I have an anonymous function in there (defined with ‘fun’) because for some reason, this:
:::erlang
decipher_map(Msg) -> lists:map(trans, Msg).
Didn’t work. I’m still not sure why I had to wrap trans/1 in an anonymous function to get lists:map/2 to work right.)
Using map/2 doesn’t really gain you much in terms of clarity over list comprehensions, but it does mean that you could easily switch it to pmap/2 and your code will run in parallel across multiple processors or machines in a distributed environment without any other changes, Let that one sink in for a minute. Yes, it should remind you of google’s MapReduce.
I have to admit that I actually burned a fair amount of time on this level because of one stupid little syntax issue that took me forever to figure out. If you look closely at the trans/1 function, you’ll notice that Erlang uses =< as “less than or equal to” rather than <= which I’m more accustomed to.
My first attempt at writing trans/1 was basically what is up here, but with <=. Erlang gave me a syntax error on that and I assumed that I had messed up the syntax for guards somehow, so I attempted a version with an if statement instead. I still got a syntax error there so I thought that maybe ‘,’ wasn’t the right way to combine conditions and tried things like ‘and’, ‘&&’, etc., none of which worked. Eventually I bit my tongue and wrote a big, ugly version of trans/1 with nested if statements. When I still was getting a syntax error, it finally occurred to me that <= might not be right so I dug through the docs some more and discovered my problem. I probably should’ve been able to figure that out more quickly but <= is just so ingrained in my brain that it never occurred to me that that might be my problem.
Other than that, this was a very fun level to solve. Pattern matching, recursion, guards, pulling apart lists into heads and tails, map, and list comprehensions are all things that just warm this programmer’s heart.
On to Level 3!