# 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.