3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Graipher Jan 12 '17 at 8:39
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Graipher Jan 12 '17 at 9:56
  • 2
    \$\begingroup\$ @Grapher: I count 8 (your 7 plus the four squares in the bottom right). \$\endgroup\$ – Gareth Rees Jan 12 '17 at 19:22
  • \$\begingroup\$ @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. \$\endgroup\$ – Lin Ma Jan 13 '17 at 1:40
  • \$\begingroup\$ @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. \$\endgroup\$ – Lin Ma Jan 13 '17 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.