-- Task: compute all arithmetic expressions containing exactly
-- the numbers 2,3,6,8 having the value 24

-- Define a permutation of an integer lists
permute :: [Int] -> [Int]
permute []     = []
permute (x:xs) | us ++ vs == permute xs
               = us ++ [x] ++ vs
 where us,vs free

-- Datatype for arithmetic expressions
data Exp = Num Int
         | Add Exp Exp
         | Sub Exp Exp
         | Mul Exp Exp
         | Div Exp Exp
 deriving Show

-- Evaluate some arithmetic expression to a value if
-- this arithmetic expression contains a given list of numbers
test :: Exp -> [Int] -> Int
--test (Num y)    [z] | z == y       = y
test (Num y)    [y]                = y
test (Add e1 e2) zs | split u v zs = test e1 u + test e2 v   where u,v free
test (Sub e1 e2) zs | split u v zs = test e1 u - test e2 v   where u,v free
test (Mul e1 e2) zs | split u v zs = test e1 u * test e2 v   where u,v free
test (Div e1 e2) zs | split u v zs = test e1 u `opdiv` test e2 v
 where u,v free
       opdiv a b | b /= 0 && a `mod` b == 0 = a `div` b

-- Split is satisfied if the two first non-empty(!) lists concatenates
-- to the third list.
split :: [Int] -> [Int] -> [Int] -> Bool
split (u:us) (v:vs) zs | (u:us) ++ (v:vs) == zs = True

-- Main expression to solve the game:
-- > solve $ test exp (permute [2,3,6,8]) == 24  where exp free