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?
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!
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?
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? 
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.
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:
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?
La Disney incontra Philip K. Dick
Produrre un film di animazione, anche per la Disney, richiede anni di lavoro, tanto che sono già noti tutti i titoli che verranno presentati da adesso fino al 2012.
Ed è proprio l'ultimo di questi film che ha immediatamente catturato la mia attenzione, visto che si tratta della trasposizione di un racconto breve scritto da Philip K. Dick.
La cosa ancora più strana è che non si tratta di fantascienza, bensì dell'unica opera fantasy dell'autore, intitolata "King of the elves" (Il re degli elfi).
La storia narra di un benzinaio del Mississippi che offre rifugio ad un gruppo di minuscoli elfi verdi, i quali, per ricambiare la gentilezza dell'uomo, lo incoronano loro re.
Del film si sa solo che uscirà a Natale 2012 e l'unica immagine disponibile è il logo che potete vedere qui sotto.
Io sto già andando alla ricerca del racconto, non può mancare alla mia collezione!
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.
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
