Haskell Quiz/Numeric Maze/Solution Ninju
< Haskell Quiz | Numeric Maze
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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 ]