1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#!/bin/env python
"""
#===============================================================================
#
# FILE: ch-2.py
#
# USAGE: ./ch-2.py
#
# DESCRIPTION: Perl Weekly Challenge 088
# Task 2 - Largest Rectangle
#
# AUTHOR: Lubos Kolouch
# CREATED: 11/22/2020 04:34:38 PM
#===============================================================================
"""
def get_rectangle(input_arr):
""" Get the largest rectangle """
max_x = max_y = 0
# loop through the array
# look if the current element is 1
# if so, check how far can go in the row and columns
# if the rectangle is largest, save the dimensions
for r, row in enumerate(input_arr[:-1]):
for c, item in enumerate(row[:-1]):
if item:
# print(f"* 1 at {r} {c}")
size1 = size2 = 0
while (r+size1 < len(input_arr)) and (input_arr[r+size1][c]):
# print(f" v 1 at {r} {c}")
# scan through the column and see what is the min size
y_shift = 0
while (c+y_shift < len(row)) and (input_arr[r+size1][c+y_shift]):
# print(f" > 1 at {r+size1} {c+y_shift}")
y_shift += 1
size2 = min(size2, y_shift) if size2 else y_shift
if size2 == 1:
break
size1 += 1
if size1 * size2 > max_x * max_y:
max_x = size1
max_y = size2
# print and return the results
if not max_x * max_y > 1:
print("0")
return 0
for _ in range(max_x):
row_str = "[ "
for _ in range(max_y):
row_str += "1 "
row_str += "]"
print(row_str)
return (max_x, max_y)
assert get_rectangle([[0, 0, 0, 1, 0, 0], [1, 1, 1, 0, 0, 0], [0, 0, 1, 0, 0, 1],
[1, 1, 1, 1, 1, 0], [1, 1, 1, 1, 1, 0]]) == (2, 5)
assert get_rectangle([[1, 0, 1, 0, 1, 0], [0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 1]]) == 0
assert get_rectangle([[0, 0, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1], [0, 0, 1, 0, 0, 1],
[0, 0, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1]]) == (2, 4)
|
