Svpion Fifth problem

I attempted myself to solve #5 from Five programming problems every Software Engineer should be able to solve in less than 1 hour in Haskell.

So the task is:
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.

Initially I thought,
“Hey, this should be easy. All we need to do is create an algebra that contains Addition, Subtraction, and Multiplication (being concatenation) and we should be good!”

So I proceeded:

data Expr =
A Expr Expr |
S Expr Expr |
C Expr Expr |
I Int deriving Show

parse :: Expr -> Int
parse (A a b) = parse a + parse b
parse (S a b) = parse a - parse b
parse (C a b) = parse a * 10 + parse b
parse (I a) = a

This should be it! So for example 1 + 2 + 3 would be A (I 1) (A (I 2) (I 3)), and getting the result of it is to call parse like:

*Main> parse $ A (I 1) (A (I 2) (I 3))
6

Now all we need to do is create all possibilities of the form (1 _ 2 _ 3 _ 4 _ 5 _ 6 _ 7 _ 8 _ 9) and replace _ with any of the three operators and then finally do something like filter (== 100) parse x.

But using this grammar, there are some non-valid cases such as C (A (I 1) (I 2)) (I 3).
These are cases that we must exclude, for if we don’t, then what this expression would evaluate to is 33, i.e. (1 + 2) * 10 + 3, but this is not a valid expression given the stated task.
However 1 + 23 or 12 + 3 or 1 + 2 + 3 are.

To take care of this, we will slightly rework our grammar and parsing functions:

data Expr =
A Expr Expr |
S Expr Expr |
CE CExpr deriving Show

data CExpr =
C CExpr CExpr |
I Int deriving Show

parse :: Expr -> Int
parse (A a b) = parse a + parse b
parse (S a b) = parse a - parse b
parse (CE c) = parseCE c

parseCE :: CExpr -> Int
parseCE (C a b) = parseCE a * 10 + parseCE b
parseCE (I a) = a

Another constraint that we need to add is that the concatenations need to be successive. So we somehow need to exclude those cases as well from all of the possibilities. Let’s call this function getCExprs. So what getCExprs should do is, given a list, it should return possible successive concatenations of that list. Successive concatenations is what will allow us to remove the non-valid cases.

E.g. getCExprs [I 1,I 2,I 3] = [I 1,C (I 1) (I 2),C (C (I 1) (I 2)) (I 3)].

Additionally (we’ll see why within the foldingFunction), we want getCExprs to return the remaining part of the list (digits) it’s working on, so:

getCExprs [I 1,I 2,I 3] = [([I 2,I 3],I 1),([I 3],C (I 1) (I 2)),([],C (C (I 1) (I 2)) (I 3))].

To implement this, we’ll need a help function called listToC that given a list [I 1,I 2,I 3], it will turn it into its concatenated algebraic version, C (C (I 1) (I 2)) (I 3).

The definition for this is trivial:

listToC :: [CExpr] -> CExpr
listToC (x:xs) = foldl C x xs
listToC _ = I 0

Now we are ready to go for getCExprs:

getCExprs :: [CExpr] -> [([CExpr], CExpr)]
getCExprs x = go 1 (tail $ inits x)
where
go n xs@(x':xs') = (drop n x, listToC x') : go (n + 1) xs'
go _ [] = []
Some simple tests:

*Main> getCExprs $ map I [1,2,3]
[([I 2,I 3],I 1),([I 3],C (I 1) (I 2)),([],C (C (I 1) (I 2)) (I 3))]
*Main> getCExprs $ map I [1..9]
[([I 2,I 3,I 4,I 5,I 6,I 7,I 8,I 9],I 1),([I 3,I 4,I 5,I 6,I 7,I 8,I 9],C (I 1) (I 2)),([I 4,I 5,I 6,I 7,I 8,I 9],C (C (I 1) (I 2)) (I 3)),([I 5,I 6,I 7,I 8,I 9],C (C (C (I 1) (I 2)) (I 3)) (I 4)),([I 6,I 7,I 8,I 9],C (C (C (C (I 1) (I 2)) (I 3)) (I 4)) (I 5)),([I 7,I 8,I 9],C (C (C (C (C (I 1) (I 2)) (I 3)) (I 4)) (I 5)) (I 6)),([I 8,I 9],C (C (C (C (C (C (I 1) (I 2)) (I 3)) (I 4)) (I 5)) (I 6)) (I 7)),([I 9],C (C (C (C (C (C (C (I 1) (I 2)) (I 3)) (I 4)) (I 5)) (I 6)) (I 7)) (I 8)),([],C (C (C (C (C (C (C (C (I 1) (I 2)) (I 3)) (I 4)) (I 5)) (I 6)) (I 7)) (I 8)) (I 9))]
*Main>

Seems to be working fine!

Next, we want to create a function f that has three parameters:
1. Current expression calculated with add/sub so far, Expr
2. Current operation being done, String
3. Remaining list of expressions (digits and successive concatenated digits) to work on, [CExpr]
and this function should return a list of (Expr, String), i.e. which expression is produced for what operations.

So we have:

f :: Expr -> [String] -> [CExpr] -> [(Expr, [String])]

This should be a fold, so what f should do is basically go through all valid possibilities (which are created by getCExprs), so, what we have so far:

f s ops [] = [(s, ops)]
f s ops xs = foldr foldingFunction [] $ getCExprs xs

In the first definition of f, we pattern match against an empty list, which is basically the base case and it returns the last pair of (sum, operations) done at that point.

So, this is what we currently have:

import Data.List (inits, nub)

data Expr =
A Expr Expr |
S Expr Expr |
CE CExpr deriving Show

data CExpr =
C CExpr CExpr |
I Int deriving Show

parse :: Expr -> Int
parse (A a b) = parse a + parse b
parse (S a b) = parse a - parse b
parse (CE c) = parseCE c

parseCE :: CExpr -> Int
parseCE (C a b) = parseCE a * 10 + parseCE b
parseCE (I a) = a

listToC :: [CExpr] -> CExpr
listToC (x:xs) = foldl C x xs
listToC _ = I 0

getCExprs :: [CExpr] -> [([CExpr], CExpr)]
getCExprs x = go 1 (tail $ inits x)
where
go n xs@(x':xs') = (drop n x, listToC x') : go (n + 1) xs'
go _ [] = []

f :: Expr -> [String] -> [CExpr] -> [(Expr, [String])]
f s ops [] = [(s, ops)]
f s ops xs = foldr foldingFunction [] $ getCExprs xs
where
foldingFunction = undefined

So, all we need to do is implement foldingFunction and we are done.

To be able to implement foldingFunction, we need to look at getCExprs and see what it produces for us. We know that it gives us back a pair, ([CExpr], CExpr). CExpr is the current concatenations done, and [CExpr] is the remaining part of the list.

Therefore,
foldingFunction (a, b) l = undefined

Remember f had three params. The way we defined f makes it easily callable by the foldingFunction.

We need to call f from within the foldingFunction and add the current value we are iterating to the sum. We also need to note which operation we are applying, and to pass the current list of digits we are working on. Note that we have the variable s (expression calculated so far) in the scope since we will define foldingFunction within f itself. We also have the variable b produced by getCExprs, but its type is CExpr. if b :: CExpr, then CE b will be Expr, which is what our function f requires, i.e. to parse a complete expression (Expr), and not just digits or concatenated digits (CExpr).

So:
foldingFunction (a, b) l = f (A s (CE b)) (“+” : ops) a

In this case, we are calling f while adding s and b, i.e., we add b to the current expression so far, and then we pass the remaining list of numbers (a) to f.

This takes care of the addition. To make messages more verbose, we’ll implement a function called “calculated” which in details will explain what’s going on:

foldingFunction (a, b) l = f (A s (CE b)) (calculated “+” b) (drop a xs)
calculated op b = (op ++ show (parseCE b)) : ops

Similarly, we need to do the same for the operation minus. And then we need to append all of the results in a single list:
foldingFunction (a, b) l =
f (A s (CE b)) (calculated “+” b) a
++
f (S s (CE b)) (calculated “-” b) a
++ l

So the full code is:

import Data.List (nub)

data Expr =
A Expr Expr |
S Expr Expr |
CE CExpr deriving Show

data CExpr =
C CExpr CExpr |
I Int deriving Show

parse :: Expr -> Int
parse (A a b) = parse a + parse b
parse (S a b) = parse a - parse b
parse (CE c) = parseCE c

parseCE :: CExpr -> Int
parseCE (C a b) = parseCE a * 10 + parseCE b
parseCE (I a) = a

listToC :: [CExpr] -> CExpr
listToC (x:xs) = foldl C x xs
listToC _ = I 0

getCExprs xs = map (\x -> (drop x xs, listToC (take x xs))) [1..length xs]

f :: Expr -> [String] -> [CExpr] -> [(Expr, [String])]
f s ops [] = [(s, ops)]
f s ops xs = foldr foldingFunction [] $ getCExprs xs
where
foldingFunction (a, b) l = f (A s (CE b)) (calculated "+" b) a
++ f (S s (CE b)) (calculated "-" b) a
++ l
calculated op b = (op ++ show (parseCE b)) : ops

main = do
let l = f (CE (I 0)) [] (map I [1..9])
let l' = filter (\x -> parse (fst x) == 100) l
mapM_ (\(x, y) -> print $ concat $ reverse y) l'

Call main to get:

[1 of 1] Compiling Main             ( test.hs, interpreted )
iOk, modules loaded: Main.
*Main> main
"+1+2+3-4+5+6+78+9"
"+1+2+34-5+67-8+9"
"+1+23-4+5+6+78-9"
"+1+23-4+56+7+8+9"
"-1+2-3+4+5+6+78+9"
"+12+3+4+5-6-7+89"
"+12+3-4+5+67+8+9"
"+12-3-4+5-6+7+89"
"+123+4-5+67-89"
"+123-4-5-6-7+8-9"
"+123+45-67+8-9"
"+123-45-67+89"
*Main>

Solving this problem in a functional language like Haskell reveals its background when it’s represented using an algebraic data type. For instance, if this problem was solved in Python, you would run through all combinations of “1_2_3_4_5_6_7_8_9”, change underscores with plus, minus, or append, and then eval the string expression. But if you solve it this way, you wouldn’t have any deeper insight regarding its algebra, e.g. the “successive concatenations” part might not be immediately visible.

Algebraic data types representation helps us with adding constraints, but to some point. Additional more complex constraints were handled by the functions themselves.

This is why I do not believe this is solvable in under 1 hour when you first meet this problem. There is much more background in this than what the author states.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s