diff options
Diffstat (limited to 'AoC2022')
| -rw-r--r-- | AoC2022/12/solver.lisp | 33 |
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 |