(ql:quickload '(fiveam uiop))

(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 elevations (data)
  (map 'vector (lambda (chr)
                    (case chr
                      (#\S 0)
                      (#\E 27)
                      (t (- (char-code chr) 96))))
       data))

(defun next-steps (place candidates land paths)
  (let ((elevation (aref land place)))
    (unless (= 27 elevation)
      (mapcan (lambda (option)
                (when (and (not (gethash option paths))
                           (>= (1+ elevation) (aref land option)))
                  (setf (gethash option paths) (cons option (gethash place paths)))
                  (list option)))
              (funcall candidates place)))))

(defun shortest-path (starts candidates land paths)
  (let ((next (mapcan (lambda (place) (next-steps place candidates land paths)) starts)))
    (when next
      (shortest-path next candidates 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)))
         (paths (make-hash-table :test #'eq))
         (finish (position 27 land :test #'eq))
         (starts (loop for i from 0
                       for el across land
                       when (funcall start-p el) collect (progn (setf (gethash i paths) (list i)) i))))
    (shortest-path starts candidates 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)