Add solution for problem 7HEADmaster

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