-
Notifications
You must be signed in to change notification settings - Fork 0
/
675. Cutoff Trees For Golf Event
104 lines (94 loc) · 4.71 KB
/
675. Cutoff Trees For Golf Event
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
#######################################
Haddocks Algorithm Implementation
#######################################
def cutOffTree(self, forest: List[List[int]]) -> int:
sizes = []
#get manhattan distance between two points
mdistance = lambda x, y: abs(x[0]-y[0]) + abs(x[1]-y[1])
#get positions of consecutive destinations
sizes = [(forest[i][j], i, j) for i in range(0, len(forest)) for j in range(0, len(forest[0])) if forest[i][j] != 0 and forest[i][j] != 1]
sizes.sort()
current, heap, steps, seen = (0,0,0), [], 0, {}
for val in sizes:
#for each destination calculate manhattan distance and detour steps
_, dest_i, dest_j = val
steps += mdistance((current[1], current[2]), (dest_i, dest_j))
seen = {}
while current[1] != dest_i or current[2] != dest_j:
#add new positions to heap. If position is closer to dest its priority is higher
level, cur_i, cur_j = current
cur_mdist = mdistance((cur_i, cur_j), (dest_i, dest_j))
seen[cur_i, cur_j] = 0
#up, down, left, right
for i, j in (cur_i-1, cur_j), (cur_i+1, cur_j), (cur_i, cur_j-1), (cur_i, cur_j+1):
if i > -1 and i < len(forest) and j > -1 and j < len(forest[0]) and forest[i][j] != 0:
if (i,j) not in seen.keys():
if cur_mdist > mdistance((i, j), (dest_i, dest_j)):
heappush(heap, (level, i, j))
seen[(i,j)] = level
else:
heappush(heap, (level+1,i,j))
seen[(i,j)] = level+1
else:
if cur_mdist > mdistance((i, j), (dest_i, dest_j)):
alter = level
else:
alter = level+1
if seen[(i,j)] > alter:
#remove (seen[cur_i-1][cur_j],cur_i-1,cur_j) from heap
rm_idx = heap.index((seen[(i,j)],i,j))
heap[-1], heap[rm_idx] = heap[rm_idx], heap[-1]
heap.pop()
heapify(heap)
heappush(heap, (alter, i, j))
seen[(i,j)] = alter
if not heap:
return -1
current = heappop(heap)
heap.clear()
steps += 2*(current[0])
current = (0, current[1], current[2])
seen.clear()
return steps
##############################################################
Lees Algorithm Implementation
##############################################################
def cutOffTree(self, forest: List[List[int]]) -> int:
#Lees Algorithm Implementation for Maze Routing
sizes = []
for i in range(0, len(forest)):
for j in range(0, len(forest[0])):
if forest[i][j] != 1 and forest[i][j] != 0:
sizes.append(forest[i][j])
sizes.sort()
current = (0,0,0)
q = deque([current])
steps = 0
seen = {}
for dest in sizes:
while forest[current[0]][current[1]] != dest:
current = q.pop()
seen[(current[0], current[1])] = True
i, j, level = current
#place possible paths in que
if i != 0:
if forest[i-1][j] != 0 and (i-1, j) not in seen.keys():
q.appendleft((i-1, j, level+1))
if i != len(forest)-1:
if forest[i+1][j] != 0 and (i+1, j) not in seen.keys():
q.appendleft((i+1, j, level+1))
if j != 0:
if forest[i][j-1] != 0 and (i, j-1) not in seen.keys():
q.appendleft((i, j-1, level+1))
if j != len(forest[0])-1:
if forest[i][j+1] != 0 and (i, j+1) not in seen.keys():
q.appendleft((i, j+1, level+1))
#no more paths left
if not q and forest[current[0]][current[1]] != dest:
return -1
steps+=current[2]
q.clear()
seen.clear()
current = (current[0], current[1], 0)
q.appendleft(current)
return steps