Homework 01: Dragon Tree Enclosure Division

The members of Plant Technology Research Institute in Lisabon, Portugal, work on a project commissioned by European Commission Agriculture Branch. Large area in the vicinity of the institute has been experimentally planted with a miniature dwarf variety of the famous socotra dragon tree.

The area is in the shape of a rectangle divided into a grid of elementary squares, each square contains some number of trees. Some squares may be still empty and contain no trees. There are also rectangular enclosures built in the area. Each enclosure is bordered by a fence. The fence is a part of the enclosure and its width is exactly one square. There are no trees growing on the squares with the fence. The trees which are inside the enclosures are being studied in more detail.

The researchers want to divide each enclosure into two parts. Often, an enclosure can be divided into two parts in more than one way. The researchers want to make suitable divisions in the enclosures. They introduced the notion of so called enclosure complexity, which depends on possible division of the enclosure. However, sometimes an enclosure cannot be divided into two parts. If an enclosure cannot be divided into two parts, the complexity of the enclosure is equal to the number of trees in it. If an enclosure can be divided into two parts, the complexity of the enclosure is the minimum possible absolute value of the difference between the number of the trees in one part and in the other part. For example, if an enclosure with 20 trees can be divided in into two parts containing 7 and 13 trees, and there is no other way how to divide this enclosure, the complexity of this enclosure would be |7−13| = 6. If there is another way to divide the same enclosure into parts containing 11 and 9 trees, then the complexity of the enclosure is |11−9| = 2, because 2 < 6.

A division of an enclosure is a thin rectangle made of squares, its width is exactly one square and it runs from one side of the enclosure to the opposite side. There is no tree growing anywhere in this rectangle. An enclosure can be divided into two parts if there is at least one division in it. The two parts are then separated by the division which runs between them.

The researchers want to know the total sum of all enclosure complexities.

Values correspond to the number of trees on a corresponding square in that row. The number of trees in any square may be 0,2,3,4,5,6,7,8, or 9. There is no square with only one tree in it. The value 1 indicates that the corresponding square is a part of a border of an enclosure. No two enclosures intersect or touch one another or share border square(s). Also, no enclosure is located inside another enclosure.

The output is single integer value representing the total sum of all enclosure complexities in the experimental area.

Your code will be evaluated on 8×2 test cases. Each of the 8 test cases will grant you 0.5 points if both randomly generated tests pass.

Large matrices will not be fully displayed in the BRUTE log.

Below is a basic code structure you can use. Copy-paste the following code and complete the solve function according to the description above. Then submit your final main.py.

def solve(matrix):
    """
    >>> terrain_map = [
    ... [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    ... [0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,0,0,0,0,0],
    ... [0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    ... [0,0,1,3,0,0,0,0,3,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
    ... [0,0,1,0,0,3,0,2,0,1,0,0,0,1,3,0,0,0,2,0,0,0,3,0,0,2,0,1],
    ... [0,0,1,0,0,0,0,0,0,1,5,4,0,1,0,0,0,3,0,0,0,3,0,0,0,0,0,1],
    ... [0,0,1,2,5,0,0,0,0,1,0,3,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    ... [0,0,1,0,0,0,0,0,4,1,0,0,0,1,0,2,0,0,3,0,3,0,0,0,0,0,0,1],
    ... [0,0,1,0,0,0,0,0,0,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
    ... [0,0,1,3,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    ... [0,0,1,0,2,0,0,0,0,1,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0],
    ... [0,0,1,0,0,5,0,0,0,1,0,0,1,2,0,5,1,0,0,0,0,0,1,1,1,1,0,0],
    ... [0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,0,0,0,5,1,3,0,1,0,0],
    ... [0,0,0,0,0,0,0,0,0,0,0,0,1,4,0,3,1,8,0,0,0,0,1,0,2,1,0,0],
    ... [0,0,0,2,0,0,0,0,0,0,0,0,1,1,1,1,1,8,0,0,0,0,1,0,0,1,0,0],
    ... [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0]
    ... ]    
    >>> solve(terrain_map)
    17    
    """