[AoC2022] 07 CL

1 files changed, 65 insertions, 0 deletions

diff --git a/AoC2022/07/solver.lisp b/AoC2022/07/solver.lisp
new file mode 100644
index 0000000..f0f5a93
--- /dev/null
+++ b/AoC2022/07/solver.lisp
@@ -0,0 +1,65 @@
+(ql:quickload '(:fiveam :cl-ppcre))
+
+(defun parse-to-tree (stream)
+  (labels ((scan ()
+             (loop for item = (read-line stream nil nil)
+                   while (and item (not (equal "$ cd .." item)))
+                   when (parse item) collect it))
+           (parse (item)
+             (cond
+               ((ppcre:register-groups-bind (dir) ("\\$ cd (\\w+|/)" item) (cons dir (scan))))
+               ((ppcre:register-groups-bind (size name) ("^(\\d+) (\\w+)" item)
+                  (cons name (parse-integer size)))))))
+    (car (scan))))
+
+(defun aggregate-size (tree)
+  (labels ((combiner (tri)
+             (list (car tri)
+                   (adder tri)
+                   (reduce (lambda (acc item)
+                             (if (numberp (cdr item)) ;; skips files
+                                 acc
+                                 (cons (combiner item) acc)))
+                           (cdr tri) :initial-value nil)))
+           (adder (tri)
+             (reduce (lambda (acc item)
+                       (+ acc (if (numberp (cdr item))
+                                  (cdr item)
+                                  (adder item))))
+                     (cdr tri) :initial-value 0)))
+    (combiner tree)))
+
+(defun flat-dir-size ()
+  (with-open-file (in "input")
+    (delete nil
+            (flatten-tree
+             (aggregate-size
+              (parse-to-tree in)))
+            :test #'eq) ))
+
+(defun flatten-tree (tree)
+  (cond
+    ((null tree) nil)
+    ((consp (car tree)) (nconc (flatten-tree (car tree))
+                               (flatten-tree (cdr tree))))
+    (t (cons (car tree) (flatten-tree (cdr tree))))))
+
+(defun addr-small-dirs (dir-sizes small-limit)
+  (loop for (_name size) on dir-sizes by #'cddr
+        when (< size small-limit)
+          sum size))
+
+(defun dir-to-del (dir-sizes total-disk needed-disk)
+  (let* ((free-disk (- total-disk (cadr dir-sizes)))
+         (to-free (- needed-disk free-disk)))
+    (loop for (_ size) on dir-sizes by #'cddr
+          when (> size to-free)
+            minimizing size)))
+
+(fiveam:test results
+             (fiveam:is (= 1845346
+                           (addr-small-dirs (flat-dir-size) 100000)))
+             (fiveam:is (= 3636703
+                           (dir-to-del (flat-dir-size) 70000000 30000000))))
+
+(fiveam:run-all-tests)