Claudio Cherubino's blog Life of a Googler

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.

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.