Project Euler in F# – Problem 20
Project Euler's Problem 20 was trickier than I expected.
I'm quite sure that there is a smart solution, but there is also a "dumb" one and this is the one I'm going to present you.
The problem says:
n! means n × (n ? 1) × ... × 3 × 2 × 1
Find the sum of the digits in the number 100!
Evaluating the factorial is straightforward in any functional language, but it is even easier in F# since the language already provides us with the factorial function.
As usual, let's show the code and then analyze it:
#light
open Microsoft.FSharp.Math.BigInt
let rec digits n =
match n with
| n when n < 10I -> n
| n ->
let x, y = divmod n 10I
y + digits x
let answer = digits (factorial 100I)
The open directive at line 2 permits the use of the BigInt namespace, which is needed when working with very large numbers.
Then we have the code to sum the digits of a number, which is easily implemented with pattern matching.
The algorithm is based on the modulus operator, since taking the last digit of a number is equivalent to taking the remainder of the number itself divided by 10 (in a base 10 system).
Hence, we take the last digit and recursively apply the same function to the rest of the number, until there is only one digit left, i.e. the number is less than 10.
This operation is done by the divmod function, which returns the integer quotient and the remainder as a couple (x, y).
You may have noticed that there is a capital "I" after each number. That letter stands for Big Integer and is used to distinguish them from normal integers.
It's done, we just have to apply the digits function to the output of factorial 100I.
Why did I call this solution "dumb"?
Because I had to compute 100! (which is a number with 158 digits) and then sum its digits, but this solution is not feasible if the number becomes much larger.
I think that there should be some mathematical trick to do the same job, but I don't know it.
Does anybody have a different approach to suggest?
Cuffaro si è dimesso
Finalmente noi siciliani ci siamo liberati di Cuffaro!
Certo, fare andare via un Presidente delle Regione condannato a 5 anni per favoreggiamento e con l'interdizione a vita dai pubblici uffici non è stato facile, ma a partire da oggi possiamo tornare a sognare una Sicilia libera dalla Mafia.
Speriamo solo di aver imparato la lezione e votare con coscienza fra qualche mese...
Votatemi!
No, non ho intenzione di parlare di elezioni nè della tristissima situazione politica italiana, bensì di una piccola novità di questo blog.
In fondo a ciascun post è adesso presente un sistema di rating che permette di votare l'articolo con un click, con una scala che va da 1 (scarso) a 5 (ottimo), passando da noioso, sufficiente e buono.
Il tutto si presenta come nell'immagine che segue ed è basato su un plugin per WordPress chiamato outbrain.
Ho pensato di inserire questo sistema perchè non a tutti piace dedicare un minuto del proprio tempo a commentare un post, ma da parte mia è sempre buono avere un feedback su quello che scrivo e capire cosa viene apprezzato maggiormente.
Adesso non avete più scuse, giudicare un post prende meno di un secondo!
Sorting odd and even numbers in F#
An Italian Microsoft Evangelist posted today a small programming exercise on his blog, presenting the solution with LINQ.
The exercise says (translated from Italian by me):
Given a list of unordered numbers (for instance 1, 7, 9, 2, 3, 4, 3, 4, 2, 3, 4, 5, 2, 0, 9), create a new list with all even numbers first and then all the odd ones.
The proposed solution also goes a little further, showing not only how to split the original list into odd and even numbers, but also putting them in the correct order, thus returning "022244413335799".
The following is the C# code used:
List<int> elenco = new List<int> { 1,7,9, 2, 3, 4, 3, 4, 2, 3, 4, 5, 2, 0, 9 };
var pariEdispari = elenco.OrderBy(s => s % 2 != 0);
var pariEdispariOrdinati = elenco.OrderBy(s => s % 2 != 0).ThenBy(s => s);
foreach (var item in pariEdispariOrdinati)
{
Console.WriteLine(item);
}
And now let's compare it with an F# approach:
#light let numbers = [ 1; 7; 9; 2; 3; 4; 3; 4; 2; 3; 4; 5; 2; 0; 9 ] let result = numbers |> List.sort Int32.compare |> List.partition (fun x -> x % 2 = 0) print_any ((fst result) @ (snd result))
As you can easily see, everything is done at line 4, where we apply twice the pipeline operator (|>).
This operator allows to chain functions, passing the output of one of them to the next one.
The same line could be written as:
List.partition (fun x -> x % 2 = 0) (List.sort Int32.compare numbers)
Line 6 is only used to print the result, but it has to take into account that the output of List.partition is a tuple, so we have to concatenate the two elements that can be retrieved with the fst (first) and snd (second) functions.
The @ operator actually concatenates the two lists.
I'm not sure that this is the best (and most elegant) solution, but I think that it is way ahead than any imperative solution, do you agree with me?
Project Euler in F# – Problem 1 (alternative solution)
In the last article I presented a naive solution for the first Project Euler problem, that asks us to "find the sum of all the multiples of 3 and 5 below 1000".
There are many different solutions for the same problem and today I want to show an alternative approach, which is based on a mathematical formula for an arithmetic series.
In our first solution we examined all numbers between 1 and 999 and only kept the multiples of 3 and 5, skipping all the others.
Instead of doing this, we just need to generate the multiples of 3 and 5 and sum them, subtracting the multiples of 15 because they will be included twice.
Remembering that the sum of the first n integer numbers is equal to n * (n+1) / 2, we need to adapt this formula to sum the multiples of a given number, i.e. 3, 5 and 15.
Let's call n the the result of the integer division between the maximum value (in our case 999) and step, where step is 3, 5 or 15.
According to this naming, the sum of multiples will be step * n * (n + 1) / 2, and this formula is very easy to translate in F#:
#light let sum_mult max step = let n = max / step step*n*(n + 1)/2 let max = 999 let sum = sum_mult max 3 + sum_mult max 5 - sum_mult max 15 print_any sum
At line 2 we define the sum_mult function, which takes two integer arguments this time: max and step.
The next line shows how to define a local identifier called n, whose scope is limited to the sum_mult function.
The rest of the code is straightforward, we apply the formula to sum the multiples of 3 and 5 and subtract those of 15.
Comparing the complexity of this solution with the previous one we can easily see that we moved from O(n), i.e. going through all the elements of the array, to O(1).
In fact, with this approach the number of evaluations is always fixed to 3, regardless of the maximum number to take into account.
Next time we'll face a new problem, I look forward to receiving your comments.
fsharp.it, il nuovo portale su F#
Qualche tempo fa anticipavo la mia intenzione di avviare un nuovo blog più tecnico e adesso quel momento è arrivato!
Ho aperto un portale tematico dedicato ad un tema abbastanza specialistico nel mondo dell'informatica ma che sta acquisendo sempre più popolarità.
Si tratta della programmazione funzionale ed in particolare di F#, il linguaggio basato su questo paradigma sviluppato da Microsoft per contrastare le alternative più diffuse, principalmente Erlang e Haskell.
So che per molti di voi quello che sto scrivendo non ha assolutamente senso, ma se vi occupate di informatica vi consiglio almeno di dare un'occhiata a questo nuovo mondo, magari partendo proprio dagli articoli del portale.
L'indirizzo è www.fsharp.it ed i contenuti sono scritti in lingua inglese, ma questo non può essere un freno per chi lavora nel settore.
Dategli un'occhiata e poi magari lasciate un commento, chissà che un giorno non mi ringrazierete! 
Project Euler in F# – Problem 1
I'm going through two parallel roads to learn F#: I read the "Foundations of F#" book written by Robert Pickering for the theoretical aspects and then I practice writing some code challenging myself with the problems proposed by Project Euler.
There are currently 177 mathematical exercises that can be ordered by difficulty, so I think that as soon as I solved them I'll master all aspects of F#.
Maybe my solutions are not the best at all, but I'll show them to you and I'll try to use them to explain F# programming while I'm still learning it.
Feel free to ask questions, comment or propose alternative solutions, I'll be glad to compare mine with yours.
So, let's start with the first exercise, which says:
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.
This is a very good introductory exercise and can be used to understand the power of the functional paradigm.
Here is the first version of my code, the explanation will be just below:
#light let rec sum_mul xs = match xs with | [] -> 0 | y::ys when y % 3 = 0 || y % 5 = 0 -> y + sum_mul ys | y::ys -> sum_mul ys let sum = sum_mul [1 .. 999] print_any sum
The #light clause at line 1 allows us to write code with a simpler syntax, without all the symbols and keywords, such as begin and end.
At line 2 we have the definition of a recursive function called sum_mul that accepts an argument called xs.
To define functions and literals (we don't call them variable, since their value never changes) you need to use the let keyword.
Then, in lines 3-6 we have an example of pattern matching, that is a common practice in functional programming similar to the switch statement of the imperative paradigm.
It compares xs with some patterns, which are written one per line, with a | (pipe) in front of each of them.
The first case is matched when xs is an empty list, and in that case sum_mul simply returns 0.
In the other cases xs is matched against a list, with the first element (the head of the list) being called y and the rest of the list (the tail) called ys.
If y is evenly divided by 3 or 5 (using the modulus operator: %) we add the number to our result and then recursively apply the same function to the tail.
Otherwise we just skip the head and call sum_mul on the tail.
At line 8 we actually call the sum_mul function passing a list as the argument. This list is composed by all integers between 1 and 999.
Line 9 is just used to print the output to screen.
If you want to run this code you can use Visual Studio with the F# plugin installed or simply run the F# interpreter, which is a command line tool called fsi.exe and is installed with the F# package.
I hope the explanation was clear and you started to appreciate the power of functional programming.
In the next article I'll show you an alternative (and much faster) solution to the same problem.
Twitter Updates
- @Sabrina_Miso Che ne pensi di Community Manager per Google? In caso contattami ;) http://t.co/tBQ2e0N9 #stage #casaeditrice 3 days ago
- @MarcoEscher chi si rivede! In bocca al lupo per il tuo cammino e chissà che magari un giorno tu non mi raggiunga in Google! ;) 1 week ago
- @pigatss you should give one to me because I hosted you for lunch at the Googleplex :) #volunia 3 weeks ago
- Avete visto quante posizioni per italiani sono aperte in Google a Dublino? http://t.co/ZlUfZ4uA 3 weeks ago
- @thetarro congratulations, I gained 4 kg in 4 weeks :( 3 weeks ago
- More updates...
Posting tweet...
Follow me
