Skip to content

Instantly share code, notes, and snippets.

@zerg000000
Last active February 6, 2019 05:09
Show Gist options
  • Save zerg000000/0e3ed6d43fc6b30e1f489efac60f5560 to your computer and use it in GitHub Desktop.
Save zerg000000/0e3ed6d43fc6b30e1f489efac60f5560 to your computer and use it in GitHub Desktop.
answer
(require '[clojure.set :as s])
;; Graph Data from the Picture
(def graph [#{:a :b}
#{:a :d}
#{:a :h}
#{:b :c}
#{:b :d}
#{:d :c}
#{:d :e}
#{:c :f}
#{:f :e}
#{:f :g}
#{:e :h}
#{:h :g}])
(defn walkable? [node edge]
(edge node))
; unit test
(walkable? :a #{:a :b})
(walkable? :b #{:a :b})
(walkable? :c #{:a :b})
(defn visited? [node path]
(some #(= node %) path))
; unit test
(visited? :a [:a :b :c])
(visited? :e [:a :b :c])
(defn next-node [at-node edge]
(first (disj edge at-node)))
; unit test
(next-node :a #{:a :b})
(next-node :b #{:c :b})
(defn possible-edges [graph at path]
(filter (fn [edge]
(let [next (next-node at edge)]
(and (walkable? at edge)
(not (visited? next path)))))
graph))
; unit test
(possible-edges graph :a [:a])
(possible-edges graph :b [:a :b])
(defn walk [graph paths start end at path]
(if (and (visited? start path) (visited? end path))
(conj paths path)
(when-let [nexts (->> (possible-edges graph at path)
(map #(next-node at %)))]
(apply s/union paths (map #(walk graph paths start end % (conj path %))
nexts)))))
(defn all-paths [graph start end]
(walk graph #{} start end start [start]))
(defn shortest [graph start end]
(-> (all-paths graph start end)
vec
sort
first))
(comment
(-> (all-paths graph :a :h)
vec
sort)
; answer
([:a :h]
[:a :d :e :h]
[:a :b :d :e :h]
[:a :b :c :d :e :h]
[:a :b :c :f :e :h]
[:a :b :c :f :g :h]
[:a :d :c :f :e :h]
[:a :d :c :f :g :h]
[:a :d :e :f :g :h]
[:a :b :d :c :f :e :h]
[:a :b :d :c :f :g :h]
[:a :b :d :e :f :g :h]
[:a :d :b :c :f :e :h]
[:a :d :b :c :f :g :h]
[:a :b :c :d :e :f :g :h])
(count (all-paths graph :a :h))
; answer
15
(shortest graph :a :h)
; answer
[:a :h])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment