-
Notifications
You must be signed in to change notification settings - Fork 0
/
day10.el
183 lines (170 loc) · 4.61 KB
/
day10.el
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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
;;; -*- lexical-binding: t -*-
;; a map is a list of asteroid coordinates
(defun make-map (grid)
(loop
for line being the elements of grid using (index row)
append
(loop
for char being the elements of line using (index col)
if (= ?# char)
collect (cons col row))))
;; for each other point, compute the angle to it
;; if two points have the same angle, they're on the same line and count as 1
;; use group-by to count unique number of angles
(defun compute-angle (pos1 pos2)
(atan (- (car pos1) (car pos2)) (- (cdr pos1) (cdr pos2))))
(defun compute-all-angles-from (pos map)
(let ((raw-angles
(mapcar
(lambda (other-pos)
(cons (compute-angle pos other-pos) other-pos))
(seq-difference map (list pos)))))
(cons pos (seq-group-by 'car raw-angles))))
(defun find-best-center (grid)
(let ((map (make-map grid)))
(car
(sort
(mapcar
(lambda (pos)
(compute-all-angles-from pos map))
map)
(lambda (s1 s2)
(> (length (cdr s1)) (length (cdr s2))))))))
(defconst grid1
'(".#..#"
"....."
"#####"
"....#"
"...##"))
(defconst grid2
'("......#.#."
"#..#.#...."
"..#######."
".#.#.###.."
".#..#....."
"..#....#.#"
"#..#....#."
".##.#..###"
"##...#..#."
".#....####" ))
(defconst grid3
'("#.#...#.#."
".###....#."
".#....#..."
"##.#.#.#.#"
"....#.#.#."
".##..###.#"
"..#...##.."
"..##....##"
"......#..."
".####.###."
))
(defconst grid4 '(".#..#..###"
"####.###.#"
"....###.#."
"..###.##.#"
"##.##.#.#."
"....###..#"
"..#.#..#.#"
"#..#.#.###"
".##...##.#"
".....#.#.."
))
(defconst grid5 '(".#..##.###...#######"
"##.############..##."
".#.######.########.#"
".###.#######.####.#."
"#####.##.#.##.###.##"
"..#####..#.#########"
"####################"
"#.####....###.#.#.##"
"##.#################"
"#####.##.###..####.."
"..######..##.#######"
"####.##.####...##..#"
".#####..#.######.###"
"##...#.##########..."
"#.##########.#######"
".####.#.###.###.#.##"
"....##.##.###..#####"
".#.#.###########.###"
"#.#.#.#####.####.###"
"###.##.####.##.#..##"))
(defconst problem1 '("#.#.##..#.###...##.#....##....###"
"...#..#.#.##.....#..##.#...###..#"
"####...#..#.##...#.##..####..#.#."
"..#.#..#...#..####.##....#..####."
"....##...#.##...#.#.#...#.#..##.."
".#....#.##.#.##......#..#..#..#.."
".#.......#.....#.....#...###....."
"#.#.#.##..#.#...###.#.###....#..#"
"#.#..........##..###.......#...##"
"#.#.........##...##.#.##..####..#"
"###.#..#####...#..#.#...#..#.#..."
".##.#.##.........####.#.#...##..."
"..##...#..###.....#.#...#.#..#.##"
".#...#.....#....##...##...###...#"
"###...#..#....#............#....."
".#####.#......#.......#.#.##..#.#"
"#.#......#.#.#.#.......##..##..##"
".#.##...##..#..##...##...##.....#"
"#.#...#.#.#.#.#..#...#...##...#.#"
"##.#..#....#..##.#.#....#.##...##"
"...###.#.#.......#.#..#..#...#.##"
".....##......#.....#..###.....##."
"........##..#.#........##.......#"
"#.##.##...##..###.#....#....###.#"
"..##.##....##.#..#.##..#.....#..."
".#.#....##..###.#...##.#.#.#..#.."
"..#..##.##.#.##....#...#........."
"#...#.#.#....#.......#.#...#..#.#"
"...###.##.#...#..#...##...##....#"
"...#..#.#.#..#####...#.#...####.#"
"##.#...#..##..#..###.#..........#"
"..........#..##..#..###...#..#..."
".#.##...#....##.....#.#...##...##"))
;; (find-best-center problem1)
(defun square (x) (* x x))
(defun distance (pos1 pos2)
(sqrt
(+ (square (- (car pos1) (car pos2)))
(square (- (cdr pos1) (cdr pos2))))))
(defun laser-asteroids (grid)
(let* ((result (find-best-center grid))
(station (car result))
(angle-and-points
(mapcar
(lambda (x) (cons (car x) (mapcar 'cdr (cdr x))))
(cdr result)))
(angles
(sort
angle-and-points
(lambda (p1 p2)
(let ((c1 (car p1))
(c2 (car p2)))
(if (or (and (>= 0 c1) (>= 0 c2))
(and (< 0 c1) (< 0 c2)))
(> c1 c2)
(> c2 0))))))
(seen (make-hash-table :test 'equal))
(last-removed))
;; could sort above when computing angle-and-points
(mapc
(lambda (angle)
(setcdr angle
(sort (cdr angle) (lambda (p1 p2) (< (distance station p1) (distance station p2))))))
angles)
(while (< (hash-table-count seen) 200)
(loop
for angle in angles do
(loop
for point in (cdr angle)
while (gethash point seen)
finally do
(and point
(puthash point t seen)
(setq last-removed point)))
while (< (hash-table-count seen) 200)))
last-removed))
(laser-asteroids problem1)
;; => (16 . 23)