DigitalJoel

2011/03/31

Project Euler problem 22 in Erlang

Filed under: development — Tags: , — digitaljoel @ 7:24 pm

At work I’m in a reading group covering Bruce Tate’s Seven Languages in Seven Weeks. Each week we get together for an hour to discuss the current language. One person or duo is responsible for giving a presentation on the current language. This week was Erlang, and I was partly responsible for the presentation. After reading the chapter, I was trying to find a small program I could write in order to demonstrate some of the concepts discussed. I settled on problem 22 of Project Euler.

The problem is as follows:

Using names.txt (right click and ‘Save Link/Target As…’), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 53 = 49714.

What is the total of all the name scores in the file?

This is the very first problem I tried to solve with Erlang. Fortunately, the documentation on the language is pretty good, and the standard libraries are nice too. When I started programming in 1993 in college, my first language was Pascal, but I haven’t done much in a functional language since then, and working in Java exclusively for my occupation since 2000 hasn’t really kept me in the functional frame of mind. Anyway, to the code.

-module(euler).
-export([prob22/0]).

% http://projecteuler.net/index.php?section=problems&id=22
% problem 22 in project euler.
% Load the names in names.txt, then sort them alphabetically
% Then working out the alphabetical value for each name, multiply this value 
% by its alphabetical position in the list to obtain a name score.
% Then find the total of all name scores in the file.
%
% I massaged input by putting all names on their own line and remove quote characters
% before running this program.

prob22() -> 
    UnsortedNameList = readlines("names.txt"),
    SortedNameList = lists:sort(UnsortedNameList),
    % convert the Names to the integers representing the characters.
    % but don't accept the \n at the end of each name.
    NumberNameList = lists:map(fun(Name) -> [X-64 || X <- Name, X>64] end, SortedNameList),
    % NumberNameList contains all the names adjusted so A=1, B=2, etc.
    addNameValues( NumberNameList, 1).

% add the name values in the list, as specified in the requirements of problem 22.
addNameValues( [], _ ) -> 0;
addNameValues( [Head|Tail], Index ) -> 
    HeadValue = lists:foldl(fun(X, Sum) -> X + Sum end, 0, Head),
    HeadValue*Index + addNameValues(Tail, Index+1).
    

% file reading blatantly borrowed from http://www.trapexit.org/Read_File_to_List
readlines(FileName) ->
    {ok, Device} = file:open(FileName, [read]),
    get_all_lines(Device, []).

get_all_lines(Device, Accum) ->
    case io:get_line(Device, "") of
        eof  -> file:close(Device), lists:reverse(Accum);
        Line -> get_all_lines(Device, [Line|Accum])
    end.

Not any big rocket science. Note that I modified the source file by putting each name on its own line and removing the quotes around each name, so maybe that’s cheating, but I only had a little while to work on this, so I didn’t want to spend the time really looking into getting around that.

In the book, each of the functions were quite terse with their variable names and most were a single line. I didn’t feel like that did the reader any favors, but just for fun I thought I would try to condense it a bit. Here’s what I came up with

-module(eulerSmall).
-export([prob22/0]).

prob22() -> add( lists:map(fun(N) -> [X-64 || X <- N, X>64] end, lists:sort(readlines("names.txt"))), 1).

% add the name values in the list, as specified in the requirements of problem 22.
add( [], _ ) -> 0;
add( [H|T], I ) -> I * lists:foldl(fun(X, Sum) -> X + Sum end, 0, H) + add(T, I+1).

% file reading blatantly borrowed from http://www.trapexit.org/Read_File_to_List
readlines(FileName) ->
    {ok, Device} = file:open(FileName, [read]),
    get_all_lines(Device, []).

get_all_lines(Device, Accum) ->
    case io:get_line(Device, "") of
        eof  -> file:close(Device), lists:reverse(Accum);
        Line -> get_all_lines(Device, [Line|Accum])
    end.

Notice that by combining all of the list manipulation together, the prob22() function now takes a single line. That’s kind of fun.

About these ads

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Silver is the New Black Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 226 other followers