Erlang Challenge: Level 1

by anders pearson Mon 21 Aug 2006 00:18:03

I've been pretty fascinated with the concurrency and reliability aspects of the Erlang programming language lately. Lessons I've learned from reading about Erlang's concurrency model have even been popping up in my day to day Python programming.

However, most of my knowledge of Erlang stuff is purely academic. I've read the documentation, the whitepapers and numerous advocacy blog posts, but I haven't really written anything non-trivial in Erlang myself yet. Clearly I have to change that.

It's been quite a while since I've done any programming in a functional language at all and all my ideas for Erlang projects are... ambitious to say the least. I realized that I really need some fairly simple tasks to get myself up to a level of basic familiarity with the syntax and standard library before I go too crazy with self assembling distributed applications designed to survive massive hardware failure, etc. etc.

There's this great website called the Python Challenge that's basically a 33 level riddle where every level requires some sort of programming to figure out the URL for the next level. It's called the "Python" challenge since it was originally designed to get a programmer familiar with Python's features and libraries. For the most part though, It can be done with any language and works nearly as well for familiarizing the programmer with that language's features and libraries. Exactly what I needed. [Apparently, levels 5 and 23 do require python though, so I'll probably skip them.]

So I decided to start working through the Python Challenge with my limited knowledge of Erlang. While I was at it, I figured I'd blog my efforts on each level, including my missteps and questions. I'm going to try not to give away the answers, but my entries are clearly going to be massive hints at least. So if you want to solve the puzzle yourself, you might not want to read any of these posts until you've completed the level yourself.

Entries may be few and far between as it takes a bit of time to write them up and this week I'm supposed to be packing to move to a new apartment. We'll see how far I get before I get distracted and move on to something else :)

If it wasn't clear already, you definitely shouldn't expect any code here to be an example of how Erlang should be written. I'm still figuring out which way is up in the language and I fully expect that when I'm more comfortable with Erlang I'll look back on these early entries and cringe. Any experienced Erlang programmers who want to offer suggestions for cleaner, more idiomatic solutions, please post comments.

Now then...

Level one asks you to raise 2 to the 38th power. This would be easy enough to solve with a good scientific calculator, but the point of this is to do everything in Erlang.

A little poking through the documentation and I find the math library which includes the pow/2 function. Erlang has arbitrary precision arithmetic so at least I don't have to worry about overflowing a 16-bit integer type or anything stupid like that. Simple enough. I fire up the Erlang interactive shell (if your programming language doesn't have a REPL, ask for your money back):

$ erl
Erlang (BEAM) emulator version 5.4.6 [source] [hipe] [threads:0]

Eshell V5.4.6  (abort with ^G)
1> math:pow(2,38).

OK, so Erlang's default display of large numbers is in scientific notation. It's right, but I suspect that the challenge is looking for the full number written out. In another language, I'd do some sort of sprintf or format string magic with a '%f' in it somewhere to convert the large floating point number into a string or even just int() it to an integer.

Erlang has an io library with a format/2 function in it. Erlang's format uses '~' as the control character instead of '%' like most of the C influenced languages. '~' formatting still feels a little weird to me but it's how Lisp does its formatting too, so at least Erlang's in good company.

At the prompt, I put in:

2> io:format("~f",[math:pow(2,38)]).

and it gives me the number i'm looking for formatted as a regular decimal. It's good enough to get me to the next level, but while I'm here figuring out number stuff, I figure it would be good to figure out how to properly convert between float and integer types.

It actually takes a fair amount of scouring the Erlang documentation looking for a function like python's int(). I expect it to be called something like 'int', 'integer', or 'float_to_integer'. Eventually, I stumble on the function that I want: round/1, which is a built-in function. I guess the name makes sense, it just wasn't what I expected coming from Python. Ultimately, this is the simplest solution that I've found yet:

3> round(math:pow(2,38)).

prints out exactly the number that I'm looking for.

That was simple enough. I'm a long way from being a master of Erlang, but at least now I have the library reference bookmarked, have skimmed through it a little, and know a couple simple things like how to format strings and convert between floats and integers.

Tomorrow (hopefully): Level 2.

4> halt().
TAGS: programming erlang python challenge erlang challenge


Being curious, I thought I'd try to avoid floats and make an integer pow function...


pow(X, 0) -> 1;
pow(X, Y) -> X * pow(X, Y-1).

Neat. It hadn't even occurred to me that it might just be simpler to implement it myself. For something fairly basic, my instinct is still to look in the standard library first.

This runs in time O(Y) a better algorthim runs in time O(log(Y))

pow(A, B, M) computes A^B mod M. To compute this we proceed as follows: if B is even we compute pow(A, B div 2, M) and square the result (modulo M). If B is odd and greater than one we compute P = pow(A, (B-1)div 2, M) and then PPA mod M:

 pow(A, 1, M) ->
     A rem M;
 pow(A, 2, M) ->
     A*A rem M;
 pow(A, B, M) ->
     B1 = B div 2,
     B2 = B - B1,
     %% B2 = B1 or B1+1
     P = pow(A, B1, M),
     case B2 of
         B1 -> (P*P) rem M;
         _  -> (P*P*A) rem M

Taken from

Where you can also find functions for crypto arithmetic, testing primes, RSA etc.

formatting is with Markdown syntax. Comments are not displayed until they are approved by a moderator. Moderators will not approve unless the comment contributes value to the discussion.

remember info?