From c9b54ba38fde531dd16a6ce72e587a8165edda53 Mon Sep 17 00:00:00 2001
From: Oscar Najera <hi@oscarnajera.com>
Date: Sat, 7 Jan 2023 03:03:23 +0100
Subject: Day 18 part 2

---
 AoC2022/18/solver.lisp | 46 +++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 45 insertions(+), 1 deletion(-)

(limited to 'AoC2022/18/solver.lisp')

diff --git a/AoC2022/18/solver.lisp b/AoC2022/18/solver.lisp
index 05c0102..00df016 100644
--- a/AoC2022/18/solver.lisp
+++ b/AoC2022/18/solver.lisp
@@ -15,6 +15,50 @@
             (mapcar #'parse-integer (uiop:split-string l :separator ",")))
           (uiop:read-file-lines filename)))
 
+(defun bounding-corner (points edge)
+  (reduce (lambda (edges point)
+            (mapcar edge edges point))
+          points))
+
+(defun box-surface (min-point max-point)
+  (* 2
+     (loop for (a . rest) on (mapcar #'- max-point min-point)
+           sum (loop for b in rest
+                     sum (* a b)))))
+
+(defconstant +neighbor-dirs+ '((1 0 0) (0 1 0) (0 0 1)
+                               (-1 0 0) (0 -1 0) (0 0 -1)))
+
+(defun spread-steam (next outer-region cubes min-point max-point)
+  (loop for dir in +neighbor-dirs+
+        for nbg = (mapcar #'+ next dir)
+        when (and (every #'<= min-point nbg max-point)
+                  (not (member nbg cubes :test #'equal))
+                  (not (member nbg outer-region :test #'equal)))
+          collect nbg))
+
+(defun fill-outside (queue outer-region cubes min-point max-point)
+  (reduce (lambda (out voxel)
+            (let ((next-queue (spread-steam voxel out cubes min-point max-point)))
+              (fill-outside next-queue
+                            (append next-queue out)
+                            cubes min-point max-point)))
+          queue
+          :initial-value outer-region))
+
+(defun exterior-surface (cubes)
+  (let* ((min (mapcar #'1- (bounding-corner cubes #'min)))
+         (max (mapcar #'1+ (bounding-corner cubes #'max)))
+         (outer (list min)))
+    (- (surface
+        (fill-outside outer outer cubes min max))
+       (box-surface min (mapcar #'1+ max)))))
+
+
 (fiveam:test solutions
+  ;; part 1
   (fiveam:is (= 64 (surface (parse-coords "eg-in"))))
-  (fiveam:is (= 4474 (surface (parse-coords "input")))))
+  (fiveam:is (= 4474 (surface (parse-coords "input"))))
+  ;; part 2
+  (fiveam:is (= 58 (exterior-surface (parse-coords "eg-in"))))
+  (fiveam:is (= 2518 (exterior-surface (parse-coords "input")))))
-- 
cgit v1.2.3