Difference between revisions of "Haskell Quiz/Numeric Maze/Solution Ninju"

From HaskellWiki
Jump to navigation Jump to search
(Solution the Numeric Maze Quiz)
 
m
 
(4 intermediate revisions by one other user not shown)
Line 1: Line 1:
  +
[[Category:Haskell Quiz solutions|Numeric Maze]]
−
I haven't yet any added any optimization, because I wanted to keep the program as simple (and therefore readable) as possible, but I might add some later.
  
−  
−
As a Haskell beginner, comments on whether or not this is the right sort of way to go about a problem such as this are appreciated - I actually wrote another solution that took a different approach, but I think this is slightly better.
  
   
 
<haskell>
  
<haskell>
Line 7: Line 5:
 
import System.Environment
  
import System.Environment
 
import Data.List
  
import Data.List
  +
  ⚫
data Operator = AddTwo | Double | Halve
   
 
main :: IO ()
  
main :: IO ()
 
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"
−
return ()
  
⚫
 
⚫
data Operation = AddTwo Integer | Double Integer | Halve Integer
  
   
  +
apply :: Operator -> Integer -> Integer
−
valid :: Operation -> Bool
  
−
valid (Halve x) = x `mod` 2 == 0
 +
apply AddTwo x = x + 2
−
valid _ = True
 +
apply Double x = x * 2
  ⚫
apply Halve x = x `div` 2
   
−
apply :: Operation -> Integer
 +
valid :: Operator -> Integer -> Bool
−
apply (AddTwo x) = x + 2
+
valid Halve x = even x
  +
valid _ _ = True
−
apply (Double x) = x * 2
 
⚫
apply (Halve x) = x `div` 2
  
   
 
solve :: Integer -> Integer -> [Integer]
  
solve :: Integer -> Integer -> [Integer]
−
solve a b = solve' [[a]] b
 +
solve a b = solve' [[a]] b [a]
  +
−
where
  
  +
solve' :: [[Integer]] -> Integer -> [Integer] -> [Integer]
−
solve' paths target = case find ((== target) . last) paths of
 +
solve' paths target seen = case find ((== target) . last) paths of
⚫
Just path -> path
  
−
Nothing -> solve' (concatMap buildPathsFrom paths) target
 +
Just path -> path
  +
Nothing -> let newPaths = filter ((`notElem` seen) . last) $ concatMap buildPathsFrom paths
⚫
buildPathsFrom path = [ path ++ [apply (op (last path))] | op <- [AddTwo, Double, Halve], valid (op (last path)) ]
  
  +
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 ]
 
</haskell>
  
</haskell>

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 ]
Retrieved from "https://wiki.haskell.org/index.php?title=Haskell_Quiz/Numeric_Maze/Solution_Ninju&oldid=31968"