aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--AoC2022/07/makefile13
-rw-r--r--AoC2022/07/solver.lisp65
2 files changed, 78 insertions, 0 deletions
diff --git a/AoC2022/07/makefile b/AoC2022/07/makefile
new file mode 100644
index 0000000..73929a6
--- /dev/null
+++ b/AoC2022/07/makefile
@@ -0,0 +1,13 @@
+##
+# run solutions
+#
+# @file
+# @version 0.1
+
+
+
+# end
+
+run:
+ emacs -batch -l ert -l solver.el -f ert-run-tests-batch-and-exit
+ sbcl --load ~/.sbclrc --script solver.lisp
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)