(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 ((#'parse-integer size) name) ("^(\\d+) ([.\\w]+)" item)
                  (cons name size))))))
    (car (scan))))

(defun aggregate-size (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) in dir-sizes
        when (< size small-limit)
          sum size))

(defun dir-to-del (dir-sizes total-disk needed-disk)
  (let* ((free-disk (- total-disk (cdar (last dir-sizes))))
         (to-free (- needed-disk free-disk)))
    (loop for (_name . size) in dir-sizes
          when (> size to-free)
            minimizing size)))

(fiveam:test results
  (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))))