import Data.List (transpose)
type Maze = [String]
sample1 :: Maze
sample1 = [“*********”,
“* * * *”,
“* * * * *”,
“* * * * *”,
“* * *”,
“******* *”,
” *”,
“*********”]
sample2 :: Maze
sample2 = [” “,
” “,
” *** “,
” *** “,
” *** “,
” “,
” “]
sample3 :: Maze
sample3 = [” * * “,
” ##### “,
” *** “,
” * * “,
” *** “,
” * “,
” “]
sample4 :: Maze
sample4 = [“*********”,
“*s* *e*”,
“* * * *”,
“* * * *”,
“* *”,
“******* *”,
” *”,
“*********”]
arrow :: Maze
arrow = [ “….#….”,
“…###…”,
“..#.#.#..”,
“.#..#..#.”,
“….#….”,
“….#….”,
“….#####”]
printMaze :: Maze -> IO ()
printMaze x = putStr (concat (map (++”\n”) x))
–Place one maze above another.
above x y =x++y
–Place two mazes side by side (consider, that they have the same height)
sideByside (x:xs) (y:ys)= (x++y) : sideByside xs ys
–Rotate maze to the left and to the right.
toRow xs = map (\x->[x]) xs
rotateR [x] = toRow x
rotateR (x:xs)= rotateR xs `sideByside` toRow x
rotateL [] = []
rotateL maze = reverse (transpose maze)
–ghci> getFromMaze sample1 (1,1)
‘ ‘
getFromMaze maze (row, col) = (maze !! row) !! col
–printMaze(putIntoMaze sample2 [(0,0,’1′),(6,6,’2′),(0,6,’3′)]) 1 3 *** *** *** 2
updateRow row col char = take col row ++ [char] ++ drop (col + 1) row
putIntoMazeHelper maze (row, col, char) =
take row maze ++ [updateRow (maze !! row) col char] ++ drop (row + 1) maze
putIntoMaze maze [] = maze
putIntoMaze maze (x:xs) = putIntoMaze (putIntoMazeHelper maze x) xs
–printMaze(getPart sample1 (1,1) (7,7)) * * * * * * * * * ****** *******
getPart maze (startRow, startCol) (height , width)= map (take width. drop startCol)(take height . drop startRow $ maze)
–Implement the function solveMaze. (path from ‘s’ to ‘e’)
solveMaze :: Result -> Int
solveMaze sample4
12
solveMaze maze = let
–flatten the maze into a list of (row,col,char) triplets
allPositions= concat [[(row,col,char)|(col,char)<- zip [0..] line]|(row,line)<-zip [0..]maze]
–find the starting and ending positions
(startR,startC, _ )= head $ filter (matchesChar ‘s’) allPositions
(endR, endC,_ )=head $ filter (matchesChar ‘e’) allPositions
–filter positions that are either free spaces (‘ ‘) or the end (‘e’)
freePositions =[(row,col)| (row,col,char)<-allPositions, char ==’ ‘||char ==’e’]
–BFS function to solve maze
bfs [] _=[]
bfs ((row,col,dist):rest) remaining=
let
neighbors =[(r, c) | (r, c) <- [(row + 1, col), (row – 1, col), (row, col + 1), (row, col – 1)], (r, c) `elem` remaining]
updatedRemaining =[pos | pos <- remaining, pos `notElem` neighbors]
in
(row, col, dist) : bfs (rest ++ [(r, c, dist + 1) | (r, c) <- neighbors]) updatedRemaining
–find solution using BFS
solution = bfs [(startR, startC, 0)] freePositions
in
–extract the distant of the end position from the BfS result
head [dist | (row, col, dist) <- solution, row == endR, col == endC]
matchesChar char (_, _, c) = c == char
