diff options
| -rw-r--r-- | 2022/7.lisp | 167 |
1 files changed, 121 insertions, 46 deletions
diff --git a/2022/7.lisp b/2022/7.lisp index 60c85a6..a9bb0ff 100644 --- a/2022/7.lisp +++ b/2022/7.lisp @@ -26,7 +26,13 @@ :initarg :parent :accessor parent :type dir - :documentation "Parent directory.")) + :documentation "Parent directory.") + (size + :initarg :size + :initform 0 + :accessor size + :type fixnum + :documentation "Directory size.")) (:documentation "Directory class.")) (defclass file () @@ -44,75 +50,144 @@ :documentation "File size.")) (:documentation "Representation of a file")) +(defparameter *max-size* 70000000) +(defparameter *needed-space* 30000000) +(defvar *part1-test* "$ 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") + (defmethod find-child ((dir dir) child) (declare (type string child)) (find child (children dir) - :test (lambda (dir ch) + :test (lambda (ch dir) (string= ch (name dir))))) +;; (defmethod print-object ((dir dir) stream) +;; (format stream "~a~%~{~T~a~}" (name dir) (children dir))) (defmethod print-object ((dir dir) stream) - (format stream "~a~%~{~T~a~}" (name dir) (children dir))) + (format stream "#<DIR ~a>" (name dir))) (defmethod print-object ((file file) stream) - (format stream "~a~T~a~%" (name file) (size file))) - -(defvar *tree* - (make-instance 'dir :name "/") - "Root of the directory tree.") - -(defun reset () - (setf *tree* (make-instance 'dir :name "/"))) + (format stream "#<FILE ~a>" (name file))) -(defun parse-command (line) +(defun parse-command (line last-dir tree) "Parse lines that start with '$', there are three possible outcomes: cd [directory] -> Return an object of type dir named after DIRECTORY -cd .. -> Return the symbol PARENT -ls -> Return the symbol LS" +cd .. -> Return LAST-DIR's parent +ls -> Return LAST-DIR" (declare (type string line)) - (let* ((line* (subseq line 2)) ; remove "$ " - (words (words line*)) - (command (car words)) - (dir (second words))) - (if (and (string= command "cd")) - (if (string= dir "..") - 'parent - (make-instance 'dir :name dir)) - 'ls))) - -(defun parse-directory-children (line) + (let ((line* (subseq line 2))) ; remove "$ " + (destructuring-bind (command &optional dir) (words line*) + (if (string= command "cd") + (if (string= dir "..") + (parent last-dir) + (if (string= dir "/") + tree + (find-child last-dir dir))) + last-dir)))) + +(defun parse-directory-children (line last-dir) "Parse LINE as output to the ls command. It may return objects of type DIR or FILE." (declare (type string line)) - (let ((words (words line))) - (if (string= (first words) "dir") - (make-instance 'dir :name (second words)) - (make-instance 'file :name (second words))))) + (destructuring-bind (type name) (words line) + (if (string= type "dir") + (make-instance 'dir :name name :parent last-dir) + (make-instance 'file :name name :size (parse-integer type))))) ;; Does not work -(defun parse-line (line last-dir) +(defun parse-line (line last-dir tree) "Parse LINE, executing commands or adding children to LAST-DIR. Return the next directory (that may be changed by a 'cd' command)." (declare (type string line) (type dir last-dir)) (if (char= (aref line 0) #\$) - (let ((dir (parse-command line))) - (case dir - (parent - (parent last-dir)) - (ls - last-dir) - (otherwise dir))) - (let ((child (parse-directory-children line))) - (when (eq (type-of child) 'dir) - (setf (parent child) last-dir)) - (appendf (children last-dir) - (list child)) + (parse-command line last-dir tree) + (let ((child (parse-directory-children line last-dir))) + (push child (children last-dir)) last-dir))) (defun parse-input (&optional (stream *standard-input*)) "Parse all of the lines in STREAM." - (let ((last-dir *tree*)) + (let* ((tree (make-instance 'dir :name "/")) + (last-dir tree)) (loop :for line := (read-line stream nil) - :do (setf last-dir (parse-line line last-dir))))) + :while (not (null line)) + :do (setf last-dir (parse-line line last-dir tree))) + tree)) + +(defun part1% (stream) + (let ((tree (parse-input stream)) + (result nil)) + (labels ((mapdir (f) + (mapcar (lambda (c) + (typecase c + (dir (incf (size f) (mapdir c))) + (file (incf (size f) (size c))))) + (children f)) + (when (< (size f) 100000) + (push f result)) + (size f))) + (mapdir tree) + (loop :for dir :in result + :sum (size dir))))) + +(defun part1-test () + (with-input-from-string (stream *part1-test*) + (part1% stream))) (defun part1 () (with-open-file (stream #p"input-7") - (parse-input stream) - *tree*)) + (part1% stream))) + +(defun part2% (stream) + (let ((tree (parse-input stream))) + (labels ((mapsize (dir) + (mapcar (lambda (c) + (typecase c + (dir (incf (size dir) (mapsize c))) + (file (incf (size dir) (size c))))) + (children dir)) + (size dir)) + (filter-dirs (dir) + (let ((result nil)) + (loop :for c :in (children dir) + :when (eq (type-of c) 'dir) + :do (progn + (push (size c) result) + (alexandria:appendf result (filter-dirs c)))) + result))) + (mapsize tree) + (let* ((free-space (- *max-size* (size tree))) + (space-to-free (- *needed-space* free-space)) + (sizes (sort (filter-dirs tree) #'>)) + (last-size 0)) + (loop :for size :in sizes + :when (< size space-to-free) + :return last-size + :do (setf last-size size)))))) + +(defun part2-test () + (with-input-from-string (stream *part1-test*) + (part2% stream))) + +(defun part2 () + (with-open-file (stream #p"input-7") + (part2% stream))) |