#!/usr/local/bin/chicken-csi -ss
(import srfi-69
        (chicken io))

(define (filter pred lst)
  (cond ((null? lst) '())
        ((pred (car lst))
         (cons (car lst) (filter pred (cdr lst))))
        (else (filter pred (cdr lst)))))

(define (lvl c)
  (cond ((equal? c #\S) 0)
        ((equal? c #\E) 25)
        (else (- (char->integer c) 97))))

(define (get grid r c)
  (vector-ref (vector-ref grid r) c))

(define (find grid needle)
  (let ((n (vector-length grid))
        (m (vector-length (vector-ref grid 0))))
    (let iloop ((i 0))
      (if (>= i n)
          #f
          (let jloop ((j 0))
            (if (>= j m)
                (iloop (add1 i))
                (let ((x (get grid i j)))
                  (if (equal? x needle)
                      (list i j)
                      (jloop (add1 j))))))))))

(define (make-grid lines transform)
  (list->vector (map (lambda (l) (list->vector (map transform (string->list l))))
               lines)))

(define (ident x) x)


(define (neigh grid pos dir)
  (define (in-bounds? pt)
    (let ((n (vector-length grid))
          (m (vector-length (vector-ref grid 0))))
      (and (>= (cadr pt) 0)
           (<  (cadr pt) n)
           (>= (caddr pt) 0)
           (<  (caddr pt) m))))
  (define (in-reach? pt)
    (let* ((d (car pos))
           (i (cadr pos))
           (j (caddr pos))
           (i2 (cadr pt))
           (j2 (caddr pt))
           (l1 (get grid i j))
           (l2 (get grid i2 j2)))
      (if (eq? dir 'up)
          (and (<= l2 (add1 l1)))
          (and (>= (add1 l2) l1)))))
  (let* ((d (car pos))
         (i (cadr pos))
         (j (caddr pos)))
    (filter (lambda (pt) (and (in-bounds? pt) (in-reach? pt)))
            `((,(add1 d) ,(add1 i) ,j)
              (,(add1 d) ,(sub1 i) ,j)
              (,(add1 d) ,i ,(add1 j))
              (,(add1 d) ,i ,(sub1 j))))))
    

(define (dist grid start goal)
  ;; BFS to find the goal, each item is (D i j) where D is depth
  (let ((seen (make-hash-table)))
    (let loop ((Q (list (cons 0 start))))
      (if (null? Q)
          #f
          (let ((pos (car Q)))
            (hash-table-set! seen (cdr pos) 'seen)
            (if (equal? (cdr pos) goal)
                (car pos)
                (let ((neighs (filter (lambda (p) (not (hash-table-exists? seen (cdr p))))
                                      (neigh grid pos 'up))))
                  (for-each (lambda (p) (hash-table-set! seen (cdr p) 1)) neighs)
                  (loop (append (cdr Q) neighs)))))))))

;; Part 2 is a simple flip of the search: don't search for one goal loc
;; search starting at E and until depth 0 (with inverted 'in-reach?)
(define (dist-down grid start)
  ;; BFS to find the goal, each item is (D i j) where D is depth
  (let ((seen (make-hash-table)))
    (let loop ((Q (list (cons 0 start))))
      (if (null? Q)
          #f
          (let ((pos (car Q)))
            (hash-table-set! seen (cdr pos) 'seen)
            (if (equal? (get grid (cadr pos) (caddr pos)) 0)
                (car pos)
                (let ((neighs (filter (lambda (p) (not (hash-table-exists? seen (cdr p))))
                                      (neigh grid pos 'down))))
                  (for-each (lambda (p) (hash-table-set! seen (cdr p) 1)) neighs)
                  (loop (append (cdr Q) neighs)))))))))


(define (main args)
  (let* ((lines (read-lines))
         (cgrid (make-grid lines ident))
         (lgrid (make-grid lines lvl))
         (start (find cgrid #\S))
         (goal (find cgrid #\E)))
    (print (dist lgrid start goal))
    (print (dist-down lgrid goal))))

; for repl
(define ln '("Sabqponm"
             "abcryxxl"
             "accszExk"
             "acctuvwj"
             "abdefghi"))