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)