maze solver (haskell version. 제대로 안돌아감)

maze_with_bug.hs

-- 하스켈을 이용해 미로를 표현하라.
-- Maze 자료형과 Node 자료형이 필요할 것이다.
-- 주어진 좌표에 따라 하나의 노드를 리턴하는 함수도 필요하다.
-- 그렇게 리턴된 노드는 다른 노드로 넘어갈 수 있는 출구의 리스트를 담고 있어야한다.

-- 미로를 해결하기 위해 리스트 모나드를 사용하라.

module Main where

data Maze t = Maze [[t]] deriving (Show)
data Node p g = Node p p g deriving (Show)

nodeGetX (Node x y g) = x
nodeGetY (Node x y g) = y

nodeEq (Node x1 y1 g1) (Node x2 y2 g2) = (x1 == x2) && (y1 == y2) && (g1 == g2)

mazeHeight (Maze grid) = length grid
mazeWidth (Maze grid) = length (head (take 1 grid))

mazeStartNode maze =
  let (node, succ) = head (filter (\(node, s) -> s) (mazeFindSpeialType maze gridTypeStart))
  in node

mazeFinishNode maze =
  let (node, succ) = head (filter (\(node, s) -> s) (mazeFindSpeialType maze gridTypeFinish))
  in node

mazeFindSpeialType maze gridType =
  do x <- [0..(mazeWidth maze)-1]; y <- [0..(mazeHeight maze)-1];
     let { node = getNode maze x y; (Node px py g) = node };
     if g == gridType
       then return (node, True)
       else return (node, False)


gridTypePath = 'x'
gridTypeWall = '.'
gridTypeStart = 'S'
gridTypeFinish = 'G'

accessGridType grid x y =
  let line = head (take 1 (drop y grid))
  in head (take 1 (drop x line))

gridType grid x y
  | x < 0 = gridTypeWall
  | x >= mazeWidth (Maze grid) = gridTypeWall
  | y < 0 = gridTypeWall
  | y >= mazeHeight (Maze grid) = gridTypeWall
  | otherwise = accessGridType grid x y

getNextNodes (Maze grid) x y =
  let up = Node x (y + 1) (gridType grid x (y + 1))
      right = Node (x + 1) y (gridType grid (x + 1) y)
      down = Node x (y - 1) (gridType grid x (y - 1))
      left = Node (x - 1) y (gridType grid (x - 1) y)
      allNodes = [up, right, down, left]
  in
    filter (\(Node x y g) -> g /= gridTypeWall) allNodes

getNode (Maze grid) x y = Node x y (gridType grid x y)

nodeExistInList [] node = False
nodeExistInList (h:t) node = (nodeEq h node) || (nodeExistInList t node)

calcVisitablNextNodes maze [] visitedList = []
calcVisitablNextNodes maze (h:t) visitedList
  | nodeExistInList visitedList h = calcVisitablNextNodes maze t visitedList
  | otherwise = [h] ++ calcVisitablNextNodes maze t visitedList

solveMaze_r maze node [] visitedList =
  if nodeEq node (mazeFinishNode maze)
  then return ([node] ++ visitedList)
  else return []


solveMaze_r maze node (h:t) visitedList =
  -- note
  -- 1. 왜 return 을 붙이면 타입 문제가 생기나
  -- 2. print와 로직을 같이 둘수 없나?
  -- 3. 마지막 리턴값에 ++ [] 를 붙이면 왜 문제가 생기나? IO 떄문인가?
  let nextVisitedList = ([node] ++ visitedList)
      nextAvailNextNodes = (calcVisitablNextNodes maze
                            (getNextNodes maze (nodeGetX h) (nodeGetY h))
                            ([node] ++ visitedList));
  in do print "-----------"
        print ("node: " ++ show node)
        print ("head node: " ++ show h)
        print ("next visited list: " ++ show nextVisitedList)
        print ("next avail next nodes: " ++ show nextAvailNextNodes)
        let {_ = 1};
          if nodeEq node (mazeFinishNode maze)
          then return nextVisitedList
          else (solveMaze_r maze h nextAvailNextNodes nextVisitedList) ++ []

solveMaze maze =
  let start = mazeStartNode maze
      node = start
      nextNodes = getNextNodes maze (nodeGetX node) (nodeGetY node)
      availNextNodes = calcVisitablNextNodes maze nextNodes []
  in solveMaze_r maze node availNextNodes []

representMaze = do
  print ("width: " ++ show (mazeWidth sampleMaze))
  print ("height: " ++ show (mazeHeight sampleMaze))
  print ("start node: " ++ show (mazeStartNode sampleMaze))
  print ("finish node: " ++ show (mazeFinishNode sampleMaze))

  print (getNextNodes sampleMaze 1 1)
  print (getNode sampleMaze 1 0)

run =
  solveMaze sampleMaze

-- example
--sampleGrid =
--  [
--    "xS.xx",
--    "xxxx.",
--    "x..xG",
--    "xxxx."
--  ]

-- 어쩃든 굴러가는거. 방향을 맞춰둔거
sampleGrid =
  [
    "Sx.",
    ".x.",
    ".xG"
  ]

errorGrid =
  [
    "Sx.",
    ".x.",
    "Gxx"
  ]


--sampleMaze = Maze sampleGrid
sampleMaze = Maze errorGrid