Claudio Cherubino's blog Life of a Googler

30Jul/083

Vista è già superato?

E' passato circa un anno e mezzo dall'uscita di Windows Vista e, come vi ho già raccontato, le mie prime impressioni non sono state sicuramente le migliori, tanto da spingermi a reinstallare XP.

Quello che non vi ho detto è che, grazie all'acquisto del nuovo notebook, ho dato una seconda chance a Vista e sono finalmente riuscito ad apprezzarlo a pieno.

Tuttavia, a quanto si legge su Internet, la maggioranza delle persone continua ancora a preferire Windows XP, sostenendo che il nuovo sistema operativo sia pieno di bug e, in generale, di scarsa qualità.

Si tratta di giudizi motivati o di semplice opinione diffusa ma senza fondamenti, anche grazie alla martellante campagna negativa Mac vs Windows di Apple?

Per sciogliere questo dubbio, in Microsoft hanno fatto un esperimento, che io personalmente trovo geniale.

Questo esperimento, chiamato Mojave Experiment, consisteva nell'invitare circa un centinaio di utenti Windows, Linux e MacOS per fargli provare in anteprima il successore di Vista, chiamato proprio Mojave.

Alla fine del test, gli utenti erano invitati a valutare questo nuovo sistema operativo e ben il 90% di essi lo hanno giudicato molto positivamente (in media 8,5 su 10), mentre il voto medio per Vista era stato circa 4,5.

Peccato che Windows Mojave non esista e che il sistema operativo appena testato fosse semplicemente Vista sotto falso nome!

Non dico che Vista sia perfetto, ma di sicuro ci sono troppi pregiudizi e molta gente si lascia trasportare da quello che si dice in giro.

Ecco perché l'azzeccato slogan della nuova campagna di Microsoft è "decide for yourself"...

22Jul/083

Balanced parenthesis

Checking whether a series of parenthesis is balanced and valid is a classic puzzle in computer science and can be easily met during a job interview.

In my opinion, there is no better solution than using a regular expression and solve the problem with a single (but almost unreadable) line of code, however I'd like to describe an algorithm which can be easily implemented in any functional or imperative programming language.

The idea is simple: start from the first character and check if it is an opening parenthesis. In this case we have to push it on a LIFO data structure such as a stack and continue with the next character.

If the character is a closing parenthesis, we take (pop) the top element from the stack and check if it makes a valid couple of brackets with the examined element.

If this is not the case, the series is not balanced, otherwise we can discard both parenthesis and go on with the next character, until the series is over.

When there are no parenthesis left to examine, if the stack is empty our series is valid; if there are still elements on the stack we can conclude that the series is unbalanced.

Lets give a look at the F# implementation I wrote to answer Dev102's challenge:

#light

let brackets = [('(',')'); ('[',']'); ('{','}'); ('<','>')]

let is_opening bracket =  List.exists ( fun (a,b) -> a = bracket) brackets
let is_closing bracket =  List.exists ( fun (a,b) -> b = bracket) brackets
let is_valid (opening, closing) = List.exists (fun (a,b) -> (a,b) = (opening, closing)) brackets

let rec check_valid stack char_array  =
   match char_array with
   | [] -> stack = List.Empty
   | c::cs when is_opening c -> check_valid (c::stack) cs
   | c::cs ->
      match stack with
      | [] -> false
      | x::xs when is_valid (x, c) -> check_valid xs cs
      | x::xs -> false

At the beginning I defined the list of valid couples and three functions to check respectively if a char is an opening or closing bracket or if a couple is valid.

After that there is a function implementing the algorithm explained above. The stack is just a normal list, where items are always added and removed from the front.

18Jul/083

Riapre BlogBabel!

Dopo quasi quattro mesi dalla chiusura improvvisa, oggi è tornato online BlogBabel con una nuova grafica e nuove funzionalità.

La discussa classifica è sempre là e i primi nomi sono più o meno sempre gli stessi, con Beppe Grillo sempre davanti a tutti.


La classifica di BlogBabel

La classifica di BlogBabel


Dite che adesso tutti noi blogger torneremo a fare a gara a "chi ce l'ha più lungo" ovvero a confrontare i piazzamenti in classifica?

Nel mio caso il problema non credo che si ponga, alla fine la mia posizione si aggira intorno a 2400, e non penso che potrà mai salire più di tanto.

Dite che ce la faremo a non fare chiudere BlogBabel una seconda volta? :)

16Jul/081

Priston Tale II arriva in Europa

Qualche mese fa vi segnalavo Dofus, un MMORPG in stile manga sviluppato dalla francese Ankama Games, mentre oggi vi voglio presentare Priston Tale II, il seguito del famoso (almeno in Corea) Priston Tale, che da Settembre farà il suo sbarco nel Vecchio Continente.

Per adesso le informazioni disponibili sono veramente poche, in pratica l'unica cosa che si è vista è questo trailer:

A dire la verità ci sarebbe anche il sito ufficiale www.pt2europe.com, che sembra non contenere nulla, ma cela invece una serie di hotspot (pixel nascosti) che, se cliccati, conducono a degli extra, tra cui scene di gioco, trailer, scenari e personaggi.

Vi lascio con una delle (poche) immagini distribuite, penso proprio che di questo Priston Tale II ne riparleremo...


Priston Tale II

Priston Tale II


1Jul/0812

The missing number

There is an interesting series of programming job interview challenges proposed by Dev102.com, which is now at its tenth puzzle:

This week question is pretty easy. Your input is an unsorted list of n numbers ranging from 1 to n+1, all of the numbers are unique, meaning that a number can’t appear twice in that list. According to those rules, one of the numbers is missing and you are asked to provide the most efficient method to find that missing number. Notice that you can’t allocate another helper list, the amount of memory that you are allowed to allocate is O(1). Don’t forget to mention the complexity of your algorithm…

I'm not sure I understood correctly the constraint related to the memory allocation.

In my opinion, when they say we are limited to O(1), they mean that we can only allocate a single numeric variable and not any other data structure.

According to this interpretation, the solution is quite easy.

First of all, we take our only variable and store into it the sum of all the numbers between 1 and n + 1, which can be easily computed remembering that 1 + 2 + ... + n = n (n + 1) / 2.

Then, we subtract each element of the array from this value, eventually the result is actually our missing number.

The functional implementation of this imperative algorithm is straightforward:

#light

let sum n = ((n + 1) * (n + 2)) / 2

let answer nums = (nums |> List.length |> sum) - (List.reduce_left (+) nums)

Let's talk about the complexity of the algorithm.

If the length of the input list list is known, evaluating the sum of the first n natural numbers takes O(1), otherwise we have to scan the entire list, i.e. O(n).

Then we have to subtract each element of the list, and this takes another iteration, so another O(n).

Therefore we have O(n) + O(n), which is definitely O(n), and can be easily optimized a little by scanning the list only once.

The only problem left is: "am I following the instructions"?