Facebook Hacker Cup is a coding competition held every year, where you have to some algorithm problems. Code golf is a type of recreational computer programming competition in which participants strive to achieve the shortest possible code that implements a certain algorithm. Square was the easy level problem proposed at this year's qualification round and I managed to solve it just in 12 lines of Python code learning some awesome tricks down the road.
 You are given a grid of N×N square cells. Each cell is either white or black. Your task is to detect whether all the black cells form a square shape.
The statement of the problem is simple to understand. The obvious solution I came up with is:
  1. iterate over the matrix and build a 0 or 1 new matrix for each white or black cells
  2. count the number of black cells (I'll call it X)
  3. if X is a perfect square then we may have a square matrix with the side length of sqrt(X)
      • or else we cannot have a square shape inside the matrix
      1. iterate in the matrix and find the first row with black cells
      2. get the first and the last positions of a black cell in that row
      3. sum up the portions of the list in between the indices from the last step for every row
        • until that sum is different from the expected side length
        • or the matrix ends
        1. check to see we have iterated the correct number of times

          Good example:
          0 0 0 0 0 0 0 0
          0 0 1 1 1 1 0 0
          0 0 1 1 1 1 0 0
          0 0 1 1 1 1 0 0
          0 0 1 1 1 1 0 0
          0 0 0 0 0 0 0 0
          We have 16 black cells, so we should have 4 consecutive row with 4 consecutive black cells. In step 4 and get indices 2 and 5. We then iterate for the next 4 rows and our algorithm stops returning a positive answer.

          Bad example:
          0 0 0 0 0 0 0 0
          0 0 1 1 1 1 0 0
          0 0 1 1 1 1 0 0
          0 0 1 1 1 1 0 0
          0 0 1 1 0 1 0 0
          0 0 0 0 1 0 0 0
          Same 16 black cells, but this time our algorithm will stop at step 7 after only 3 iterations.

          This is the solution I would have coded in C++ if I would not know Python.

          Now let's try to compress those lines with some beautiful Python syntax. Let's start first with the matrix conversion. We could use a list comprehension for each line of the matrix, and sum it with the builtin sum function.

          Loading gist ....

          Remember that m[-1] means the last element of a list.

          Now, we could get the first line with a black cell by using the filter method and by leveraging the fact that an empty list can be viewed as False (Python is pretty logical).


          Those left and right indices could get some love. We could use enumerate to iterate over the list and get the index and the value in a list comprehension.


          Finally, here come slices, which I think it are the most concise and powerful feature in Python. v[left : right] means you will get a list only with the elements in between the left and right indexes.


          We could move the line that asserts that our number of black cells is a perfect square to our last testing statement because we do not care about speed and we have two lines that print NO. Finally, our readable code after phytonification looks smooth.


          What remains last is to minify the code. I managed to reduce it to 12 lines and 412 chars.


          If this article convinced you to switch to Python you can start learning at Codecademy where they have a nice introduction track. If you are a more visual person, Sebastian Thrun (the guy who is in charge of self-driving cars at Google) has an online course at Udacity. Finally, if you are a 1337 hardcore geek, learn python the hard way.

          Edit: more Python elegance can be seen in the Facebook official solutions.

          Edit 2: Andrei Olariu sent me a better version in 9 lines and 334 chars. I guess I'm still learning this sport :)