aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2022/12
diff options
context:
space:
mode:
Diffstat (limited to 'AoC2022/12')
-rw-r--r--AoC2022/12/solver.el3
-rw-r--r--AoC2022/12/solver.lisp57
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)