Solve in LISP

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)