Personal tools

Haskell Quiz/Numeric Maze/Solution Ninju

From HaskellWiki

< Haskell Quiz | Numeric Maze(Difference between revisions)
Jump to: navigation, search
m
 
Line 11: Line 11:
 
main = do args <- getArgs
 
main = do args <- getArgs
 
if length args == 2
 
if length args == 2
then do let [a,b] = map read args
+
then let [a,b] = map read args
putStrLn $ show $ solve a b
+
in print $ solve a b
 
else putStrLn "Usage: solve START TARGET"
 
else putStrLn "Usage: solve START TARGET"
   
Line 21: Line 21:
   
 
valid :: Operator -> Integer -> Bool
 
valid :: Operator -> Integer -> Bool
valid Halve x = x `mod` 2 == 0
+
valid Halve x = even x
 
valid _ _ = True
 
valid _ _ = True
   

Latest revision as of 08:23, 27 November 2009


module Main where
import System.Environment
import Data.List
 
data Operator = AddTwo | Double | Halve
 
main :: IO ()
main = do args <- getArgs
          if length args == 2
            then let [a,b] = map read args
                 in print $ solve a b 
            else putStrLn "Usage: solve START TARGET"
 
apply :: Operator -> Integer -> Integer 
apply AddTwo x = x + 2 
apply Double x = x * 2 
apply Halve x = x `div` 2
 
valid :: Operator -> Integer -> Bool 
valid Halve x = even x
valid _ _ = True
 
solve :: Integer -> Integer -> [Integer]
solve a b = solve' [[a]] b [a] 
 
solve' :: [[Integer]] -> Integer -> [Integer] -> [Integer]
solve' paths target seen =  case find ((== target) . last) paths of
                                Just path -> path
                                Nothing -> let newPaths = filter ((`notElem` seen) . last) $ concatMap buildPathsFrom paths
                                               newSeen = seen ++ map last newPaths
                                           in solve' newPaths target newSeen
 
 
buildPathsFrom :: [Integer] -> [[Integer]] 
buildPathsFrom path = let n = last path
                      in [ path ++ [ apply operator n ] | operator <- [AddTwo, Double, Halve], valid operator n ]