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

All done - hooray

misha07:12:50

day 23 2 harold

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

lucaspolymeris15: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

lucaspolymeris15:12:26

my solution runs in 2s

lucaspolymeris15:12:08

yours takes over a minute

norman15:12:18

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

lucaspolymeris15: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).

lucaspolymeris15:12:22

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