Guest User

Untitled

a guest
Dec 15th, 2015
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. {-# LANGUAGE FlexibleInstances #-}
  2. import Data.List hiding (permutations)
  3. import Control.Monad
  4. import Data.Ratio
  5.  
  6. data Exp a = Plus (Exp a) (Exp a) | Minus (Exp a) (Exp a) |
  7.              Mul (Exp a) (Exp a) | Div (Exp a) (Exp a) | Number a
  8.                                                                            
  9. instance (Show (Exp Rational)) where
  10.   show exp = case exp of
  11.     Number a -> show $ numerator a `div` denominator a
  12.     Plus a b -> "(" ++ show a ++ "+" ++ show b ++ ")"
  13.     Minus a b -> "(" ++ show a ++ "-" ++ show b ++ ")"
  14.     Mul a b -> "(" ++ show a ++ "*" ++ show b ++ ")"
  15.     Div a b -> "(" ++ show a ++ "/" ++ show b ++ ")"
  16.  
  17. eval exp = case exp of
  18.   Number a -> a
  19.   Plus a b -> eval a + eval b
  20.   Minus a b -> eval a - eval b
  21.   Mul a b -> eval a * eval b
  22.   Div a b -> eval a / eval b
  23.  
  24.  
  25. operations a b = if eval b == 0 then safeOps else Div a b:safeOps
  26.                                              where safeOps = [Plus a b, Minus a b, Mul a b]
  27. parseRational = Number . toRational . read
  28.  
  29. combinations :: [a] -> [[[a]]]
  30. combinations [] = []
  31. combinations [x] = [[[x]]]
  32. combinations (x:xs) = map (\(y:ys) -> (x:y):ys) (combinations xs)  ++ map ([x]:) (combinations xs)
  33.  
  34. expressions :: [Exp Rational] -> [Exp Rational]
  35. expressions [] = []
  36. expressions [x] = [x]
  37. expressions [x, y] = operations x y
  38. expressions (x:y:ys) = concat $ map (expressions . (:ys)) leftexpressions ++ map (operations x) rightexpressions
  39.   where
  40.     leftexpressions = operations x y
  41.     rightexpressions = expressions (y:ys)
  42.  
  43. permutations :: String -> [Exp Rational]
  44. permutations = concat . map expressions . map (map parseRational) . combinations
  45.  
  46. main = do
  47.   number <- getLine
  48.   print $  filter ((== 100) . eval) $ permutations number
Advertisement
Add Comment
Please, Sign In to add comment