I've bumped into this brain teaser recently:

"Given two integer numbers describing an n by m graph, where n represents the height and m represents the width, calculate the number of ways you can get from the top left to the bottom right if you can only go right and down"

That's a fine challenge, and prior to knowing recursive types in Haskell, I don’t know how I would have approached the problem.

Let's draw what the paths would look like first.

Given 1x1, the case is pretty simple:

{- The is what the matrix would look like: (0,1) - (1,1) | | (0,0) - (1,0) -}

The only way to get from the top left to the bottom right is to "walk" the perimeters:

{- (0,1) - (1,1) - (1,0) (0,1) - (0,0) - (1,0) -}

This case is so easy, I don’t even bother with devising a solution. Let's look at a 1 by 2 graph:

{- (0-1) - (1,1) - (2,1) | | | (0-0) - (1,0) - (2,0) -}

Following the rules laid out, there are 3 ways to get from the top left to the bottom right point:

{- (0-1) - (1,1) - (2,1) - (2,0) (0-1) - (1,1) - (1,0) - (2,0) (0-1) - (0,0) - (1,0) - (2,0) -}

The rule "you can only go right and down" tells us something: it's a binary tree. How could I draw up a recursive tree structure for this?

I'd like to make sure the logic is correct, I put all this logic into an HSpec file. How 'bout this?

-- test/PathCountSpec.hs import Test.Hspec main :: IO () main = hspec spec type Point = (Int, Int) data Tree a = Leaf | Node a (Tree a) (Tree a) deriving (Show, Eq) spec :: Spec spec = describe "Path Count" $ do it "can calculate tree branches for 1x2 matrix" $ do let tree = Node (0,1) (Node (1,1) (Node (2,1) Leaf (Node (2,0) Leaf Leaf)) (Node (1,0) (Node (2,0) Leaf Leaf) Leaf)) (Node (0,0) (Node (1,0) (Node (2,0) Leaf Leaf) Leaf) Leaf) {- Possible paths: (0,1) - (1,1) - (2,1) - (2,0) (0,1) - (1,1) - (1,0) - (2,0) (0,1) - (0,0) - (1,0) - (2,0) -} pending

The key here, that the number of times `Node (2,0) Leaf Leaf`

appears is the number of different ways I can get from the top left to the bottom right. All I have to do is counting the number of times this sub-tree appears in the tree itself.

I wrote a function (that I put into the HSpec file itself) to do just that:

leafCount :: Tree Point -> Int leafCount Leaf = 0 leafCount (Node _ Leaf Leaf) = 1 leafCount (Node _ left right) = leafCount left + leafCount right

When I call this function with the provided tree I have in the spec, I should receive 3. This assertion passes:

leafCount tree `shouldBe` 3

I manually had to build up this tree, next I looked at how I could generate it myself based on the top left and bottom right points. I had to make sure I won’t add branches outside of the matrix, what I accomplished with two guards.

buildTree :: Point -> Point -> Tree Point buildTree (a,b) end@(c,d) | a > c = Leaf | b < 0 = Leaf | otherwise = Node (a, b) (buildTree (a+1,b) end) (buildTree (a,b-1) end)

This logic will keep "walking" right and down until the guards will stop it.

I added another assertion to make sure this still passes:

buildTree (0,1) (2,0) `shouldBe` tree

I wanted to make sure this logic still holds when I pivot the two numbers. This is the next assertion I added:

buildTree (0,2) (1,0) `shouldBe` tree

Tests are passing. All right, I need to set up an outer function that takes two numbers and returns the number of paths.

Here it is:

pathCount :: Int -> Int -> Int pathCount m n = leafCount $ fromTree m n where fromTree m n = buildTree (0,m) (n,0)

This assertion will exercise this function:

pathCount 1 2 `shouldBe` 3

Everything is green!

I added one more test to make sure the 1x1 graph works:

pathCount 1 1 `shouldBe` 2

And finally I added a 2x2 test as well. This one has 6 different paths to get from the top left to the bottom right:

{- Possible paths: (0,2) - (1,2) - (2,2) - (2,1) - (2,0) (0,2) - (1,2) - (1,1) - (2,1) - (2,0) (0,2) - (1,2) - (1,1) - (1,0) - (2,0) (0,2) - (0,1) - (1,1) - (2,1) - (2,0) (0,2) - (0,1) - (1,1) - (1,0) - (2,0) (0,2) - (0,1) - (0,0) - (1,0) - (2,0) -} pathCount 2 2 `shouldBe` 6

And when I run the spec again, it all works! You can find the solution in this gist.