aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2022/12/solver.lisp
diff options
context:
space:
mode:
Diffstat (limited to 'AoC2022/12/solver.lisp')
-rw-r--r--AoC2022/12/solver.lisp32
1 files changed, 17 insertions, 15 deletions
diff --git a/AoC2022/12/solver.lisp b/AoC2022/12/solver.lisp
index b2a0752..e0320c3 100644
--- a/AoC2022/12/solver.lisp
+++ b/AoC2022/12/solver.lisp
@@ -17,28 +17,28 @@
(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 elevation (chr)
+ (case chr
+ (#\S 0)
+ (#\E 27)
+ (t (- (char-code chr) 96))))
(defun land (input-file)
(let ((data (uiop:read-file-lines input-file)))
- (make-land :elevation (elevations (apply #'concatenate 'string data))
+ (make-land :elevation (map 'vector #'elevation (apply #'concatenate 'string data))
:neighbors (possible-directions (length (car data)) (length data)))))
+(defun appropriate (place elevation land paths)
+ (and (not (gethash place paths)) ;; not visited
+ (>= elevation (aref (land-elevation land) place))))
+
(defun next-steps (place land paths)
(let ((elevation (aref (land-elevation land) place)))
(unless (= 27 elevation)
- (mapcan (lambda (option)
- (when (and (not (gethash option paths))
- (>= (1+ elevation) (aref (land-elevation land) option)))
- (setf (gethash option paths) (cons option (gethash place paths)))
- (list option)))
- (funcall (land-neighbors land) place)))))
+ (loop :for option :in (funcall (land-neighbors land) place)
+ :when (appropriate option (1+ elevation) land paths)
+ :do (setf (gethash option paths) (cons option (gethash place paths)))
+ :and collect option))))
(defun shortest-path (starts land paths)
(let ((next (mapcan (lambda (place) (next-steps place land paths)) starts)))
@@ -51,7 +51,9 @@
(finish (position 27 (land-elevation land) :test #'eq))
(starts (loop for i from 0
for el across (land-elevation land)
- when (funcall start-p el) collect (progn (setf (gethash i paths) (list i)) i))))
+ when (funcall start-p el)
+ do (setf (gethash i paths) (list i))
+ and collect i)))
(shortest-path starts land paths)
(1- (length (gethash finish paths)))))