Claudio Cherubino's blog Life of a Googler

30Apr/084

Project Euler in F# – Problem 48

The following problem from Project Euler is one of those supposed to be solved either with intensive computation or a "smarter" approach.

Here is the description of problem number 48:

The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.

Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.

If our language allows us to evaluate the series mentioned above (and F# does!), we can just do it and then take the last 10 digits of the result as required.

This can be implemented by the following F# code:

#light
open Microsoft.FSharp.Math.BigInt

let last10 num = num % (pow 10I 10I)

let answer = [1I .. 1000I] |> Seq.map (fun x -> pow x x) |> Seq.fold (+) 0I |> last10

The first problem is extracting the last ten digits from a given number, and this is done by dividing the number by 10^10 and returning the remainder of the division (line 4).

Then we have to generate the series n^n for all n from 1 to 1000 and sum the items.

This sum is actually a huge number (more than 3000 digits) but we are only interested in the last ten digits, so we can use the pipeline operator (|>) to pass it to the last10 function.

The only caveat is to use BigInt, otherwise the numbers we are talking about will never fit into the other numeric data types.

Easy, isn't it?

28Apr/080

Dofus sfida World of Warcraft

Se si pensa al mondo dei MMORPG (Massively Multiplayer Online Role-Playing Game), il primo titolo che viene in mente è sicuramente World of Warcraft, che da solo può vantare più di 10 milioni di giocatori.

Eppure WoW non è di certo l'unico esponente del suo genere, ma anzi molto frequentemente vengono annunciati dei nuovi rivali e oggi vi voglio parlare proprio di uno di essi, che porta il nome di Dofus.

Sviluppato dalla francese Ankama Games, Dofus presenta un'accattivante grafica stile manga in due dimensioni e propone un innovativo sistema di combattimento turn-based.

Da un paio di giorni è anche nata la community italiana del gioco, che consente di iniziare a conoscere il mondo di Dofus e di scaricarne la versione Beta, che occupa poco più di 150 Mb e gira su Windows, Mac e Linux.

Inoltre, tutti coloro che si iscriveranno alla Beta riceveranno un regalo misterioso.

Ammetto di non essere mai stato rapito da World of Warcraft nè di avere mai avuto un grande interesse verso i MMORPG in generale, eppure questo nuovo progetto mi spinge a provarlo.

Sarà per la grafica, sarà per il sistema di combattimento, non lo so, ma di sicuro gli concederò un'occasione!

23Apr/080

Password in cambio di cioccolato

Un indagine condotta da Infosecurity Europe ha rivelato che il 45% delle donne intervistate rivelerebbe la propria password in cambio di una barretta di cioccolato.

Gli uomini che sono caduti nella trappola sono stati solo il 10%, tuttavia penso che molti di più rivelerebbero password, dati personali e quant'altro se a chiederlo fosse stato una bella ragazza con un sorriso smagliante.

La stessa indagine ha anche fatto notare che le persone non si fanno molti problemi nel fornire, anche per telefono, la propria data di nascita o il numero di telefono, con la semplice scusa di partecipare ad un sorteggio per un viaggio a Parigi.

Inoltre metà degli impiegati ammette di conoscere le password dei colleghi e di rivelarle per telefono ad una persona che dichiara di appartenere al reparto IT dell'azienda.

Infine, ed è probabilmente la cosa più grave, la maggior parte degli intervistati usa sempre la stessa password (o al massimo un paio di esse) per l'accesso a servizi differenti.

Il campione era composto da 576 impiegati londinesi, ma non ho dubbi che anche rivolgendo l'attenzione alla popolazione italiana i risultati non miglioreranno, anzi temo proprio che la situazione sia ancora peggiore.

Anche voi vi riconoscete nel profilo che è stato delineato? Come vi comportate con la tutela delle vostre password?

23Apr/087

Remove duplicate values from a List in F#

Once in a while I give a look at the web server log to find out how people landed in this blog and yesterday there was someone that entered the following search string into Google:

Given a random List of integers, write a function that removes all the duplicate values

This site appears as the first result, even if there is no solution for that problem, but I want to help you anyway, unknown visitor!

In fact, we can make use of the Set data type to easily solve the problem.

According to the definition, a Set represents a collection of elements without duplicates.
So, if we create a Set from the given list, all duplicate values will be automatically filtered.

This can be done in a single line, I'll call the function nub because this is the name of the corresponding Haskell one:

let nub xs = xs |> Set.of_list |> Set.to_list

As I said, to return a List without duplicate values we just need to create a Set from it and then create a List from the new Set.

Do you think it is fair to act this way or should I say that I'm cheating? :)

21Apr/081

Le offerte flat di Skype

Le tariffe di Skype per chiamare i telefoni di tutto il mondo sono sempre state particolarmente contenute, ma oggi sono stati finalmente presentati degli abbonamenti flat, che permettono cioè di effettuare un qualunque numero di telefonate ad un prezzo fisso.

In particolare sono state lanciate tre tariffe, chiamate rispettivamente Senza limiti Uno, Senza limiti Europa e Senza limiti Mondo.

La prima, Senza limiti Uno, consente di chiamare tutti i telefoni fissi di una nazione europea a scelta (anche l'Italia) con soli 2,95 Euro + IVA al mese.

La tariffa Senza limiti Europa copre le numerazioni fisse di 20 nazioni europee al costo mensile di 3,95 Euro, mentre Senza limiti Mondo (8,95 Euro/mese) offre chiamate illimitate verso i fissi di 34 paesi del mondo, la cui lista può essere consultata sul sito di Skype insieme a tutti gli altri dettagli dell'offerta.

Quest'ultimo abbonamento copre inoltre i telefoni cellulari di Canada, Cina, Hong Kong, Singapore e USA.

Ad essere onesti, le tariffe non sono veramente flat, avendo un limite pari a 10000 minuti di conversazione al mese, che corrispondono circa a 6 ore al giorno, ma restano comunque molto più convenienti di quelle offerte dagli operatori del nostro paese.

17Apr/083

Project Euler in F# – Problem 45

A long time has passed since I last posted the solution of one of Project Euler's problems.

Problem 45 is related to figurate numbers, i.e. numbers that can be represented as geometrical patterns.

In particular, we are going to find a number that is triangular, pentagonal and hexagonal at the same time:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle: Tn=n(n+1)/2
Pentagonal: Pn=n(3n?1)/2
Hexagonal: Hn=n(2n?1)

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

A trivial solution will be computing the lists of triangular, pentagonal and hexagonal numbers and then find their intersection. However, we don't know how big the searched number can be, so we are not able to determine when to stop the generation of each list.

Hence we need a smarter solution, based on the mathematical properties of these numbers.

First of all, every hexagonal number is also a triangular number, so our problem is reduced to finding the smallest hexagonal pentagonal number greater than 40755.

Then we can generate the hexagonal numbers and check whether they are also pentagonal, stopping at the first one found.

According to the definition, we can test if a positive integer x is a pentagonal number by computing:

Test for pentagonal numbers

If n is an integer, then x is the nth pentagonal number. If n is not an integer, then x is not pentagonal.

Let's look at the F# code:

#light
open System
open Microsoft.FSharp.Math.BigInt

let hexagonal n = n * (2I * n - 1I)
let isPentagonal x = ((sqrt(to_float (24I * x + 1I)) + 1.0) % 6.0) = 0.0

let nums = 144I |> Seq.unfold (fun i -> Some (i, i + 1I))
let answer = nums |> Seq.map hexagonal |> Seq.find isPentagonal

At lines 5 and 6 we define the functions to compute the nth hexagonal number and to check if an integer x is pentagonal.

Then we start generating the hexagonal numbers to be tested, starting from the 144th, since the solution must be greater than 40755, that is the 143th hexagonal number.

In the last line we just return the first number for which isPentagonal is true, without having to know when to stop thanks to lazy evaluation, which allows us to continue generating numbers only when actually needed.

The solution to the problem is greater than I could imagine, that's why we need to use BigInt instead of normal integers.

What do you think about the approach I followed to solve this problem?

7Apr/083

Even Digits Multiple Of Nine

The mathematical exercise we are going to solve comes from mathschallenge.net and can be summarized in a single sentence:

Find the smallest multiple of nine containing only even digits.

We just need a function to check if a number contains only even digits and then pass to it the multiples of nine.

This algorithm can be translated into the following code:

#light
open System

let isEven n = (n % 2 = 0)

let rec allEvenDigits n =
    match n with
    | n when n < 10 -> isEven n
    | n -> (isEven (n % 10)) && (allEvenDigits (Int32.div n 10))

let nums = 9 |> Seq.unfold (fun i -> Some (i, i + 9))

let answer = Seq.find allEvenDigits nums

The isEven function is just a "shortcut" for the modulus operator and it is used inside allEvenDigits, where it is applied to each digit of the given number.

Then, we have to generate the multiples of nine, but we don't know when to stop, so we need an infinite sequence, that can be produced by the Seq.unfold function.

At the end we use Seq.find, which takes a boolean function (allEvenDigits) and a sequence (nums), and returns the first element of the sequence for which the given function returns "true", i.e. the smallest multiple of nine containing only even digits, that is exactly what we had to find.

1Apr/080

Il concorso da un milione di dollari

Stavolta non vi parlerò di uno quei concorsi dedicati ai blogger nei quali si vince un premio a seguito di una estrazione, ma di una sfida veramente complessa rivolta ai migliori sviluppatori del mondo e con un milione di dollari come premio!

Il concorso è promosso da Netflix, il famoso portale americano per il noleggio di film online.

Il Netflix Prize (così si chiama la competizione) mette a disposizione dei team partecipanti un database con circa 17000 film definiti da tre campi (id, titolo e anno) e un set di dati di addestramento che comprende 100 milioni di rating sui film assegnati da 480000 utenti anonimi.

Oltre a questi dati di input vengono forniti 2,8 milioni di record formati da tre campi ciascuno (id dell'utente, id del film, rating). Il compito dei partecipanti è proprio riempire questi campi, cercando di prevedere i rating effettivamente assegnati dagli utenti di Netflix.

Per vincere il premio di un milione di dollari bisognerà ottenere una previsione migliore del 10% rispetto a quella di Netflix. Inoltre, fintanto che nessuno riesce ad ottenere questo risultato, il migliore di ogni anno vincerà 50000 dollari.

Attualmente il team che guida la classifica ha ottenuto una percentuale di miglioramento pari allo 9,05%, quindi se volete soffiare loro il primo premio vi conviene affrettarvi, ma non pensate che sia una sfida poco impegnativa.