Skip to content

Instantly share code, notes, and snippets.

@mattj1

mattj1/largest-rect-in-tile-grid.py

Last active March 16, 2021 18:34
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save mattj1/1f32dfbbd3758e195cb013b601bbcbb8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save mattj1/1f32dfbbd3758e195cb013b601bbcbb8 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. mattj1 revised this gist Mar 16, 2021. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions largest-rect-in-tile-grid.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,4 @@
    # Slow. Should use something like this instead https://www.geeksforgeeks.org/largest-rectangle-under-histogram/
    rows, cols = (8, 8)
    arr = [[0]*cols]*rows

  2. mattj1 created this gist Mar 16, 2021.
    120 changes: 120 additions & 0 deletions largest-rect-in-tile-grid.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,120 @@
    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)