Claudio Cherubino's blog Life of a Googler

12Feb/082

Project Euler in F# – Problem 22

Unlike pure functional programming languages, F# is a multi-paradigm language, so you can mix object-oriented code with functional one, mainly to exploit the features of the .Net framework.

In Project Euler Problem 22 we are asked to open a file (imperative paradigm) containing a long list of names, sort them and perform some calculation on the characters composing the text.

Here is the description of the exercise:

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?

In order to open the given file, we rely on the IO functions provided by the .Net Base Class Library (BCL), that we can access thanks the open statement at line 2 of the following code:

#light
open System.IO

let names = File.ReadAllText("names.txt").Split([|','|]) |> Seq.to_list
let couples = names |> List.map (fun x -> x.Replace("\"", "")) |> List.sort compare |> List.zip [1 .. names.Length]

let score (pos, str) =
    let value = str |> Seq.map (fun x -> (1 + Char.code x - Char.code 'A')) |> Seq.fold1 (+)
    value * pos

let answer = couples |> Seq.map score |> Seq.fold1 (+)

At line 4 we read the whole content of the names.txt file, split it on the "," (comma) characters and store the result in a list called names.

Since the names written in the file are enclosed by double quotes, we have to remove all of them with the Replace function before we can alphabetically sort the list.

When names is sorted, we combine (zip) it with another list containing the position of each element inside the sequence itself, i.e. the numbers from 1 to the length of the names list.

The result is a sequence of tuples (position, name) such as (938, "COLIN").

At line 7 we define the main function of this exercise, called score. It takes a couple (position, name) and returns the name score, which is computed multiplying the alphabetical value of the name by its position.

The value of a name is obtained by summing the position in the alphabet of each character composing the name itself.

The Char.code function converts the value of a Unicode character to an integer, so we just need to subtract from it the code of the first letter of the alphabet ("A") to get its alphabetical position.

Please notice that using "A" as the first element works because in the input file all names are written with uppercase characters only.

Then we multiply the alphabetical value of the name by its position to return the score of the couple passed as argument.

The exercise asks us to sum the scores of all elements in the input file, so we map the score function and sum the results with fold1 (+), getting the correct answer.

Comments (2) Trackbacks (0)
  1. Here is another solution using List.mapi:

    #light
    open System.IO
    let answer2 =
    let names = File.ReadAllText(@”C:\dev\Chapter4\names.txt”).Split([|','|]) |> Seq.map (fun x -> x.Replace(“\”", “”))
    let sortednames = names |> Seq.to_list |> List.sort compare
    let CharVal x = 1 + Char.code x – Char.code ‘A’
    let Score i x =
    (i+1) * (Seq.map CharVal x |> Seq.fold1 (+))
    List.mapi Score sortednames |> Seq.fold1 (+)

  2. You don’t need to remove the quotes to sort the list. The list will sort correctly with the quote. When you add the value of the names, you can just ignore quotes when adding values.


Leave a comment

(required)

No trackbacks yet.