**Keywords: **
visit slot, mark visit, kelimelik clj, board, return, list, algorithm, clojure, function, flood, empty, dendiz, source.
*Powered by TextRank.*

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.

*Powered by TF-IDF/Cosine similarity*

First published on 2018-05-09

Generated on May 29, 2024, 10:02 PM

Mobile optimized version. Desktop version.