-
Notifications
You must be signed in to change notification settings - Fork 0
/
day10.py
executable file
·160 lines (133 loc) · 4.7 KB
/
day10.py
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
import numpy as np
import math
f = open('input10.txt','r')
txt = f.read()
txt = txt.split('\n')
txt = txt[:-1]
# txt = ['.#..##.###...#######',
# '##.############..##.',
# '.#.######.########.#',
# '.###.#######.####.#.',
# '#####.##.#.##.###.##',
# '..#####..#.#########',
# '####################',
# '#.####....###.#.#.##',
# '##.#################',
# '#####.##.###..####..',
# '..######..##.#######',
# '####.##.####...##..#',
# '.#####..#.######.###',
# '##...#.##########...',
# '#.##########.#######',
# '.####.#.###.###.#.##',
# '....##.##.###..#####',
# '.#.#.###########.###',
# '#.#.#.#####.####.###',
# '###.##.####.##.#..##']
rows = len(txt)
cols = len(txt[0])
# Note: I use point = (row,col) or (y,x) convention
def euclidean_distance(p1, p2):
return np.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
def is_point_on_line(p, line):
# line - given by [a, b] where y=a*x+b
if np.isinf(line[0]):
if p[1]==line[1]:
return True
else:
return False
if math.isclose(p[0], (line[0]*p[1] + line[1])):
return True
else:
return False
def is_visible(p1, p2, points):
points_tmp = points.copy()
# returns whether p2 is visible from p1
dist = euclidean_distance(p1, p2)
ang = math.atan2(p2[0]-p1[0], p2[1]-p1[1])
if p1[1]!=p2[1]:
a = (p2[0] - p1[0]) / (p2[1] - p1[1])
b = p1[0] - a*p1[1]
else:
a = np.inf
b = p1[1]
line = [a, b]
# remove p1 and p2 from points:
points_tmp.remove(p1)
points_tmp.remove(p2)
# find points that lie on the same line:
for p in points_tmp:
if is_point_on_line(p, line):
# check for minimal distance and same view direction
if dist > euclidean_distance(p1, p) and math.isclose(ang, math.atan2(p[0]-p1[0],p[1]-p1[1])):
return False
return True
points = []
for r in range(rows):
for c in range(cols):
if txt[r][c] == '#':
points.append((r,c))
def calc_visibility_mat(points):
# matrix denoting visibility from each point to other points:
visibility_mat = np.zeros((len(points), len(points)))
for r in range(len(points)):
for c in range(len(points)):
if r==c:
continue
visibility_mat[r,c] = is_visible(points[r], points[c], points)
return visibility_mat
print('Part 1 - calculating visibility matrix (this takes a while...)')
visibility_mat = calc_visibility_mat(points)
best_idx = np.argmax(np.sum(visibility_mat,0))
best_num_visible = int(np.max(np.sum(visibility_mat,0)))
best_point = points[best_idx]
print('Part 1 answer:')
print('best location = ' + str(best_point))
print('# of points visible = ' + str(best_num_visible))
# Part 2
start_point = best_point
def angle_to_point(start_point, p):
# find the angle between the vector from start point
# to point p, and an upward facing vector (-1,0)
p = np.array(p)
sp = np.array(start_point)
up = np.array((-1,0))
sp_to_p = p - sp
angle = (180/np.pi)*np.arccos(np.dot(up,sp_to_p)/(np.linalg.norm(up)*np.linalg.norm(sp_to_p)))
if p[1]<start_point[1]:
angle = 360-angle
return angle
# remove start point from points:
points.remove(start_point)
# calculate all angles and ranges to different points
angles = []
ranges = []
for p in points:
angles.append(angle_to_point(start_point, p))
ranges.append(euclidean_distance(start_point, p))
ang_sort_inds = np.argsort(angles).tolist()
sorted_data = [[points[i], angles[i], ranges[i]] for i in ang_sort_inds]
sorted_data_updated = sorted_data.copy()
cnt = 1
while len(sorted_data_updated)>1:
data_current = sorted_data_updated
last_point = data_current[0][0]
last_angle = data_current[0][1]
min_dist = data_current[0][2]
data_current = data_current[1:]
for i,p in enumerate(data_current):
if not math.isclose(data_current[i][1], last_angle):
sorted_data_updated.remove([last_point, last_angle, min_dist])
if cnt==200:
print(f'the {cnt}th asteroid to be vaporized is at x={last_point[1]},y={last_point[0]}')
print(f'part 2 answer = {last_point[1]*100+last_point[0]}')
cnt+=1
last_point = data_current[i][0]
last_angle = data_current[i][1]
min_dist = data_current[i][2]
#ind_to_remove = i
else:
if data_current[i][2]<min_dist:
last_point = data_current[i][0]
last_angle = data_current[i][1]
min_dist = data_current[i][2]