type Result = (Expr,Int)

data Op = Add | Sub | Mul | Div
           deriving (Eq,Ord,Show,Read)
		  
data Expr = Val Int | App Op Expr Expr
               deriving (Eq,Ord,Show,Read)
			   

--results ns = [(e,n) | e <- exprs ns
--                    , n <- eval e]

-- (expression,value) pairs

results []  = []
results [n] = [(Val n,n) | n > 0]
results ns  =
   [res | (ls,rs) <- split ns
        , lx      <- results ls
        , ry      <- results rs
        , res     <- combine2 lx ry]
					
combine2 (l,x) (r,y) =
   [(App o l r, apply o x y)
      | o <- [Add,Sub,Mul,Div]
      , valid o x y]
					
			
solutions2 ns n =
   [e | ns'   <- choices ns
      , (e,m) <- results ns'
      , m == n]
	  
---------------------------------	  
			
toBinary 0 = [False]
toBinary 1 = [True]
toBinary n | n `mod` 2 == 0 = False:(toBinary (n `div` 2))
           | otherwise      = True:(toBinary (n `div` 2))

makeList 0 _item = []
makeList n item = item:(makeList (n-1) item)

-- put zeroes at the beginning of the binary representation (i.e. end here)
pad [] [] = []
pad (h:t) (h2:t2) = h2:(pad t t2)
pad (h:t) [] = False:(pad t [])
		   
binaryUpTo n = [ pad (toBinary n) (toBinary m) | m <- [0..n] ]		   

split aList = [(take x aList, drop x aList)| x <- [1..(length aList)-1]]

mySplit aList = [(take x aList, drop x aList)| x <- [0..length aList] ]

inject x aList = [left ++ [x] ++ right | (left,right) <- mySplit aList]

perm [] = []
perm [x] = [[x]]
perm (h:t) = [ r | temp <- (perm t), r <- (inject h temp) ]

choose [] _ = []
choose (True:rest) (h:t) = h:(choose rest t)
choose (False:rest) (h:t) = choose rest t

choices aList = let listSize = length aList
                in 
				    [ aPermutation |  aBinary <- binaryUpTo ((2^listSize)-1), 
					                  aChosenSubList <- [choose aBinary aList], -- a singleton
					                  aPermutation <- perm aChosenSubList
					]
					++
					[[]]




apply Add x y  = x + y
apply Sub x y  = x - y
apply Mul x y  = x * y
apply Div x y  = x `div` y

valid Add x y  = x<=y
valid Sub x y  = x > y
valid Mul x y  = x<y && not(x==1) && not(y==1)
valid Div x y  = x `mod` y == 0 && not (y==1)

eval (Val n)     = [n | n > 0]
eval (App o l r) = [apply o x y | x <- eval l
                                , y <- eval r
                                , valid o x y]

values (Val n)     = [n]
values (App _ l r) = values l ++ values r

-- checking for a specific solution
solution e ns n = elem (values e) (choices ns)
                  && eval e == [n]
								
exprs []  = []

exprs [n] = [Val n]

exprs ns  = [App o l r | (ls,rs) <- split ns
                        , l       <- exprs ls
                        , r       <- exprs rs
                        , o       <- [Add,Sub,Mul,Div]]
								
combine l r =
   [App o l r | o <- [Add,Sub,Mul,Div]]
   
-- generates all solutions   
solutions ns n = [e | ns2 <- choices ns
                    , e   <- exprs ns2
                    , eval e == [n]]