Fork me on GitHub
#adventofcode
<
2021-12-12
>
alekszelark04:12:35

🧵Day 12 answers thread: post your answers here

norman06:12:18

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

😅 1
👏 1
AC06:12:26

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.

norman06:12:27

You have me beat by about 25s.

😢 1
alekszelark08:12:06

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

nbardiuk09:12:16

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

jacoelho11:12:50

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

mikelis13:12:11

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

mikelis13:12:46

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

Antonio Bibiano13:12:20

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

Joe13:12:22

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))

👏 2
tschady14:12:25

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

👍 1
Antonio Bibiano14:12:08

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

tschady14:12:49

@U01HY37QQUA 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

Callum Oakley14:12:30

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

nice 3
👏 1
Antonio Bibiano15:12:06

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

Antonio Bibiano15:12:57

I like these counting solutions!

Sam Adams17:12:34

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

AC18:12:41

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..

1
euccastro20:12:32

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

karol20:12:33

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)))
😄

karol20:12:58

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

Stuart20:12:31

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)))
Part 2 is... running... Might have an answer some time Xmas day

😂 1
clojure-spin 2
🎄 1
Stuart21:12:56

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 ?

Stuart22:12:08

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?

genmeblog22:12:27

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

Stuart22:12:28

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.

kevinc22:12:26

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.

AC02:12:31

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)))

Björn Ebbinghaus02:12:39

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.

👍 1
Stuart18:12:22

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))))))))
My slowest solution so far this year

🙌 3
Stuart13:12:15

Havent' got a clue where to start today.

Joe13:12:03

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

Stuart17:12:10

This is annoying

'({:path ["start" "A" "c" "A" "b" "A" "end"], :finished true}
  [:path ["start" "A" "c" "A" "b" "d"]] [:finished true]  ;; <<< WTF
  {:path ["start" "A" "c" "A" "b" "end"], :finished true}
  {:path ["start" "A" "c" "A" "end"], :finished true}
  {:path ["start" "A" "b" "A" "c" "A" "end"], :finished true}
  {:path ["start" "A" "b" "A" "end"], :finished true}
  [:path ["start" "A" "b" "d"]] [:finished true] ;; << WTF
  {:path ["start" "A" "b" "end"], :finished true}
  {:path ["start" "A" "end"], :finished true}
  {:path ["start" "b" "A" "c" "A" "end"], :finished true}
  {:path ["start" "b" "A" "end"], :finished true}
  [:path ["start" "b" "d"]] [:finished true]  ;; <<< WTF
  {:path ["start" "b" "end"], :finished true})
At some point sometimes I'm going from a map to vectors, and I can't find why!

Antonio Bibiano19:12:20

did you find the problem in the end?

Stuart19:12:03

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.

💪 1
Stuart19:12:11

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

Benjamin18:12:40

Is the puzzle input 25 lines?

Stuart18:12:43

mines is 24

Stuart18:12:50

for day 12 (if that is what you are asking)