diff options
| -rw-r--r-- | AoC2022/12/solver.el | 3 | ||||
| -rw-r--r-- | AoC2022/12/solver.lisp | 57 |
2 files changed, 59 insertions, 1 deletions
diff --git a/AoC2022/12/solver.el b/AoC2022/12/solver.el index bb5749a..580cc1d 100644 --- a/AoC2022/12/solver.el +++ b/AoC2022/12/solver.el @@ -37,7 +37,8 @@ (ert-deftest test-directions () (should (equal (solver-directions 6 (land--create :width 5 :height 5)) '(7 11 5 1))) - (should (equal (solver-directions 0 (land--create :width 5 :height 5)) '(1 5)))) + (should (equal (solver-directions 0 (land--create :width 5 :height 5)) '(1 5))) + (should (equal (solver-directions 1 (land--create :width 8 :height 5)) '(2 9 0)))) (defun solver-land (data) (cl-map 'string (lambda (chr) diff --git a/AoC2022/12/solver.lisp b/AoC2022/12/solver.lisp new file mode 100644 index 0000000..e00861a --- /dev/null +++ b/AoC2022/12/solver.lisp @@ -0,0 +1,57 @@ +(ql:quickload '(fiveam uiop)) + +(defun possible-directions (width height) + ;; point on grid is p=x+y*width + (lambda (pos) + (let ((x (mod pos width)) + (y (floor pos width))) + (delete nil + (list + (when (< -1 x (1- width)) (1+ pos)) ;; right move + (when (< -1 y (1- height)) (+ pos width)) ;; down move + (when (< 0 x width) (1- pos)) ;; left move + (when (< 0 y height) (- pos width))) ;; up move + :test #'eq)))) + +(defun elevations (data) + (map 'vector (lambda (chr) + (case chr + (#\S 0) + (#\E 27) + (t (- (char-code chr) 96)))) + data)) + +(defun next-steps (place candidates land paths) + (let ((elevation (aref land place))) + (unless (= 27 elevation) + (mapcan (lambda (option) + (when (and (not (gethash option paths)) + (>= (1+ elevation) (aref land option))) + (setf (gethash option paths) (cons option (gethash place paths))) + (list option))) + (funcall candidates place))))) + +(defun shortest-path (starts candidates land paths) + (let ((next (mapcan (lambda (place) (next-steps place candidates land paths)) starts))) + (when next + (shortest-path next candidates land paths)))) + +(defun solver (input-file start-p) + (let* ((data (uiop:read-file-lines input-file)) + (candidates (possible-directions (length (car data)) (length data))) + (land (elevations (apply #'concatenate 'string data))) + (paths (make-hash-table :test #'eq)) + (finish (position 27 land :test #'eq)) + (starts (loop for i from 0 + for el across land + when (funcall start-p el) collect (progn (setf (gethash i paths) (list i)) i)))) + (shortest-path starts candidates land paths) + (1- (length (gethash finish paths))))) + +(fiveam:test solver + (fiveam:is (= 31 (solver "eg-in" (lambda (x) (= x 0))))) + (fiveam:is (= 29 (solver "eg-in" (lambda (x) (<= x 1))))) + (fiveam:is (= 361 (solver "input" (lambda (x) (= x 0))))) + (fiveam:is (= 354 (solver "input" (lambda (x) (<= x 1)))))) + +(fiveam:run-all-tests) |