Escape a Large Maze LeetCode solution in Python

1
class Solution(object):
2
    def isEscapePossible(self, blocked, source, target):
3
        """
4
        :type blocked: List[List[int]]
5
        :type source: List[int]
6
        :type target: List[int]
7
        :rtype: bool
8
        """
9

10
        self.blocked = blocked
11
        self.source = source
12
        self.target = target
13

14
        # hashset of all blocked cells
15
        self.blocked_dict = {}
16

17
        # hashset of all visited edges
18
        self.edge_dict = {}
19

20
        # min/max x/y coords used for checking if an edge intersects the "easy path"
21
        self.min_x = min(self.source[0], self.target[0])
22
        self.max_x = max(self.source[0], self.target[0])
23
        self.min_y = min(self.source[1], self.target[1])
24
        self.max_y = max(self.source[1], self.target[1])
25

26
        # iterate through all cells in blocked,
27
        # and add each cell to the hash set
28
        for blocked_cell in blocked:
29
            if blocked_cell[0] in self.blocked_dict:
30
                self.blocked_dict[blocked_cell[0]][blocked_cell[1]] = None
31
            else:
32
                self.blocked_dict[blocked_cell[0]] = {blocked_cell[1]: None}
33

34
        # for each cell in blocked
35
        for blocked_cell in self.blocked:
36

37
            # list the faces of blocked_cell that belong to an outline (4 of these at most)
38
            exposed_faces = self.enumerate_exposed_faces(
39
                blocked_cell[0], blocked_cell[1]
40
            )
41

42
            # for each of these faces
43
            for face in exposed_faces:
44

45
                # check to see if we've already visited the edge while tracing out a loop
46
                x_edge = face[3]
47
                y_edge = face[4]
48
                edge_type = face[5]
49
                edge_visited = (
50
                    x_edge in self.edge_dict
51
                    and y_edge in self.edge_dict[x_edge]
52
                    and edge_type in self.edge_dict[x_edge][y_edge]
53
                )
54

55
                # if not, then we are looking at a new outline that we haven't seen before
56
                if not edge_visited:
57

58
                    # count the number of edges of the outline that intersect the "easy path"
59
                    num_intervening_edges = self.check_loop(face[0], face[1], face[2])
60

61
                    # if the number of intersections is odd, a path does not exist. return false
62
                    if num_intervening_edges % 2 == 1:
63
                        return False
64

65
        # if we could not find an outline the separates source from target, return true
66
        return True
67

68
    # lists the faces of occupied cell x,y that do not touch other occupied cells
69
    # these cell faces are edges that belong to one of the outlines that are formed
70
    # by painting in all occupied cells and grid boundaries
71
    # there are at most 4 such edges per cell
72
    def enumerate_exposed_faces(self, x, y):
73
        out_list = []
74

75
        # iterate through each neighbor of the cell
76
        for i in range(4):
77

78
            # if the neighbor cell is not occupied (blocked), then the corresponding face is a boundary face
79
            # in which case, add it to the list
80
            if not self.is_occupied(x + self.dxe[i], y + self.dye[i]):
81

82
                # there is a little bit of accounting going on to keep track of the correct edge coordinates
83
                # note that what we are really listing here is a starting grid point (not cell) + starting direction
84
                # and we also need to take into account that cells are indexed by their bottom left corner
85
                x_star = x + self.dxe2[i]
86
                y_star = y + self.dye2[i]
87
                x_edge_coords = x_star + self.dx_edge_coords[(i + 2) % 4]
88
                y_edge_coords = y_star + self.dy_edge_coords[(i + 2) % 4]
89

90
                out_list.append(
91
                    [
92
                        x_star,
93
                        y_star,
94
                        i,
95
                        x_edge_coords,
96
                        y_edge_coords,
97
                        self.edge_code_list[i],
98
                    ]
99
                )
100
        return out_list
101

102
    # returns the number of times a given outline intersects the "easy path"
103
    # x_start,y_start is the starting gridpoint on the outline
104
    # starting_direction is... the starting direction (see __init__ for how it's coded)
105
    # is_cc is True if traversing in counterclockwise direction, False if clockwise
106
    # note that (counter)clockwise is referring to the winding number of the whole outline we are tracing
107
    def check_loop(self, x_start, y_start, starting_direction, is_cc=True):
108
        # correct the starting direction if it needs to be adjusted
109
        starting_direction = self.update_edge_direction(
110
            x_start, y_start, starting_direction, is_cc
111
        )
112
        direction = starting_direction
113

114
        x = x_start
115
        y = y_start
116

117
        num_intervening_edges = 0
118

119
        # return False
120
        touched_grid_boundary = False
121

122
        # iterate until we either touch the grid boundary
123
        # or return to where we started
124
        # this is a do-while, hence the True + break condition
125
        while True:
126
            # evaluate next grid point after moving along edge
127
            x_new = x + self.dxp[direction]
128
            y_new = y + self.dyp[direction]
129

130
            # if the edge is on the boundary, do not proceed. break out of the loop
131
            if self.edge_on_boundary(x, y, x_new, y_new):
132
                touched_grid_boundary = True
133
                break
134

135
            # otherwise, mark the edge as visited
136
            x_edge_coords = x + self.dx_edge_coords[direction]
137
            y_edge_coords = y + self.dy_edge_coords[direction]
138
            edge_coords = [x_edge_coords, y_edge_coords]
139

140
            # a little bit of a hassle since it's a dictionary of dictionaries of 1-2 element lists
141
            if x_edge_coords in self.edge_dict:
142
                if y_edge_coords in self.edge_dict[x_edge_coords]:
143
                    if (
144
                        self.edge_code_list[direction]
145
                        not in self.edge_dict[x_edge_coords][y_edge_coords]
146
                    ):
147
                        self.edge_dict[x_edge_coords][y_edge_coords].append(
148
                            self.edge_code_list[direction]
149
                        )
150
                else:
151
                    self.edge_dict[x_edge_coords][y_edge_coords] = [
152
                        self.edge_code_list[direction]
153
                    ]
154
            else:
155
                self.edge_dict[x_edge_coords] = {
156
                    y_edge_coords: [self.edge_code_list[direction]]
157
                }
158

159
            # check to see if the edge intersects our "easy path" from source to target
160
            # if an intersection has occured, increment the intersection counter
161

162
            # checks to see if the edge intersects the horizontal portion of the easy path
163
            # for an edge to do so, it must be vertical, have the same y as source
164
            # and must have an x between source and target
165
            if self.edge_code_list[direction] == "v":
166
                if (
167
                    self.min_x < edge_coords[0]
168
                    and edge_coords[0] <= self.max_x
169
                    and edge_coords[1] == self.source[1]
170
                ):
171

172
                    num_intervening_edges += 1
173

174
            # checks to see if the edge interesects the vertical portion of the easy path
175
            # for an edge to do so, it must be horizontal, have the same x as source
176
            # and must have a y between source and target
177
            if self.edge_code_list[direction] == "h":
178
                if (
179
                    self.min_y < edge_coords[1]
180
                    and edge_coords[1] <= self.max_y
181
                    and edge_coords[0] == self.target[0]
182
                ):
183

184
                    num_intervening_edges += 1
185

186
            # update the grid point
187
            x = x_new
188
            y = y_new
189

190
            # update the direction
191
            direction = self.update_edge_direction(x, y, direction, is_cc)
192

193
            # if we returned back to the beginning, break out of the loop
194
            # we need to take direction into account, because it is possible to return to
195
            # the same grid point during the the middle of the traversal
196
            # for example, imagine tracing the outline of two cells that are diagonally adjacent
197
            # here, you would pass through the point where the two cells touch each other twice
198
            # if you happen to get unlucky and start at such a point, things would break if you
199
            # terminated conditioned just on the x/y coordinates
200
            # taking into account the current direction dodges this issue
201
            if x == x_start and y == y_start and direction == starting_direction:
202
                break
203

204
        # if we touched a grid boundary, we need to go back to the beginning
205
        # and then go in reverse until we touch the grid boundary again
206
        # thus finishing the outline.
207
        # since we are going in reverse direction,
208
        # the setting is clockwise instead of counter-clockwise
209
        if touched_grid_boundary and is_cc:
210
            num_intervening_edges += self.check_loop(
211
                x_start, y_start, (starting_direction + 2) % 4, is_cc=False
212
            )
213

214
        # return the number of intersections between the loop and the easy path
215
        return num_intervening_edges
216

217
    # changes the edge direction right or left (or keeps straight)
218
    # depending on our current grid point and direction
219
    def update_edge_direction(self, x, y, direction, is_cc):
220
        # coordinate of the cell in front of us (given our current direction) and to the right
221
        x_right = x + self.dx_fwrd_right[direction]
222
        y_right = y + self.dy_fwrd_right[direction]
223

224
        # coordinate of the cell in front of us (given our current direction) and to the left
225
        x_left = x + self.dx_fwrd_left[direction]
226
        y_left = y + self.dy_fwrd_left[direction]
227

228
        # the following logic tells us how to change the direction as we move along the outline
229
        # I'm not going to explain it here, but if you draw the cases out, it will become apparent
230
        # the one thing to note is that, you can still turn right during a counter-clockwise traversal
231
        # (and left during a clockwise traversal). The traversal handedness is referring
232
        # to the global winding number of the whole loop
233
        # (which is either +1 or -1 depending on clockwise or counter-clockwise)
234
        # if we are doing a counterclockwise traversal...
235
        if is_cc:
236
            # if the cell in front of us to the right is occupied, turn right
237
            if self.is_occupied(x_right, y_right):
238
                direction += 1
239
                direction %= 4
240
            # if neither cells in front of us are occupied, turn left
241
            elif not self.is_occupied(x_left, y_left):
242
                direction -= 1
243
                direction %= 4
244

245
        # if we are doing a clockwise traversal...
246
        else:
247
            # if the cell in front of us to the left is occupied, turn left
248
            if self.is_occupied(x_left, y_left):
249
                direction -= 1
250
                direction %= 4
251
            # if neither cells in front of us are occupied, turn right
252
            elif not self.is_occupied(x_right, y_right):
253
                direction += 1
254
                direction %= 4
255
        return direction
256

257
    # checks to see if an edge belongs to the boundary of the grid
258
    def edge_on_boundary(self, x0, y0, x1, y1):
259
        # an edge is on the boundary of the grid iff both endpoints
260
        # are on the boundary of the grid
261
        b_test0 = x0 == 0 or x0 == self.l or y0 == 0 or y0 == self.l
262
        b_test1 = x1 == 0 or x1 == self.l or y1 == 0 or y1 == self.l
263
        return b_test0 and b_test1
264

265
    # checks to see if a given cell is blocked. a cell is blocked if either
266
    # it is on the boundary/exterior of the grid, or it was listed in blocked
267
    def is_occupied(self, x, y):
268
        return (
269
            (x in self.blocked_dict and y in self.blocked_dict[x])
270
            or x < 0
271
            or y < 0
272
            or x == self.l
273
            or y == self.l
274
        )
275

276
    # here is where I hid away all the definitions of constants that we use to make things easier
277
    def __init__(self):
278
        # grid dimensions, which we use to check if we hit a grid boundary
279
        self.l = 10**6
280

281
        # used to traverse perimeter. clockwise order
282
        # direction 0 = down
283
        # direction 1 = left
284
        # direction 2 = up
285
        # direction 3 = right
286
        self.dxp = [0, -1, 0, 1]
287
        self.dyp = [-1, 0, 1, 0]
288

289
        # used to check for faces of a cell that are exposed
290
        # if the face of a cell is exposed, then that face belongs
291
        # to a perimeter that may prevent source from reaching target
292

293
        # perimeters are traversed in a counterclockwise loop by default
294
        # specifically, while travelling along a perimenter,
295
        # the cell to your left will always be occupied and the
296
        # the cell to your right will always be empty
297

298
        # faces of the cell are indexed as:
299
        # [left, top, right, bottom]
300
        # if cell x+dxe[i],y+dye[i] if not occupied, then the ith face
301
        # of the cell is part of a perimeter, which corresponds to motion
302
        # in direction i
303
        self.dxe = [-1, 0, 1, 0]
304
        self.dye = [0, 1, 0, -1]
305

306
        # used to maps an exposed face of a cell to the corner of the cell
307
        # used to start the perimeter traversal
308
        # left face: start at bottom left corner
309
        # top face: start at top left corner
310
        # right face: start at top right corner
311
        # bottom face: start at bottom right corner
312
        self.dxe2 = [0, 0, 1, 1]
313
        self.dye2 = [0, 1, 1, 0]
314

315
        # used to determine what cells to look at
316
        # when checking if we need to turn clockwise or counterclockwise
317
        # while traversing the perimeter
318
        self.dx_fwrd_right = [-1, -1, 0, 0]
319
        self.dy_fwrd_right = [-1, 0, 0, -1]
320

321
        self.dx_fwrd_left = [0, -1, -1, 0]
322
        self.dy_fwrd_left = [-1, -1, 0, 0]
323

324
        # note that, for the above, a grid point and a cell have the same
325
        # coordinates if the grid point is the bottom left corner of that cell
326

327
        # used to map directed edges to undirected edges
328
        # we index edges using their bottom/leftmost point, and whether they
329
        # are vertical or horizontal
330
        self.edge_code_list = ["v", "h", "v", "h"]
331
        self.dx_edge_coords = [0, -1, 0, 0]
332
        self.dy_edge_coords = [-1, 0, 0, 0]