from math import sqrt

"""
Bin Packing Assignment
Tom Warner
Jason Sanders

Our solution was to create columns of boxes by ordering them by width, then placing them down in order. When a skinnier box is placed on a wider box, the program searches the 
list to find more boxes to fill the remaining gap, before moving down again. A maximum y value is chosen such that when the placement is complete, the area will be very close 
to a perfect square. When the column's height reaches that maximum value, any excess area is filled in with small rectangles, then the program moves over to the next column to 
start again.

Example: (0, max_y) is top left
 ____________
|      1     |
|____________|
|        |  |
|        |  |
|        | 3|
|   2    |  |
|        |__|
|________|

Credits:
ideas and strategy - mostly Jason, a little bit Tom
coding/implementation - mostly Tom, a little bit Jason
"""
def find_solution(rectangles):
    print("start")
    n = len(rectangles)
    print("num rectangles:", n)
    placement = list(rectangles) # clone into a new list
    rectangles = sorted(rectangles, key=lambda r: -r[0]) # sort the list by width, descending
    
    # height of the square we are making is approximatly the square root of the sum of all the rectangles' areas, to approximate a square
    max_y = int(sqrt(sum([r[0]*r[1] for r in rectangles])))

    #start in upper left
    x = 0
    y = max_y
    col_max_width = 0 # maximum width of the current column

    # fill threshold is the value at which we stop filling in gaps with smaller rectangles
    # This value can be tweaked to provide better results at the cost of slower run time. It is currently set to finish 10K boxes in about 1.5\ seconds
    fill_threshold = 10
    print("fill threshold:", fill_threshold)

    print("ideal solution:", 4*max_y) # if everything was packed perfectly (not always possible)
    
    # loop while we still have rectangles to place
    while len(rectangles) > 0:
        rectangle = rectangles[0] # Look at the next rectangle

        if (y - rectangle[1]) < 0: # If we can't fit the next rectangle in line in the space remaining for y...
            if y > fill_threshold: # if there's enough room to fill
                for taller in rectangles: # iterate through (widest first)
                    if taller[1] <= y and taller[0] <= col_max_width: # If a good rectangle fits in the space, use it to cap the height gap
                        tpos = [x, y]

                        k = placement.index(taller) # find index of rectangle in original ordering
                        placement[k] = tpos # put postion in original ordering (place the rectangle)
                        rectangles.remove(taller) # remove rectangle from list we need to place

                        y -= taller[1] # adjust remaining height to fill
                    if y <= fill_threshold: # past the threshold? break the loop
                        break
                    
            y = max_y               # reset to top ...
            x += col_max_width  # ... and move over a column
        else: # We CAN fit the next rectangle, so place it!
            if y == max_y: # We're starting a new column ...
                col_max_width = rectangle[0] # ... so the first rectangle is the widest
    
            pos = [x, y] # using a list, not a tuple, to distinguish placed coords from rectangle dimensions

            i = placement.index(rectangle) # find index of rectangle in original ordering
            placement[i] = pos # put postion in original ordering (place the rectangle)
            rectangles.pop(0) # remove rectangle from the list
            
            wiggle_width = col_max_width - rectangle[0] # The "wiggle room" width we have fill
            if wiggle_width > fill_threshold: # if there's enough room to fill
                # search through sorted list until we find something that fits
                for squeeze in sorted(rectangles, key=lambda r: -r[1]): # sort by height, descending
                    if squeeze[1] <= rectangle[1] and squeeze[0] <= wiggle_width: # if the glove fits...
                        # squeeze that rectangle in
                        sx = x + col_max_width - wiggle_width
                        spos = [sx, y]

                        j = placement.index(squeeze) # find index of rectangle in original ordering
                        placement[j] = spos # put postion in original ordering (place the rectangle)
                        rectangles.remove(squeeze) # remove rectangle from the list
                        
                        wiggle_width -= squeeze[0] # adjust remaining width to fill
                    if wiggle_width <= fill_threshold: # past the threshold? break the loop
                        break

            y -= rectangle[1] # move down the width of the rectangle

    print("done")
    return placement