Difference between revisions of "Haskell Quiz/Numeric Maze/Solution Ninju"
< Haskell Quiz | Numeric Maze
Jump to navigation
Jump to search
m |
|||
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
[[Category:Haskell Quiz solutions|Numeric Maze]] |
[[Category:Haskell Quiz solutions|Numeric Maze]] |
||
− | |||
− | I haven't yet added any optimization, because I wanted to keep the program as simple (and therefore readable) as possible, but I might add some later. |
||
<haskell> |
<haskell> |
||
Line 7: | Line 5: | ||
import System.Environment |
import System.Environment |
||
import Data.List |
import Data.List |
||
+ | |||
⚫ | |||
main :: IO () |
main :: IO () |
||
main = do args <- getArgs |
main = do args <- getArgs |
||
− | if length args == 2 |
+ | if length args == 2 |
− | then |
+ | then let [a,b] = map read args |
− | + | in print $ solve a b |
|
else putStrLn "Usage: solve START TARGET" |
else putStrLn "Usage: solve START TARGET" |
||
− | return () |
||
⚫ | |||
⚫ | |||
+ | apply :: Operator -> Integer -> Integer |
||
− | valid :: Operation -> Bool |
||
− | + | apply AddTwo x = x + 2 |
|
− | + | apply Double x = x * 2 |
|
⚫ | |||
− | + | valid :: Operator -> Integer -> Bool |
|
− | + | valid Halve x = even x |
|
+ | valid _ _ = True |
||
− | apply (Double x) = x * 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 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 |
||
⚫ | |||
⚫ | |||
+ | buildPathsFrom :: [Integer] -> [[Integer]] |
||
+ | buildPathsFrom path = let n = last path |
||
⚫ | |||
</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 ]