largest-rect-in-tile-grid.py

# Slow. Should use something like this instead https://www.geeksforgeeks.org/largest-rectangle-under-histogram/
rows, cols = (8, 8)
arr = [[0]*cols]*rows

arr[0] = [0, 0, 0, 0, 0, 0, 0, 0]
arr[1] = [0, 1, 0, 1, 1, 0, 1, 0]
arr[2] = [0, 1, 0, 1, 1, 0, 1, 0]
arr[3] = [0, 1, 0, 1, 1, 0, 1, 0]
arr[4] = [0, 1, 0, 1, 1, 0, 1, 0]
arr[5] = [0, 1, 0, 0, 0, 0, 1, 0]
arr[6] = [0, 1, 1, 1, 1, 1, 1, 0]
arr[7] = [0, 0, 0, 0, 0, 0, 0, 0]

print(arr)

def hist_largest_rect(hist):
    print("hist_largest_rect", hist)

    largest_area = 0
    largest_x = 0
    largest_y = 0
    largest_width = 0
    largest_height = 0


    for x in range(0, len(hist)):
        # print("check {} ---".format(x))

        if hist[x] == 0:
            continue

        # Find out how long we can go

        endX = x

        for i in range(x, len(hist)):
            if i + 1 == 8:
                endX = i + 1
                break

            if hist[i+1] == 0:
                endX = i + 1
                break

        # print("hist length is", (endX - x))

        rect_width = endX - x

        # Find the smallest value in this range
        rect_height = 999
        for i in range(x, endX):
            if hist[i] < rect_height:
                rect_height = hist[i]

        # print("height:", rect_height)
        #
        print("Rect (height check): {} x {} = {}".format(rect_width, rect_height, rect_width * rect_height))
        area = rect_width * rect_height
        if area > largest_area:
            largest_area = area
            largest_x = x
            largest_width = rect_width
            largest_height = rect_height


        # Fit largest rectangle that is hist[x] high from x up to endX (if possible)
        endX2 = x
        for i in range(x, endX):
            if i + 1 == 8:
                endX2 = i + 1
                break

            if hist[i+1] < hist[x]:
                endX2 = i + 1
                break

        print("endX 2 is {}".format(endX2))
        rect_width = endX2 - x
        rect_height = hist[x]

        print("Rect (length check): {} x {} = {}".format(rect_width, rect_height, rect_width * rect_height))
        area = rect_width * rect_height
        if area > largest_area:
            largest_area = area
            largest_x = x
            largest_y = hist[x]
            largest_width = rect_width
            largest_height = rect_height


    print("Largest: {} x {} at x = {}, y = {}".format(largest_width, largest_height, largest_x, largest_y))

    print("returning", largest_area)

    return (largest_x, largest_y, largest_width, largest_height, largest_area)

# hist_largest_rect([0, 1, 4, 0, 3, 4, 5, 2])
#
# exit(1)
largest_rect=(0,0,0,0,0)
largest_rect_row = 0

hist = [0, 0, 0, 0, 0, 0, 0, 0]
for row in range(0, 8):
    print("Calculate row", row)
    for x in range(0, 8):
        if arr[row][x] == 0:
            hist[x] = 0
        else:
            hist[x] = hist[x] + 1

    rect = hist_largest_rect(hist)

    if rect[4] > largest_rect[4]:
        largest_rect = rect
        largest_rect_row = row

print("Largest: ", largest_rect)
print("Largest at row", largest_rect_row)
# print(hist)