Emanuel Koczwara poczta at emanuelkoczwara.pl
Sat Feb 23 16:39:53 CET 2013

```Hi,

Note: Following code is a solution for a problem from hackerrank.com
(Category: Artifical Intelligence / Single Player Games / Bot saves
princess).

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

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

```