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] ] 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 ] ++ [[]] -- choices aList = noDuplicates ([ (take upTo aPerm) | aPerm <- perm aList, upTo <- [1.. length aList] ] ++ [[]]) --noDuplicates [] = [] --noDuplicates (h:t) | member h t = noDuplicates t -- | otherwise = h:(noDuplicates t) --member x [] = False --member x (h:t) = x==h || (member x t) data Op = Add | Sub | Mul | Div deriving (Eq,Ord,Show,Read) data Expr = Val Int | App Op Expr Expr deriving (Eq,Ord,Show,Read) 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 _ _ = True valid Sub x y = x > y valid Mul _ _ = True valid Div x y = x `mod` y == 0 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 = [e | (ls,rs) <- split ns , l <- exprs ls , r <- exprs rs , e <- combine l r] combine l r = [App o l r | o <- [Add,Sub,Mul,Div]] -- generates all solutions solutions ns n = [e | ns' <- choices ns , e <- exprs ns' , eval e == [n]]