Kata

Background

An old rich man buried many diamonds in a large family farm. He passed a secret map to his son. The map is divided into many small square parcels. The number of diamonds in each parcel is marked on the map. Now the son wants to sell off some land parcels. The buyer knows about the diamonds and wishes to get some buried diamonds.

Task

Given a map of the farm, and the number of diamonds, find out the smallest rectangular region that contains exactly that number of diamonds. If multiple land parcels of the same minimum size meet that requirement, return all of them.

Input

• diamond_map:
  A rectangular matrix in which diamond_map[i][j] is a non-negative integer between 0 and 10. The size of the matrix can go upto 50 x 50
• num_of_diamonds:
  A positive integer representing the number of diamonds

Output

A sorted list of rectangles expressed in the form of 2-element lists of tuples of two coordinates: [ (top_left_row_index, top_left_col_index), (bottom_right_row_index, bottom_right_col_index)]. The two elements represents the top left corner and the bottom right corner of the rectangle. Each element has two coordinates - the horizontal index and the vertical index, counting from 0.

Coordinates are typically expressed in tuples in python, which are immutable and lighter in memory.

Sorting criteria: sort from top to bottom, and break the tie by sorting left to right

Example on breaking ties: If two rectangles has left corner at same place, then you would have to place the rectangle which has smaller width first and then that of larger width

Examples

(In the pictorial representation, blank represents 0 and diamond represents 10.)

For example, in the following map,

if 3 diamonds are demanded, the answer would be:

[
  [(1, 1), (1, 2)], 
  [(2, 2), (2, 3)], 
  [(2, 2), (3, 2)] 
]

Which is:

Here's an example of a larger map. The diamond icon represents 10 diamonds.

If 98 diamonds are demanded, the answer would be:

  [
    [(1, 1), (2, 8)], 
    [(1, 8), (8, 9)]
  ]

Your code will be tested by 50 10x10 maps and 10 more larger maps, including one 40x40, one 40x50, and one 50x50.

Happy counting diamonds!