Indian Computing 2015, afternoon problem 2

#!/usr/bin/python


'''Solver for problem 2 of http://www.iarcs.org.in/inoi/2015/zco2015/zco2015-afternoon.pdf.'''


import random


SIZE = (100000, 500)

def random_points(N):
    '''Return a list of N random points (tuples x,y).'''
    points = set()
    for dummy_i in range(N):
        insertion_todo = True
        while insertion_todo:
            point = (random.randint(1, SIZE[0]-1), random.randint(1, SIZE[1]-1))
            if not point in points:
                points.add(point)
                insertion_todo = False
    return list(points)


def remove_same_x_value(points):
    '''
    Return a list where points with identical x value and higher y are removed
    and the list is sorted by x value (descending).
    '''
    # sort by x and then y value; use pythons dictionary ordering
    ordered = sorted(points, reverse=True)
    # create new list with first element already included
    cleaned = [ordered[0]]
    for point in ordered:
        if point[0] == cleaned[-1][0]:
            # if the current point has the same x value, use its lower y value
            cleaned[-1] = point
        else:
            # otherwise (new x value), add it
            cleaned.append(point)
    return cleaned


def max_rectangle(points):
    '''
    Return the largest possible rectangle area from a list of points.

    Algorithm: Try to use points from right to left in the rectangle.
        - If there are more points for one x value, only the one with lowest y
          value is used.
        - First check the extreme x points; most right and most left, spanning
          a rectangle to the resp. limits.
        - Then go the the rightmost point and try to build a rectangle including it.
          There are two possibilities:
            - this point is on a horizontal edge
              Find its two neighbours, left and right, that have lower y value,
              as points on the left resp. right edge.  If there is no
              left/right neighbour, use the end of the space.
            - this point is on a vertical edge
              Find the next-left point, use limit of the space as horizontal
              edge.
    '''
    # order and clean (remove points with same x value) points
    clean_points = remove_same_x_value(points)

    # compute area right of most-right point
    max_x = clean_points[0]
    area_right = (SIZE[0] - max_x[0]) * SIZE[1]
    # compute area left of most-left point
    min_x = clean_points[-1]
    area_left = min_x[0] * SIZE[1]
    max_area = max(area_right, area_left)

    #print('area left: {:.2e}, right: {:.2e}'.format(area_left, area_right))

    # now try to include each point in the rectangle
    for index in (range(len(clean_points))):

        # use point as on horizontal edge
        upper_edge_index = index
        height = clean_points[upper_edge_index][1]
        left = None
        right = None
        # search left neighbour (increasing index)
        for left_edge_index in range(upper_edge_index, len(clean_points)):
            if clean_points[left_edge_index][1] < height:
                left = clean_points[left_edge_index][0]
                break
        # if unable to find a left border, use the border of the area
        if left is None:
            left = 0
        # search right neighbour:
        for right_edge_index in range(upper_edge_index-1, 0-1, -1):
            if clean_points[right_edge_index][1] < height:
                right = clean_points[right_edge_index][0]
                break
        # if unable to find a right border, use the border of the area
        if right is None:
            right = SIZE[0]
        # compute area of this found rectangle
        area = (right - left) * height
        #print('Found bounded rectangle between x {}, {} and height {}; area {:.2e}'.format(left, right, height, area))

        if area > max_area:
            max_area = area


        # use point as on vertical edge
        right_edge = clean_points[index][0]
        # next vertical edge is simply next point
        try:
            left_edge = clean_points[index + 1][0]
            area = (right_edge - left_edge) * SIZE[1]

            #print('Found open rectangle between x {}, {}; area {:.2e}'.format(left_edge, right_edge, area))

            if area > max_area:
                max_area = area

        except IndexError:
            # no next edge; this is the leftmost-case from above...
            pass



    return max_area



# actual program

def run_random(N):
    print('Running for {} points (area {})'.format(
        N, max_rectangle(random_points(N))))

def run_random_silent(N):
    max_rectangle(random_points(N))

# Run from command line with first argument as number of points to create.
import sys
run_random(int(sys.argv[1]))

# Simple tests
def test_max_rectangle():
    assert max_rectangle([(1, 4), (2, 3), (3, 2), (5, 1), (5, 2)]) == 49997500, 'test case from problem'
    assert max_rectangle([(90000, 4)]) == 90000 * SIZE[1], 'biggest rectangle to the left'
    print('test')
    assert max_rectangle([(3, 25), (SIZE[0] - 10, 13)]) == (SIZE[0] - 10 - 3) * SIZE[1], 'biggest rectangle open in middle'
    assert max_rectangle([(5, 90), (45000, 428), (99000, 33)]) == (99000 - 5) * 428, 'biggest rectangle bounded in middle'

def test_remove_same_x_value():
    assert remove_same_x_value([(3,3), (3,4)]) == [(3,3)], 'remove x values 1'
    assert remove_same_x_value([(2,1), (2,5), (3,5), (3,4)]) == [(3,4), (2,1)], 'remove x values 2'

def tests():
    test_max_rectangle()
    test_remove_same_x_value()