Claudio Cherubino's blog Life of a Googler

22Feb/0812

Il computer vi legge nel pensiero

Da anni esiste un sito web chiamato 20Q, che è sostanzialmente un semplice gioco online nel quale ci viene richiesto di pensare ad un oggetto e un'intelligenza artificiale tenterà di indovinarlo sottoponendoci un massimo di 20 domande (da cui il nome 20 Questions).

Il sistema funziona veramente bene, con una media dell'80% di successo con 20 domande e 98% con 25, tanto che adesso riceve circa 50 milioni di visite al mese.

Inoltre il sistema raffina continuamente la propria base di conoscenza, dato che ad ogni partita giocata apprende ulteriori dettagli su come noi esseri umani classifichiamo gli oggetti.

Del gioco originale ne esistono adesso versioni in numerose lingue, italiano incluso, e vi consiglio di fare un tentativo se non l'avete mai fatto, sono certo che resterete sorpresi come me la prima volta.

Dato che 20Q esiste ormai da parecchi anni, la vera novità è un altra: ne è stata realizzata una versione dedicata al mondo dei Simpson, con tutti i personaggi, i luoghi e le cose.

La potete trovare su http://www.20q.net/simpsons/, l'unica pecca è che è disponibile solo in lingua inglese, però è completissimo, ho ritrovato anche personaggi che non avrei mai ricordato altrimenti.

Quale sarà la cosa più strana che riuscirete a fargli indovinare?

20Feb/082

The 2008 Winter Scripting Games: Pairing Off

Since 2005 Microsoft sponsors an annual scripting competition called Winter Scripting Games, whose competitors are given a series of exercises to be solved with VBShell, Powershell or Perl scripts.

I confess that I only discovered this competition a couple of days ago, and I think that some of the proposed exercises can be useful to practice F# as I'm doing with Project Euler.

There are two Divisions (Beginner and Advanced) with 10 problems each, and today we'll try to solve the first exercise of the Beginner division, called Pairing Off:

In this event we’ll be working with a standard deck of playing cards. A standard deck consists of four suits: Hearts, Spades, Clubs, and Diamonds. Within each suit are the numbers two through ten, plus a Jack, a Queen, a King, and an Ace.

Given a random set of five cards, your task is to find out how many pairs are in that set. In other words, if your five cards are the 2 of hearts, the 4 of spades, the 4 of clubs, the queen of diamonds and the queen of spades, you have 2 pairs: 2 fours and 2 queens. As another example, you might have a 3 of clubs, a 3 of diamonds, a 3 of hearts, a 10 of spades and an ace of hearts. In that case you have 3 pairs: 3 of clubs and 3 of diamonds; 3 of diamonds and 3 of hearts; and 3 of clubs and 3 of hearts.

Let's write the F# solution and then we'll comment it line by line:

#light
open System

let deck =
    [| for y in ["Hearts"; "Spades"; "Clubs"; "Diamonds"]
      for x in [1 .. 13] -> (x,y) |]

let swap a i j =
    let t = a.[i]
    a.[i] <- a.[j]
    a.[j] <- t

let shuffle a =
    let rand = new Random()
    Array.iteri (fun i _ -> swap a i (rand.Next(Array.length a))) a

let rec pairs elem list =
    match list with
    | [] -> 0
    | x::xs when (fst x) = elem -> 1 + pairs elem xs
    | x::xs -> pairs elem xs

let rec count_pairs hand =
    match hand with
    | [] -> 0
    | x::xs -> pairs (fst x) xs + count_pairs xs

do shuffle deck
let hand = deck |> Seq.to_array |> Seq.take 5

let answer = hand |> count_pairs

First of all we need to simulate a deck of cards, with four suits and 13 cards for each suit, and this is done at line 4 thanks to array comprehension.

We need now to shuffle the deck, in order to randomly get five different cards every time we run the application. To do so, we defined the shuffle function at line 13, which swaps the elements of an array in-place, i.e. without returning a new object.

In fact the shuffle function is of type array -> unit, and unit is a special type that means "no value".

When this function is applied to our deck, it iterates each element and swaps it with a random selected one from the same array, using the swap function defined at line 8.

Since the shuffle function doesn't return anything, to call it we have a special syntax: instead of "let" we have to use the "do" keyword, as in line 28.

We are now able to create a card deck and shuffle it, the next step will be writing a function to count the number of pairs contained in a hand of cards.

To accomplish this task we have two functions, called count_pairs and pairs. The idea is to take the first card and check how many couples can be formed with the cards next to it.

The count_pairs function simply applies the pairs function to each element of the hand array, and the pairs function counts how many times the numeric part of the given card is equal to the number contained in the other cards.

To get our answer we just create a random hand of five cards and then apply the pairs_count function to it.

Nice, isn't it? Please let me know if you liked this article and you'd like to read some other on this topic, I'll be glad to write more.

19Feb/080

Microsoft eroe opensource

Da qualche giorno è apparsa una nuova pagina web all'interno del sito Microsoft, ma della quale non si sa praticamente nulla a parte l'indirizzo, che è molto suggestivo: www.opensourcehero.com.

All'interno della pagina, tutta nera, c'è solo una scritta "{Forge} New Powers" e una data, il 27 Febbraio 2008.


Opensource Hero

Su Internet molti si chiedono cosa succederà il 27 Febbraio, e soprattutto cosa leghi Microsoft al mondo open-source, di sicuro è strana la scelta della data, che coincide con quella dell'evento "Heroes Happen Here" dedicato al lancio di Windows Server 2008, Visual Studio 2008 e SQL Server 2008.

C'è chi sostiene che "{Forge} New Powers" si riferisca al rilascio anticipato della versione 2.0 di Silverlight, la tecnologia ideata da Microsoft come rivale di Flash, ma la versione più accreditata è quella del lancio del progetto "The WorldWide Telescope" per l'esplorazione dell'universo.

Di sicuro non sapremo la verità fino al 27 Febbraio, però c'è da ammettere che anche Microsoft sta imparando a sfruttare il viral marketing...

18Feb/083

Il Blu-Ray ha vinto la guerra

Qualche anno fa sono stati presentati al pubblico due formati in competizione fra loro come successore del dvd, caratterizzati ovviamente da maggiori capacità e qualità dell'immagine.

I due formati, Blu-Ray e HD-DVD, sono supportati rispettivamente da due grossi consorzi di imprese. Nel primo caso, il principale promotore è sicuramente Sony, mentre l'altro gruppo vede forti le partecipazioni di Toshiba e Microsoft.

Per quanto riguarda il confronto fra i due tipi di supporto, possiamo dire che HD-DVD costituisce una sorte di evoluzione naturale del dvd e quindi i costi dei lettori e dei masterizzatori è stato sin dall'inizio più contenuto.

Blu-Ray invece è basato su una tecnologia più avanzata (ma anche più costosa) che consente di ottenere capacità di immagazzinamento dati superiori rispetto alla concorrenza.

Come sempre però l'affermarsi di un prodotto non è dovuto esclusivamente alla sua tecnologia, ma soprattutto alla capacità dei produttori di farsi adottare dai consumatori, ed in questo Sony è stata sicuramente più abile.

Innanzitutto la Playstation 3 contiene un lettore Blu-Ray e anzi questo lettore è stato per un discreto periodo di tempo il lettore Blu-Ray più economico sul mercato. Oltre a questo, la Sony è stata in grado di promuovere il formato Blu-Ray come il vero successore del dvd, tanto che moltissimi consumatori non sanno nemmeno dell'esistenza di HD-DVD.

In risposta a ciò, la Microsoft ha messo sul mercato un lettore HD-DVD esterno per la propria consolle X-BOX 360, ma probabilmente si è mossa troppo tardi, e questo accessorio non ha avuto quasi alcun successo.

La battaglia fra Blu-Ray e HD-DVD è durata un bel pò, ma pare che adesso ci sia un vincitore: Toshiba ha deciso di issare bandiera bianca e abbandonare il formato HD-DVD.

La cosa non può che fare felici noi consumatori, visto che un appassionato si trovava costretto a comprare due diversi lettori per poter vedere i film in alta definizione. Di certo non sarà altrettanto felice chi ha già comprato un HD-DVD Player e adesso si trova in casa un costoso (e inutile) soprammobile!

Io per fortuna non avevo ancora fatto la mia scelta proprio per evitare problemi di questo tipo, magari non appena la PS3 cala ulteriormente di prezzo ci faccio un pensierino...

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.

12Feb/086

Scapagnini lascia Catania (nella merda)

La notizia buona è che dopo Cuffaro finalmente ci siamo tolti dalle palle anche Scapagnini, quella brutta è che la situazione che il sindaco uscente lascia è veramente pessima.

Non solo il degrado della città è totale, ma le finanze sono state disastrate e il comune è sommerso dai debiti.

Mi vergogno a dirlo, ma la mia città deve 10 milioni di euro all'ENEL e per questo in molti quartieri, anche centrali, è stata tagliata la luce, le strade sono diventate una specie di gruviera, i dipendenti comunali sono senza stipendio, le Poste hanno crediti per altri 7 milioni e molti degli immobili della città sono stati venduti.

Inutile dire che se Catania venisse commissariata per i debiti nessuno si stupirebbe.

Facile capire allora perchè Scapagnini abbia deciso di andare via: non ha più niente da prendere da noi catanesi!

Quello che fa ancora più male però è la sfacciataggine dell'ormai ex-sindaco, il quale si candida al Senato grazie all'appoggio del suo amico Berlusconi e dichiara di farlo solo per poter "servire Catania da un seggio del Senato"!

Vorrei proprio sapere chi avrà il coraggio di votarlo e con quali motivazioni, ha passato gli ultimi 8 anni da Sindaco della mia città e non riesco a ricordare una sua decisione che abbia aiutato Catania e i catanesi (a parte i lauti compensi ai suoi consulenti di fiducia).

Speriamo solo che ce ne ricorderemo quando andremo a votare...

11Feb/081

Partito Democratico 2.0

Siamo in piena campagna elettorale e sebbene sembri che il centro-sinistra sia attualmente in svantaggio nei sondaggi, di sicuro è in prima posizione per quanto riguarda il confronto su Internet con il centro-destra.

La modernità del Partito Democratico è facilmente visibile sul proprio portale (www.partitodemocratico.it), che presenta tutte le caratteristiche tipiche del cosiddetto Web 2.0.

Abbiamo infatti un social network, dei blog, la possibilità di partecipare con dei propri contributi, una mappa che mostra la posizione geografica degli iscritti (già più di 3000), tagcloud e tanti altri contenuti interessanti, tutte cose che non siamo abituati a vedere nei siti dei partiti nostrani.

Trovo originale anche la sezione "Ciò che ci sta a cuore", che mostra in modo gradevole i valori del PD e ciò che la gente si aspetta dalla politica.

Sarà perché voglio crederci, ma a me questo portale è piaciuto.
Provate anche a confrontarlo con quello del Popolo della Libertà, il paragone è impietoso!

10Feb/080

Il cambio di sesso lo paga l’azienda

Nelle mie esperienze lavorative i benefit aziendali sono sempre stati quelli più convenzionali: telefonino, portatile, auto, viaggi premio, ecc...

C'è chi adesso offre corsi da sommelier o di free-climbing ma di sicuro quello che propone la banca Goldman Sachs non si era mai visto.

Si tratta infatti della copertura finanziaria per l'operazione di cambio sesso, che può arrivare a costare anche 100 mila euro!

Ovviamente è un benefit riservato ai manager di livello più alto, ma quello che mi chiedo è se ci sia veramente così tanta gente interessata ad esso.

E voi a quali benefit avete acceso e quali vorreste avere?

8Feb/084

Project Euler in F# – Problem 5 (alternative solution)

There was some buzz concerning my last post on Project Euler Problem 5, since the solution presented implemented a naive brute-force algorithm and its performance was very poor.

In my mind it was only meant to be an introductory article devoted to presenting a first solution to a common problem, the least common multiple (LCM) of a set of numbers, and I planned to write a second post (the one you are reading now) to show how a "smart" algorithm could lead to outstanding performance.

Let's read the text of the exercise another time:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

As we already explained, the exercise just asks us to find the least common multiple of all numbers from 1 to 20, and we can compute it by using the greatest common divisor of these numbers.

In fact, we have that:

lcm (a,b) = a * b / gcd (a,b)

In order to compute the LCM of the numbers from 1 to 20, we start computing the LCM of the first two numbers (1 and 2) and then we go on computing the LCM of the result and the third element of the sequence. We go on this way until all elements have been included in the computation.

The application of the same function to all elements of a sequence while keeping an "accumulator" is called folding, and it is a common practice in functional programming.

Let's look at the code:

#light
open Microsoft.FSharp.Math.BigInt

// Greater Common Divisor
let rec gcd a b =
 match b with
 | b when b = 0I -> a
 | b -> gcd b (a % b)

// Least Common Multiple
let lcm a b = a * b / (gcd a b)

let answer = Seq.fold1 lcm [1I .. 20I]

At line 11 we defined the least common multiple as explained above, while at line 5 we have the implementation of the Euclidean algorithm for the Greatest Common Divisor.

Then we simply fold the lcm function on the sequence [1 .. 20] and we get the output.

Do you remember how much time our "optimized" algorithm in the last article takes to perform the same calculation? 25 seconds.

The solution presented here only needs 15 milliseconds!

7Feb/086

Project Euler in F# – Problem 5

The exercise we are going to face today is ranked as one of the easiest of Project Euler's, so I don't think you will have any problem in solving it.

However, it allows me to discuss a little bit on algorithm optimization and how to refine a working solution to obtain a better one.

The text of the exercise says:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Some programming languages (for instance Haskell) provide a native function for evaluating the least common multiple (LCM) of two numbers, i.e. the smallest positive integer that is multiple of both numbers.

In F# we don't have this function, hence we have to write our own code to perform this calculation, and we need it to be able to find the LCM of a set of numbers and not only two.

Let's see the implementation of my algorithm:

#light
open System

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

let divisibleByList list n =
    Seq.for_all (fun x -> n % x = 0) list

let answer = nums |> Seq.first (fun i -> if divisibleByList [1 .. 20] i then Some (i) else None)

My solution will simply take the integers starting from 1 and check if they are evenly divisible by all numbers from 1 to 20.

We don't know when to stop, so at line 4 we have to create an infinite list of integers.
To do so, we use the unfold function, which allows us to create a lazy list by passing another function to be repeatedly evaluated to provide the elements of the list.

In our case we start from 1 and for each iteration we add one to the previous value, without an upper limit.

At line 6 we have the definition of the divisibleByList function, which takes a list of numbers and an integer n and checks if n is evenly divisible by all the elements of the given list.

This is done by using Seq.for_all, which tests if all the elements of the sequence satisfy the given predicate.

We have now everything we need to find our solution.
Let's just feed the divisibleByList function with the elements of the infinite list of integers and stop when we find the first that satisfy our conditions, thanks to Seq.first.

The solution is complete, but it is not very fast, since it takes about 8 minutes to run in my computer.

We can improve this time by using some very simple math.
First of all, we are sure that the number we are looking for will be a multiple of 2, so we can skip all odd numbers, by changing line 4 with:

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

With this simple change the execution time drops to 4 minutes, as the amount of integers to check is is actually halved.

I want to go a little further and instead of checking all even numbers we can just test the multiples of 20.
To do so, we change again line 4 with this new one:

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

Now I can be proud of myself as the execution time is reduced to 25 seconds, twenty times less than the original solution!

Obviously this is not the only solution and there are smarter approaches, maybe we can see them in a future post.