(defstruct grid data dim0 dim1)
(defstruct point i j)
(defstruct pdir point dir)

(defun parse-grid (filespec)
  (with-open-file (stream filespec)
    (let ((lines (loop for line = (read-line stream nil)
                       while line
                       collect line)))
      (make-grid :data (apply #'concatenate 'string lines)
                 :dim0 (length lines)
                 :dim1 (length (first lines))))))

(defun grid-character (grid i j)
  (aref (grid-data grid) (+ (* i (grid-dim1 grid)) j)))

(defun grid-character-update (grid i j item)
  (setf (aref (grid-data grid) (+ (* i (grid-dim1 grid)) j)) item))

(defun grid-point (grid item)
  (let ((pos (position item (grid-data grid))))
    (when pos
      (multiple-value-bind (i j) (truncate pos (grid-dim1 grid))
        (make-point :i i :j j)))))

(defun point-in-grid (point grid)
  (and (and (>= (point-i point) 0) (< (point-i point) (grid-dim0 grid)))
       (and (>= (point-j point) 0) (< (point-j point) (grid-dim1 grid)))))

(defun next-pdir (grid pdir)
  (let* ((i   (point-i (pdir-point pdir)))
         (j   (point-j (pdir-point pdir)))
         (dir (pdir-dir pdir))
         (next-point (cond ((= dir 0) (make-point :i (1- i) :j j))   ; up
                           ((= dir 1) (make-point :i i :j (1+ j)))   ; right
                           ((= dir 2) (make-point :i (1+ i) :j j))   ; down
                           ((= dir 3) (make-point :i i :j (1- j))))) ; left
         (i (point-i next-point))
         (j (point-j next-point)))
    (when (point-in-grid next-point grid)
      (let* ((next-char (grid-character grid i j))
             (next-dir (cond ((equal next-char #\S) dir)
                             ((= dir 0) (cond ((equal next-char #\7) 3)
                                              ((equal next-char #\F) 1)
                                              ((equal next-char #\|) dir)))
                             ((= dir 1) (cond ((equal next-char #\7) 2)
                                              ((equal next-char #\J) 0)
                                              ((equal next-char #\-) dir)))
                             ((= dir 2) (cond ((equal next-char #\L) 1)
                                              ((equal next-char #\J) 3)
                                              ((equal next-char #\|) dir)))
                             ((= dir 3) (cond ((equal next-char #\L) 0)
                                              ((equal next-char #\F) 2)
                                              ((equal next-char #\-) dir))))))
        (when next-dir
          (make-pdir :point next-point :dir next-dir))))))

(defun grid-loop (grid start pdir &optional (count 0) visited)
  (if (and (equalp start (pdir-point pdir)) (/= count 0))
      visited
      (let* ((visited (cons pdir visited))
             (pdir (next-pdir grid pdir)))
        (when pdir
          ;; Updating the grid for a quick visited check
          (let* ((i (point-i (pdir-point pdir)))
                 (j (point-j (pdir-point pdir)))
                 (c (grid-character grid i j)))
            (unless (equal c #\S)
              (grid-character-update grid i j #\.)))
          (grid-loop grid start pdir (1+ count) visited)))))

(defun solve1 (filespec)
  (let* ((grid (parse-grid filespec))
         (start (grid-point grid #\S))
         (positions (or (grid-loop grid start (make-pdir :point start :dir 0))
                        (grid-loop grid start (make-pdir :point start :dir 1))
                        (grid-loop grid start (make-pdir :point start :dir 2))
                        (grid-loop grid start (make-pdir :point start :dir 3)))))
    (ash (length positions) -1)))

(defun solve2 (filespec)
  (let* ((grid (parse-grid filespec))
         (start (grid-point grid #\S))
         (positions (or (grid-loop grid start (make-pdir :point start :dir 0))
                        (grid-loop grid start (make-pdir :point start :dir 1))
                        (grid-loop grid start (make-pdir :point start :dir 2))
                        (grid-loop grid start (make-pdir :point start :dir 3)))))
    (let* ((area (loop for cur in (append (cdr positions) (list (car positions)))
                       for prv in positions
                       as curi = (point-i (pdir-point cur))
                       as curj = (point-j (pdir-point cur))
                       as prvi = (point-i (pdir-point prv))
                       as prvj = (point-j (pdir-point prv))
                       sum (- (* prvi curj) (* prvj curi))))
           (iarea (- (abs area) (length positions))))
      (1+ (ash iarea -1)))))

(print (solve1 "data/10/example1.txt"))  ;; 4
(print (solve1 "data/10/example2.txt"))  ;; 8
(print (solve1 "data/10/input.txt"))     ;; 6690
(print (solve2 "data/10/example3.txt"))  ;; 4
(print (solve2 "data/10/example4.txt"))  ;; 8
(print (solve2 "data/10/example5.txt"))  ;; 10
(print (solve2 "data/10/input.txt"))     ;; 525