|
1
|
|
|
import heapq |
|
2
|
|
|
from collections import defaultdict |
|
3
|
|
|
from itertools import combinations |
|
4
|
|
|
from math import floor, hypot |
|
5
|
|
|
|
|
6
|
|
|
|
|
7
|
|
View Code Duplication |
def shortestPath(graph, start, end): |
|
|
|
|
|
|
8
|
|
|
queue = [(0, start, [])] |
|
9
|
|
|
seen = set() |
|
10
|
|
|
while True: |
|
11
|
|
|
(cost, v, path) = heapq.heappop(queue) |
|
12
|
|
|
if v not in seen: |
|
13
|
|
|
path = path + [v] |
|
14
|
|
|
seen.add(v) |
|
15
|
|
|
if v == end: |
|
16
|
|
|
return cost, path |
|
17
|
|
|
for (next_item, c) in graph[v].items(): |
|
18
|
|
|
heapq.heappush(queue, (cost + c, next_item, path)) |
|
19
|
|
|
return queue |
|
20
|
|
|
|
|
21
|
|
|
|
|
22
|
|
|
def find_entities(bunker, entity): |
|
23
|
|
|
positions = [] |
|
24
|
|
|
for y in range(len(bunker)): |
|
25
|
|
|
for x in range(len(bunker[y])): |
|
26
|
|
|
if bunker[y][x] == entity: |
|
27
|
|
|
positions.append((x, y)) |
|
28
|
|
|
return positions |
|
29
|
|
|
|
|
30
|
|
|
|
|
31
|
|
|
def numbers(x, y): |
|
32
|
|
|
if x <= y: |
|
33
|
|
|
return range(0, y - x + 1) |
|
34
|
|
|
else: |
|
35
|
|
|
return range(0, y - x - 1, -1) |
|
36
|
|
|
|
|
37
|
|
|
|
|
38
|
|
|
def get_slope(position_1, position_2): |
|
39
|
|
|
return (position_2[1] - position_1[1]) / (position_2[0] - position_1[0]) |
|
40
|
|
|
|
|
41
|
|
|
|
|
42
|
|
|
def path_coordinates(position_1, position_2): |
|
43
|
|
|
path = [] |
|
44
|
|
|
if position_2[0] == position_1[0]: |
|
45
|
|
|
# vertical |
|
46
|
|
|
for i in numbers(position_1[1], position_2[1]): |
|
47
|
|
|
path.append((position_1[0], position_1[1] + i)) |
|
48
|
|
|
elif position_2[1] == position_1[1]: |
|
49
|
|
|
# horizontal |
|
50
|
|
|
for i in numbers(position_1[0], position_2[0]): |
|
51
|
|
|
path.append((position_1[0] + i, position_1[1])) |
|
52
|
|
|
else: |
|
53
|
|
|
slope = get_slope(position_1, position_2) |
|
54
|
|
|
if abs(slope) == 1: |
|
55
|
|
|
# diagnal |
|
56
|
|
|
for i in numbers(position_1[0], position_2[0]): |
|
57
|
|
|
path.append((position_1[0] + i, round(position_1[1] + i * slope))) |
|
58
|
|
|
# this is an edge case that the bat will hit the corner of a wall |
|
59
|
|
|
if len(path) > 1 and get_slope(path[-2], path[-1]) in [1, -1]: |
|
60
|
|
|
path = [ |
|
61
|
|
|
(path[-2][0], path[-1][1]), |
|
62
|
|
|
(path[-1][0], path[-2][1]), |
|
63
|
|
|
] + path |
|
64
|
|
|
else: |
|
65
|
|
|
# get the minimal step |
|
66
|
|
|
steps_per_cell = int(max(abs(slope), abs(1 / slope))) |
|
67
|
|
|
x_steps = abs(position_2[0] - position_1[0]) * steps_per_cell |
|
68
|
|
|
y_steps = abs(position_2[1] - position_1[1]) * steps_per_cell |
|
69
|
|
|
steps = max(x_steps, y_steps) * 2 |
|
70
|
|
|
x_progress = (position_2[0] - position_1[0]) / steps |
|
71
|
|
|
y_progress = (position_2[1] - position_1[1]) / steps |
|
72
|
|
|
for i in range(steps + 1): |
|
73
|
|
|
new_x = position_1[0] + i * x_progress |
|
74
|
|
|
new_y = position_1[1] + i * y_progress |
|
75
|
|
|
path.append((round(new_x), round(new_y))) |
|
76
|
|
|
# hit the conner |
|
77
|
|
|
if new_x - int(new_x) == 0.5 and new_y - int(new_y) == 0.5: |
|
78
|
|
|
path.append((round(new_x - 0.1), round(new_y - 0.1))) |
|
79
|
|
|
path.append((round(new_x - 0.1), round(new_y + 0.1))) |
|
80
|
|
|
path.append((round(new_x + 0.1), round(new_y - 0.1))) |
|
81
|
|
|
path.append((round(new_x + 0.1), round(new_y + 0.1))) |
|
82
|
|
|
return list(set(path)) |
|
83
|
|
|
|
|
84
|
|
|
|
|
85
|
|
|
def bats_visibility(BatPositions, bunker): |
|
86
|
|
|
walls = find_entities(bunker, 'W') |
|
87
|
|
|
visibility = defaultdict(dict) |
|
88
|
|
|
for i, j in combinations(BatPositions, 2): |
|
89
|
|
|
path = path_coordinates(i, j) |
|
90
|
|
|
if not set(path).intersection(set(walls)): |
|
91
|
|
|
distance = hypot(i[0] - j[0], i[1] - j[1]) |
|
92
|
|
|
visibility[i][j] = distance |
|
93
|
|
|
visibility[j][i] = distance |
|
94
|
|
|
return visibility |
|
95
|
|
|
|
|
96
|
|
|
|
|
97
|
|
|
def checkio(bunker): |
|
98
|
|
|
bats = find_entities(bunker, 'B') |
|
99
|
|
|
alpha = find_entities(bunker, 'A') |
|
100
|
|
|
all_bats = bats + alpha |
|
101
|
|
|
visibility = bats_visibility(all_bats, bunker) |
|
102
|
|
|
return shortestPath(visibility, alpha[0], (0, 0))[0] |
|
103
|
|
|
|
|
104
|
|
|
|
|
105
|
|
|
# These "asserts" using only for self-checking and not necessary for |
|
106
|
|
|
# auto-testing |
|
107
|
|
|
if __name__ == '__main__': |
|
108
|
|
|
|
|
109
|
|
|
def almost_equal(checked, correct, significant_digits=2): |
|
110
|
|
|
precision = 0.1 ** significant_digits |
|
111
|
|
|
return correct - precision < checked < correct + precision |
|
112
|
|
|
|
|
113
|
|
|
assert almost_equal(checkio(["B--", "---", "--A"]), 2.83), "1st example" |
|
114
|
|
|
assert almost_equal(checkio(["B-B", "BW-", "-BA"]), 4), "2nd example" |
|
115
|
|
|
assert almost_equal(checkio(["BWB--B", "-W-WW-", "B-BWAB"]), 12), "3rd example" |
|
116
|
|
|
assert almost_equal( |
|
117
|
|
|
checkio(["B---B-", "-WWW-B", "-WA--B", "-W-B--", "-WWW-B", "B-BWB-"]), 9.24 |
|
118
|
|
|
), "4th example" |
|
119
|
|
|
|
KenMercusLai /
checkio
Loading history...