Clojurians Log v2

They are talking about day 9

All done - hooray

day 23 2 :harold:

Honestly, I lucked my way through that one at the repl. It’s the only one I’m not sure I could do from scratch again. I still don’t know what a correct algorithm is. 😞

I am reusing today's solution for 23/2 right now : )

at this point I'll accept anything under 30minutes, will see how it goes

out of 1000, 978 ranges intersect

@norman Which algorithm for connected components did you use?

(for Day25)

For search? Just a simple bfs https://github.com/orb/advent2018/blob/master/src/advent2018/day25.clj#L36

I’m looking at ubergraph at the moment though https://github.com/Engelberg/ubergraph

That’s probably worth having in the toolbelt

my solution runs in 2s

yours takes over a minute

Yeah. It was 1am when I got started. I’m really surprised it runs 🙂

at all

(defn connected-with [x graph]
  (loop [gs graph, cs #{x}]
    (let [ng (mapcat #(get gs %) cs)]
      (if (empty? ng)
        [cs gs]          
        (recur (reduce dissoc gs cs) (reduce conj cs ng))))))

(defn find-connected
  "Graph should be a map from nodes to their neighbors"
  [graph]
  (loop [gs graph, ac #{}]
    (if (empty? gs)
      ac
      (let [[cs ngs] (connected-with (ffirst gs) gs)]
        (recur ngs (conj ac cs))))))

All the work in my solution is that nest for loop. O(n^2).

I'm wondering if by some chance I accidentally implemented an already known connected components algorithm. Or something very similar