drkcore

2010/01/14 22:18:42

迷路のやつをHaskellで解いてみる（未完）

実際にやってみると位置を記録すんのに手間取ったり(pythonはenumarateがあるので楽)とか、リストモナドの使い方をちゃんと理解してなかったりとかで、終わらん。

import List

maze = ["**************************",
        "*S* *                    *",
        "* * *  *  *************  *",
        "* *   *    ************  *",
        "*    *                   *",
        "************** ***********",
        "*                        *",
        "** ***********************",
        "*      *              G  *",
        "*  *      *********** *  *",
        "*    *        ******* *  *",
        "*       *                *",
        "**************************"]

type Pos = (Int,Int)
type Path = [Pos]

findPos :: [String] -> Char -> Pos
findPos maze c = 
    let y = findY maze c 0 
        x = findX (maze!!y) c 0
    in (x,y)
    where
      findY :: [String] -> Char -> Int -> Int
      findY [] _ _     = error (c : " not found\n")
      findY (x:xs) c n | c `elem` x = n
                       | otherwise  = findY xs c (n+1)
      findX :: String -> Char -> Int -> Int
      findX (x:xs) c n | x == c     = n
                       | otherwise  = findX xs c (n+1)

start = findPos maze 'S'
goal  = findPos maze 'G'

canMove :: [String] -> Pos -> Bool
canMove maze (x,y) | maze !! y !! x == '*' = False
                   | otherwise             = True

enableSteps :: [String] -> [Pos] -> [Pos]
enableSteps maze path@((x,y):_) = filter (canMove maze) [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]

getAllPaths :: [String] -> Pos -> [Path]
getAllPaths maze start = [[start]] >>= toward
                         where 
                           toward :: Path -> [Path]
                           toward path
                                  | not.null $ moves = map (:path) moves >>= toward
                                  | otherwise = [path]
                                  where 
                                    moves = enableSteps maze path

結局、リストモナドをどうつなげていったらいいのかというところでつまづいている。あと[String]っていう型じゃなくてMazeとかいう型にしといた方がよかったかも。

Comments