Count islands in a binary grid

Question

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

Answer 1

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)