file - Haskell 中的二维数组处理

Question

很抱歉我的问题对某些人来说似乎微不足道(我是新手)。我有一个文件，其中包含一个看起来像这样的 map :

---#--###----

-#---#----##-

------------@

在这个文件中， –字符表示您可以朝这个方向自由移动。 #字符表示你不能在这个方向上进一步移动，你应该去别的地方。 @字符表示宝藏的位置。在本例中，它位于右下角，但可以位于 map 中的任何位置。所以我必须通过这些线路，看看我是否可以到达 @ .在这里，我们从左上角开始。到目前为止，我已经设法阅读了文件的内容。我想知道如何在 Haskell 中处理它。在 Java 中使用二维数组会很容易，但是我如何在 Haskell 中解决这个问题？

例如，对于前面的示例，路径为:

+++#--###----

-#+--#----##-

--++++++++++@

+符号表示@符号的路径。

这是我必须在 Java 中实现它的算法:

Dfs(i,j) {
  if (arr[i][j+1] == "-" && i >=0 && i<=row.size && j>=0  && j<=column.size) {
      Dfs(i,j+1) 
  } else if(arr[i][j+1] == "@") {

  }

  if (arr[i][j-1] == "-" && i >=0 && i<=row.size && j>=0  && j<=column.size) {
        Dfs(i,j-1) 
  }   else if(arr[i][j-1] == "@") {

  }

  if (arr[i+1][j] == "-" && i >=0 && i<=row.size && j>=0  && j<=column.size) {
      Dfs(i+1,j) 
  } else if(arr[i+1][j] == "@") {

  }
}

谢谢

Answer 1

在 Haskell 中有很多制作二维数组的方法，这里有一个有点费力的例子，将字符读入 Data.Array 数组，然后用所谓的 state monad 移动东西。 :

import Data.Array
import Control.Monad.State.Strict

main = do str <- getContents -- accepts string from stdin
          let array = mkThingArray str -- we parse the string
              limits = snd (bounds array) -- we remember (height,width)
              initialState = ((0::Int,-1::Int),limits,array)
          ((position,(h,w),a)) <- execStateT findpath initialState
          let chars = elems $ fmap toChar a
          putStrLn ""
          putStrLn $ splitText (w+1) chars

parseArray str = listArray ((0,0),(height-1, width-1)) total where 
    rawlines = lines str
    ls       = filter (not . null) rawlines
    lens     = map length ls
    height   = length ls 
    width    = minimum lens 
    proper   = map (take width) ls
    total    = concat proper              

data Thing = Open | Closed | Home | Taken deriving (Show, Eq, Ord)
toThing c = case c of '-' -> Open; '#' -> Closed; '@' -> Home;
                      '+' -> Taken; _ -> error "No such Thing"
toChar c = case c of Open -> '-'; Closed -> '#'; 
                     Home -> '@'; Taken -> '+'

mkThingArray str = fmap toThing (parseArray str)

并继续一个 absurd 的原始状态变化“逻辑”:

-- we begin with moveright, which may then pass on to movedown 
-- and so on perhaps in a more sophisticated case
findpath = moveright 
  where
  moveright = do ((n,m), (bound1,bound2), arr) <- get
                 if m < bound2 
                 then case arr ! (n,m+1) of
                   Open   -> do liftIO (putStrLn "moved right")
                                put ((n,m+1), (bound1,bound2), arr // [((n,m+1),Taken)])
                                moveright
                   Closed -> movedown
                   Home   -> return ()
                   Taken  -> movedown
                 else movedown

  movedown = do ((n,m), (bound1,bound2), arr) <- get
                if n < bound1 
                then case arr ! (n+1,m) of
                   Open   -> do liftIO (putStrLn "moved down")
                                put ((n+1,m), (bound1,bound2), arr // [((n+1,m),Taken)])
                                moveright
                   Closed -> moveright
                   Home   -> return ()
                   Taken  -> moveright
                else moveright    

splitText n str = unlines $ split n [] str 
   where split n xss []  = xss
         split n xss str = let (a,b) = splitAt n str
                           in if not (null a) 
                                then split n (xss ++ [a]) b
                                else xss

在这种快乐的情况下，它给出了这样的输出

{-
$ pbpaste | ./arrayparse 
moved right
moved right
moved right
moved down
moved right
moved right
moved down
moved right
moved right
moved right
moved right
moved right
moved right
moved right

+++#--###----
-#+++#----##-
----++++++++@
-}

逻辑必须更复杂，使用 moveleft和 moveup ，等等，等等，但这应该给出想法，或想法。

编辑:这是一个不使用中间类型并且不向状态机抛出任何 IO 的版本。它应该在 ghci 中更有用，因此您可以更轻松地将其拆开:

import Data.Array
import Control.Monad.Trans.State.Strict

main = do str <- readFile "input.txt"
          ((pos,(h,w),endarray)) <- execStateT findpath 
                                               (mkInitialState str)
          putStrLn $ prettyArray endarray

-- the following are just synonyms, nothing is happening:
type Pos = (Int, Int)      -- Our positions are in 2 dimensions
type Arr = Array Pos Char  -- Characters occupy these positions
type ArrState = (Pos, Pos, Arr) -- We will be tracking not just 
                                --  an array of Chars but a 
                                --  current position and the total size
parseArray :: String -> Arr
parseArray str = listArray ((1,1),(height, width)) (concat cropped) where 
    ls       = filter (not . null) (lines str)
    width    = minimum (map length ls)     
    height   = length ls            
    cropped  = map (take width) ls -- the map is cropped to shortest line

prettyArray :: Arr -> String
prettyArray arr = split [] (elems arr)
  where (ab,(h,w)) = bounds arr 
        split xss []  = unlines xss 
        split xss str = let (a,b) = splitAt w str
                        in if null a then unlines xss else split (xss ++ [a]) b

mkInitialState :: String -> ArrState
mkInitialState str = ((1::Int,0::Int), limits, array)
 where array = parseArray str      -- we parse the string
       limits = snd (bounds array) -- we remember (height,width)
        -- since we don't resize, tracking this could be avoided

makeStep :: Arr -> Pos -> Arr   
makeStep arr (n, m) = arr // [((n,m),'+')]  -- this is crude

moveRight, moveDown, findpath :: Monad m => StateT ArrState m ()
moveRight = do ((n,m),bounds,arr) <- get
               put ((n,m+1), bounds, makeStep arr (n,m+1))
moveDown = do ((n,m),bounds,arr) <- get
              put ((n+1,m), bounds, makeStep arr (n+1,m))
findpath = tryRight  
  where -- good luck for most paths ...
  tryRight  = do ((n,m), (_,bound2), arr) <- get
                 if m < bound2 
                 then case arr ! (n,m+1) of
                   '@' -> return ()
                   '-' -> do moveRight
                             tryRight 
                   _   -> tryDown 
                 else tryDown 

  tryDown  = do ((n,m), (bound1,_), arr) <- get
                if n < bound1 
                then case arr ! (n+1,m) of
                   '@'   -> return ()
                   '-'   -> do moveDown
                               tryRight 
                   _  -> tryRight 
                else tryRight     

runInput :: String -> String
runInput str = prettyArray endarray
 where ((position,(h,w),endarray)) = execState findpath (mkInitialState str)
 -- If I wanted to include IO things in the state machine,
 -- I would have to use execStateT not execState, which presupposes purity
test :: String -> IO ()
test str = putStrLn (runInput str)

t1 = unlines ["---#--###----" 
             , ""
             , "-#---#----##-"
             , ""
             , "------------@"
             ] :: String
--
t2 = unlines ["---#--###----"
             ,""
             ,"---#-#----##-"
             ,""
             ,"------------@"
             ] :: String