1 files changed, 104 insertions, 0 deletions
diff --git a/day10.lisp b/day10.lisp
new file mode 100644
index 0000000..cd0402f
--- /dev/null
+++ b/day10.lisp
@@ -0,0 +1,104 @@
+(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