Sample question2

-- Question:
-- Modify the BFS algorithm to return a list of all reachable points from the start position (1, 1) in the following maze:
-- Write a function reachablePoints :: Maze -> Position -> [Position].
-- Example Output: For the start (1, 1), the output should be:
-- [(1,1), (2,1), (3,1), (4,1), (5,1), (5,2), (5,3), (5,4), (5,5)]

type Maze = [String]
type Position = (Int, Int)

-- Check if a position is valid for movement
isValid :: Maze -> Position -> Bool
isValid maze (x, y) =
  x >= 0 && x < length maze &&
  y >= 0 && y < length (head maze) &&
  (maze !! x !! y == ' ')

-- BFS to find all reachable points
reachablePoints :: Maze -> Position -> [Position]
reachablePoints maze start = bfs [start] [] []
  where
    -- BFS function
    bfs :: [Position] -> [Position] -> [Position] -> [Position]
    bfs [] _ reachable = reachable
    bfs (current:queue) visited reachable
      | current `elem` visited = bfs queue visited reachable
      | otherwise =
          let (x, y) = current
              neighbors = filter (isValid maze) 
                          [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
              newQueue = queue ++ filter (`notElem` visited) neighbors
          in bfs newQueue (current : visited) (reachable ++ [current])

sample1 :: Maze
sample1 =
  [ "*********"
  , "* *   * *"
  , "* * * * *"
  , "* * * * *"
  , "*   *   *"
  , "******* *"
  , "        *"
  , "*********"
  ]

printMaze :: Maze -> IO ()
printMaze x = putStr (concat (map (++ "\n") x))

-- 3. Count the Steps in Shortest Path

-- Question:
-- Write a function shortestPathLength :: Maze -> Position -> Position -> Int 
-- that returns the number of steps in the shortest path between two positions. Use the following maze:

shortestPathLength :: Maze -> Position -> Position -> Int
shortestPathLength maze start end = bfs [start] 0 []
  where
    bfs :: [Position] -> Int -> [Position] -> Int
    bfs [] _ _ = -1 -- return -1 if there is no path
    bfs (current:queue) steps visited
      | current == end = steps -- return the number of steps when the end is reached
      | current `elem` visited = bfs queue steps visited
      | otherwise =
          let (x, y) = current
              neighbors = filter (isValid maze) 
                          [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
              newQueue = queue ++ filter (`notElem` visited) neighbors
          in bfs newQueue (steps + 1) (current : visited)

-- Write a function generateDistanceMap :: Maze -> Position -> [[Int]] 
-- that generates a grid where each cell contains the distance from the start position.
-- Unreachable cells should contain -1. Use this maze
-- (Chức năng generateDistanceMap chưa được cung cấp trong yêu cầu ban đầu)

-- Write a function isReachable :: Maze -> Position -> Position -> Bool 
-- that returns True if there is a path from the start to the goal, and False otherwise. Use the maze:

isReachable :: Maze -> Position -> Position -> Bool
isReachable maze start goal = bfs [start] []
  where
    bfs :: [Position] -> [Position] -> Bool
    bfs [] _ = False
    bfs (current:queue) visited
      | current == goal = True
      | current `elem` visited = bfs queue visited
      | otherwise =
          let (x, y) = current
              neighbors = filter (isValid maze) 
                          [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
              newQueue = queue ++ [n | n <- neighbors, n `notElem` visited]
          in bfs newQueue (current : visited)

-- Write a function longestPath :: Maze -> Position -> Position -> Int 
-- that finds the longest possible path between two points in a maze. 
-- Assume the maze may have loops and cycles, and all cells are reachable.

longestPath :: Maze -> Position -> Position -> Int
longestPath maze start end = dfs start [] 0
  where
    dfs :: Position -> [Position] -> Int -> Int
    dfs current visited currentLength
      | current == end = currentLength -- Goal reached, return the path length
      | otherwise =
          let (x, y) = current
              neighbors = filter (`notElem` visited) $
                          filter (isValid maze) 
                          [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
              pathLengths = [dfs n (current : visited) (currentLength + 1) | n <- neighbors]
          in if null pathLengths 
                then currentLength 
                else maximum pathLengths

-- Hàm main để chạy chương trình và kiểm tra các hàm
main :: IO ()
main = do
  putStrLn "Maze:"
  printMaze sample1

  let start = (1, 1)
  let reachable = reachablePoints sample1 start
  putStrLn "\nReachable Points from (1,1):"
  print reachable

  let end = (5, 5)
  let steps = shortestPathLength sample1 start end
  putStrLn $ "\nShortest path length from " ++ show start ++ " to " ++ show end ++ ": " ++ show steps

  let reachableCheck = isReachable sample1 start end
  putStrLn $ "\nIs reachable from " ++ show start ++ " to " ++ show end ++ ": " ++ show reachableCheck

  let longest = longestPath sample1 start end
  putStrLn $ "\nLongest path length from " ++ show start ++ " to " ++ show end ++ ": " ++ show longest

Result

Maze:
*********
* *   * *
* * * * *
* * * * *
*   *   *
******* *
        *
*********

Reachable Points from (1,1):
[(1,1),(2,1),(3,1),(4,1),(4,2),(4,3),(3,3),(2,3),(1,3),(1,4),(1,5),(2,5),(3,5),(4,5),(4,6),(4,7),(3,7),(5,7),(2,7),(6,7),(1,7),(6,6),(6,5),(6,4),(6,3),(6,2),(6,1),(6,0)]

Shortest path length from (1,1) to (5,5): -1

Is reachable from (1,1) to (5,5): False

Longest path length from (1,1) to (5,5): 24