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 :: Maze -> Maze -> Maze
above x y = x ++ y
-- Place two mazes side by side (assumes same height)
sideBySide :: Maze -> Maze -> Maze
sideBySide (x:xs) (y:ys) = (x ++ y) : sideBySide xs ys
sideBySide [] [] = []
sideBySide _ _ = error "Mazes must have the same height"
-- Rotate maze to the right.
toRow :: [a] -> [[a]]
toRow xs = map (\x -> [x]) xs
rotateR :: Maze -> Maze
rotateR [x] = toRow x
rotateR (x:xs) = rotateR xs `sideBySide` toRow x
-- Rotate maze to the left.
rotateL :: Maze -> Maze
rotateL [] = []
rotateL maze = reverse (transpose maze)
-- ghci> getFromMaze sample1 (1,1) ' '
getFromMaze :: Maze -> (Int, Int) -> Char
getFromMaze maze (row, col) = (maze !! row) !! col
-- printMaze(putIntoMaze sample2 [(0,0,'1'),(6,6,'2'),(0,6,'3')])
updateRow :: [a] -> Int -> a -> [a]
updateRow row col char = take col row ++ [char] ++ drop (col + 1) row
putIntoMazeHelper :: Maze -> (Int, Int, Char) -> Maze
putIntoMazeHelper maze (row, col, char) =
take row maze ++ [updateRow (maze !! row) col char] ++ drop (row + 1) maze
putIntoMaze :: Maze -> [(Int, Int, Char)] -> Maze
putIntoMaze maze [] = maze
putIntoMaze maze (x:xs) = putIntoMaze (putIntoMazeHelper maze x) xs
-- printMaze(getPart sample1 (1,1) (7,7))
getPart :: Maze -> (Int, Int) -> (Int, Int) -> Maze
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 :: Maze -> Int
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 :: [(Int, Int, Int)] -> [(Int, Int)] -> [(Int, Int, Int)]
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 distance of the end position from the BFS result
head [ dist | (row, col, dist) <- solution, row == endR, col == endC ]
matchesChar :: Char -> (Int, Int, Char) -> Bool
matchesChar ch (_, _, c) = c == ch