aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--AoC2022/07/eg-in23
-rw-r--r--AoC2022/07/solver.lisp71
2 files changed, 53 insertions, 41 deletions
diff --git a/AoC2022/07/eg-in b/AoC2022/07/eg-in
new file mode 100644
index 0000000..09a921e
--- /dev/null
+++ b/AoC2022/07/eg-in
@@ -0,0 +1,23 @@
+$ cd /
+$ ls
+dir a
+14848514 b.txt
+8504156 c.dat
+dir d
+$ cd a
+$ ls
+dir e
+29116 f
+2557 g
+62596 h.lst
+$ cd e
+$ ls
+584 i
+$ cd ..
+$ cd ..
+$ cd d
+$ ls
+4060174 j
+8033020 d.log
+5626152 d.ext
+7214296 k
diff --git a/AoC2022/07/solver.lisp b/AoC2022/07/solver.lisp
index a6c99ae..497b6f6 100644
--- a/AoC2022/07/solver.lisp
+++ b/AoC2022/07/solver.lisp
@@ -8,58 +8,47 @@
(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)))))))
+ ((ppcre:register-groups-bind ((#'parse-integer size) name) ("^(\\d+) ([.\\w]+)" item)
+ (cons name 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))))))
+ (let (dir-list)
+ (labels ((combiner (tri)
+ (push (cons (car tri) (adder tri)) dir-list)
+ (mapc (lambda (item)
+ (unless (numberp (cdr item)) ;; skips files
+ (combiner item)))
+ (cdr tri)))
+ (adder (tri)
+ (reduce (lambda (acc item)
+ (+ acc (if (numberp (cdr item))
+ (cdr item)
+ (adder item))))
+ (cdr tri) :initial-value 0)))
+ (combiner tree))
+ dir-list))
+
+(defun flat-dir-size (filename)
+ (with-open-file (in filename)
+ (aggregate-size
+ (parse-to-tree in))))
(defun addr-small-dirs (dir-sizes small-limit)
- (loop for (_name size) on dir-sizes by #'cddr
+ (loop for (_name . size) in dir-sizes
when (< size small-limit)
sum size))
(defun dir-to-del (dir-sizes total-disk needed-disk)
- (let* ((free-disk (- total-disk (cadr dir-sizes)))
+ (let* ((free-disk (- total-disk (cdar (last dir-sizes))))
(to-free (- needed-disk free-disk)))
- (loop for (_ size) on dir-sizes by #'cddr
+ (loop for (_name . size) in dir-sizes
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:is (= 95437 (addr-small-dirs (flat-dir-size "eg-in") 100000)))
+ (fiveam:is (= 1845346
+ (addr-small-dirs (flat-dir-size "input") 100000)))
+ (fiveam:is (= 3636703
+ (dir-to-del (flat-dir-size "input") 70000000 30000000))))