AoC 2019 Day 10

day-10.lisp

(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