Erlang solutions for Euler problems 19, 24, 25 and 48.

Solving project Euler problems has been fun and useful to learn the basics of sequential programming in Erlang and to get used to heavy emphasis on tail-recursion in Erlang.

However, the programs for solving Euler problems tend to use only a very small subset of the Erlang features: they generally don't use binaries, don't spawn processes, don't send messages, don't have error handling, don't use mnesia, etc.

I will continue to work on Euler problems in the background (because they are fun) but to take my learning of Erlang to the next level I have chosen a different set of exercises, namely the ones which are listed in the exercises section of the Erlang website.

Below are the Erlang programs for Euler problem numbers 19, 24, 25 and 48. This brings me to a grand total of 25 solved Euler problems and gives me bragging rights for reaching "Level 1".

While working on Euler problem 67 I discovered what I think is a bug in function io:fread. I posted this bug on stack overflow and on the erlang mailing list, but I haven't had any response yet.

Code for Erlang problem 19:

%% Project Euler, problem 19
%% 
%% How many Sundays fell on the first of the month during the twentieth century?

-module(euler19).
-author('Cayle Spandon').

-export([solve/0]).

is_leap_year(Year) ->
    if
        Year rem 400 == 0 ->
            true;
        Year rem 100 == 0 ->
            false;
        Year rem 4 == 0 ->
            true;
        true ->
            false
    end.

days_in_month(Month, Year) ->
    case Month of
        1 -> 31;
        2 ->
            case is_leap_year(Year) of 
                true -> 29;
                false -> 28
            end;
        3 -> 31;
        4 -> 30;
        5 -> 31;
        6 -> 30;
        7 -> 31;
        8 -> 31;
        9 -> 30;
        10 -> 31;
        11 -> 30;
        12 -> 31
    end.

next_date({Day, Month, Year, Dow}) ->
    NewDow = (Dow + 1) rem 7,
    case Day == days_in_month(Month, Year) of
        false ->
            NewDay = Day + 1,
            NewMonth = Month,
            NewYear = Year;
        true ->
            case Month == 12 of
                false ->
                    NewDay = 1,
                    NewMonth = Month + 1,
                    NewYear = Year;
                true ->
                    NewDay = 1,
                    NewMonth = 1,
                    NewYear = Year + 1
            end
    end,
    {NewDay, NewMonth, NewYear, NewDow}.

is_first_of_month_sunday({Day, _Month, _Year, Dow}) ->
    (Day == 1) and (Dow == 0).

solve() ->
    solve({1, 1, 1900, 1}, 0).

solve(Date = {_Day, _Month, Year, _Dow}, Count) ->
    NextDate = next_date(Date),
    if
        Year < 1901 ->                         % Not in 20th century yet
            solve(NextDate, Count);
        Year =< 2000 ->
            case is_first_of_month_sunday(Date) of
                false -> NewCount = Count;
                true -> NewCount = Count + 1
            end,
            solve(NextDate, NewCount);
        true ->
            Count
    end.

Code for Erlang problem 24:

%% Project Euler, problem 24
%% 
%% What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
%%
%% Note that we compute ALL permutations of the 10 digits even though we only need the first million. I can't figure
%% out an easy way to "break off the comprehension early" and I thought the code using comprehension was too elegant
%% to pass up. This algorithm still finishes well within the allowed 1 minute.

-module(euler24).
-author('Cayle Spandon').

-export([solve/0, permutations/1]).

permutations([]) -> [[]];
permutations(L) -> [[H|T] || H <- L, T <- permutations(L--[H])]. 

solve() -> lists:nth(1000000, permutations("0123456789")).

Code for Erlang problem 25:

%% Project Euler, problem 25
%% 
%% What is the first term in the Fibonacci sequence to contain 1000 digits?

-module(euler25).
-author('Cayle Spandon').

-export([solve/0, solve/1]).

nr_digits(N) ->
    if 
        N < 10 ->
            1;
        true ->
            1 + nr_digits(N div 10)
    end.

fibonacci(WantedDigits) ->
    fibonacci(WantedDigits, 1, 1, 2).

fibonacci(WantedDigits, Prev, Current, Term) ->
    NrDigits = nr_digits(Current),
    if
        NrDigits >= WantedDigits ->
            Term;
        true ->
            fibonacci(WantedDigits, Current, Prev + Current, Term + 1)
    end.

solve() ->
    solve(1000).

solve(WantedDigits) ->
    fibonacci(WantedDigits).

Code for Erlang problem 48:

%% Project Euler, problem 48
%% 
%% Find the last ten digits of 1^1 + 2^2 + ... + 1000^1000.

-module(euler48).
-author('Cayle Spandon').

-export([solve/0, solve/1]).

last_ten_digits(N) -> N rem 10000000000.

n_pow_n(N) -> n_pow_n(N, N).
n_pow_n(N, 1) -> N;
n_pow_n(N, Rem) -> N * n_pow_n(N, Rem-1).

sum_of_powers(Max) -> lists:sum([n_pow_n(N) || N <- lists:seq(1, Max)]).

solve() ->
    solve(1000).

solve(Max) ->
    last_ten_digits(sum_of_powers(Max)).