-
Notifications
You must be signed in to change notification settings - Fork 0
/
day10.lisp
59 lines (52 loc) · 2.17 KB
/
day10.lisp
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
;;;; day10.lisp
(in-package :aoc2019.day10)
(defun load-asteroids ()
(loop-line-by-line (puzzlefile 10)
:for y :from 0
:nconc (loop
:for char :across line
:for x :from 0
:when (char= char #\#) :collect (complex x y))))
(defun line-of-sight (a b)
(let* ((delta (- b a)))
(/ delta (gcd (realpart delta) (imagpart delta)))))
(defun build-all-lines-of-sight (asteroids)
(loop
:with visibles := (make-hash-table :test 'equal)
:for current-sublist := asteroids :then (rest current-sublist)
:while current-sublist
:do (loop
:with current := (first current-sublist)
:for other :in (rest current-sublist)
:for los := (line-of-sight current other)
:do (push los (gethash current visibles))
:do (push (- los) (gethash other visibles)))
:finally (return visibles)))
(defun vec->angle (complex)
(let ((value
(- (/ pi 2) (atan (- (imagpart complex)) (realpart complex)))))
(if (> 0 (round value 1e-5))
(+ value (* 2 pi))
value)))
(defun find-station-location (lines-of-sight)
(loop
:with station-location := -1
:for location :being :the :hash-key
:using (hash-value visible) :of lines-of-sight
:for visible-count := (length (remove-duplicates visible))
:maximizing visible-count :into max-count
:when (= max-count visible-count) :do (setf station-location location)
:finally (return (values station-location max-count))))
(defun day10 ()
(let ((lines-of-sight (build-all-lines-of-sight (load-asteroids))))
(multiple-value-bind (station-location visible-count) (find-station-location lines-of-sight)
(format t "The optimal spot for the station is (~a|~a) and there are ~a asteroids visible.~%"
(realpart station-location) (imagpart station-location) visible-count)
(loop :with direction := (nth 199
(sort (remove-duplicates
(gethash station-location lines-of-sight))
#'< :key #'vec->angle))
:for curr-pos := (+ station-location direction) :then (+ curr-pos direction)
:until (gethash curr-pos lines-of-sight nil)
:finally (format t "The 200th asteroid to be obliterated is at (~a|~a).~%"
(realpart curr-pos) (imagpart curr-pos))))))