(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))))