Test3 Preparation v2

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
Categories: Code, Creative, Design

Leave a reply

Your email address will not be published. Required fields are marked *