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)))))

user=> (main 4)
(1 1 1 0)
(1 1 0 0)
(0 0 0 1)
(1 1 1 0)
groups
[2 2] : [[2 1] [2 2] [1 2] [1 3] [0 3] [2 0]]
[3 2] : [[3 2] [3 0] [3 1]]
[1 1] : [[1 0] [0 0] [1 1] [0 1] [0 2]]
[3 3] : [[3 3]]
[2 3] : [[2 3]]
count 5
nil
user=> (main 4)
(1 1 0 0)
(1 1 0 1)
(1 1 1 0)
(1 0 1 0)
groups
[3 2] : [[2 1] [3 2] [1 0] [2 2] [0 0] [1 1] [0 1] [3 0] [2 0]]
[3 3] : [[3 3] [2 3]]
[1 2] : [[1 2] [0 2] [0 3]]
[1 3] : [[1 3]]
[3 1] : [[3 1]]
count 5
nil
user=> (main 5)
(0 0 1 1 1)
(0 1 0 1 0)
(0 0 1 0 0)
(1 0 0 0 1)
(1 1 0 0 0)
groups
[4 4] : [[2 1] [3 2] [4 3] [1 0] [3 3] [4 4] [0 0] [2 3] [0 1] [2 4] [1 4] [3 1] [4 2] [2 0]]
[2 2] : [[2 2]]
[1 1] : [[1 1]]
[3 4] : [[3 4]]
[1 2] : [[1 2]]
[1 3] : [[0 2] [1 3] [0 3] [0 4]]
[4 1] : [[4 0] [3 0] [4 1]]
count 7