# HG changeset patch # User Steve Losh # Date 1576433644 18000 # Node ID f524273415d079effcb3b21aba3d9005d36ee1a5 # Parent 81b47667837b96796cc564811a1b6966232f61ba 2019/15 diff -r 81b47667837b -r f524273415d0 data/2019/15.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/data/2019/15.txt Sun Dec 15 13:14:04 2019 -0500 @@ -0,0 +1,1 @@ +3,1033,1008,1033,1,1032,1005,1032,31,1008,1033,2,1032,1005,1032,58,1008,1033,3,1032,1005,1032,81,1008,1033,4,1032,1005,1032,104,99,102,1,1034,1039,1002,1036,1,1041,1001,1035,-1,1040,1008,1038,0,1043,102,-1,1043,1032,1,1037,1032,1042,1106,0,124,1002,1034,1,1039,102,1,1036,1041,1001,1035,1,1040,1008,1038,0,1043,1,1037,1038,1042,1105,1,124,1001,1034,-1,1039,1008,1036,0,1041,102,1,1035,1040,102,1,1038,1043,1002,1037,1,1042,1105,1,124,1001,1034,1,1039,1008,1036,0,1041,102,1,1035,1040,102,1,1038,1043,1002,1037,1,1042,1006,1039,217,1006,1040,217,1008,1039,40,1032,1005,1032,217,1008,1040,40,1032,1005,1032,217,1008,1039,33,1032,1006,1032,165,1008,1040,35,1032,1006,1032,165,1101,2,0,1044,1106,0,224,2,1041,1043,1032,1006,1032,179,1101,1,0,1044,1106,0,224,1,1041,1043,1032,1006,1032,217,1,1042,1043,1032,1001,1032,-1,1032,1002,1032,39,1032,1,1032,1039,1032,101,-1,1032,1032,101,252,1032,211,1007,0,37,1044,1105,1,224,1102,0,1,1044,1105,1,224,1006,1044,247,101,0,1039,1034,101,0,1040,1035,102,1,1041,1036,1001,1043,0,1038,1002,1042,1,1037,4,1044,1105,1,0,31,10,7,30,32,67,8,24,11,62,6,11,19,78,16,20,8,80,14,19,63,8,40,36,65,34,59,23,33,29,79,19,47,28,54,8,11,41,33,57,85,25,56,48,16,90,74,39,11,79,68,18,46,33,74,47,25,60,1,23,78,69,5,55,12,28,73,22,80,30,26,55,2,6,96,21,57,34,33,10,91,72,61,31,2,24,29,94,24,12,43,60,72,79,27,24,21,95,59,15,53,34,9,36,82,83,4,67,30,62,5,70,94,1,81,75,6,18,68,9,26,38,31,1,98,57,97,63,8,60,35,5,48,36,59,75,4,88,23,21,39,10,99,13,36,53,66,73,28,33,80,28,78,23,7,30,27,77,28,69,69,1,65,78,17,17,2,16,27,91,43,27,72,93,6,5,92,12,55,79,94,98,60,19,15,36,35,55,9,62,84,27,74,56,25,9,60,72,15,34,59,15,31,58,76,24,81,62,99,35,31,14,39,25,60,3,5,46,24,48,22,1,73,99,96,27,46,48,5,65,26,6,48,11,13,69,12,33,22,95,11,72,28,42,28,88,5,31,56,50,72,30,49,84,52,32,11,45,7,54,60,12,72,33,38,62,18,54,31,8,92,53,34,4,76,21,46,81,53,81,21,10,63,12,75,22,62,87,32,23,30,40,29,24,61,6,88,70,14,18,99,13,14,4,72,5,22,54,90,75,35,1,10,49,17,7,98,8,81,13,47,59,13,80,70,9,26,73,22,77,3,22,73,99,74,11,10,60,4,27,86,46,67,30,94,29,93,26,66,25,8,14,92,24,45,78,24,23,97,31,9,25,25,61,44,35,31,73,52,80,35,96,32,43,8,66,57,87,31,85,12,50,74,7,23,61,12,7,78,1,1,53,14,54,18,18,63,41,25,90,1,85,24,22,98,62,35,14,19,50,80,20,7,73,21,14,81,19,89,11,31,84,7,53,9,54,20,90,72,31,70,54,17,31,59,18,8,69,83,58,78,12,98,20,81,26,50,95,19,25,54,31,80,67,6,3,87,6,99,93,22,75,73,34,52,58,22,32,52,34,30,85,54,58,75,14,22,97,12,36,53,67,32,99,54,15,4,66,69,7,48,87,25,17,41,57,10,63,35,24,43,5,57,25,93,22,71,7,36,63,84,26,4,7,78,26,68,77,35,9,70,17,12,59,41,78,18,54,18,80,18,86,93,19,35,73,34,53,97,23,2,95,30,32,85,21,21,79,19,18,85,57,23,85,35,34,61,30,66,29,19,76,30,17,46,1,16,98,26,25,91,15,47,54,75,26,17,36,74,60,33,28,49,53,15,13,45,6,90,26,73,17,87,4,68,18,30,22,96,92,97,14,40,24,50,96,15,49,55,79,8,16,1,50,5,60,55,14,41,67,25,26,71,18,26,89,70,14,6,51,11,94,68,69,22,73,63,6,33,88,36,51,20,6,44,26,71,17,31,11,86,81,23,31,80,18,87,26,12,91,8,41,6,18,9,33,90,1,59,56,32,29,54,50,34,12,74,97,10,39,87,41,9,52,67,21,22,38,61,57,1,87,4,35,98,61,16,95,78,65,17,31,9,71,9,52,52,9,8,73,40,36,16,48,52,9,26,39,4,17,42,1,35,80,93,4,40,23,13,66,7,28,84,73,22,31,76,31,21,39,4,83,84,41,27,66,34,88,15,50,65,45,22,65,26,78,15,50,40,79,31,38,9,60,2,51,24,46,99,42,27,45,1,71,20,78,86,95,9,81,0,0,21,21,1,10,1,0,0,0,0,0,0 diff -r 81b47667837b -r f524273415d0 package.lisp --- a/package.lisp Sat Dec 14 20:00:14 2019 -0500 +++ b/package.lisp Sun Dec 15 13:14:04 2019 -0500 @@ -80,6 +80,12 @@ :bisect-integers-left :bisect-integers-right + :print-hash-table-map + + :clear + :green + :reset + )) (eval-when (:compile-toplevel :load-toplevel :execute) diff -r 81b47667837b -r f524273415d0 src/2019/days/day-03.lisp --- a/src/2019/days/day-03.lisp Sat Dec 14 20:00:14 2019 -0500 +++ b/src/2019/days/day-03.lisp Sun Dec 15 13:14:04 2019 -0500 @@ -1,16 +1,6 @@ (defpackage :advent/2019/03 #.cl-user::*advent-use*) (in-package :advent/2019/03) -(defun print-grid (grid) - (multiple-value-bind (left right bottom top) - (bounds (alexandria:hash-table-keys grid)) - (iterate - (for y :from (1+ top) :downto (1- bottom)) - (iterate - (for x :from (1- left) :to (1+ right)) - (princ (gethash (complex x y) grid #\.))) - (terpri)))) - (defun parse-path (string) (iterate (for ((#'first-character direction) (#'parse-integer distance)) @@ -62,11 +52,15 @@ (flet ((intersection-cost (point) (+ (gethash point scores1) (gethash point scores2)))) + ;; (print-hash-table-map grid :default #\. :pad 1) (values (alexandria:extremum (mapcar #'manhattan-distance intersections) #'<) (alexandria:extremum (mapcar #'intersection-cost intersections) #'<))))) -;; (run '("R8,U5,L5,D3" "U7,R6,D4,L4")) +#; Scratch -------------------------------------------------------------------- + +(run '("R8,U5,L5,D3" "U7,R6,D4,L4")) + ;; (run '( ;; "R75,D30,R83,U83,L12,D49,R71,U7,L72" ;; "U62,R66,U55,R34,D71,R55,D58,R83" diff -r 81b47667837b -r f524273415d0 src/2019/days/day-12.lisp --- a/src/2019/days/day-12.lisp Sat Dec 14 20:00:14 2019 -0500 +++ b/src/2019/days/day-12.lisp Sun Dec 15 13:14:04 2019 -0500 @@ -1,4 +1,4 @@ -(defpackage :advent/2019/12 #.cl-user::*advent-use*) +(advent:defpackage* :advent/2019/12) (in-package :advent/2019/12) (defclass* moon () (pos vel)) diff -r 81b47667837b -r f524273415d0 src/2019/days/day-13.lisp --- a/src/2019/days/day-13.lisp Sat Dec 14 20:00:14 2019 -0500 +++ b/src/2019/days/day-13.lisp Sun Dec 15 13:14:04 2019 -0500 @@ -39,31 +39,13 @@ :score score))))) (values screen score))) -(defun esc (string) - (format t "~C~A" #\esc string) - (force-output)) - -(defun clear () - (esc "[2J") - (esc "[;H")) - -(defun green () - (esc "[32m")) - -(defun reset () - (esc "[0m")) (defun draw-screen (update) (clear) (green) (format t "SCORE: ~D~%" (score update)) (reset) - (multiple-value-bind (left right bottom top) - (bounds (hash-table-keys (screen update))) - (do-irange ((row bottom top)) - (do-irange ((col left right)) - (write-char (tile-char (gethash (complex col row) (screen update))))) - (terpri)))) + (print-hash-table-map (screen update) :key #'tile-char :default nil :flip-y t)) (defun play-interactively (program) (setf (elt program 0) 2) @@ -100,3 +82,4 @@ #; Scratch -------------------------------------------------------------------- (play-interactively *data*) + diff -r 81b47667837b -r f524273415d0 src/2019/days/day-15.lisp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/2019/days/day-15.lisp Sun Dec 15 13:14:04 2019 -0500 @@ -0,0 +1,134 @@ +(advent:defpackage* :advent/2019/15 (:shadow :step)) +(in-package :advent/2019/15) + +(defparameter *animate* nil) +(defparameter *directions* '(#c(0 1) #c(0 -1) #c(-1 0) #c(1 0))) + +(defclass* repair-machine () + ((machine) + (input) + (output) + (pos :initform 0) + (world :initform (make-hash-table)) + (oxygen-position))) + +(defmethod initialize-instance :after ((machine repair-machine) &key) + (setf (gethash 0 (world machine)) #\.)) + +(defun make-repair-machine (program) + (let ((input (make-queue)) + (output (make-queue))) + (make-instance 'repair-machine + :machine (advent/intcode:init program + :input (curry #'dequeue input) + :output (rcurry #'enqueue output)) + :input input + :output output))) + +(defun step (machine) + "Run `machine` until it produces some output." + (loop :while (queue-empty-p (output machine)) + :do (advent/intcode:step (machine machine)))) + +(defun print-world (machine) + (print-hash-table-map + (world machine) + :pad 1 + :get (lambda (pos) + (if (= (pos machine) pos) + #\@ + (gethash pos (world machine) #\space))))) + +(defun dir->int (dir) + (ecase dir + (#c( 0 1) 1) + (#c( 0 -1) 2) + (#c(-1 0) 3) + (#c( 1 0) 4))) + +(defun int->reply (int) + "Parse `int`, returning `(values result actually-moved found-oxygen)`." + (ecase int + (0 (values 'wall nil nil)) + (1 (values 'ok t nil)) + (2 (values 'oxygen t t)))) + +(defun result->char (reply) + (ecase reply + (wall #\#) + (ok #\.) + (oxygen #\O))) + +(defun move (machine direction) + (let ((target (+ (pos machine) direction))) + (enqueue (dir->int direction) (input machine)) + (step machine) + (multiple-value-bind (result actually-moved found-oxygen) + (int->reply (dequeue (output machine))) + (setf (gethash target (world machine)) + (result->char result)) + (when actually-moved + (setf (pos machine) target)) + (when found-oxygen + (setf (oxygen-position machine) target)) + actually-moved))) + +(defun explore (machine) + (labels ((seenp (pos) + (nth-value 1 (gethash pos (world machine)))) + (seen-direction-p (pos direction) + (seenp (+ pos direction))) + (unseen-directions (pos) + (remove-if (curry #'seen-direction-p pos) *directions*))) + (iterate + (with frontier = (list (unseen-directions 0))) + (with path = '()) + (when *animate* + (clear) + (print-world machine) + (sleep 1/60)) + (until (null frontier)) + (if (null (first frontier)) + (progn (pop frontier) ; backtrack + (when path (move machine (pop path)))) + (progn (for dir = (pop (first frontier))) + (when (move machine dir) + (push (unseen-directions (pos machine)) frontier) + (push (- dir) path))))))) + +(defun find-oxygen (machine) + (flet ((ref (pos) + (gethash pos (world machine)))) + (astar :start 0 + :neighbors (lambda (pos) + (remove #\# (manhattan-neighbors pos) :key #'ref)) + :goalp (lambda (pos) + (char= #\O (ref pos))) + :cost (constantly 1) + :heuristic (curry #'manhattan-distance (oxygen-position machine)) + :test #'eql))) + +(defun flood-oxygen (machine) + (labels ((ref (pos) + (gethash pos (world machine))) + (empty-neighbors (pos) + (remove #\. (manhattan-neighbors pos) :key #'ref :test-not #'char=)) + (oxygenate (pos) + (setf (gethash pos (world machine)) #\O))) + (iterate + (with frontier = (empty-neighbors (oxygen-position machine))) + (until (null frontier)) + (counting t) + (map nil #'oxygenate frontier) + (setf frontier (remove-duplicates (mapcan #'empty-neighbors frontier)))))) + +(define-problem (2019 15) (data read-numbers) (222 394) + (let ((machine (make-repair-machine data))) + (explore machine) + (values (1- (length (find-oxygen machine))) + (flood-oxygen machine)))) + +#; Scratch -------------------------------------------------------------------- + +(let ((*animate* t)) + (run)) diff -r 81b47667837b -r f524273415d0 src/utils.lisp --- a/src/utils.lisp Sat Dec 14 20:00:14 2019 -0500 +++ b/src/utils.lisp Sun Dec 15 13:14:04 2019 -0500 @@ -755,6 +755,55 @@ (recur low mid))))))) +(defun print-hash-table-map (table &key + flip-y + get + (pad 0) + (default #\space) + (key #'identity)) + "Print `table` to standard out. + + `table` must be a hash table with complex keys. `default` will be used as the + default value for the hash table. `key` will be called on the values before + printing (including `default`), and must return a character. + + If `get` is provided, it must be a function of one argument that will be + called on the keys instead of `(gethash ... table default)` to produce the + values. `key` will still be called on the result. + + The y-axis will be printed with higher values at the top, unless `flip-y` is + true. + + " + (multiple-value-bind (left right bottom top) + (bounds (alexandria:hash-table-keys table)) + (incf left (- pad)) + (incf right pad) + (incf bottom (- pad)) + (incf top pad) + (do-irange ((y (if flip-y bottom top) + (if flip-y top bottom))) + (do-irange ((x left right)) + (princ (funcall key (if get + (funcall get (complex x y)) + (gethash (complex x y) table default))))) + (terpri)))) + +(defun esc (string) + (format t "~C~A" #\esc string) + (force-output)) + +(defun clear () + (esc "[2J") + (esc "[;H")) + +(defun green () + (esc "[32m")) + +(defun reset () + (esc "[0m")) + + ;;;; A* Search ---------------------------------------------------------------- (defstruct path state