Problem5

problem5.hs

-- Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.
-- Source: https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour

data Join = Plus | Minus | Concat deriving Show

compute :: Integer -> (Integer, Join) -> Integer
compute x (y, Plus) = x+y
compute x (y, Minus) = x-y
compute x (y, Concat) = read(show(x)++show(y))

n = 9
sumTo = 100

getAllCombinations :: [[a]] -> [[a]]
getAllCombinations [] = [[]]
getAllCombinations (xs:xxs) = [(x:ys) | ys <- (getAllCombinations xxs), x <- xs]

-- all combinations of Plus, Minus, Concat, but with always Plus in the beginning,
-- so when we foldl with first element 0 we don't change final value.
allCombinations = map (\pmcs -> [1..n] `zip` pmcs) (map (\xs -> (Plus:xs)) c)
    where c = getAllCombinations (map (\x -> [Plus, Minus, Concat]) [1..n-1])

sum' :: [(Integer, Join)] -> Integer
sum' xs = foldl (\l r -> compute l r) 0 xs

answer = [map snd combination | combination <- allCombinations, (sum' combination) == sumTo]