(ql:quickload '(fiveam uiop))

(defstruct land
  elevation
  neighbors)

(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 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 (map 'vector #'elevation (apply #'concatenate 'string data))
               :neighbors (possible-directions (length (car data)) (length data)))))

(defun next-steps (current land paths)
  (flet ((appropriate (next)
           (and (not (gethash next paths)) ;; not visited
                (>= 1 (- (aref (land-elevation land) next)
                         (aref (land-elevation land) current)))
                (setf (gethash next paths) (cons next (gethash current paths))))))
    (remove-if-not #'appropriate (funcall (land-neighbors land) current))))

(defun shortest-path (starts land paths)
  (unless (null starts)
    (shortest-path (append (cdr starts) (next-steps (car starts) land paths))
                   land paths)))

(defun solver (input-file start-p)
  (let* ((land (land input-file))
         (paths (make-hash-table :test #'eq))
         (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)
                         do (setf (gethash i paths) (list i))
                         and collect i)))
    (shortest-path starts 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))))))