This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2018-12-25
Channels
- # adventofcode (18)
- # announcements (10)
- # beginners (59)
- # calva (9)
- # cider (1)
- # clojure (43)
- # clojure-austin (1)
- # clojure-europe (6)
- # clojure-italy (2)
- # clojure-nl (1)
- # clojure-uk (3)
- # clojurescript (8)
- # cursive (3)
- # emacs (3)
- # fulcro (3)
- # hoplon (1)
- # klipse (1)
- # off-topic (24)
- # reagent (2)
- # reitit (1)
- # shadow-cljs (41)
- # specter (5)
- # vim (1)
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. 😞
@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
my solution runs in 2s
yours takes over a minute
(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 differenceI'm wondering if by some chance I accidentally implemented an already known connected components algorithm. Or something very similar