diff options
Diffstat (limited to 'AoC2022/07')
| -rw-r--r-- | AoC2022/07/eg-in | 23 | ||||
| -rw-r--r-- | AoC2022/07/solver.lisp | 71 |
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)))) |