# Island detection / Flood fill with clojure

May 9, 2018

I had already talked about a mutable version of this algorithm for flood filling island detection here. This time I went immutable with clojure The algorithm is a bit different, this we will not have a variable in the outer scope but pass a new instance of a board (which is efficiently managed by clojure) to the function for each iteration/recursion.

The full source is at https://gitlab.com/dendiz/kelimelik-clj/tree/master

there a few helper functions

`first-char-on-board` scans the board to find the first tile that is not empty `split` this will split a string such as “abc” into a vector as `["a" "b" "c"]`

the basic idea is to keep a list of next slots to visit on the board as we visit slots. the `next-frontier` function will return a list of next slots. This is basically BFS search on a graph.

``````(defn flood-fill
"flood fill the board starting from the first non empty slot.
the flooded slots will contain '!' empty slots '.'. If there
are islands they will contain letters.
"
[board]
(let [[y x] (first-char-on-board board)
board (mapv split board)
]
(loop [board board
frontier [[x y]]]
(if (-> frontier count zero?)
board
(let [front (first frontier)
x (first front)
y (second front)]
(recur
(assoc-in board [y x] "!")
(concat (next frontier) (next-frontier board [x y]))))))))

``````

the `next-frontier` code is also worth mentioning

``````(defn next-frontier
"return the coordinates of candidate neighbors for flood filling"
[board [x y]]
(for [i [(dec y) y (inc y)]
j [(dec x) x (inc x)]
:when (and (>= i 0)
(>= j 0)
(< i 15)
(< j 15)
(or (= x j) (= y i))
(not (and (= x j) (= y i)))
(not= "!" (get-in board [i j]))
(not= "." (get-in board [i j])))]
[j i]))
``````

`flood-fill` will mark visited slots with `!` and `next-frontier` will return a list of the candidate slot from the 8 neighbors of the current slot. if the neighbor is visited or empty it’s not included in the list.

if the starting board was like this

``````...a...
...bc..
..de...
``````

the flood would start with `a` and the `next-frontier` would return only `b` from the neighbors and mark `a` as `!`. `b` would return `c` and `e` and `d`. `a` would be marked as `!` so it would not be included. After the fill the board would be like

``````...!...
...!!..
..!!...
``````

this algorithm is useful when detecting if the scrabble board is connected.