[Haskell-beginners] First code review

[Brent Yorgey]

On Sat, Feb 23, 2013 at 04:39:53PM +0100, Emanuel Koczwara wrote:
> Hi,
> 
> Note: Following code is a solution for a problem from hackerrank.com
> (Category: Artifical Intelligence / Single Player Games / Bot saves
> princess).

Looks pretty good overall.  One note is that using lists of lists for
Grid and Heuristic will be slow, especially Heuristic since you do
lots of repeated lookups.  For small grids it really doesn't make much
difference, but if you wanted to run it on larger grids you might
notice.  Since both the Grid and Heuristic values are created once and
then used in a read-only fasion, this is a perfect opportunity to use
arrays: see 

  http://hackage.haskell.org/packages/archive/array/latest/doc/html/Data-Array.html

Using read-only arrays is really quite simple (as opposed to
read/write arrays which require a monad of some sort).

-Brent

> 
> Here is my first Haskell code! Short explanation of the problem: it's
> standard path finding problem, we have a matrix where 'm' denotes the
> bot, 'p' denotes the princess and '-' is for empty space.
> 
> Sample input (grid size followed by the grid itself, where each row is
> separated by new line):
> 
> 3
> ---
> -m-
> p--
> 
> Sample output:
> 
> DOWN
> LEFT
> 
> Here is the code:
> 
> module Main where
> 
> import Data.List
> import Data.Maybe
> 
> type Size = Int
> 
> type Grid = [String]
> 
> type Path = [Move]
> 
> type Heuristic = [[Int]]
> 
> type Position = (Int,Int)
> 
> data Move = LEFT | RIGHT | UP | DOWN deriving Show
> 
> getSize :: IO Size
> getSize = readLn
> 
> getGrid :: Size -> IO Grid
> getGrid s = sequence $ replicate s getLine
> 
> getHeuristic :: Size -> Position -> Heuristic
> getHeuristic s p = map (getHeuristic' s p) [0..s-1]
> 
> getHeuristic' :: Size -> Position -> Int -> [Int]
> getHeuristic' s p y = map (getHeuristic'' p y) [0..s-1]
> 
> getHeuristic'' :: Position -> Int -> Int -> Int
> getHeuristic'' (x2, y2) y1 x1 = abs (x1 - x2) + (abs (y1 - y2))
> 
> getPos :: Char -> Size -> Grid -> Position
> getPos c s g = (i `mod` s, i `div` s)
>   where g' = concat g
>         i = fromJust $ elemIndex c g'
> 
> getSteps :: Size -> Heuristic -> Position -> Position -> Path
> getSteps s h b p | b == p = []
>                  | otherwise = let (m,b') = getStep s h b 
>                                in m : (getSteps s h b' p)
> 
> getStep :: Size -> Heuristic -> Position -> (Move,Position)
> getStep s h b = head $ sortBy compareCost (getAvailableSteps s h b)
>   where compareCost (_,(x1,y1)) (_,(x2,y2)) = 
>           compare (h !! y1 !! x1) (h !! y2 !! x2)
> 
> getAvailableSteps :: Size -> Heuristic -> Position -> [(Move,Position)]
> getAvailableSteps s h (x,y) = up ++ down ++ left ++ right
>   where up = if y > 0 then [(UP, (x, y - 1))] else []
>         down = if y < (s - 1) then [(DOWN, (x, y + 1))] else []
>         left = if x > 0 then [(LEFT, (x - 1, y))] else []
>         right = if x < (s - 1) then [(RIGHT, (x + 1, y))] else []
> 
> main :: IO ()
> main = do
>   size <- getSize
>   grid <- getGrid size
>   let botPos = getPos 'm' size grid
>       princessPos = getPos 'p' size grid
>       heuristic = getHeuristic size princessPos
>       result = getSteps size heuristic botPos princessPos
>   mapM_ print result
> 
> Please point out all my mistakes.
> 
> Emanuel
> 
> 
> 
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners