Fork me on GitHub

Day 7 - Solutions

norman05:12:15 I'm a disappointed at the repeated evaluation for directory sizes. I'm glad this problem didn't punish that.

Alex Alemi06:12:48

I had also started by building the fs tree, but then realized that I only needed to keep track of the directory sizes directly.


;; 202207
(let [f (fn [state [_ cmd path filesize filename]]
          (if (= "cd" cmd)
            (if (= path "..")
              (update state :path pop)
              (update state :path conj path))
            (let [size (parse-long filesize)]
              (loop [state state, path (:path state)]
                (if (seq path)
                  (recur (update-in state [:size path] #(+ size (or % 0))) (pop path))
      m (->> (slurp "resources/202207")
             (re-seq #"\$ (cd) (.+)|(\d+) (.+)")
             (reduce f {:path []})
      v (vals m)
      x (+ (m ["/"]) -70000000 30000000)
      q1 (->> v (filter #(>= 100000 %)) (reduce +))
      q2 (->> v (filter #(>= % x))      (reduce min))]
  [q1 q2])
;; [1667443 8998590]

🙌 11

[HINT]: A folder can contains an other folder with the same name 😅

☝️ 1
😫 2

Over-engineered it a bit by actually building the tree, but got some practice using clojure.walk.


bit braindead but I've got a headache today:

(ns day7)

(defn tally [sizes path fsize]
  (loop [p path s sizes]
    (if-not (empty? p)  
      (recur (pop p) (update s (apply str p) #(+ (or %1 0) fsize))) s)))

(def sizes (loop [[[f s t] & r] (->> "input/day7.txt" slurp lines (map #(split % " "))) 
                  path [] 
                  sizes {}]
               (nil? f) sizes
               (and (= f "$") (= s "cd") (= t "..")) (recur r (pop path) sizes)
               (and (= f "$") (= s "cd")) (recur r (conj path t) sizes)
               (not (#{"dir" "$"} f)) (recur r path (tally sizes path (parse-long f)))
               :else (recur r path sizes))))

(def to-free (- (- 70000000 30000000 (sizes "/"))))

(println "1:" (reduce + (filter (partial >= 100000) (vals sizes))))
(println "2:" (apply min (filter (partial <= to-free) (vals sizes))))


sporting newly added vals


I also used a tree of nested maps for the fs.. parsing the input turned out to be really easy, but calculating the sizes of the nested dirs was a PITA


parsed tree, then flattened into flat list of files, then reduced into folder sizes - too complicated

Valentin Mouret13:12:35

I am not super satisfied as there are probably more elegant solutions with walk, but I am not quite used to it for now. 🙂


(defn partition-with [pred]
  (fn [xf]
    (let [acc (atom nil)]
        ([] (xf))
         (let [result (if-let [r (seq @acc)]
                        (do (reset! acc nil)
                            (unreduced (xf result r)))
           (xf result)))
        ([result input]
         (if (pred input)
           (let [new-input @acc]
             (reset! acc [input])
             (if (seq new-input)
               (xf result new-input)
             (swap! acc conj input)
transducer to split input into partitions where each partition begins with an element for which pred returns true and the rest - false. Similar to split-with but transducer friendly. I used it for day-7 solution to get from input lines blocks like [command & output]


Feel like a dropped an atom bomb on this one with zippers and a full-info map. specter helped a bit.


I just realized my input is in perfect DFS order. Probably a super short solution if you can assume that.

R.A. Porter15:12:53

As most, over-engineered it a ton in anticipation of a request for more detailed results. Not happy with much of this at all -


(defn incr-dir-size [state path size]
  (->> (reduce
        (fn [acc dir]
          (let [d (if-some [p (:parent acc)]
                    (str p "-" dir)
            (-> acc
                (update-in [:state d] (fnil + 0) size)
                (assoc :parent d))))
        {:parent nil :state state}

(defn solve-tree [filename]
  (loop [[h & t] (parse-input filename)
         current-path []
         dir-size {}]
    (if (nil? h)
        (str/starts-with? h "$ cd")
        (let [d (last (str/split h #" "))
              current-path (if (= d "..") (pop current-path) (conj current-path d))]
          (recur t current-path dir-size))

        (not (or (= h "$ ls") (str/starts-with? h "dir")))
        (let [[file-size] (str/split h #" ")
              dir-size (incr-dir-size dir-size current-path (parse-long file-size))]
          (recur t current-path dir-size))

        (recur t current-path dir-size)))))

(defn part1 [filename]
  (->> (solve-tree filename)
       (filter #(>= 100000 %))
       (reduce +)))

(defn part2 [filename]
  (let [sizes (solve-tree filename)
        target (+ (sizes "/") -70000000 30000000)]
    (->> (vals sizes)
         (sort <)
         (drop-while #(<= % target))


Ugly ugly ugly, but it works and now from reading all of your comments above I can go back later and learn about zippers and walk.


A rather verbose using a transducer to provide a sequence of file (which wasn't actually necessary) and directory entries


I modified my solution, dropping the step where I added directory sizes to the tree, and instead I just calculate them on the fly with a recursive function.


I liked @U04575QMU2K use of match, so I incorporated that as well. At what point must I stop tweaking and get on with the real things I’m supposed to be doing today?


😆 Second try. I munged the input string, eval’d it directly into a tree structure.

(defn parse-tree [input]
  (let [open (-> input
                 (str/replace "$ cd .." "]")
                 (str/replace #"\$ cd (.*?)\n" " [")
                 (str/replace #"[^\d \[\]]" ""))
        missing (- (get (frequencies open) \[)
                   (get (frequencies open) \]))]
    (read-string (str open (apply str (repeat missing "]"))))))

(defn dir-sizes [input]
  (->> (parse-tree input)
       (tree-seq vector? identity)
       (filter vector?)
       (map #(sp/select (sp/walker number?) %))
       (map (partial reduce +))

(defn part-1 [input]
  (->> (dir-sizes input)
       (filter #(>= 100000 %))
       (reduce +)))

(defn part-2 [input]
  (let [dirs (dir-sizes input)
        space-needed (- 30000000 (- 70000000 (last dirs)))]
    (->> dirs
         (drop-while #(> space-needed %))

😛 1

cool! does the trick work because the input is in depth first order?


yes, I think that’s a requirement. And what do you mean “trick”? Production ready.

😂 1

what if I did

cd /
cd a
cd ..
cd a


Well, I made a mess today... I mean, it worked, and I got both stars. But I made a mess in the process. My solution creates a map like this (from the test data):

{["/"] {:files #{["c.dat" 8504156] ["b.txt" 14848514]},
        :dirs #{"d" "a"},
        :sizes 23352670},

 ["/" "a"] {:files #{["f" 29116] ["g" 2557] ["h.lst" 62596]},
            :dirs #{"e"},
            :sizes 94269},

 ["/" "a" "e"] {:files #{["i" 584]},
                :dirs #{},
                :sizes 584},

["/" "d"] {:files #{["k" 7214296] ["j" 4060174] ["d.log" 8033020] ["d.ext" 5626152]},
           :dirs #{},
           :sizes 24933642}}
Stupid me thought all that info on files and stuff would be necessary for part 2... sigh Once I had that I reduce each key over a map of simple directories and sizes (start at 2). e.g.
["/" "a" "e"] would set map to {["/" "a" "e"] n}
Then increase ["/" "a"] by the same size, then finally ["/"] by the same size again. Which gave me a map of full directory paths and their size.


Like I said, I made a mess. It at least did make part 2 trivial.


clojure.walk/postwalk into a flatten is a great way to get the dir totals after making the dir structure. Don’t forget about postwalk-demo which helps get a feel for the execution order


I just finished making some tweaks that do exactly that, @U064J0EFR. Okay, now I’m done. No more fiddling. I’m satisfied.


I also went full nuclear on this one 😅 I had a feeling it was overkill (especially not knowing what the second part was going to be) but I felt like it was a good opportunity to practice writing a stateful transducer and playing with zippers. edit: realizing after posting that end-loc can be refactored using loc-seq but what's done is done


I parsed the input into a fs tree {:name name :type :dir/:file :size size :children [for dirs only]} and then traversed using tree-seq :

Mark Wardle11:12:09

Building a tree sounded complicated to me, so I used a different approach and simply built a flattened list of paths and file sizes, and then did filter by prefix, and reduce to calculate directory sizes. (defn parse-line [{:keys [current-path] :as ctx} line] (m/match (str/split line #"\s") ["dir" _] ctx ;; NOP ["$" "cd" "/"] (assoc ctx :current-path [""]) ["$" "cd" ".."] (update ctx :current-path pop) ["$" "cd" dir] (let [path (conj current-path dir)] (-> ctx (assoc :current-path path) (update :dirs conj (str (str/join "/" path) "/")))) ["$" "ls"] ctx ;; NOP [size filename] (update ctx :files conj [(str/join "/" (conj current-path filename)) (parse-long size)]) :else (update ctx :errors conj {:error "Unknown command: " :line line}))) (defn parse-commands ([lines] (parse-commands {:current-path []} lines)) ([ctx lines] (if-let [line (first lines)] (recur (parse-line ctx line) (rest lines)) (dissoc ctx :current-path)))) (defn size "Given a sequence of files (tuples of path and size), determine total size of the specified directory." [files dir] (reduce (fn [acc [path size]] (if (str/starts-with? path dir) (+ acc size) acc)) 0 files))


Revisited version. Discoveries: you don't need dir lines at all. Also tree-seq simplifies the things.


Day seven part one:

(defn command-walker ; part-one solution
  (let [commands (read-input input)
        cd (fn [c] (.contains c "$ cd"))
        ls (fn [c] (.contains c "$ ls"))
        file (fn [s]
               (let [[size name] (string/split s #" ")]
                 {name (Long/parseLong size)}))
        oddsor (fn [tree] ; walks the created map with data to sum the sizes
                  (fn [node]
                    (if (map? node)
                      {:size (reduce +
                                      (filter number? (vals node))
                                      (keep :size (vals node))))
                       :children node}
        totalsize (atom 0)
        calculate-size (fn [tree] ; calculates the sum of all sizes < 100000
                          (fn [node]
                            (let [size? (fn [s] (< s 100000))
                                  size  (fn [s] (-> (select-keys s [:size]) :size (#(when (size? %) %))))]
                              (if (and (map? node) (not-empty (select-keys node [:size])))
                                (when-let [total (size node)]
                                  (swap! totalsize + total))
                          (oddsor tree)))
        foldercontent (atom {})
        folders (atom {})
        foldertree (atom [])
        previousfolder (atom nil)
        currentfolder (atom nil)
        _inputwalker (doall ; converts the input to a map with data
                      (for [c commands
                            :let [cdto (first (when (cd c) (take-last 1 (re-seq #"[a-zA-Z0-9/[..]]+" c))))]]
                        (if cdto
                            (reset! previousfolder @currentfolder)
                            (if (= ".." cdto)
                              (reset! foldertree  (into [] (take (dec (count @foldertree)) @foldertree)))
                              (swap! foldertree conj cdto))
                            (reset! currentfolder (last @foldertree))
                            (reset! foldercontent {}))
                          (when-not (ls c)
                            (when-not (.contains c "dir ")
                              (swap! foldercontent conj (file c)))
                            (swap! folders assoc-in @foldertree @foldercontent)))))]
    (calculate-size @folders) ; calculate the size
    @totalsize)) ; return the size


Finally got back to AoC. Didn’t want to build the tree, so I made a graph-like thing and recursively resolved the absolute paths as references while walking from "/". Not the most elegant solution, but somehow I believed it’d be more flexible and easier to reason about: TIL from Apple’s approach that you don’t even need to consider subdirectories in ls output, because the cd commands contain all the information when you just recursively add the file sizes to all parent directories!


I just had a thought that one could implement a file system, insert all the files from the problem into it and then shell out to du to find out the sizes 😂

😄 4

or better yet, regexp the problem into a shell script for creating all those files on disk i.e.

dir foo -> mkdir foo
123 bar -> dd if=/dev/zero of=bar count=123 bs=1
$ cd <x> -> cd <x>
and then du


almost got it... du is tricky


dirs probably weight something in posix


yeah, that was the whole problem


we can sum just the files in a subshell


felipecortez@izac 07-in-prod % find .
felipecortez@izac 07-in-prod %  find . -type d -print0 | xargs -0 -I{} bash -c "find {} ! -type d -print0 | xargs -r0 stat -c %s | paste -sd+ - | bc" | awk '$1 < 100000 {total += $1} END { print total }'


piping find to find? yeah sure


works on the real input too!

partyparrot 5

@UA2U3KW0L this is epic

😁 1

Or... now bear with me... write a generator of random nested directory/files and repeat until tree matches the original input problem, and then just du 😂

book_guy 1

Is there something like "code golf" for AOC, where the purpose is to find the most ridiculous way to solve the problem? This should be a separate leaderboard.


"code rube goldberg"


There is some on that over on the reddit with the tag Upping The Ante:

👍 2
Cal Herries15:12:29

There’s a separate competition for die-hard code golfers over on stack exchange. Not the same problems though


meh, they have home-made languages for golfing


and it seems like they don't have to parse the input


postwalk and tree-seq come in very handy here.


Spent the good afternoon on day 7 part one. At the moment I have a ds thats a map and contains each folder and its size in files. Now im stuck because i need to add the size of a subfolder to the parent folder. I have yet to figure out how :rolling_on_the_floor_laughing:

{:/ {:a {:e {:files [{:name "i", :size 584}],
                             :folders [],
                             :foldersize 0,
                             :totalfilesize 584},
                         :files [{:name "f", :size 29116} {:name "g", :size 2557}
                                 {:name "h.lst", :size 62596}],
                         :folders [:e],
                         :foldersize 0,
                         :totalfilesize 94269},
                     :d {:files [{:name "j", :size 4060174} {:name "d.log", :size 8033020}
                                 {:name "d.ext", :size 5626152} {:name "k", :size 7214296}],
                         :folders [],
                         :foldersize 0,
                         :totalfilesize 24933642},
                     :files [{:name "b.txt", :size 14848514} {:name "c.dat", :size 8504156}],
                     :folders [:a :d],
                     :foldersize 0,
                     :totalfilesize 23352670}}
*edit, was some info missing


Maybe you already figured it out, but I solved this by using postwalk. I rebuild the hierarchy to contain an easily available size-parameter, which is used to add the folder’s size to the parent folders. Note that my data structure looks like this so you’d need to modify the code a bit:

{"b.txt" 14848514,
 "c.dat" 8504156,
 "a" {"f" 29116, "g" 2557, "h.lst" 62596, "e" {"i" 584}},
 "d" {"j" 4060174, "d.log" 8033020, "d.ext" 5626152, "k" 7214296}}
(defn assign-size-to-directories [tree]
  (walk/postwalk (fn [node]
                   (if (map? node)
                     {:size (reduce + (concat
                                       (filter number? (vals node))
                                       (keep :size (vals node))))
                      :children node}


thanks! ill have another look tomorrow when i have a day off

👍 1


{:size 48381165,
 {"b.txt" 14848514,
  "c.dat" 8504156,
  "a" {:size 94853, :children {"f" 29116, "g" 2557, "h.lst" 62596, "e" {:size 584, :children {"i" 584}}}},
  "d" {:size 24933642, :children {"j" 4060174, "d.log" 8033020, "d.ext" 5626152, "k" 7214296}}}}


With your tip I was able to finish day seven part one, thanks!


I name the fn in my solution oddsor 😉

😁 1
👏 1

I refuse to adopt transducers, zippers and all those other quirky post-modern solutions... Simply because I don't have them in the language 😂

💯 2
😅 2

@UJEK1RGJ0 what happens if you just copy/paste the source of map, etc in your language?


it usually works but I need to cleaan up stuff relating to chunked & lazy seqs for now, also some clojure RT stuff has to be replaced if present


but some of the core fns just work


I've omitted the transducer arities though


do you re-implement core functions or execute them from source?


wrote transduce and mapt , filtert etc and it works


well 😅 I usually paste them over and remove 2/3 of the code and adjust the rest - I have no way to execute full core source atm


what I mean, do you compile the source or have them built in go


aah, some of them are written in go, but many are already written in let-go


and does it pre-compile the stuff into the binary or are these functions compiled on the fly at startup?


everything is compiled at startup atm, although it will not stay that way


what I want to do is compile built-in NSes and take an image of the bytecode, then ship the interpreter with that image so it doesn't compile anything at boot


right. image is just a byte array or so?


maybe there will be a .lgc or so with bytecode?


yeah, that's the plan


i.e. let-go -c foo -o foo.lgc and then let-go foo.lgc , or even (dump-image "foo.lgc") from a REPL


why you ask?


no reason, just wondering how you are doing things

😁 1

I might actually look into this over the weekend