Erlang fizzbuzzery: Project Euler Problem 1

Another excercise in solving a simple problem using multiple programming idioms in the same language, Erlang. This time the simple problem is Problem 1 from Project Euler: "If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000." In particular, the solutions presented are (1) a simple single-function loop which uses if to check for termination and matching numbers, (2) a simple loop using Erlang's guard syntax, and (3) a few solutions using some of the functions of the lists module, one using Erlang's list comprehension syntax.


Simple loop without guards:

-module(euler_1_loop).

-export([start/0,solve_euler_1/1]).

start() -> io:format("~w~n",[solve_euler_1(1000)]).

solve_euler_1(N) -> solve_euler_1(0,1,N).

solve_euler_1(Sum,Cur,N) ->
  if Cur >= N -> Sum;
     (0 == (Cur rem 3)) or (0 == (Cur rem 5)) -> solve_euler_1(Sum+Cur,Cur+1,N);
     true -> solve_euler_1(Sum,Cur+1,N)
  end.

The above does a few things right, such as remembering that all calls in Erlang are call by value and thus the easiest way to implement a recursive loop for this little problem is by simply keeping all the relevant data around as function parameters. It uses Erlang's if to test a series of expressions. As before, the simple module is constructed so that its main path, solve_euler_1/1, is exported so it can be externally tested, and the simple start function is exported so we can simply run the example (after compiling with erlc, of course) with:

erl -s euler_1_loop -run init stop -noshell

We can use Erlang's guard syntax to transform the above code into:

-module(euler_1_guards).

-export([start/0,solve_euler_1/1]).

start() -> io:format("~w~n",[solve_euler_1(1000)]).

solve_euler_1(N) -> solve_euler_1(0,1,N).

solve_euler_1(Sum,Cur,N) when Cur >= N -> Sum;
solve_euler_1(Sum,Cur,N) when (0 == (Cur rem 3)) or (0 == (Cur rem 5)) -> solve_euler_1(Sum+Cur,Cur+1,N);
solve_euler_1(Sum,Cur,N) -> solve_euler_1(Sum,Cur+1,N).

The above is a fairly simplistic example, but after all the problem is itself fairly simplistic. The first match for solve_euler_1/3 checks the end case, for when we have reached the end of the list of numbers we are supposed to be adding, and simply returns our running total. The second match checks to see if the current number is evenly divisible by 3 or 5, and if so, adds the current number to the running total, adds one to the current number, and re-enters the loop, keeping in mind that the matching process will start over again and so the end case will be handled appropriately. The last match simply leaves the running total alone, adds one to the current number, and re-enters the loop.

Using the lists module and Erlang's list comprehension syntax:

-module(euler_1_comprehension).

-export([start/0,solve_euler_1/1]).

start() -> io:format("~w~n",[solve_euler_1(1000)]).

solve_euler_1(N) -> lists:sum([X || X <- lists:seq(1,N-1), (X rem 3 == 0) or (X rem 5 == 0)]).

The above illustrates four important concepts:

lists:sum(List) which returns the sum of each element in a list;

lists:seq(Start,End) which returns a list of numbers from Start through End;

[X || X <- List] which is a simple list comprehension syntax example that actually produces the exact same input List (unlike [math:pow(X,2) || X <- List] which produces a list of the squares of the elements in the input List, or [{n,X} || X <- List] which produces a list of tuples where the first element is the atom 'n' and the second element is the original list element, or [{X,math:pow(X,2)} || X <- List], or...);

[X || X <- List, Expression] which filters the original List by only including those elements for which the given Expression is true, in this case, (X rem 3 == 0) or (X rem 5 == 0).

Similar to the above is using the lists module's filter function:

-module(euler_1_filter).

-export([start/0,solve_euler_1/1]).

start() -> io:format("~w~n",[solve_euler_1(1000)]).

solve_euler_1(N) -> lists:sum(lists:filter(fun(X) -> (X rem 3 == 0) or (X rem 5 == 0) end,lists:seq(1,N-1))).

This introduces the filter function itself, as well as the creation of an anonymous function in Erlang.

Yet another method of solving this problem comes again from the lists module, this time using foldl to accumulate along the list, and showing that anywhere you might declare an anonymous function (such as above) you can also use named functions:

-module(euler_1_foldl).

-export([start/0,solve_euler_1/1]).

start() -> io:format("~w~n",[solve_euler_1(1000)]).

solve_euler_1(N) -> lists:foldl(fun accum_fun/2,0,lists:seq(1,N-1)).

accum_fun(X,Sum) when X rem 3 == 0; X rem 5 == 0 -> X + Sum;
accum_fun(_X,Sum) -> Sum.

Here we have a couple of new things to see, of course the foldl function itself, but also we use a named function, accum_fun, where previously we had declared an anonymous function inline, and we used a special guard syntax where ; is really quite the same as or.

Hopefully this was at least a little helpful in illustrating a few ways that using some of Erlang's features can be fun, simple, fast, and clear. This example didn't really give us an opportunity to look at processes or matching, but I'm sure those will come along again soon enough.