leetcode/1591_print.py at main · lukeviens/leetcode · GitHub

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
from typing import List

class Solution:
    def isPrintable(self, grid: List[List[int]]) -> bool:

        # look for top left and bottom right corners of rectangles
        # find outmost top, left, bottom, and right for each number
        def build(rects):
            print("build top lefts, bottom rights")
            for i in range(m):
                for j in range(n):
                    num = grid[i][j]
                    rect = rects.setdefault(num, [i, j, i, j])

                    if i < rect[0]:
                        rect[0] = i  # top
                    if j < rect[1]:
                        rect[1] = j  # left

                    if i > rect[2]:
                        rect[2] = i  # bottom
                    if j > rect[3]:
                        rect[3] = j  # right

                    print(rects)
                print()

            # sort by smallest rectangle
            rects = sorted(
                rects.items(),
                key=lambda r: (
                    (r[1][2] - r[1][0] + 1) *
                    (r[1][3] - r[1][1] + 1)
                )
            )

            print(rects, "\n")


        # check if a rectangle is blocked
        def blocked(num):
            if num not in blockers:
                return False, None

            if blockers[num][0] in rects:
                return True, None

            idx = blockers[num][1]
            del blockers[num]

            return False, idx

        # for each top left, see if we can reach bottom right
        def check_nums():
            print("check nums is_rectangle")
            print(f"blockers: {blockers}\n")
            for num in rects.keys():
                is_blocked, index = blocked(num)
                if is_blocked:
                    continue

                top, left, bottom, right = rects[num]
                t, l, b, r = top, left, bottom, right

                if index:
                    t, l = index

                # see if it's a rectangle
                is_rectangle = True
                print(f"check [{num}]: [{t}, {l}, {b}, {r}]")
                while t != b or l != r:
                    print(f"{grid[t][l]}: {t} {l}, {b} {r}")

                    if grid[t][l] != num and grid[t][l] not in used:
                        blockers[num] = [grid[t][l], [t, l]]
                        is_rectangle = False
                        break

                    l += 1
                    if l == r + 1 and t < b:
                        t, l = t + 1, left


                # if it's a full rectangle, delete it
                if is_rectangle is True:
                    return True, num

            return False, None


        # TOP LEFT BOTTOM RIGHT

        # find full rectangles and attempt to go backwards
        m = len(grid)
        n = len(grid[0])

        used = set()
        rects = {}  # rects[num] = [top, left, bottom, right]
        blockers = {}  # blockers[num] = num

        print("start")
        print(*grid, sep='\n')
        print()

        build(rects)

        while rects:
            print("grid")
            print(*grid, sep='\n')
            print()

            found, num = check_nums()

            if found is False:
                return False

            print(f"found rect {num}\n")
            rects.pop(num)
            used.add(num)

            if not rects:
                return True

        return True


s = Solution()

c1 = [[1,1,1,1],
      [1,2,2,1],
      [1,2,2,1],
      [1,1,1,1]]

c2 = [[1,1,1,1],
      [1,1,3,3],
      [1,1,3,4],
      [5,5,1,4]]

c3 = [[1,2,1],
      [2,1,2],
      [1,2,1]]

print(s.isPrintable(c1))
print(s.isPrintable(c2))
print(s.isPrintable(c3))