# Python code golf - Square @ Facebook Hacker Cup 2014

You are given a grid ofThe statement of the problem is simple to understand. The obvious solution I came up with is:N×Nsquare cells. Each cell is either white or black. Your task is to detect whether all the black cells form a square shape.

- iterate over the matrix and build a 0 or 1 new matrix for each white or black cells
- count the number of black cells (I'll call it X)
- 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
- iterate in the matrix and find the first row with black cells
- get the first and the last positions of a black cell in that row
- 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
- check to see we have iterated the correct number of times

Good example:

0 0 0 0 0 0 0 0We 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.

0 01 1 1 10 0

0 01 1 1 10 0

0 01 1 1 10 0

0 01 1 1 10 0

0 0 0 0 0 0 0 0

Bad example:

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

0 01 1 1 10 0

0 01 1 1 10 0

0 01 1 1 10 0

0 0 1 1 0 10 0

0 0 0 0 1 0 0 0

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 :)