(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 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)
      (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)))
    (when next
      (shortest-path next 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))))))

(fiveam:run-all-tests)