Claudio Cherubino's blog Life of a Googler

21May/089

Google Treasure Hunt 2008, second puzzle in F#

Unlike the first puzzle, which required some maths knowledge, in the second one we have to prove to be able to recursively process the filesystem.

I think that this puzzle should be quite easy to solve for the system administrators and in general those used to scripting languages.

Here is the text of the second Google Treasure Hunt 2008 problem:

Here is a random zip archive for you to download:
GoogleTreasureHunt08_1767743498252291641.zip

Unzip the archive, then process the resulting files to obtain a numeric result. You'll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like '.pdf' and '.js', but all are plain text files containing a small number of lines of text.

Sum of line 4 for all files with path or name containing jkl and ending in .txt
Sum of line 1 for all files with path or name containing zzz and ending in .xml
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.

As usual, the puzzle may seem challenging at a first glance, so it is important to break it into smaller (and simpler) pieces.

First of all, we have to get the list of files ending with a given extension and containing a specific substring in their name.

There is an overloaded version of the Directory.GetFiles() function which takes two parameters, the directory to be searched and a pattern to be found in the files.

Then we have to filter the results checking if the complete filenames (path + filename) contain the given substring.

This first sub-problem can be solved with the following F# code:

#light
open System.IO

let file_list dir pattern content =
  let rec allFiles dir pattern =
      seq
          { for file in Directory.GetFiles(dir, pattern) do
              yield file
            for subdir in Directory.GetDirectories(dir) do
              for file in allFiles subdir pattern do
                  yield file }
  let elems = allFiles dir pattern
  let filt (str : string) = str.Contains(content)
  Seq.filter filt elems

Now we have the list of all files that satisfy the requirements of the exercise.

The next step is to open them (they are plain text files, despite their extensions) and take the numeric value from the right line, if present.

Let's write a function to accomplish this task for a single file and then map it to the entire list:

let getvalue numline filename =
  let lines = File.ReadAllLines(filename)
  let linevalue (lines : string[]) numline =
    let realindex = numline - 1
    if lines.Length > realindex then
      System.Int32.Parse(lines.[realindex])
    else
      0
  linevalue lines numline

The File.ReadAllLines(filename) function returns an array of strings, one for each line of the source file.

Arrays in F# have indexes starting from 0, so we have to subtract 1 from the line number supplied by the user to get the real index.

We also have to be sure that the searched line exists. In this case we return its content, otherwise we return zero.

We have now all the elements we need to compute one of the numbers requested by the exercise, we should only supply the appropriate parameters in this way:

let treasurehunt2 dir pattern content numline =
  file_list dir pattern content |> Seq.map (getvalue numline) |> Seq.fold (+) 0

For instance, to solve the first line of my puzzle we have to run the following command, assuming that the archive was unzipped in C:\google:

treasurehunt2 "C:\google" "*.txt" "jkl" 5

I hope you don't need my help to run this command twice with different parameters and multiply the results to get your answer to the quiz!

19May/083

Google Treasure Hunt 2008, first puzzle in F#

A couple of days ago Google launched a contest called Treasure Hunt 2008, which will be composed of 4 puzzles.

Only the first of these quizzes is already available at http://treasurehunt.appspot.com/, and the new ones will be posted once per week.

At the end of the four puzzles there will be some prizes, even if nothing has been revealed yet.

Here is the description of the first puzzle:

A robot is located at the top-left corner of a n x k grid.
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.
How many possible unique paths are there?
(Note: Answer must be an exact, decimal representation of the number. Image not to scale.)

Google Treasure Hunt 2008

If the number of rows is r and the number of columns c, the robot can move r-1 steps down and c-1 steps to the right to get to the bottom-right corner of the grid.

The number we want to find is the combination of r1 and c1, and this can be easily computed using the binomial coeficient:

Binomial coeficient

Let's assume r1 = r-1 and c1 = c-1, and write some F# code to get the solution to our problem:

#light
open Microsoft.FSharp.Math.BigInt

let robot rows columns =
  let r1 = rows - 1I
  let c1 = columns - 1I
  (factorial (r1 + c1)) / ((factorial r1) * (factorial c1))

This first puzzle was very easy to solve, if you go to the Treasure Hunt website now, you'll find the next exercise.

I'll give it a try, if you are interested just drop a comment and we'll discuss it here.

19May/082

FireNes, l’emulatore Nintendo dentro il browser

Grazie a FireNes la vita per gli impiegati che non hanno voglia di lavorare diventerà sempre più facile.

Si tratta di un'estensione per Firefox che inserisce all'interno del browser un completo emulatore NES (Nintendo Entertainment System) con più di 2500 giochi a disposizione.

L'installazione è semplicissima ed uguale a quella di qualunque altra estensione per Firefox.

Basta infatti andare sul sito (https://addons.mozilla.org/en-US/firefox/addon/7233), scaricare l'estensione e riavviare il browser.

A questo punto sarà comparsa una nuova voce "FireNes" all'interno del menu Strumenti, che farà aprire una barra laterale con la lista dei giochi supportati.

FireNes, emulatore NES per FireFox

Tra questi spiccano anche alcuni titoli che hanno fatto la storia dei videgiochi, tra cui Super Mario, Zelda, Bubble Bobble e tantissimi altri.

L'emulatore è basato su vNES e non consente di ridefinire i tasti, che sono:

  • Sinistra: Freccia sinistra
  • Destra: Freccia destra
  • Sopra: Freccia su
  • Sotto: Freccia giù
  • Start: Enter
  • Select: Ctrl
  • A: X
  • B: Z

Per le ultime novità e per qualunque richiesta vi rimando al sito ufficiale dello sviluppatore, peccato che sia solo in lingua spagnola.

14May/080

Powerset, il motore di ricerca rivoluzionario

Quando una decina di anni fa venne lanciato Google nessuno avrebbe mai potuto immaginare che sarebbe diventato il colosso che è adesso.

Alla fine si trattava semplicemente di un nuovo motore di ricerca che cercava di entrare nel mercato dominato da due realtà affermate, Altavista e Yahoo.

Nonostante ciò Google, grazie al suo sistema di ricerca molto più efficiente degli altri, riuscì ad attirare sempre più utenti e diventare leader assoluto del mercato.

Ma questa è storia nota, quello di cui vi voglio parlare oggi è un nuovo motore di ricerca chiamato Powerset che tenta di strappare lo scettro a Google, sfruttando un approccio rivoluzionario.

Mentre i motori di ricerca classici si basano esclusivamente sulle keyword presenti nelle pagine e i link che le collegano, Powerset è in grado di comprendere interrogazioni espresse in linguaggio naturale, sebbene per adesso solo in inglese e limitate alle informazioni contenute in Wikipedia.

Ad esempio è possibile fare ricerche del tipo "what is chemotherapy" o "what is the surface of mars composed of" e i risultati sono sempre azzeccatissimi.

Nella homepage di Powerset (http://www.powerset.com/) vengono anche presentate una serie di interrogazioni di esempio per iniziare a provare questo servizio.

Il passo avanti rispetto alle ricerche a cui siamo abituati è evidente, quello che bisognerà capire è come faranno ad estendere il sistema a tutto il web e come supportare altre lingue diverse dall'inglese.

Dite che Powerset potrà diventare veramente il nuovo Google?

13May/080

Guardare la tv con Windows Live Messenger

Per una volta siamo noi italiani ad essere all'avanguardia rispetto al resto del mondo.

Da un team italiano di Microsoft è nata infatti la Messenger TV, un servizio che integra la comunicazione via chat che tutti conoscono con la possibilità di guardare (e condividere) i canali televisivi preferiti.

L'offerta attualmente include una selezione dei migliori programmi di MTV Italia, fra cui Very Victoria e Loveline, ma è già stata annunciate un'altra partnership con Mediaset, che consentirà di visionare Canale5, Italia1 e Rete4.

Previsti inoltre accordi con Sony Bmg, Ansa, Agr, Coming Soon e Sportal.

Se volete provare questo nuovo servizio dovete seguire questi seguire questi 3 semplici passaggi:

Istruzioni per usare Windows Live Messenger TV

  1. Aprire una finestra di conversazione e cliccare sul pulsante Attività
  2. Selezionare la voce Messenger TV
  3. Scegliere il canale ed il video

Buon divertimento!