Home Preparation For Test 3 – 2024
The task requires implementing a function makePath
that calculates the shortest path in a maze using breadth-first search (BFS) and marks each step of the path on the maze. Below is the implementation:
type Maze = [String]
type Position = (Int, Int)
type Queue = [(Position, [Position])]
printMaze :: Maze -> IO ()
printMaze x = putStr (concat (map (++"\n") x))
getFromMaze :: Maze -> Position -> Char
getFromMaze maze (row, col) = (maze !! row) !! col
putIntoMaze :: Maze -> [(Int, Int, Char)] -> Maze
putIntoMaze maze [] = maze
putIntoMaze maze ((row, col, c):rest) =
let rowStr = maze !! row
newRow = take col rowStr ++ [c] ++ drop (col + 1) rowStr
newMaze = take row maze ++ [newRow] ++ drop (row + 1) maze
in putIntoMaze newMaze rest
bfs :: Maze -> Position -> Position -> Maybe [Position]
bfs maze start end = bfs' [(start, [start])] []
where
height = length maze
width = length (head maze)
bfs' :: Queue -> [Position] -> Maybe [Position]
bfs' [] _ = Nothing
bfs' ((pos, path):rest) visited
| pos == end = Just path
| pos `elem` visited = bfs' rest visited
| otherwise = bfs' (rest ++ neighbors) (pos:visited)
where
neighbors = [(next, path ++ [next]) | next <- validMoves pos]
validMoves (r, c) = filter isValid [(r+1,c), (r-1,c), (r,c+1), (r,c-1)]
isValid p@(r, c) = r >= 0 && r < height &&
c >= 0 && c < width &&
getFromMaze maze p /= '*' &&
p `notElem` visited
makePath :: Maze -> Position -> Position -> Maze
makePath maze start end =
case bfs maze start end of
Nothing -> maze
Just path -> putIntoMaze maze (zipWith makeMark [0..] path)
where
makeMark n pos = (fst pos, snd pos, intToChar n)
intToChar n | n > 9 = head $ show (n `mod` 10)
| otherwise = head $ show n
sample1 :: Maze
sample1 = ["*********",
"* * * *",
"* * * * *",
"* * * * *",
"* * *",
"******* *",
" *",
"*********"]
sample2 :: Maze
sample2 = [" ",
" ",
" *** ",
" *** ",
" *** ",
" ",
" "]
main :: IO ()
main = do
putStrLn "Sample 1:"
printMaze (makePath sample1 (1,1) (6,1))
putStrLn "\nSample 2:"
printMaze (makePath sample2 (5,5) (1,1))
Results:
Sample 1:
*********
*0*890* *
*1*7*1* *
*2*6*2* *
*345*345*
*******6*
3210987*
*********
Sample 2:
87654
***3
***2
***1
0