# Counting squares in a grid that is subdivided by line segments

Problem:

Given a picture of square with a bunch of horizontal and vertical lines in it (lines are not necessarily spanning the full square length, in other words think of a fine grid with many holes in it), design data structure(s) representing the data and a function that returns a number of squares pictured.

My ideas for the solution (in Python 2.7) are:

1. Using a enum to represent if a cell in a square has left, right, top and bottom border, and initial square with 4 borders;
2. For each horizontal line, the cell above the line has bottom border, and the cell under the line top border;
3. For each vertical line, the right cell has left border and the left border has right border;
4. Count how many cells have 4 borders, the result is the # of sub-squares.

Any advice on better data structure/method design, better algorithm performance in terms of time complexity, or code style advice are highly appreciated.

class SquareBorder:
has_left = 1
has_right = 2
has_top = 4
has_bottom = 8

def init_square(matrix):
for col in range(len(matrix[0])):
matrix[0][col] |= SquareBorder.has_top
matrix[len(matrix)-1][col] |= SquareBorder.has_bottom
for row in range(len(matrix)):
matrix[row][0] |= SquareBorder.has_left
matrix[row][len(matrix[0])-1] |= SquareBorder.has_right

def add_horizonal_line(matrix, row, start_col, end_col): # on top of row
for col in range(start_col, end_col + 1):
matrix[row][col] |= SquareBorder.has_top
matrix[row-1][col] |= SquareBorder.has_bottom
def add_vertical_line(matrix, col, start_row, end_row): # on left of col
for row in range(start_row, end_row + 1):
matrix[row][col] |= SquareBorder.has_left
matrix[row][col-1] |= SquareBorder.has_right

def find_squares(matrix):
result = 0
has_four_borders = SquareBorder.has_right | SquareBorder.has_left | SquareBorder.has_bottom | SquareBorder.has_top
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if matrix[row][col] == has_four_borders:
result += 1
return result

if __name__ == "__main__":
'''
_ _ _
|_|_ _|
|_|_ _|
|_|_|_|
'''
size = 3
matrix = [[0] * size for _ in range(size)]
init_square(matrix)
add_horizonal_line(matrix, 1, 0, 2)
add_horizonal_line(matrix, 2, 0, 2)
add_vertical_line(matrix, 1, 0, 2)
add_vertical_line(matrix, 2, 2, 2)
print find_squares(matrix) # output is 5
• In your solution you seem to be neglecting that squares made up from multiple cells can also form a square (i.e four cells). Or do these not count in your assignment? – Graipher Jan 12 '17 at 8:39
• In other words, I would have counted 7 squares, not 5, in your example, one square is the full grid and the last square is the four cells in the upper right corner. – Graipher Jan 12 '17 at 9:56
• @Grapher: I count 8 (your 7 plus the four squares in the bottom right). – Gareth Rees Jan 12 '17 at 19:22
• @GarethRees, only need to count unit square, I need to make it more clear. If you have any thoughts on my original question, it will be great. – Lin Ma Jan 13 '17 at 1:40
• @GarethRees, only need to count unit square, I need to make it more clear. If you have any thoughts on my original question, it will be great. – Lin Ma Jan 13 '17 at 1:40