day-14.lisp (7119B)
1 (defpackage #:aoc/day-14 2 (:use #:cl #:aoc/utils) 3 (:export 4 #:parse-robots 5 #:task-1 6 #:day-14)) 7 (in-package #:aoc/day-14) 8 9 (defparameter *tree* '((0 . 0) (1 . 0) (2 . 0) (3 . 0) (4 . 0) (5 . 0) (6 . 0) (7 . 0) (8 . 0) 10 (9 . 0) (10 . 0) (11 . 0) (12 . 0) (13 . 0) (14 . 0) (15 . 0) (16 . 0) 11 (17 . 0) (18 . 0) (19 . 0) (20 . 0) (21 . 0) (22 . 0) (23 . 0) (24 . 0) 12 (25 . 0) (26 . 0) (27 . 0) (28 . 0) (29 . 0) (30 . 0) (0 . 1) (30 . 1) (0 . 2) 13 (30 . 2) (0 . 3) (30 . 3) (0 . 4) (30 . 4) (0 . 5) (15 . 5) (30 . 5) (0 . 6) 14 (14 . 6) (15 . 6) (16 . 6) (30 . 6) (0 . 7) (13 . 7) (14 . 7) (15 . 7) 15 (16 . 7) (17 . 7) (30 . 7) (0 . 8) (12 . 8) (13 . 8) (14 . 8) (15 . 8) 16 (16 . 8) (17 . 8) (18 . 8) (30 . 8) (0 . 9) (11 . 9) (12 . 9) (13 . 9) 17 (14 . 9) (15 . 9) (16 . 9) (17 . 9) (18 . 9) (19 . 9) (30 . 9) (0 . 10) 18 (13 . 10) (14 . 10) (15 . 10) (16 . 10) (17 . 10) (30 . 10) (0 . 11) (12 . 11) 19 (13 . 11) (14 . 11) (15 . 11) (16 . 11) (17 . 11) (18 . 11) (30 . 11) (0 . 12) 20 (11 . 12) (12 . 12) (13 . 12) (14 . 12) (15 . 12) (16 . 12) (17 . 12) 21 (18 . 12) (19 . 12) (30 . 12) (0 . 13) (10 . 13) (11 . 13) (12 . 13) (13 . 13) 22 (14 . 13) (15 . 13) (16 . 13) (17 . 13) (18 . 13) (19 . 13) (20 . 13) 23 (30 . 13) (0 . 14) (9 . 14) (10 . 14) (11 . 14) (12 . 14) (13 . 14) (14 . 14) 24 (15 . 14) (16 . 14) (17 . 14) (18 . 14) (19 . 14) (20 . 14) (21 . 14) 25 (30 . 14) (0 . 15) (11 . 15) (12 . 15) (13 . 15) (14 . 15) (15 . 15) (16 . 15) 26 (17 . 15) (18 . 15) (19 . 15) (30 . 15) (0 . 16) (10 . 16) (11 . 16) (12 . 16) 27 (13 . 16) (14 . 16) (15 . 16) (16 . 16) (17 . 16) (18 . 16) (19 . 16) 28 (20 . 16) (30 . 16) (0 . 17) (9 . 17) (10 . 17) (11 . 17) (12 . 17) (13 . 17) 29 (14 . 17) (15 . 17) (16 . 17) (17 . 17) (18 . 17) (19 . 17) (20 . 17) 30 (21 . 17) (30 . 17) (0 . 18) (8 . 18) (9 . 18) (10 . 18) (11 . 18) (12 . 18) 31 (13 . 18) (14 . 18) (15 . 18) (16 . 18) (17 . 18) (18 . 18) (19 . 18) 32 (20 . 18) (21 . 18) (22 . 18) (30 . 18) (0 . 19) (7 . 19) (8 . 19) (9 . 19) 33 (10 . 19) (11 . 19) (12 . 19) (13 . 19) (14 . 19) (15 . 19) (16 . 19) 34 (17 . 19) (18 . 19) (19 . 19) (20 . 19) (21 . 19) (22 . 19) (23 . 19) 35 (30 . 19) (0 . 20) (9 . 20) (10 . 20) (11 . 20) (12 . 20) (13 . 20) (14 . 20) 36 (15 . 20) (16 . 20) (17 . 20) (18 . 20) (19 . 20) (20 . 20) (21 . 20) 37 (30 . 20) (0 . 21) (8 . 21) (9 . 21) (10 . 21) (11 . 21) (12 . 21) (13 . 21) 38 (14 . 21) (15 . 21) (16 . 21) (17 . 21) (18 . 21) (19 . 21) (20 . 21) 39 (21 . 21) (22 . 21) (30 . 21) (0 . 22) (7 . 22) (8 . 22) (9 . 22) (10 . 22) 40 (11 . 22) (12 . 22) (13 . 22) (14 . 22) (15 . 22) (16 . 22) (17 . 22) 41 (18 . 22) (19 . 22) (20 . 22) (21 . 22) (22 . 22) (23 . 22) (30 . 22) (0 . 23) 42 (6 . 23) (7 . 23) (8 . 23) (9 . 23) (10 . 23) (11 . 23) (12 . 23) (13 . 23) 43 (14 . 23) (15 . 23) (16 . 23) (17 . 23) (18 . 23) (19 . 23) (20 . 23) 44 (21 . 23) (22 . 23) (23 . 23) (24 . 23) (30 . 23) (0 . 24) (5 . 24) (6 . 24) 45 (7 . 24) (8 . 24) (9 . 24) (10 . 24) (11 . 24) (12 . 24) (13 . 24) (14 . 24) 46 (15 . 24) (16 . 24) (17 . 24) (18 . 24) (19 . 24) (20 . 24) (21 . 24) 47 (22 . 24) (23 . 24) (24 . 24) (25 . 24) (30 . 24) (0 . 25) (14 . 25) (15 . 25) 48 (16 . 25) (30 . 25) (0 . 26) (14 . 26) (15 . 26) (16 . 26) (30 . 26) (0 . 27) 49 (14 . 27) (15 . 27) (16 . 27) (30 . 27) (0 . 28) (30 . 28) (0 . 29) (30 . 29) 50 (0 . 30) (30 . 30) (0 . 31) (30 . 31) (0 . 32) (1 . 32) (2 . 32) (3 . 32) 51 (4 . 32) (5 . 32) (6 . 32) (7 . 32) (8 . 32) (9 . 32) (10 . 32) (11 . 32) 52 (12 . 32) (13 . 32) (14 . 32) (15 . 32) (16 . 32) (17 . 32) (18 . 32) 53 (19 . 32) (20 . 32) (21 . 32) (22 . 32) (23 . 32) (24 . 32) (25 . 32) 54 (26 . 32) (27 . 32) (28 . 32) (29 . 32) (30 . 32))) 55 (defparameter *tree-width* 56 (1+ (apply #'max (mapcar #'point-x *tree*)))) 57 (defparameter *tree-height* 58 (1+ (apply #'max (mapcar #'point-y *tree*)))) 59 60 (defun parse-robots (input) 61 (loop for line = (read-line input nil) 62 until (null line) 63 collect (parse-robot line))) 64 65 (defun parse-robot (line) 66 (let* ((pspace (position #\Space line)) 67 (p (uiop:split-string (subseq line 2 pspace) :separator '(#\,))) 68 (v (uiop:split-string (subseq line (+ pspace 3)) :separator '(#\,))) 69 (p (mapcar #'parse-integer p)) 70 (v (mapcar #'parse-integer v))) 71 (list (cons (first p) (second p)) 72 (cons (first v) (second v))))) 73 74 (declaim (inline robot-after)) 75 76 (defun robot-after (robot seconds bounds) 77 (point-mod (point+ (first robot) 78 (point* (second robot) (cons seconds seconds))) 79 bounds)) 80 81 (defun task-1 (robots width height) 82 (loop with bounds = (cons width height) 83 with hmiddle = (floor width 2) 84 with vmiddle = (floor height 2) 85 with quadrants = (list 0 0 0 0) 86 for robot in robots 87 for new-pos = (robot-after robot 100 bounds) 88 for x = (point-x new-pos) 89 for y = (point-y new-pos) 90 unless (or (= x hmiddle) (= y vmiddle)) 91 do (incf (nth (+ (* (round x width) 2) 92 (round y height)) 93 quadrants)) 94 finally (return (apply #'* quadrants)))) 95 96 (defun tree-matches-p (map offset) 97 (loop for pos in *tree* 98 for tpos = (point+ pos offset) 99 unless (gethash tpos map) 100 do (return nil) 101 finally (return t))) 102 103 (defun contains-tree-p (map width height) 104 (loop for y from 0 below (- height *tree-height*) 105 thereis (loop for x from 0 below (- width *tree-width*) 106 thereis (tree-matches-p map (cons x y))))) 107 108 (defun task-2 (robots width height) 109 (loop with bounds = (cons width height) 110 for seconds from 1 111 for map = (make-hash-table :test #'equal) 112 when (and (loop for robot in robots 113 for new-pos = (robot-after robot seconds bounds) 114 when (gethash new-pos map) 115 do (return nil) 116 do (setf (gethash new-pos map) t) 117 finally (return t)) 118 (contains-tree-p map width height)) 119 do (return seconds))) 120 121 (defun day-14 (input) 122 (let ((robots (parse-robots input))) 123 (values 124 (task-1 robots 101 103) 125 (task-2 robots 101 103))))