aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2022
diff options
context:
space:
mode:
Diffstat (limited to 'AoC2022')
-rw-r--r--AoC2022/12/solver.lisp33
1 files changed, 20 insertions, 13 deletions
diff --git a/AoC2022/12/solver.lisp b/AoC2022/12/solver.lisp
index e00861a..b2a0752 100644
--- a/AoC2022/12/solver.lisp
+++ b/AoC2022/12/solver.lisp
@@ -1,5 +1,9 @@
(ql:quickload '(fiveam uiop))
+(defstruct land
+ elevation
+ neighbors)
+
(defun possible-directions (width height)
;; point on grid is p=x+y*width
(lambda (pos)
@@ -21,31 +25,34 @@
(t (- (char-code chr) 96))))
data))
-(defun next-steps (place candidates land paths)
- (let ((elevation (aref land place)))
+(defun land (input-file)
+ (let ((data (uiop:read-file-lines input-file)))
+ (make-land :elevation (elevations (apply #'concatenate 'string data))
+ :neighbors (possible-directions (length (car data)) (length data)))))
+
+(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 option)))
+ (>= (1+ elevation) (aref (land-elevation land) option)))
(setf (gethash option paths) (cons option (gethash place paths)))
(list option)))
- (funcall candidates place)))))
+ (funcall (land-neighbors land) place)))))
-(defun shortest-path (starts candidates land paths)
- (let ((next (mapcan (lambda (place) (next-steps place candidates land paths)) starts)))
+(defun shortest-path (starts land paths)
+ (let ((next (mapcan (lambda (place) (next-steps place land paths)) starts)))
(when next
- (shortest-path next candidates land paths))))
+ (shortest-path next 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)))
+ (let* ((land (land input-file))
(paths (make-hash-table :test #'eq))
- (finish (position 27 land :test #'eq))
+ (finish (position 27 (land-elevation land) :test #'eq))
(starts (loop for i from 0
- for el across land
+ for el across (land-elevation land)
when (funcall start-p el) collect (progn (setf (gethash i paths) (list i)) i))))
- (shortest-path starts candidates land paths)
+ (shortest-path starts land paths)
(1- (length (gethash finish paths)))))
(fiveam:test solver