(in-package :ca.mhcat.advent2022)
;; --- Day 7: No Space Left On Device ---
;; You can hear birds chirping and raindrops hitting leaves
;; as the expedition proceeds. Occasionally, you can even
;; hear much louder sounds in the distance; how big do the
;; animals get out here, anyway?
;; The device the Elves gave you has problems with more than
;; just its communication system. You try to run a system
;; update:
;; $ system-update --please --pretty-please-with-sugar-on-top
;; Error: No space left on device
;; Perhaps you can delete some files to make space for the
;; update?
;; You browse around the filesystem to assess the situation
;; and save the resulting terminal output (your puzzle
;; input). For example:
;; $ 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
;; The filesystem consists of a tree of files (plain data)
;; and directories (which can contain other directories or
;; files). The outermost directory is called /. You can
;; navigate around the filesystem, moving into or out of
;; directories and listing the contents of the directory
;; you're currently in.
;; Within the terminal output, lines that begin with $ are
;; commands you executed, very much like some modern
;; computers:
;; cd means change directory. This changes which
;; directory is the current directory, but the specific
;; result depends on the argument:
;; cd x moves in one level: it looks in the current
;; directory for the directory named x and makes it
;; the current directory.
;; cd .. moves out one level: it finds the directory
;; that contains the current directory, then makes
;; that directory the current directory.
;; cd / switches the current directory to the
;; outermost directory, /.
;; ls means list. It prints out all of the files and
;; directories immediately contained by the current
;; directory:
;; 123 abc means that the current directory contains
;; a file named abc with size 123.
;; dir xyz means that the current directory contains
;; a directory named xyz.
;; Given the commands and output in the example above, you
;; can determine that the filesystem looks visually like
;; this:
;; - / (dir)
;; - a (dir)
;; - e (dir)
;; - i (file, size=584)
;; - f (file, size=29116)
;; - g (file, size=2557)
;; - h.lst (file, size=62596)
;; - b.txt (file, size=14848514)
;; - c.dat (file, size=8504156)
;; - d (dir)
;; - j (file, size=4060174)
;; - d.log (file, size=8033020)
;; - d.ext (file, size=5626152)
;; - k (file, size=7214296)
;; Here, there are four directories: / (the outermost
;; directory), a and d (which are in /), and e (which is in
;; a). These directories also contain files of various
;; sizes.
;; Since the disk is full, your first step should probably
;; be to find directories that are good candidates for
;; deletion. To do this, you need to determine the total
;; size of each directory. The total size of a directory is
;; the sum of the sizes of the files it contains, directly
;; or indirectly. (Directories themselves do not count as
;; having any intrinsic size.)
;; The total sizes of the directories above can be found as
;; follows:
;; The total size of directory e is 584 because it
;; contains a single file i of size 584 and no other
;; directories.
;; The directory a has total size 94853 because it
;; contains files f (size 29116), g (size 2557), and
;; h.lst (size 62596), plus file i indirectly (a
;; contains e which contains i).
;; Directory d has total size 24933642.
;; As the outermost directory, / contains every file.
;; Its total size is 48381165, the sum of the size of
;; every file.
;; To begin, find all of the directories with a total size
;; of at most 100000, then calculate the sum of their total
;; sizes. In the example above, these directories are a and
;; e; the sum of their total sizes is 95437 (94853 + 584).
;; (As in this example, this process can count files more
;; than once!)
;; Find all of the directories with a total size of at most
;; 100000. What is the sum of the total sizes of those
;; directories?
(defparameter day7/test-data
'("$ 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"))
(labels ((commandp (line) (string-equal "$" (car line)))
(dirp (line) (string-equal "dir" (car line)))
(file-size (line) (parse-integer (car line) :junk-allowed t))
(filep (line) (integerp (file-size line)))
(command (line) (second line))
(cdp (line) (string-equal "cd" (command line)))
(operand (line) (third line))
(node-name (line) (second line))
(change-dir (target cwd)
(if (string-equal ".." target)
(cdr cwd)
(cons target cwd)))
(directories (acc cwd lines)
(let ((line (car lines)))
(cond
((null line) acc)
((commandp line)
(if (cdp line)
;; change directory without modifying structure
(directories acc
(change-dir (operand line) cwd)
(cdr lines))
;; otherwise it's a ls command, so throw it away
(directories acc cwd (cdr lines))))
((or (dirp line) (filep line))
(let* ((n (or (position "$" lines :key #'car :test #'string-equal)
(length lines)))
(rest (nthcdr n lines)))
(if (assoc cwd acc :test #'equal)
(directories acc cwd rest)
(directories (acons cwd (subseq lines 0 n) acc) cwd rest))))
(t (error "poop"))))))
(defun day7/directories (lst)
(directories nil nil lst)))
(defun day7/parse-line (line)
(labels ((parse-line (acc line)
(let ((sp (position #\space line :test #'char=)))
(if (null sp)
(mapcar (lambda (l) (coerce l 'string))
(cons line acc))
(parse-line (cons (subseq line 0 sp) acc)
(subseq line (1+ sp)))))))
(nreverse
(parse-line nil (coerce line 'list)))))
(defun day7/load-dataset (lst)
(mapcar #'day7/parse-line lst))
(defun day7/sum-contents (alst)
(labels ((sum-files (lst)
(loop for (x y) in (cdr lst)
if (string-equal "dir" x)
sum (sum-files (assoc (cons y (car lst)) alst
:test #'equal))
else
sum (parse-integer x))))
(mapcar (lambda (lst)
(list (car lst) (sum-files lst)))
alst)))
(defun day7/compute-part1 (lst)
(let* ((parsed-data (day7/load-dataset lst))
(dirs (day7/directories parsed-data))
(dir-sizes (day7/sum-contents dirs))
(sums (mapcar #'second dir-sizes))
(smol-sums (remove-if-not #'(lambda (v) (<= v 100000)) sums)))
(apply #'+ smol-sums)))
(defun day7/part1 ()
(day7/compute-part1
(load-lines "day7.txt")))
;; --- Part Two ---
;; Now, you're ready to choose a directory to delete.
;; The total disk space available to the filesystem is
;; 70000000. To run the update, you need unused space of at
;; least 30000000. You need to find a directory you can
;; delete that will free up enough space to run the update.
;; In the example above, the total size of the outermost
;; directory (and thus the total amount of used space) is
;; 48381165; this means that the size of the unused space
;; must currently be 21618835, which isn't quite the
;; 30000000 required by the update. Therefore, the update
;; still requires a directory with total size of at least
;; 8381165 to be deleted before it can run.
;; To achieve this, you have the following options:
;; Delete directory e, which would increase unused space by 584.
;; Delete directory a, which would increase unused space by 94853.
;; Delete directory d, which would increase unused space by 24933642.
;; Delete directory /, which would increase unused space by 48381165.
;; Directories e and a are both too small; deleting them
;; would not free up enough space. However, directories d
;; and / are both big enough! Between these, choose the
;; smallest: d, increasing unused space by 24933642.
;; Find the smallest directory that, if deleted, would free
;; up enough space on the filesystem to run the update. What
;; is the total size of that directory?
(defun day7/compute-part2 (lst)
(let* ((parsed-data (day7/load-dataset lst))
(dirs (day7/directories parsed-data))
(dir-sizes (day7/sum-contents dirs))
(total-used (second (assoc '("/") dir-sizes :test #'equal)))
(available (- 70000000 total-used))
(required (- 30000000 available))
(candidates (remove-if (lambda (cons) (< (second cons) required)) dir-sizes)))
(car (sort candidates #'< :key #'second))))
(defun day7/part2 ()
(day7/compute-part2
(load-lines "day7.txt")))