Clojurians Log v2

My starting point was to google "graph algorithm all paths" and go from there 🙂

did you find the problem in the end?

Yes, I expected my next-cave function to return a vector of paths, but when there was no possible paths I was returning a map. SO I stuck that map in a vector and it works.

Got part 1 solved, but it takes 25 seconds to run!

My initial attempt at part 2 took at least 4 hours to run (maybe a lot longer, I cancelled it.) After some thinking and sleeping on it, I've got something that is still slow (~9.5 seconds), but it works!

(ns stuartstein777.2021.day12b
  (:require [stuartstein777.file :as f]
            [stuartstein777.utils :as u]
            [clojure.string :as str]
            [clojure.set :as set]))

(defn parser [line]
  (let [[start end] (str/split line #"-")]
    [[start end] [end start]]))

(defn merge-vector-of-maps [xs]
  (reduce (fn [acc [k v]] (update acc k conj v)) {} xs))

(defn find-continuation [continuations path-so-far allowed-twice]
  (let [possible-caves (continuations (last path-so-far))]
    (remove (fn [cave] 
              (cond (= cave allowed-twice)
                    (-> path-so-far
                        (frequencies)
                        (get allowed-twice 0)
                        (>= 2))
                    
                    :else (and (= (str/lower-case cave) cave)
                               (not= (.indexOf path-so-far cave) -1)))) possible-caves)))

(defn next-paths [continuations [path finished? allowed-twice]]
  (let [next-caves (find-continuation continuations path allowed-twice)]
    (if (empty? next-caves)
      []
      (mapv (fn [nc] [(conj path nc) finished? allowed-twice]) next-caves))))

(time
 (let [continuations (-> (->> (f/read-all-lines-and-parse "puzzle-inputs/2021/day12" parser)
                              (apply concat)
                              (merge-vector-of-maps))
                         (u/remove-it-from-all-vals "start"))

       lower-case-caves (->> continuations
                             (keys)
                             (filter #(= (str/lower-case %) %))
                             (filter (fn [s] (and (not= "start" s)
                                                  (not= "end" s)))))

       starts (mapv (fn [x] [["start"] false x]) lower-case-caves)]
   (loop [possible-paths starts
          finished       []]
     (if (empty? possible-paths)
       (count (set (map first finished)))
       (let [cur-path     (nth possible-paths 0)
             new-paths    (set (next-paths continuations cur-path))
             new-finished (set (filter (fn [[path _ _]] (= "end" (last path))) new-paths))
             unfinished   (set/difference new-paths new-finished)]
         (if (empty? new-paths)
            ;; got no new paths for this path, so just drop it and recur (it's a dead end.) 
           (recur (rest possible-paths)
                  finished)
            ;; otherwise, drop it and add on all the new unfinished paths and add the finished paths to finished.
           (recur (apply conj (rest possible-paths) unfinished)
                  (apply conj finished new-finished))))))))

I will probably refact it later on. Solving of part 2 takes ~2366 msecs https://github.com/zelark/AoC-2021/blob/main/src/zelark/aoc_2021/day_12.clj

Part 2 is slow, although I've put some optimizations ~1.4s https://github.com/nbardiuk/adventofcode/blob/master/2021/src/day12.clj

End up using a map to track (and decrement) small caves visits. In part02 brute force explore with an increased allowance. Felt a bit cheating returning strings when reached the end, but I wasn't able to flatten it correctly. Part 02 runs in like 1.4s on my machine https://github.com/jacoelho/advent-of-code-clj/blob/main/src/aoc/2021/day12.clj

https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/y2021/day12.clj

I initially misread the question and thought any cave can be visited twice per run, not just one

but only 1 cave makes it pretty easy to track, you don’t even have to track which one was visited twice

This is my attempt today..kinda unoptimized brute force :(

Day 12 https://github.com/RedPenguin101/aoc2021/blob/main/clojure/src/aoc2021/day12.clj and https://github.com/RedPenguin101/aoc2021/blob/main/day12.md My part 2 is extremely slow, but it's ~16 LOC, and I love how the solution code came out as just a statement of the problem:

(count (all-paths with-no-lc-revisits graph))
(count (all-paths with-one-lc-revisit graph))

22ms/820ms. I use a map of number of times each cave can be visited, with big caves as ##Inf, which you can dec forever. https://github.com/tschady/advent-of-code/blob/main/src/aoc/2021/d12.clj

@tws mine is similar to yours in the looping, but I was wondering what makes it slower, is it mostly the "check" that I do every time, while yours only checks the allowances and it's much faster?

@antbbn couple things I can see at quick glance (might be wrong): • (big one) I stop recursing on “end”, you keep going which is going to be a bigger search space. • (small?) your .indexOf is checking a vector for the current node, I use a map which is much faster. • (small?) lots of repeat work in your part 2 allowed function

recursion counting the leaves, avoids actually building the paths 18ms/352ms https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2021/12.clj

@tws thanks for checking! i think i also stop on "end" because in my graph "end" has no children

I like these counting solutions!

https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2021/day12.clj

down to 10ms/135ms with transduce https://github.com/callum-oakley/advent-of-code/blob/main/src/aoc/2021/12.clj

Back with part 2: https://github.com/kconner/advent-of-code/blob/master/2021/12a.clj, https://github.com/kconner/advent-of-code/blob/master/2021/12b.clj

Separate DFS functions for parts 1 and 2… ?/340ms: https://samadams.dev/2021/12/12/advent-of-code-day-12.html

Memoizing my lower-case? function sped up my part2 from 2.5s to 800ms. Further refactoring of my logic got me to 228ms. Unfortunately it’s still pretty ugly code..

https://github.com/dgtized/advent-of-code/blob/master/2021/day12/passage_pathing.clj

https://github.com/euccastro/advent-of-code-2021/blob/main/day12.clj

500ms in my machine; I didn't do anything special to optimize it

https://github.com/kfirmanty/advent-of-code-2021/blob/main/src/day12.clj here is a first solution that came to my mind, obviously unoptimized but even part-2 executes in 2 seconds which is not that bad. From the first reading of description when I saw that it will be graph based I got worried that it will be much harder than it was in reality as I managed to solve it without problems, but again this might be advent of code practice kicking in 😄 And this day definitely gets a shortest solve-2 definition, by it just being:

(defn solve-2 []
  (with-bindings {#'can-visit-twice? true}
    (solve-1)))

Obviously got lazy and did not want to rewrite fns to get this flag passed on as argument as then it will be even shorter ;d

Part 1, Takes about 25 seconds

(defn parser [line]
  (let [[start end] (str/split line #"-")]
    [[start end] [end start]]))

;; input  -> [{"start" "A"} {"start" "b"} {"A" "c"} {"A" "d"}]
;; output -> {"start" ["A" "b"], "A" ["c" "d"]}
(defn merge-vector-of-maps [xs]
  (reduce (fn [acc [k v]] (update acc k conj v)) {} xs))

;; path-so-far -> {:path ["start" "A" "b"] :finished false}
;; given a map of continuations it gets the continatuations for the last item in the path-so-far path.
;; it excludes those that are lower-case and have already appeared in (:path path-so-far)
;;
;; Continuations looks like this:
;; {"start" '("b" "A")
;;   "A" '("end" "b" "c" "start")
;;   "b" '("A" "end" "d" "start")
;;   "c" '("A")
;;   "d" '("b")
;;   "end" '("b" "A")} 
(defn find-continuation [continuations path-so-far]
  (let [possible-caves (continuations (last (:path path-so-far)))]
    (remove (fn [cave] (and (= (str/lower-case cave) cave)
                            (not= (.indexOf (:path path-so-far) cave) -1))) possible-caves)))

;; Given a path-so-far, it gets all possible continuations and returns a
;; list of the path-so-far with continuations.
(defn next-path [continuations path-so-far]
  (let [next-caves (find-continuation continuations path-so-far)]
    (if (empty? next-caves)
      [(assoc path-so-far :finished true)]
      (mapv (fn [nc] (update path-so-far :path conj nc)) next-caves))))

;; Marks the :finished key in a path as true if the last item in the path is "end"
(defn mark-finished [paths]
  (mapv (fn [{:keys [path] :as cur-path}]
          (if (= (last path) "end")
            (assoc cur-path :finished true)
            cur-path)) paths))

;; Finds all the paths for the given map of continuations.
(defn find-paths [paths continuations]
  (let [{:keys [path] :as first-unfinished} (first (filter (fn [{:keys [finished]}] (false? finished)) paths))]
    (if (nil? first-unfinished)
      paths
      (recur (->> (remove (fn [p] (= path (:path p))) paths)
                  (concat (next-path continuations first-unfinished))
                  (mark-finished))
             continuations))))

;; Needed because their is a bug where dead-ends end up as two vectors intead of maps.
(defn count-paths [paths]
  (->> (mapv :path paths)
       (remove (fn [path] (not= "end" (last path))))
       (count)))

(time
 (->> (f/read-all-lines-and-parse "puzzle-inputs/2021/day12" parser)
      (apply concat)
      (merge-vector-of-maps)
      (find-paths [{:path ["start"] :finished false}])
      (count-paths)))

It's still running.🙃 But if I cancel it, I know it will have been seconds away from finishing. Is this what people call the sunk cost fallacy ?

I just realised, it could be possible to do something like "start->A->C->A->C->....->A->C" infinite loop. Is this something that I need to code against?

it's rather not possible, there should be no such path I believe

ON the one hand, that's good, my code isn't stuck in an infinite loop. On the other hand, my code is really slow. Approaching 2 hours.

I found that none of the examples, nor my input, had any big cave - big cave lines. that alone should prevent infinite loops if it's only big caves you let run unrestricted.

13s hoo boy but it works! https://github.com/tjefferson08/advent-of-code/blob/main/2021/12/core.clj

after some cleanup and refactoring to speed things up -- (my pre-game warmup is to refactor the previous day’s solution)

(ns aoc21.day12
  (:require [ :as io]))

;; part 1

(defn input-data [filename]
  (reduce (fn [m [k v]]
            ;; add a->b; b->a edges
            ;; but skip _->start to make logic below simpler
            (cond-> m
              (not (= v "start")) (update k conj v)
              (not (= k "start")) (update v conj k)))
          {}
          (->> (slurp (io/resource filename))
               (re-seq #"\w+")
               (partition 2))))

(def lower-case?
  (memoize
   (fn [s]
     (Character/isLowerCase (first s)))))

(defn walk
  ([m]
   (walk m #{"start"} '("start")))
  ([m seen [p & _ps :as path]]
   (if (= p "end")
     1
     (let [poss (remove #(seen %) (get m p))]
       (reduce #(+ %1 (walk m
                            (if (lower-case? %2) (conj seen %2) seen)
                            (conj path %2)))
               0
               poss)))))

(defn soln-1 [filename]
  (walk (input-data filename)))

;; part 2

(defn walk-2
  ([m]
   (walk-2 m false #{"start"} '("start")))
  ([m bonus seen [p & _ps :as path]]
   (if (= p "end")
     1
     (let [poss (get m p)]
       (if bonus
         ;; we've already doubled-up, so only unseen nodes
         (reduce #(+ %1 (walk-2 m
                                bonus
                                (if (lower-case? %2) (conj seen %2) seen)
                                (conj path %2)))
                 0
                 (remove #(seen %) poss))
         ;; no restrictions, but bonus=true if it's a previously seen node
         (reduce #(+ %1 (walk-2 m
                                (if (seen %2) true false)
                                (if (lower-case? %2) (conj seen %2) seen)
                                (conj path %2)))
                 0
                 poss))))))

(defn soln-2 [filename]
  (walk-2 (input-data filename)))

I have a solution that needs 50ms for Task 1 and 1,5s for Task 2. (After parsing) https://github.com/MrEbbinghaus/advent-of-code/blob/master/2021/day12.clj#L54 I first built up a prefix tree and then counted the number of leaves. (tree-seq) is nice for that. This took 3s for Task 2. But just recursively counting and summing the number of paths and not building the paths themselves is at least twice as fast.

https://gitlab.com/maximoburrito/advent2021/-/blob/main/src/day12/main.clj If I wrote code this ugly for work, I'd fire myself :)

I’m not proud of mine either, but fortunately it got the job done. I need to do some refactoring - my part2 takes 2.5s which seems too long.

You have me beat by about 25s.

Just part one for now: https://github.com/kconner/advent-of-code/blob/master/2021/12a.clj