# Count islands in a binary grid

This is the No of Island code challenge. Please review my implementation in Haskell. I know there must be some better way of doing this.

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

### Input:

1  1  1  1  0
1  1  0  1  0
1  1  0  0  0
0  0  0  0  0


### Output:

1


# Solution:

-- leetcode number of island
import qualified Data.Vector as V
import Data.Maybe
{--
1  1  1  1  0
1  1  0  1  0
1  1  0  0  0
0  0  0  0  0
--}
data Visited = N | O deriving (Eq, Show)
data Cell = Cell Int Int Visited deriving (Show)
-- Function to compare the cells
instance Eq Cell where
(==) (Cell r0 c0 _) (Cell r1 c1 _) = r0 == r1 && c0 == c1

-- main function takes the Vector Vector Int
islands :: V.Vector (V.Vector Int) -> [Cell]
islands v = islandhelper1 (0,0) []
where
-- fetch the row
islandhelper1 :: (Int, Int) ->  [Cell] -> [Cell]
islandhelper1 b@(r, c) cell = case v V.!? r of
Just x -> islandhelper2 x b  cell
_ -> cell
-- fetch the cell and then call neighbors on it
islandhelper2 :: V.Vector Int -> (Int, Int) ->  [Cell] -> [Cell]
islandhelper2 rw (r, c)  cells = case rw V.!? c of
Just 1 -> islandhelper2 rw (r, c + 1)  (getNeighbors v (r,c) cells)
Just 0 -> islandhelper2 rw (r, c+ 1)  cells
_ -> islandhelper1 (r + 1, 0)  cells

-- fetch the neighbors
-- add initial cell and neighboring cells
getNeighbors:: V.Vector (V.Vector Int) -> (Int, Int) -> [Cell] -> [Cell]
getNeighbors v (r, c) clls =   initcl ++ getnbs4
where
getnbs4:: [Cell]
getnbs4 = catMaybes $map clfilter [(0,1),(1, 0),(0, -1),(-1, 0)] clfilter:: (Int, Int) -> Maybe Cell clfilter (r', c') = let m = r' + r n = c' + c in case getCellValue v (m, n) of Just (1, cl@(Cell m' n' _)) -> if cl elem clls then Nothing else Just (Cell m' n' O) _ -> Nothing initcl :: [Cell] initcl = case getCellValue v (r,c) of Just (1, cl@(Cell m' n' _)) -> if cl elem clls then clls else ((Cell m' n' N) : clls) _ -> clls -- get the cell value getCellValue::V.Vector (V.Vector Int) -> (Int, Int) -> Maybe (Int, Cell) getCellValue v (r, c) = case v V.!? r of Just x -> case x V.!? c of Just m -> Just (m, Cell r c O) _ -> Nothing _ -> Nothing -- to Filter the cell based on N isNew :: Cell -> Bool isNew (Cell _ _ k) = k == N -- Converts list to vector ltoV :: [a] -> V.Vector a ltoV = V.fromList -- converts the String to Int vector conV :: String -> V.Vector Int conV = ltoV . map (read::String -> Int) . words main::IO() main = do content <- ltoV . ( map conV) . lines <$> readFile "noofisland.txt"
print $length . filter isNew$ islands content



## Edit: all of the below was premature.

The basic algorithm you're using doesn't work. Try this test case:

0 0 0 0 0 0
0 1 1 1 1 0
0 0 0 0 1 0
0 1 0 0 1 0
0 1 1 1 1 0
0 0 0 0 0 0


The usual comments of Code Review apply: Use a linter. Name things clearly. (You've got at least one test case, so that's good!)

Some Haskell-specific code-smell stuff also applies:

• Visited is used like a Bool, so let it be a Bool. (You can wrap it up various different ways for clarity though!)
• At the same time, your use of Int to represent the land/water distinction isn't great. What if a 3 snuck in by mistake? Again, wrap up a bool!
• Use record types to name data fields.
• I suggest using type applications for things like read instead of an inline type hint.
• There's probably a better way to write getCellValue using lenses, but in this case I'd leverage the Maybe monad.
• In general, learning more abstractions will be good. For example, if I introduce a Coordinates type to wrap up (Int, Int), I can make it an instance of Semigroup and Monoid.
• getCellValue returns a lot of redundant data; simplify it down to just get the new stuff. This will push a little extra complexity up into the places where it's used, but the complexity belongs there (and can be resolved there).

With respect to the algorithm: Instead of checking if each element is already in the list, consider always adding everything and then using nub at the end. This relies on the specific behavior of nubBy (it keeps the first match). So the code does get a little more fragile, but it enables substantial simplification!

Also, in your list of ±1 offsets, there's no reason to be searching backward; you already checked those cells!

I've been a bit lazy documenting my process, but the above got me to

import Data.Function (on)
import Data.List (nubBy)
import Data.Maybe
import qualified Data.Vector as V

newtype Terrain = Terrain{isLand :: Bool}

data Coordinates = Coord{row :: Int, column :: Int} deriving (Eq, Ord, Show)
instance Semigroup Coordinates where
(Coord r1 c1) <> (Coord r2 c2) = Coord (r1 + r2) (c1 + c2)
instance Monoid Coordinates where
mempty = Coord 0 0
incementColumn :: Coordinates -> Coordinates
incementColumn (Coord r c) = Coord r (c + 1)

data Cell = Cell {
coordinates :: Coordinates,
isNew :: Bool
} deriving (Show)

islands :: V.Vector (V.Vector Terrain) -> Int
islands oceanscape = length . filter isNew . nubBy ((==) on coordinates) . reverse $islandhelper1 mempty [] where islandhelper1 :: Coordinates -> [Cell] -> [Cell] islandhelper1 coord cells = case oceanscape V.!? row coord of Just rowVector -> islandhelper2 rowVector coord cells _ -> cells islandhelper2 :: V.Vector Terrain -> Coordinates -> [Cell] -> [Cell] islandhelper2 rowVector coord cells = case rowVector V.!? column coord of Just (Terrain True) -> islandhelper2 rowVector (incementColumn coord) (getNeighbors oceanscape coord ++ Cell coord True : cells) Just (Terrain False) -> islandhelper2 rowVector (incementColumn coord) cells _ -> islandhelper1 (Coord{row = row coord + 1, column = 0}) cells getNeighbors:: V.Vector (V.Vector Terrain) -> Coordinates -> [Cell] getNeighbors oceanscape coord = mapMaybe (clfilter . (coord <>) . uncurry Coord) [(0,1), (1,0)] where clfilter :: Coordinates -> Maybe Cell clfilter coord' = do -- The Maybe Monad! Terrain True <- oceanscape !? coord' -- pattern match failure will yield Nothing. return$ Cell coord' False

-- get the cell value
(!?) :: V.Vector (V.Vector a) -> Coordinates -> Maybe a
oceanscape !? coord = do  -- The Maybe Monad!
x <- oceanscape V.!? row coord
x V.!? column coord


At this point we can see that the entire recursive structure of islands is just generating 0-5 items for each step of an iteration, so let's use fmap. (Even if we did need to be examining the accumulator, we could still use a fold.)

Here's my final version. I'm pretty sure there's a better way to build locations, but I gotta go do actual work :) There are probably even better ways of thinking about the whole problem, but at that point we'd be changing your fundamental algorithm, so that's out of scope.

module Main where

import Data.Function (on)
import Data.List (nubBy)
import Data.Maybe
import qualified Data.Vector as V

newtype Terrain = Terrain{isLand :: Bool}

data Coordinates = Coord{row :: Int, column :: Int} deriving (Eq, Ord, Show)
instance Semigroup Coordinates where
(Coord r1 c1) <> (Coord r2 c2) = Coord (r1 + r2) (c1 + c2)

data Cell = Cell {
coordinates :: Coordinates,
isNew :: Bool
} deriving (Show)

islands :: V.Vector (V.Vector Terrain) -> Int
islands oceanscape = length . filter isNew . nubBy ((==) on coordinates) $islandHelper concatMap locations where islandHelper :: (Coordinates, Terrain) -> [Cell] islandHelper (coord, Terrain True) = Cell coord True : getNeighbors oceanscape coord islandHelper (_, Terrain False) = [] locations :: V.Vector (Coordinates, Terrain) locations = do -- The Vector Monad! (rowIndex, rowVector) <- V.generate (length oceanscape) id V.zip oceanscape (columnIndex, value) <- V.generate (length rowVector) id V.zip rowVector return (Coord{row=rowIndex, column=columnIndex}, value) getNeighbors:: V.Vector (V.Vector Terrain) -> Coordinates -> [Cell] getNeighbors oceanscape coord = mapMaybe (clfilter . (coord <>) . uncurry Coord) [(0,1), (1,0)] where clfilter :: Coordinates -> Maybe Cell clfilter coord' = do -- The Maybe Monad! Terrain True <- oceanscape !? coord' -- pattern match failure will yield Nothing. return$ Cell coord' False

-- get the cell value
(!?) :: V.Vector (V.Vector a) -> Coordinates -> Maybe a
oceanscape !? coord = do  -- The Maybe Monad!
x <- oceanscape V.!? row coord
x V.!? column coord

main::IO()
main = do
content1 <- parse <$> readFile "code_review_283543_1.test" print$ islands content1
content2 <- parse <$> readFile "code_review_283543_2.test" print$ islands content2
content3 <- parse <$> readFile "code_review_283543_3.test" print$ islands content3
content4 <- parse <$> readFile "code_review_283543_4.test" print$ islands content4
content8 <- parse <$> readFile "code_review_283543_8.test" print$ islands content8
where parse :: String -> V.Vector (V.Vector Terrain)
parse = V.fromList . map (V.fromList . map parseCell . words) . lines
parseCell = Terrain . (/= 0) . (read @Int)

• Thank you very much for your time. This helps a lot. Mar 2 at 3:55