adventofcode2022

My solutions for Advent of Code 2022
Log | Files | Refs

day07.lisp (3020B)

      1 (defpackage #:adventofcode2022/day07
      2   (:use #:cl #:adventofcode2022))
      3 (in-package #:adventofcode2022/day07)
      4 
      5 (defgeneric size (entry))
      6 
      7 (defclass fs-entry ()
      8   ((name :initarg :name
      9          :initform (error "Please specify a name")
     10          :reader name)))
     11 
     12 (defmethod dir-p ((entry fs-entry))
     13   nil)
     14 
     15 (defclass fs-directory (fs-entry)
     16   ((parent :initarg :parent
     17            :reader parent)
     18    (children :accessor children
     19              :initform nil)
     20    (size-cache :accessor size-cache
     21                :initform nil)))
     22 
     23 (defun make-fs-directory (name &optional parent)
     24   (make-instance 'fs-directory
     25                  :name name
     26                  :parent parent))
     27 
     28 (defmethod dir-p ((dir fs-directory))
     29   t)
     30 
     31 (defmethod size ((dir fs-directory))
     32   (if (not (null (size-cache dir)))
     33       (size-cache dir)
     34       (setf (size-cache dir)
     35             (loop for child in (children dir)
     36                   sum (size child)))))
     37 
     38 (defmethod add-child ((dir fs-directory) (child fs-entry))
     39   (push child (children dir)))
     40 
     41 (defmethod get-child ((dir fs-directory) child-name)
     42   (if (string= child-name "..")
     43       (parent dir)
     44       (loop for child in (children dir)
     45             when (string= (name child) child-name)
     46               return child)))
     47 
     48 (defclass fs-file (fs-entry)
     49   ((size :initarg :size
     50          :accessor size)))
     51 
     52 (defun make-fs-file (name size)
     53   (make-instance 'fs-file :name name :size size))
     54 
     55 (defun build-fs-tree (inputs)
     56   (loop with root = (make-fs-directory "")
     57         with current-dir = root
     58         for line in inputs
     59         for parts = (str:split " " line)
     60         do (if (string= (car parts) "$")
     61                (when (string= (cadr parts) "cd")
     62                  (if (string= (caddr parts) "/")
     63                      (setf current-dir root)
     64                      (setf current-dir (get-child current-dir (caddr parts)))))
     65                (if (string= (car parts) "dir")
     66                    (add-child current-dir (make-fs-directory (cadr parts) current-dir))
     67                    (add-child current-dir (make-fs-file (cadr parts)
     68                                                         (parse-integer (car parts))))))
     69         finally (return root)))
     70 
     71 (defun get-all-directories (dir)
     72   (loop with dirs = nil
     73         for child in (children dir)
     74         when (dir-p child)
     75           do (push child dirs)
     76           and do (setf dirs (concatenate 'list
     77                                          dirs
     78                                          (get-all-directories child)))
     79         finally (return dirs)))
     80 
     81 (defun task1 (inputs)
     82   (let ((tree (build-fs-tree inputs)))
     83     (loop for dir in (get-all-directories tree)
     84           when (<= (size dir) 100000)
     85             sum (size dir))))
     86 
     87 (defun task2 (inputs)
     88   (loop with tree = (build-fs-tree inputs)
     89         with free-space = (- 70000000 (size tree))
     90         with needed-space = (- 30000000 free-space)
     91         for dir in (get-all-directories tree)
     92         when (>= (size dir) needed-space)
     93           minimize (size dir)))
     94 
     95 (define-day 7
     96     ()
     97   #'task1
     98   #'task2)