xmonkee/find-islands.clj

## find-islands.clj
;"Find number of disjoint islands in a square matrix of 0's and 1's"

(defn rand-mat [size]
"Make a random matrix of 1's and 0's"
  (vec (for [i (range size)]
         (vec (for [j (range size)]
               [(-> 2 rand int) [i j]])))))

(defn print-mat [mat]
"Print the matrix"
  (doseq [r mat]
    (println (map first r))))

(defn- make-pairs-helper [mat size]
"Go through each element and add it's right neighbor or down-neighbor if any
of them have the same number (0 or 1)"
  (for [i (range size)
        j (range size)
        ns [[i (inc j)] [(inc i) j]]
        :let [[c xy] (get-in mat [i j])]]
    (when-let [[c2 xy2] (get-in mat ns)]
      (when (= c c2) [xy xy2]))))

(defn make-pairs [mat]
  (let [size (count mat)
        pr (make-pairs-helper mat size)]
    (filter identity pr))) ;Remove nils

(defn make-datamap [mat size]
"Initial union-find where each element has itself as root"
  (into {} (for [r mat [val xy] r]
             [xy xy])))

(defn root [datamap el]
"Return the root of the root of the root... till it returns itself"
  (if (= el (datamap el))
    el
    (recur datamap (datamap el))))

(defn union [datamap [el1 el2]]
"make root of element1 refer to root of element 2"
  (assoc datamap (root datamap el1) (root datamap el2)))

(defn main [size]
"Putting it all together"
  (let [mat (rand-mat size)
        init (make-datamap mat size)
        pairs (make-pairs mat)
        final (reduce union init pairs)
        groups (group-by (partial root final) (keys final))]
        (do
          (print-mat mat)
          (println "groups")
          (doseq [[group-name els] groups]
            (println group-name " : " els))
          (println "count" (count groups)))))
	;"Find number of disjoint islands in a square matrix of 0's and 1's"

	(defn rand-mat [size]
	"Make a random matrix of 1's and 0's"
	(vec (for [i (range size)]
	(vec (for [j (range size)]
	[(-> 2 rand int) [i j]])))))

	(defn print-mat [mat]
	"Print the matrix"
	(doseq [r mat]
	(println (map first r))))

	(defn- make-pairs-helper [mat size]
	"Go through each element and add it's right neighbor or down-neighbor if any
	of them have the same number (0 or 1)"
	(for [i (range size)
	j (range size)
	ns [[i (inc j)] [(inc i) j]]
	:let [[c xy] (get-in mat [i j])]]
	(when-let [[c2 xy2] (get-in mat ns)]
	(when (= c c2) [xy xy2]))))

	(defn make-pairs [mat]
	(let [size (count mat)
	pr (make-pairs-helper mat size)]
	(filter identity pr))) ;Remove nils

	(defn make-datamap [mat size]
	"Initial union-find where each element has itself as root"
	(into {} (for [r mat [val xy] r]
	[xy xy])))

	(defn root [datamap el]
	"Return the root of the root of the root... till it returns itself"
	(if (= el (datamap el))
	el
	(recur datamap (datamap el))))

	(defn union [datamap [el1 el2]]
	"make root of element1 refer to root of element 2"
	(assoc datamap (root datamap el1) (root datamap el2)))

	(defn main [size]
	"Putting it all together"
	(let [mat (rand-mat size)
	init (make-datamap mat size)
	pairs (make-pairs mat)
	final (reduce union init pairs)
	groups (group-by (partial root final) (keys final))]
	(do
	(print-mat mat)
	(println "groups")
	(doseq [[group-name els] groups]
	(println group-name " : " els))
	(println "count" (count groups)))))