Problem 7 AoC 2022 solution from the Clojure Berlin Meetup

scratch.clj

(ns scratch
  (:require [clojure.string :as str]))

;;///////////////////////////////////////////////////////////////////////////////
;;===============================================================================
;;                                    Parsing
;;===============================================================================
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\


(defn cd? [s] (str/starts-with? s "cd"))

(defn parse-ls [s]
  (into ["ls"] (->> (map #(str/split % #" ") (next s))
                    (map (fn [[n o]]
                           (if-let [n (parse-long n)]
                             [n o]
                             [n o]))))))

(defn parse [f]
  (->> (-> (slurp f)
           (str/split #"\$"))
       (remove str/blank?)
       (map (comp str/split-lines str/trim))
       (map #(if (cd? (first %))
               (str/split (first %) #" ")
               (parse-ls %)))))

(comment
  (parse "sample.txt")
  ;; => (["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"]])
  )

;;///////////////////////////////////////////////////////////////////////////////
;;===============================================================================
;;                                   Problems
;;===============================================================================
;;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

;; we first restructure the output from parse to have a map from dir->contents
(defn restructure [input]
  (loop [s ["/"] res {} rem (next input)]
    (cond
      (empty? rem) res

      (cd? (ffirst rem))
      (let [dir (second (first rem))]
        (if (= dir "..")
          (recur (pop s) res (next rem))
          (recur (conj s dir) res (next rem))))
      :else
      (recur s (assoc res s (nfirst rem)) (next rem)))))

(comment
  (restructure (parse "sample.txt"))
  ;; => {["/"]
  ;;     (["dir" "a"] [14848514 "b.txt"] [8504156 "c.dat"] ["dir" "d"]),
  ;;     ["/" "a"] (["dir" "e"] [29116 "f"] [2557 "g"] [62596 "h.lst"]),
  ;;     ["/" "a" "e"] ([584 "i"]),
  ;;     ["/" "d"]
  ;;     ([4060174 "j"] [8033020 "d.log"] [5626152 "d.ext"] [7214296 "k"])}
  )

;; from this map we calculate directory sizes cursively, bottoming out at the leafs
(defn calc [cur-dir res]
  (if (contains? res cur-dir)
    (let [[size new-res]
          (reduce (fn [[cur-size res] [n-or-dir dir-name]]
                    (if (number? n-or-dir)
                      [(+ cur-size n-or-dir) res]
                      (let [new-path (conj cur-dir dir-name)
                            new-res (calc new-path res)]
                        [(+ cur-size (get new-res new-path)) new-res])))
                  [0 res]
                  (get res cur-dir))]
      (assoc new-res cur-dir size))
    (assoc res cur-dir 0)))

(comment
  (->> (parse "sample.txt") restructure (calc ["/"]))
  ;; => {["/"] 48381165,
  ;;     ["/" "a"] 94853,
  ;;     ["/" "a" "e"] 584,
  ;;     ["/" "d"] 24933642}
  )

(defn problem1 [input]
  (->> input
       restructure
       (calc ["/"])
       vals
       (filter #(<= % 100000))
       (reduce +)))

(comment
  (problem1 (parse "sample.txt"))
  (problem1 (parse "input7.txt")))


(def total-size 70000000)

(defn problem2 [input]
  (let [dir->size (->> input
                       restructure
                       (calc ["/"]))
        total-used (get dir->size ["/"])
        total-avail (- total-size total-used)
        total-need (- 30000000 total-avail)]
    (->> (sort-by second dir->size)
         (some #(when (<= total-need (second %)) %))
         second)))

(comment
  (problem2 (parse "sample.txt"))
  (problem2 (parse "input7.txt")))