Skip to content

Instantly share code, notes, and snippets.

@johnwalker
Created October 27, 2013 17:01
Show Gist options
  • Save johnwalker/7185017 to your computer and use it in GitHub Desktop.
Save johnwalker/7185017 to your computer and use it in GitHub Desktop.
Mostly works
(ns ieee2013.carpalind)
(require 'clojure.set)
(defn read-in []
(let [n (- (read-string (read-line)) 1)]
(clojure.string/trim
(apply str (for [x (range n)]
(str (read-line) " "))))))
(defn find-bottlenecks []
(let [input (read-in)
parsed-input (map keyword (clojure.string/split input #"\s+"))
vertices (set parsed-input)
edges (apply merge-with clojure.set/union (map #(hash-map (first %) #{(second %)}) (partition 2 parsed-input)))
pruned (clojure.set/difference vertices (apply clojure.set/union (vals edges)))]
(loop [k pruned
res []]
(let [next-keys (apply clojure.set/union (vals (select-keys edges k)))]
(if (seq next-keys)
(recur next-keys
(conj res k))
(conj res next-keys))))))
(doall (map (comp println name)
(reduce into (sorted-set)
(filter #(= (count %1) 1)
(find-bottlenecks)))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment