Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
AoC 2019 Day 10
(defpackage :advent.2019.10 (:use :cl :alexandria))
(in-package :advent.2019.10)
;; (setf *default-pathname-defaults* #P"~/data/advent/2019/")
;; day 10 - part 1
(defun map-map (fn stream &aux (y 0) (x 0))
(flet ((callback () (funcall fn x y)))
(loop
for c = (read-char stream nil nil)
while c
do (case c
((#\space #\tab))
(#\. (incf x))
(#\# (callback) (incf x))
((#\newline #\|) (incf y) (setf x 0))))))
(defgeneric all-asteroids (in)
(:method ((in pathname))
(with-open-file (s in) (all-asteroids s)))
(:method ((in string))
(with-input-from-string (s in) (all-asteroids s)))
(:method ((in stream) &aux all)
(map-map (lambda (x y) (push (complex x y) all)) in)
all))
(defun best (input)
(loop
with all = (all-asteroids input)
for asteroid in all
maximize
(loop
with hash = (make-hash-table)
for other-asteroid in all
for diff = (- other-asteroid asteroid)
for gcd = (gcd (realpart diff)
(imagpart diff))
for key = (or (zerop gcd) (/ diff gcd))
do (push nil (gethash key hash))
finally
(return (1- (hash-table-count hash))))))
(best #P"10.in")
;; day 10 - part 2
(defun prepare (input)
(loop
with all = (all-asteroids input)
for asteroid in all
collect
(list* asteroid
(loop
with hash = (make-hash-table)
for other-asteroid in all
for diff = (- other-asteroid asteroid)
unless (zerop diff)
do (push other-asteroid
(gethash (/ diff
(gcd (realpart diff)
(imagpart diff)))
hash))
finally
(return (list hash (hash-table-count hash)))))
into list
finally (return
(first
(sort list #'> :key #'third)))))
(defun best (input)
(third (prepare input)))
(best #P"10.in")
=> 260
(defun cycles (input)
(destructuring-bind (laser table count) (prepare input)
(declare (ignore count))
(flet ((transform (orientation)
(let ((phase (phase
(conjugate
(* (conjugate orientation)
#C(0 -1))))))
(if (< phase 0)
(+ phase (* 2 pi))
phase))))
(sort
(loop
for (orientation . asteroids) in (hash-table-alist table)
collect (list* (transform orientation)
orientation
(sort asteroids
#'<
:key (lambda (u) (abs (- u laser))))))
#'<
:key #'first))))
(defun iter-asteroids-clockwise (in visitor)
(let* ((cycles (cycles in))
(total (loop for (_ o . r) in cycles sum (length r))))
(setf cycles (nconc cycles cycles))
(loop
with visit = 0
for entry = (pop cycles)
when (cddr entry)
do (funcall visitor (incf visit) (pop (cddr entry)))
until (>= visit total))))
(defun day-10-part-2 ()
(block nil
(iter-asteroids-clockwise #P"10.in"
(lambda (rank asteroid)
(when (= rank 200)
(return (+ (* (realpart asteroid) 100)
(imagpart asteroid))))))))
;; and check which one is 200th
(defvar *map2*
".#....#####...#..
##...##.#####..##
##...#...#.#####.
..#.....#...###..
..#.#.....#....##")
(cycles *map2*)
((0.0 #C(0 -1) #C(8 1) 8)
(0.32175055 #C(1 -3) 9)
(0.4636476 #C(1 -2) #C(9 1))
(0.5880026 #C(2 -3) 10)
(0.7853982 #C(1 -1) #C(9 2) #C(10 1))
(0.98279375 #C(3 -2) #C(11 1))
(1.1071488 #C(2 -1) #C(12 1) 14)
(1.2490457 #C(3 -1) #C(11 2))
(1.2924967 #C(7 -2) #C(15 1))
(1.3258177 #C(4 -1) #C(12 2) #C(16 1))
(1.3734008 #C(5 -1) #C(13 2))
(1.4056476 #C(6 -1) #C(14 2))
(1.4288993 #C(7 -1) #C(15 2))
(1.5707964 1 #C(12 3) #C(13 3) #C(14 3))
(1.6951513 #C(8 1) #C(16 4))
(1.7126933 #C(7 1) #C(15 4)) (2.0344439 #C(2 1) #C(10 4))
(4.467410270367758d0 #C(-4 1) #C(4 4)) (4.547240320836202d0 #C(-6 1) #C(2 4))
(4.7123889366733d0 -1 #C(2 3)) (4.83674401441683d0 #C(-8 -1) #C(0 2))
(4.854286019002096d0 #C(-7 -1) #C(1 2))
(4.957367602978842d0 #C(-4 -1) #C(0 1))
(4.990688625966207d0 #C(-7 -2) #C(1 1)) (5.03413957754244d0 #C(-3 -1) #C(5 2))
(5.117280785237448d0 #C(-7 -3) 1) (5.300391558800833d0 #C(-3 -2) #C(5 1))
(5.497787121926443d0 #C(-1 -1) #C(6 1)) (5.695182685052053d0 #C(-2 -3) 6)
(5.961434755717413d0 #C(-1 -3) 7))
(let* ((cycles (cycles *map2*))
(total (loop for (_ o . r) in cycles
sum (length r))))
(setf cycles (nconc cycles cycles))
(loop
with visit = 0
for entry = (pop cycles)
when (cddr entry)
do
(print (cons (incf visit) (pop (cddr entry))))
until (>= visit total)))
(1 . #C(8 1))
(2 . 9)
(3 . #C(9 1))
(4 . 10)
(5 . #C(9 2))
(6 . #C(11 1))
(7 . #C(12 1))
(8 . #C(11 2))
(9 . #C(15 1))
(10 . #C(12 2))
(11 . #C(13 2))
(12 . #C(14 2))
(13 . #C(15 2))
(14 . #C(12 3))
(15 . #C(16 4))
(16 . #C(15 4))
(17 . #C(10 4))
(18 . #C(4 4))
(19 . #C(2 4))
(20 . #C(2 3))
(21 . #C(0 2))
(22 . #C(1 2))
(23 . #C(0 1))
(24 . #C(1 1))
(25 . #C(5 2))
(26 . 1)
(27 . #C(5 1))
(28 . #C(6 1))
(29 . 6)
(30 . 7)
(31 . 8)
(32 . #C(10 1))
(33 . 14)
(34 . #C(16 1))
(35 . #C(13 3))
(36 . #C(14 3))
(let* ((cycles (cycles #P"10.in"))
(total (loop for (_ o . r) in cycles
sum (length r))))
(setf cycles (nconc cycles cycles))
(loop
with visit = 0
for entry = (pop cycles)
when (cddr entry)
do
(print (cons (incf visit) (pop (cddr entry))))
until (>= visit total)))
(1 . #C(14 16))
(2 . #C(15 1))
(3 . #C(15 2))
(4 . #C(15 3))
(5 . #C(15 4))
(6 . #C(15 5))
(7 . #C(15 6))
(8 . 16)
(9 . #C(16 1))
(10 . #C(16 2))
(11 . #C(15 10))
(12 . #C(16 4))
(13 . #C(16 5))
(14 . #C(17 1))
(15 . #C(15 12))
(16 . #C(17 3))
(17 . #C(17 4))
(18 . 18)
(19 . #C(15 13))
(20 . #C(18 2))
(21 . #C(16 10))
(22 . #C(17 7))
(23 . #C(18 4))
(24 . #C(16 11))
(25 . 20)
(26 . #C(19 3))
(27 . #C(18 6))
(28 . #C(20 1))
(29 . #C(19 4))
(30 . #C(16 12))
(31 . 21)
(32 . #C(17 10))
(33 . #C(21 1))
(34 . #C(18 8))
(35 . #C(19 6))
(36 . #C(21 2))
(37 . 22)
(38 . #C(15 15))
(39 . 23)
(40 . #C(22 2))
(41 . #C(19 8))
(42 . #C(18 10))
(43 . #C(21 5))
(44 . #C(23 2))
(45 . #C(22 4))
(46 . #C(23 3))
(47 . #C(16 14))
(48 . #C(23 4))
(49 . #C(19 10))
(50 . #C(22 6))
(51 . #C(17 13))
(52 . #C(21 8))
(53 . #C(22 7))
(54 . #C(23 6))
(55 . #C(19 11))
(56 . #C(22 8))
(57 . #C(15 16))
(58 . #C(23 9))
(59 . #C(21 11))
(60 . #C(20 12))
(61 . #C(19 13))
(62 . #C(22 11))
(63 . #C(21 12))
(64 . #C(20 13))
(65 . #C(22 12))
(66 . #C(23 12))
(67 . #C(16 16))
(68 . #C(23 13))
(69 . #C(21 14))
(70 . #C(22 14))
(71 . #C(17 16))
(72 . #C(21 15))
(73 . #C(22 15))
(74 . #C(23 15))
(75 . #C(19 16))
(76 . #C(20 16))
(77 . #C(21 16))
(78 . #C(22 16))
(79 . #C(23 16))
(80 . #C(15 17))
(81 . #C(21 18))
(82 . #C(20 18))
(83 . #C(23 19))
(84 . #C(18 18))
(85 . #C(21 19))
(86 . #C(20 19))
(87 . #C(19 19))
(88 . #C(21 20))
(89 . #C(23 21))
(90 . #C(16 18))
(91 . #C(23 22))
(92 . #C(21 21))
(93 . #C(19 20))
(94 . #C(22 22))
(95 . #C(21 22))
(96 . #C(18 20))
(97 . #C(15 18))
(98 . #C(19 23))
(99 . #C(17 21))
(100 . #C(18 23))
(101 . #C(17 22))
(102 . #C(17 23))
(103 . #C(16 22))
(104 . #C(15 20))
(105 . #C(15 23))
(106 . #C(14 18))
(107 . #C(13 23))
(108 . #C(13 22))
(109 . #C(13 21))
(110 . #C(12 23))
(111 . #C(12 22))
(112 . #C(13 19))
(113 . #C(12 20))
(114 . #C(11 21))
(115 . #C(9 23))
(116 . #C(13 18))
(117 . #C(7 23))
(118 . #C(8 22))
(119 . #C(10 20))
(120 . #C(7 22))
(121 . #C(11 19))
(122 . #C(9 20))
(123 . #C(7 21))
(124 . #C(5 22))
(125 . #C(3 23))
(126 . #C(4 22))
(127 . #C(2 22))
(128 . #C(4 21))
(129 . #C(1 22))
(130 . #C(6 20))
(131 . #C(3 21))
(132 . #C(11 18))
(133 . #C(1 21))
(134 . #C(4 20))
(135 . #C(0 21))
(136 . #C(3 20))
(137 . #C(10 18))
(138 . #C(1 20))
(139 . #C(5 19))
(140 . #C(0 20))
(141 . #C(3 19))
(142 . #C(8 18))
(143 . #C(1 19))
(144 . #C(7 18))
(145 . #C(6 18))
(146 . #C(2 18))
(147 . #C(1 18))
(148 . #C(0 18))
(149 . #C(13 17))
(150 . #C(0 16))
(151 . #C(2 16))
(152 . #C(3 16))
(153 . #C(6 16))
(154 . #C(7 16))
(155 . #C(8 16))
(156 . #C(3 15))
(157 . #C(4 15))
(158 . #C(5 15))
(159 . #C(1 14))
(160 . #C(10 16))
(161 . #C(7 15))
(162 . #C(1 13))
(163 . #C(8 15))
(164 . #C(0 12))
(165 . #C(3 13))
(166 . #C(6 14))
(167 . #C(1 12))
(168 . #C(9 15))
(169 . #C(2 12))
(170 . #C(7 14))
(171 . #C(1 11))
(172 . #C(12 16))
(173 . #C(1 10))
(174 . #C(7 13))
(175 . #C(4 11))
(176 . #C(1 9))
(177 . #C(6 12))
(178 . #C(3 10))
(179 . #C(0 8))
(180 . #C(5 11))
(181 . #C(1 8))
(182 . #C(7 12))
(183 . #C(2 8))
(184 . #C(1 7))
(185 . #C(5 10))
(186 . #C(0 6))
(187 . #C(9 13))
(188 . #C(3 8))
(189 . #C(2 7))
(190 . #C(1 6))
(191 . #C(0 5))
(192 . #C(6 10))
(193 . #C(4 8))
(194 . #C(2 6))
(195 . #C(13 16))
(196 . #C(1 3))
(197 . #C(2 4))
(198 . #C(3 5))
(199 . #C(5 7))
(200 . #C(6 8))
(201 . #C(7 9))
(202 . #C(8 10))
(203 . #C(9 11))
(204 . 0)
(205 . #C(5 6))
(206 . #C(1 1))
(207 . #C(10 12))
(208 . #C(3 3))
(209 . #C(7 8))
(210 . 1)
(211 . #C(8 9))
(212 . #C(3 2))
(213 . #C(9 10))
(214 . #C(3 1))
(215 . #C(12 14))
(216 . 3)
(217 . #C(5 3))
(218 . #C(7 6))
(219 . #C(4 1))
(220 . #C(6 4))
(221 . #C(11 12))
(222 . 4)
(223 . #C(7 5))
(224 . #C(10 10))
(225 . #C(5 1))
(226 . #C(8 6))
(227 . #C(7 4))
(228 . #C(6 2))
(229 . #C(13 15))
(230 . #C(7 2))
(231 . #C(10 8))
(232 . #C(11 10))
(233 . 7)
(234 . #C(12 12))
(235 . #C(9 4))
(236 . #C(8 1))
(237 . #C(10 6))
(238 . #C(9 3))
(239 . #C(13 14))
(240 . #C(9 1))
(241 . #C(11 7))
(242 . 9)
(243 . #C(12 10))
(244 . #C(11 6))
(245 . #C(10 2))
(246 . #C(11 5))
(247 . 10)
(248 . #C(12 8))
(249 . #C(11 3))
(250 . #C(12 7))
(251 . #C(11 1))
(252 . #C(12 6))
(253 . 11)
(254 . #C(13 10))
(255 . #C(13 9))
(256 . 12)
(257 . #C(13 8))
(258 . #C(13 6))
(259 . #C(13 2))
(260 . #C(13 1))
(261 . #C(14 15))
(262 . #C(16 9))
(263 . #C(17 8))
(264 . #C(20 2))
(265 . #C(20 3))
(266 . #C(16 13))
(267 . #C(18 11))
(268 . #C(20 9))
(269 . #C(17 14))
(270 . #C(23 11))
(271 . #C(18 15))
(272 . #C(20 15))
(273 . #C(17 17))
(274 . #C(23 20))
(275 . #C(18 19))
(276 . #C(22 23))
(277 . #C(16 19))
(278 . #C(14 20))
(279 . #C(12 21))
(280 . #C(10 23))
(281 . #C(12 19))
(282 . #C(6 23))
(283 . #C(4 23))
(284 . #C(2 23))
(285 . #C(5 20))
(286 . #C(2 19))
(287 . #C(0 19))
(288 . #C(12 17))
(289 . #C(0 15))
(290 . #C(2 15))
(291 . #C(6 15))
(292 . #C(0 13))
(293 . #C(5 14))
(294 . #C(0 11))
(295 . #C(10 15))
(296 . #C(0 9))
(297 . #C(4 9))
(298 . #C(11 14))
(299 . #C(0 1))
(300 . #C(2 3))
(301 . #C(4 5))
(302 . #C(2 2))
(303 . #C(5 5))
(304 . #C(4 3))
(305 . #C(4 2))
(306 . #C(5 2))
(307 . #C(6 3))
(308 . #C(11 11))
(309 . #C(10 7))
(310 . #C(12 11))
(311 . #C(10 3))
(312 . #C(11 2))
(313 . #C(12 3))
(314 . #C(12 1))
(315 . #C(14 14))
(316 . #C(18 5))
(317 . #C(18 9))
(318 . #C(20 8))
(319 . #C(18 13))
(320 . #C(22 13))
(321 . #C(21 17))
(322 . #C(18 21))
(323 . #C(14 21))
(324 . #C(11 23))
(325 . #C(8 23))
(326 . #C(2 21))
(327 . #C(8 17))
(328 . #C(8 14))
(329 . #C(9 12))
(330 . #C(10 9))
(331 . #C(11 8))
(332 . #C(14 9))
(333 . #C(19 2))
(334 . #C(21 3))
(335 . #C(19 12))
(336 . #C(22 17))
(337 . #C(14 22))
(338 . #C(7 17))
(339 . #C(2 11))
(340 . #C(5 8))
(341 . #C(7 3))
(342 . #C(9 2))
(343 . #C(14 8))
(344 . #C(20 11))
(345 . #C(5 17))
(346 . #C(0 10))
(347 . #C(4 7))
(348 . #C(14 7))
(349 . #C(23 8))
(350 . #C(4 17))
(351 . #C(14 5))
(352 . #C(1 17))
(353 . #C(14 3))
(354 . #C(0 17))
(355 . #C(14 1))
;; part 1 -- tests
(defun tests (input)
(loop
with all = (all-asteroids input)
for asteroid in all
collect
(list asteroid
(loop
with hash = (make-hash-table)
for other in all
for delta = (- other asteroid)
for gcd = (gcd (realpart delta)
(imagpart delta))
for norm = (if (= gcd 0) nil (/ delta gcd))
do (push other (gethash norm hash))
finally
(return (list (1- (hash-table-count hash))
;(alexandria:hash-table-alist hash)
))))))
(defvar *test*
".#..#..###
####.###.#
....###.#.
..###.##.#
##.##.#.#.
....###..#
..#.#..#.#
#..#.#.###
.##...##.#
.....#.#..")
(tests ".#..#|.....|#####|....#|...##")
((#C(4 4) (7)) (#C(3 4) (8)) (#C(4 3) (7)) (#C(4 2) (5)) (#C(3 2) (7))
(#C(2 2) (7)) (#C(1 2) (7)) (#C(0 2) (6)) (4 (7)) (1 (7)))
(equalp
(tests "#.#...#.#.|.###....#.|.#....#...|##.#.#.#.#|....#.#.#.|.##..###.#|..#...##..|..##....##|......#...|.####.###.")
'((#C(8 9) (27)) (#C(7 9) (29)) (#C(6 9) (27)) (#C(4 9) (29)) (#C(3 9) (23))
(#C(2 9) (29)) (#C(1 9) (25)) (#C(6 8) (33)) (#C(9 7) (28)) (#C(8 7) (32))
(#C(3 7) (31)) (#C(2 7) (32)) (#C(7 6) (34)) (#C(6 6) (28)) (#C(2 6) (29))
(#C(9 5) (28)) (#C(7 5) (28)) (#C(6 5) (30)) (#C(5 5) (30)) (#C(2 5) (31))
(#C(1 5) (29)) (#C(8 4) (29)) (#C(6 4) (30)) (#C(4 4) (33)) (#C(9 3) (28))
(#C(7 3) (28)) (#C(5 3) (28)) (#C(3 3) (29)) (#C(1 3) (27)) (#C(0 3) (29))
(#C(6 2) (30)) (#C(1 2) (35)) (#C(8 1) (30)) (#C(3 1) (30)) (#C(2 1) (30))
(#C(1 1) (29)) (8 (30)) (6 (31)) (2 (28)) (0 (28))))
(equalp
(tests
".#..#..###
####.###.#
....###.#.
..###.##.#
##.##.#.#.
....###..#
..#.#..#.#
#..#.#.###
.##...##.#
.....#.#..")
'((#C(7 9) (36)) (#C(5 9) (35)) (#C(9 8) (34)) (#C(7 8) (35)) (#C(6 8) (39))
(#C(2 8) (36)) (#C(1 8) (38)) (#C(9 7) (32)) (#C(8 7) (37)) (#C(7 7) (36))
(#C(5 7) (35)) (#C(3 7) (35)) (#C(0 7) (35)) (#C(9 6) (38)) (#C(7 6) (36))
(#C(4 6) (33)) (#C(2 6) (38)) (#C(9 5) (33)) (#C(6 5) (39)) (#C(5 5) (36))
(#C(4 5) (39)) (#C(8 4) (36)) (#C(6 4) (33)) (#C(4 4) (38)) (#C(3 4) (35))
(#C(1 4) (37)) (#C(0 4) (36)) (#C(9 3) (35)) (#C(7 3) (30)) (#C(6 3) (41))
(#C(4 3) (35)) (#C(3 3) (35)) (#C(2 3) (38)) (#C(8 2) (38)) (#C(6 2) (38))
(#C(5 2) (36)) (#C(4 2) (37)) (#C(9 1) (29)) (#C(7 1) (31)) (#C(6 1) (33))
(#C(5 1) (33)) (#C(3 1) (32)) (#C(2 1) (33)) (#C(1 1) (35)) (#C(0 1) (35))
(9 (34)) (8 (37)) (7 (34)) (4 (33)) (1 (34))))
(loop for (a (b)) in (tests
".#..##.###...#######
##.############..##.
.#.######.########.#
.###.#######.####.#.
#####.##.#.##.###.##
..#####..#.#########
####################
#.####....###.#.#.##
##.#################
#####.##.###..####..
..######..##.#######
####.##.####...##..#
.#####..#.######.###
##...#.##########...
#.##########.#######
.####.#.###.###.#.##
....##.##.###..#####
.#.#.###########.###
#.#.#.#####.####.###
###.##.####.##.#..##")
maximize b)
=> 210
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.