Clojurians Log v2

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: https://github.clerk.garden/formsandlines/aoc2022-clojure/commit/50c1e9931d26b276f0521296954ab90f3334f8ee/src/advent_of_clerk/day_07.html 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!

https://gitlab.com/maximoburrito/advent2022/-/blob/main/src/day07/main.clj I'm a disappointed at the repeated evaluation for directory sizes. I'm glad this problem didn't punish that.

https://github.com/alexalemi/advent/blob/main/2022/clojure/p07.clj

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))
                  state)))))
      m (->> (slurp "resources/202207")
             (re-seq #"\$ (cd) (.+)|(\d+) (.+)")
             (reduce f {:path []})
             :size)
      v (vals m)
      x (+ (m ["/"]) -70000000 30000000)
      q1 (->> v (filter #(>= 100000 %)) (reduce +))
      q2 (->> v (filter #(>= % x))      (reduce min))]
  [q1 q2])
;; [1667443 8998590]

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

https://github.com/rap1ds/advent-of-code-2022/blob/main/src/day7.clj

https://github.com/FelipeCortez/advent-of-code/blob/master/2022/07.clj

Over-engineered it a bit by actually building the tree, but got some practice using clojure.walk. https://github.com/motform/advent-of-clojure/blob/master/src/advent_of_clojure/2022/07.clj

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 {}]
             (cond 
               (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 https://github.com/Ramblurr/advent-of-code-2022/blob/main/src/aoc/day07.clj

parsed tree, then flattened into flat list of files, then reduced into folder sizes - too complicated https://github.com/nbardiuk/adventofcode/blob/master/2022/src/day07.clj

not the most concise (https://clojurians.slack.com/archives/C0GLTDB2T/p1670395567909029?thread_ts=1670392240.040349&cid=C0GLTDB2T@zengxh! 😅), but seemed a natural fit for zippers (parsing) and postwalk (processing) https://github.com/CarnunMP/Advent-of-Code/blob/master/src/y2022/d7.clj

https://clojurians.slack.com/archives/C0GLTDB2T/p1670411367318609?thread_ts=1670392240.040349&cid=C0GLTDB2T too, damn tiny!

I am not super satisfied as there are probably more elegant solutions with walk, but I am not quite used to it for now. 🙂 https://github.com/ValentinMouret/advent-2022/blob/main/src/day_07.clj

https://github.com/benjamin-asdf/advent-of-code/blob/master/src/Y2022/day7.clj

(defn partition-with [pred]
  (fn [xf]
    (let [acc (atom nil)]
      (fn
        ([] (xf))
        ([result]
         (let [result (if-let [r (seq @acc)]
                        (do (reset! acc nil)
                            (unreduced (xf result r)))
                        result)]
           (xf result)))
        ([result input]
         (if (pred input)
           (let [new-input @acc]
             (reset! acc [input])
             (if (seq new-input)
               (xf result new-input)
               result))
           (do
             (swap! acc conj input)
             result)))))))

Feel like a dropped an atom bomb on this one with zippers and a full-info map. specter helped a bit. https://github.com/tschady/advent-of-code/blob/main/src/aoc/2022/d07.clj

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

As most, over-engineered it a ton in anticipation of a request for more detailed results. Not happy with much of this at all - https://coyotesqrl.github.io/advent-of-code/2022/src/coyotesqrl/2022/day07.html

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

(defn solve-tree [filename]
  (loop [[h & t] (parse-input filename)
         current-path []
         dir-size {}]
    (if (nil? h)
      dir-size
      (cond
        (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))

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

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

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

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. https://github.com/zamansky/advent2022/blob/main/src/day07.clj

Not too shabby with zippers. https://github.com/wevre/advent-of-code/blob/master/src/advent_of_code/2022/day_07_directories.clj

Used match, which turned out nice. https://github.com/volesen/aoc2022/blob/main/day7/day7.clj

Lots of postwalk and tree-seq here https://github.com/bhauman/advent-of-code-2022/blob/main/src/adv2022/day7/sol.clj

A rather verbose https://github.com/lassemaatta/clj-aoc-2022/blob/master/src/lassemaatta/aoc_2022/day07.clj 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. https://github.com/wevre/advent-of-code/blob/master/src/advent_of_code/2022/day_07_directories.clj

I liked @vincolesen 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?

https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2022/day07.clj

😆 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 +))
       sort))

(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 %))
         first)))

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.

what if I did

cd /
cd a
cd ..
cd a
ls
ls

Well, I made a mess today... I mean, it worked, and I got both stars. But I made a mess in the process. https://github.com/stuartstein777/clj-advent-of-code/blob/master/src/stuartstein777/2022/day7.clj 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}}

["/" "a" "e"] would set map to {["/" "a" "e"] n}

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, @bhauman. 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

Day seven part one:

(defn command-walker ; part-one solution
  [input]
  (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
                 (walk/postwalk
                  (fn [node]
                    (if (map? node)
                      {:size (reduce +
                                     (concat
                                      (filter number? (vals node))
                                      (keep :size (vals node))))
                       :children node}
                      node))
                  tree))
        totalsize (atom 0)
        calculate-size (fn [tree] ; calculates the sum of all sizes < 100000
                         (walk/postwalk
                          (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))
                                node)))
                          (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
                          (do
                            (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

Day seven part two https://github.com/LouDnl/advent-of-code-2022/blob/09be4f6e8d6340ca38861b88fb963449927d6f37/src/clj/advent_of_code_2022/days/day_seven.clj#L140-L194

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 : https://github.com/pwojnowski/advent-of-code/blob/master/src/aoc/aoc2022.clj#L193

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. https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2022/day07.clj

https://github.com/benjamin-asdf/advent-of-code/blob/master/src/Y2022/day7_no_trees.clj yesterday in bed I was devising another day 7 solution

@zengxh wow! Nice!

I am meditating on that solution to learn the error of my ways…

took me a while. I think I've abused closures to achieve this.

(defn swap-value [m k f & args]
  (assoc m k (apply f (m k) args)))

(defn all-folders [col]
  (map (fn [n]
         (string/join " " (take n col))) (range 1 (inc (count col)))))


(defn parse-cmd [cmd]
  (let [[p1 p2 p3] (string/split cmd #" ")]
    (cond
      (= p2 "ls") identity
      (= p1 "dir") identity
      (= p3 "..") #(swap-value % :stack pop)
      (= p2 "cd") #(swap-value % :stack conj p3)
      :else (fn [m]
              (reduce (fn [acc dir]
                        (swap-value acc dir #(+ (or % 0) (parse-long p1))))
                      m (all-folders (:stack m)))))))


(defn folder-sizes [cmds]
  (dissoc (reduce #(%2 %1) {:stack []} cmds) :stack))


(let [output (string/split-lines (slurp "input/day-7-input.txt"))
      sizes (->> (map parse-cmd output)
                 (folder-sizes))
      free-space (- 70000000 (sizes "/"))
      required-space (- 30000000 free-space)]

  {:part2 (->> (filter #(>= (second %) required-space) sizes)
                (map second)
                (apply min))

   :part1 (->>
            (vals sizes)
            (filter #(<= % 100000))
            (reduce +))})

I don't see any abuse 🙂

I've re implemented update. 😅

core.match, zippers and tree-seq - OK happy with it. https://gist.github.com/maacl/85b8c886b6ec7b269cea2a1664ab6a3d

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 .
.
./a
./a/g
./a/f
./a/h.lst
./a/e
./a/e/i
./b.txt
./c.dat
./d
./d/d.log
./d/d.ext
./d/j
./d/k
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 }'
95437

piping find to find? yeah sure

works on the real input too!

woot

@felipecortezfi this is epic

lol

"code rube goldberg"

reminds me of http://tom7.org/harder/

There is some on that over on the reddit with the tag Upping The Ante: https://www.reddit.com/r/adventofcode/?f=flair_name:%22Upping%20the%20Ante%22

There’s a separate competition for die-hard code golfers over on stack exchange. Not the same problems though https://codegolf.meta.stackexchange.com/questions/25251/announcing-code-golf-advent-calendar-2022-event-challenge-sandbox

meh, they have home-made languages for golfing

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

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

I name the fn in my solution oddsor 😉

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}
                     node))
                 tree))

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

Result:

{:size 48381165,
 :children
 {"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}}}}

@xnooga 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?

https://github.com/nooga/let-go/blob/main/pkg/rt/core/core.lg

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

cool

why you ask?

no reason, just wondering how you are doing things

I might actually look into this over the weekend