Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- {-# LANGUAGE FlexibleInstances #-}
- import Data.List hiding (permutations)
- import Control.Monad
- import Data.Ratio
- data Exp a = Plus (Exp a) (Exp a) | Minus (Exp a) (Exp a) |
- Mul (Exp a) (Exp a) | Div (Exp a) (Exp a) | Number a
- instance (Show (Exp Rational)) where
- show exp = case exp of
- Number a -> show $ numerator a `div` denominator a
- Plus a b -> "(" ++ show a ++ "+" ++ show b ++ ")"
- Minus a b -> "(" ++ show a ++ "-" ++ show b ++ ")"
- Mul a b -> "(" ++ show a ++ "*" ++ show b ++ ")"
- Div a b -> "(" ++ show a ++ "/" ++ show b ++ ")"
- eval exp = case exp of
- Number a -> a
- Plus a b -> eval a + eval b
- Minus a b -> eval a - eval b
- Mul a b -> eval a * eval b
- Div a b -> eval a / eval b
- operations a b = if eval b == 0 then safeOps else Div a b:safeOps
- where safeOps = [Plus a b, Minus a b, Mul a b]
- parseRational = Number . toRational . read
- combinations :: [a] -> [[[a]]]
- combinations [] = []
- combinations [x] = [[[x]]]
- combinations (x:xs) = map (\(y:ys) -> (x:y):ys) (combinations xs) ++ map ([x]:) (combinations xs)
- expressions :: [Exp Rational] -> [Exp Rational]
- expressions [] = []
- expressions [x] = [x]
- expressions [x, y] = operations x y
- expressions (x:y:ys) = concat $ map (expressions . (:ys)) leftexpressions ++ map (operations x) rightexpressions
- where
- leftexpressions = operations x y
- rightexpressions = expressions (y:ys)
- permutations :: String -> [Exp Rational]
- permutations = concat . map expressions . map (map parseRational) . combinations
- main = do
- number <- getLine
- print $ filter ((== 100) . eval) $ permutations number
Advertisement
Add Comment
Please, Sign In to add comment