Fork me on GitHub
<
2018-12-25
>
norman07:12:52

All done - hooray

3
1
misha07:12:50

day 23 2

norman07:12:54

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

misha07:12:03

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

misha07:12:42

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

misha08:12:17

out of 1000, 978 ranges intersect

Average-user15:12:41

@norman Which algorithm for connected components did you use?

norman15:12:40

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

norman15:12:08

That’s probably worth having in the toolbelt

Average-user15:12:26

my solution runs in 2s

Average-user15:12:08

yours takes over a minute

norman15:12:18

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

Average-user15:12:57

``````(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))))))
``````
This is an algorithm to detect connected components of a graph that I came u with past year, since there also was a problem of finding connected components. Don't know how good is it. But I compared the time it takes with http://clj-me.cgrand.net/2013/03/18/tarjans-strongly-connected-components-algorithm/ . And there is almost no difference

norman15:12:46

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

Average-user15:12:22

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